Faster IntSet by using BitMaps in the lower branches
lemming at henning-thielemann.de
Sun Sep 18 23:05:25 CEST 2011
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
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.
More information about the Libraries