haskell-unordered-containers / unordered-containers

Efficient hashing-based container types
BSD 3-Clause "New" or "Revised" License
221 stars 99 forks source link

Alternative to `countTrailingZeros` for bitmap iteration #424

Open sjakobi opened 2 years ago

sjakobi commented 2 years ago

unionArrayBy and intersectionArrayBy currently use countTrailingZeros to detect set bits in bitmaps.

Alternatively, lowest set bits can be isolated like this:

isolateLowestSetBit :: Word -> Word
isolateLowestSetBit x = x .&. negate x

(Explanation in https://stackoverflow.com/a/12250963/1013393)

The latter technique is already being used in submapBitmapIndexed to create the initial bit mask.

It would be good to consistently use only one technique, ideally by refactoring this pattern into a proper function like isolateLowestSetBit.

sjakobi commented 2 years ago

clearLowestSetBit x = x .&. (x - 1) might be useful to simplify clearing the lowest set bit for the next iteration.