<br><div class="gmail_quote">On Sun, Sep 18, 2011 at 4:13 PM, Henning Thielemann <span dir="ltr"><<a href="mailto:lemming@henning-thielemann.de">lemming@henning-thielemann.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im"><br>
On Sun, 18 Sep 2011, Joachim Breitner wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I have attached some benchmarking result. While results are good for<br>
member, great for insert, intersection and union, toList is slower for<br>
sparse maps. toList is basically a foldr, so I think the culprit is this<br>
function:<br>
<br>
foldrBits :: Int -> (Int -> a -> a) -> a -> Word -> a<br>
foldrBits shift f x = go shift<br>
where STRICT_1_OF_2(go)<br>
go bi 0 = x<br>
go bi n | n `testBit` 0 = f bi (go (succ bi) (n `shiftRL` 1))<br>
| otherwise = go (succ bi) (n `shiftRL` 1)<br>
<br>
I’ll try to optimize this function individually now, any suggestions are<br>
welcome.<br>
</blockquote>
<br></div>
You can certainly do some binary search by masking and comparing with bit patterns like<br>
1 `shiftL` 32 - 1 `shiftL` 16<br>
1 `shiftL` 16 - 1 `shiftL` 0<br><br></blockquote>You can also gain some speed by switching to unsafeShiftRL, to drop the needless comparison.</div><div class="gmail_quote"><br></div><div class="gmail_quote">-Edward</div>