Faster IntSet by using BitMaps in the lower branches

[Henning Thielemann]

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