Faster IntSet by using BitMaps in the lower branches

[Edward Kmett]

I should have mentioned. This function asumes that the input n is not equal
to 0.

You can use it or a nicely ByteArray#'d and uncheckedShiftRL64#'d version
together with the iterated masking of bits to walk through the bits in
order.

-Edward

On Sun, Sep 18, 2011 at 5:07 PM, Edward Kmett <ekmett at gmail.com> wrote:

> 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/820084ae/attachment-0001.htm>