Faster IntSet by using BitMaps in the lower branches
Edward Kmett
ekmett at gmail.com
Sun Sep 18 23:11:56 CEST 2011
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>
More information about the Libraries
mailing list