Faster IntSet by using BitMaps in the lower branches

[Edward Kmett]

On Sun, Sep 18, 2011 at 4:13 PM, Henning Thielemann <
lemming at henning-thielemann.de> wrote:

>
> On Sun, 18 Sep 2011, Joachim Breitner wrote:
>
>  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.
>>
>
> You can certainly do some binary search by masking and comparing with bit
> patterns like
>   1 `shiftL` 32 - 1 `shiftL` 16
>   1 `shiftL` 16 - 1 `shiftL` 0
>
> You can also gain some speed by switching to unsafeShiftRL, to drop the
needless comparison.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110918/b99242e4/attachment.htm>