Linear time IntSet / IntMap construction from sorted input

19 May 2008

      Hi,

It's always bugged me that IntSet.fromAscList is an alias for
fromList, which is basically (foldr insert), even though a sorted list
is (almost) already in tree order. Is there a reason for this? Or was
it just that fromList is good enough? (which it is.)

Assuming the latter, and somewhat bored, I wrote a function to build
an IntSet from sorted input in linear time. This goes in
Data.IntSet.hs :

data Stack = Push {-# UNPACK #-} !Prefix !IntSet !Stack | Nada

fromAsc xs = make Nada xs
  where
    make stk []      = finish stk
    make Nada (z:zs) = make (Push z (Tip z) Nada) zs
    make stk@(Push _ y Nada) (z:zs)  = make (Push z (Tip z) stk) zs
    make stk@(Push py y stk') zs@(z:zs') =
      make (Push z (Tip z) (reduce (branchMask py z) stk)) zs'

    reduce _ stk@(Push _ x Nada) = stk
    reduce m stk@((Push px x (Push py y stk'))) =
      let !mxy = branchMask px py
          !pxy = mask px mxy
      in  if shorter m mxy
            then reduce m (Push pxy (Bin pxy mxy y x) stk')
            else stk

    finish Nada = Nil
    finish (Push _ x Nada) = x
    finish (Push px x (Push py y stk)) = finish (Push p (join px x py y) stk)
      where m  = branchMask px py
            p  = mask px m

Every trie node is allocated exactly once, and so the burden on the
heap is significantly less, even if its only a little bit faster. I
tested it by building a list from -n to n for big n, and computing the
sum. It alloc's 50% less and the MUT time is like 40% less, but the GC
time is more (why would that be?) so it runs in maybe 7/8ths the time,
versus fromList.

I have another, prettier version that uses [] instead of this hacky
Stack type, but its slower, breaking even with fromList on speed,
still allocating much less.

Is this something you guys feel would be worth including? Should I
make a proper patch? One could even use this to write an O(n)
mapKeysMonotonic, bringing the IntMap and Map APIs further into
alignment. Or is 8/7x speedup not worth the extra code weight?

Scott

Scott Dillard

Scott Dillard

Scott Dillard

Duncan Coutts

tags

participants (2)