On Sun, Sep 18, 2011 at 4:13 PM, Henning Thielemann <lemming@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