Re: Faster IntSet by using BitMaps in the lower branches

On Sun, 18 Sep 2011, Joachim Breitner wrote:

I’d like to avoid the binary search, as it is more expensive for dense sets. Milan’s suggestion of shifts by 6 might be a good compromise. Another approach might be to first use lowestBitSet to start with the lowest bit. In case of only one bit set, it will not iterate further then.

If lowestBitSet is a fast CPU instruction you can iterate through all bits by clearing the lowest set bit after visit and call lowestBitSet again. However, I am not aware of such a machine instruction on x86.