Faster IntSet by using BitMaps in the lower branches

[Joachim Breitner]

Hi,

Am Samstag, den 17.09.2011, 23:37 +0200 schrieb Milan Straka:
> Great job!

thanks for the positive feedback.

> Could you please also generate comparison of and IntSet and DenseIntSet,
> when the set is sparse (eg [1, 65 .. N])? I would like to see the time
> complexities then. Also please include toList. If the results are fine,
> I currently see no reason why not to push the code in.

I have attached some benchmarking result. While results are good for
member, great for insert, intersection and union, toList is slower for
sparse maps. toList is basically a foldr, so I think the culprit is this
function:

foldrBits :: Int -> (Int -> a -> a) -> a -> Word -> a
foldrBits shift f x = go shift
  where STRICT_1_OF_2(go)
        go bi 0 = x
        go bi n | n `testBit` 0 = f bi (go (succ bi) (n `shiftRL` 1))
                | otherwise     =       go (succ bi) (n `shiftRL` 1)

I’ll try to optimize this function individually now, any suggestions are
welcome.

Greetings,
Joachim

-- 
Joachim "nomeata" Breitner
  mail at joachim-breitner.de  |  nomeata at debian.org  |  GPG: 0x4743206C
  xmpp: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/

-------------- next part --------------
A non-text attachment was scrubbed...
Name: comparison2.pdf
Type: application/pdf
Size: 18366 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110918/a897f54e/attachment.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110918/a897f54e/attachment.pgp>