Faster IntSet by using BitMaps in the lower branches

[Edward Kmett]

There are some neat tricks you can use using deBruijn multiplication to
optimize finding the least significant set bit.

My geometric coalgebra code in
https://github.com/ekmett/algebra/blob/master/Numeric/Coalgebra/Geometric.hs#L72uses
the following:

lsb :: *Word64* -> Int
lsb n = fromIntegral $ ix ! shiftR ((n .&. (-n)) * 0x07EDD5E59A4E28C2) 58
  where
    -- a 64 bit deBruijn multiplication table
    ix :: UArray Word64 Word8
    ix = listArray (0, 63)
      [ 63,  0, 58,  1, 59, 47, 53,  2
      , 60, 39, 48, 27, 54, 33, 42,  3
      , 61, 51, 37, 40, 49, 18, 28, 20
      , 55, 30, 34, 11, 43, 14, 22,  4
      , 62, 57, 46, 52, 38, 26, 32, 41
      , 50, 36, 17, 19, 29, 10, 13, 21
      , 56, 45, 25, 31, 35, 16,  9, 12
      , 44, 24, 15,  8, 23,  7,  6,  5
      ]

which could be sped up slightly by using a byteArray# directly for the
backing store to find the least significant set bit in a Word64.

-Edward


On Sun, Sep 18, 2011 at 4:01 PM, Joachim Breitner
<mail at joachim-breitner.de>wrote:

> 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/
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110918/c70b54af/attachment-0001.htm>