6 ms·

Iterating over bit sets quickly

70 points by liamswayne 3y ago

kccqzy 3y ago
I am of the opinion that tasks like finding the least significant set bit should be inside the standard library of all languages, so that compilers (including JIT ones) can use the efficient CPU instruction to calculate it, like bsr/bsf on x86 ones. This is the first time I've heard of the `word & -word` trick because in C/C++ I'd just use __builtin_ctzll and __builtin_clzll. Oh and same for saturating arithmetic.
- pizlonator 3y ago
  Totally. The hamming weight thing this post does is available as an instruction on most cpus.
  - emmelaich 3y ago
    Exposed as popcount() in recent versions of Python and C++.
- corysama 3y ago
  Same. I’m very happy about the addition of https://en.cppreference.com/w/cpp/numeric/countr_zero https://en.cppreference.com/w/cpp/numeric/countr_zero There’s a proposal to get them to work with std::bitset. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3103r0.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p31... Don’t know if it got anywhere. Meanwhile, you might appreciate the venerable https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
- anonymoushn 3y ago
  You end up using some of these tricks even if you can access ctz, because it's faster to mask off the lowest bit in a way that doesn't depend on the output of the ctz instruction.
  - deleted 3y ago
    [deleted]
- jandrewrogers 3y ago
  At least on x86 processors, most idiomatic bit manipulation expressions like `word & -word` or `word & (word - 1)` compile to a single fast ALU instruction. __builtin_clz and similar are comparatively more expensive on many architectures.
- ndesaulniers 3y ago
  GCC now implements __builtin_ctzg for things like C23 _BitInt (and more). Makes implementing C23 stdbit.h more straightforward.
bawolff 3y ago
I was recently reading about Roaring https://roaringbitmap.org/ https://roaringbitmap.org/ which is a highly optimized compressed bitset implementation. I reccomend reading about it if you are interested in this sort of thing. The talk at https://roaringbitmap.org/talks/ https://roaringbitmap.org/talks/ is especially good.
halfcat 3y ago
Ah, brings back memories of chess programming where this stuff was discussed often. See [1] for more of this. I always found Kogge Stone [2] pretty cool, a kind of bit-twiddling flood-fill. [1] https://www.chessprogramming.org/Bit-Twiddling https://www.chessprogramming.org/Bit-Twiddling [2] https://www.chessprogramming.org/Kogge-Stone_Algorithm https://www.chessprogramming.org/Kogge-Stone_Algorithm
- vjerancrnjak 3y ago
  n-queens too, a simple example that can benefit from this bit trick. Eventually you're looking for free columns in the current row where queen can be put. Instead of going over all columns, with a few bit operations iteration can only go directly through free columns.
vanderZwan 3y ago
That was an enjoyable read, and all of these bit twiddling tricks are great. Having said that I'm fairly sure that using Math.clz32 is faster for finding the bit index than using the Hamming weight. That also lets you iterate from the most-to-least significant bit if you want. Can't blame the author for not trying that though, it's probably one of the most obscure and rarely used library functions in JavaScript. (I will bookmark this article for the next time I need to iterate over bitmaps LSB first though) [0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- dgacmu 3y ago
  clz is faster in almost all contexts. There are some times when you're doing these operations in large vector types (like AVX), in parallel, when falling back to the SWAR techniques can actually be faster because of limited bandwidth on the port for micro ops in popcnt or clz. There's a lot of research into fast ways to do these in the practical compressed data structures community if folks like it.
  - RaisingSpear 3y ago
    > There are some times when you're doing these operations in large vector types (like AVX), in parallel, when falling back to the SWAR techniques can actually be faster because of limited bandwidth on the port for micro ops in popcnt or clz. I'm doubtful of this in general. Some older processors did have a very slow BSF/BSR implementation, so it may be the case there, but I wouldn't generally stick with that assumption these days. (and it's most certainly not the case on AMD Zen, given all its ALUs can do these bit ops) AVX doesn't have lzcnt prior to AVX-512 CD, so it could make more sense there, though I'd imagine that abusing float conversion (convert to float, extract exponent) would still be faster.
    - dgacmu 3y ago
      Oh, I don't think it's a general principal, it's very processor architecture specific. But here's one example from earlier avx-supporting CPUs: http://0x80.pl/articles/sse-popcount.html http://0x80.pl/articles/sse-popcount.html
Robin_Message 3y ago
I don't understand how all that bit twiddling is faster in the 100% case (where the branch predictor should be hitting home runs.) I guess it means a js branch is very expensive even when predictable but that feels slightly unsatisfactory.
- atq2119 3y ago
  I agree it's quite surprising, but in hindsight it makes some sense: The original implementation has 2 branches per iteration: one for the loop, and one to test whether the bit is set or not. The optimized implementation has 1 branch per iteration. I doubt that the fact that it's JS matters all that much given that either loop is absolutely tiny once it's compiled down to optimized assembly.
  - nwellnhof 3y ago
    But the test whether a bit is set should be perfectly predictable in the 100% density case.
  - sfink 3y ago
    > I doubt that the fact that it's JS matters all that much given that either loop is absolutely tiny once it's compiled down to optimized assembly. It might matter. At least when run in the browser, JS needs to be interruptible (so pages don't hang on infinite loops), which is often done by checking a flag at the target of any backwards branch. So that's another (predictable) branch. And sometimes when you get enough branches, they have an effect even if they're near 100% predictable. I don't know if it's from branch aliasing, or using up general branch prediction resources, or prefetching / some other optimization giving up after too many branches, or what.
- vanderZwan 3y ago
  This is a pet peeve of mine: there is a table with benchmark nrs but no link to code to verify this. And in the case of JavaScript benchmarks, no explanation given for which JS engine was used either. So I just did it myself. Maybe I made a mistake in porting it but at least you can verify and fix the benchmarks yourself now in that case. Your intuition seems correct, because the optimized version is slower for me - both on Firefox nor on Chrome. But using the Math.clz32 version I suggested elsewhere is always faster. One other issue I have is with using () => {} as the callback. So I added a stateful callback with a small side-effect to verify whether or not this loop optimization even matters, or whether the callback overhead should be expected to dwarf it. The results do suggest optimizing the loop is worth it. I also tried using a Uint32Array backing array, which has identical performance! That is a good sign regarding plain array optimizations[1]. On lower values the optimized options are faster, as expected although the clz32 does significantly better, and in the case of Firefox helps it (almost) catch up to Chrome. [0] https://jsbenchit.org/?src=219dd9ed01e98533590fc8de40c886f4 https://jsbenchit.org/?src=219dd9ed01e98533590fc8de40c886f4 fully set [1] https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 fully set, typed array [2] https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e 50% randomly set [3] https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e 25% randomly set in lower half [4] https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 one random bit set per word [5] https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 one random bit set every two words [6] https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 empty bitset (sanity check)
modeless 3y ago
I once wrote a solver to calculate the answer to a bin packing problem where the number of bins was less than 32, so I just did the whole calculation by brute force inside 32 bit integers. Placing pieces in bins and moving pieces around and testing for collisions is super easy with bitwise operations. Even in JavaScript it was more than fast enough; the whole calculation certainly fits in cache; probably completely in registers actually. https://james.darpinian.com/pocket-palette.html https://james.darpinian.com/pocket-palette.html
tommiegannert 3y ago
Why is the 100% density speedup 1.8x? The hammingWeight seems like it should always be slower than going one-by-one in a fully-set set.

70 points by liamswayne 3y ago

I am of the opinion that tasks like finding the least significant set bit should be inside the standard library of all languages, so that compilers (including JIT ones) can use the efficient CPU instruction to calculate it, like bsr/bsf on x86 ones. This is the first time I've heard of the `word & -word` trick because in C/C++ I'd just use __builtin_ctzll and __builtin_clzll. Oh and same for saturating arithmetic.

pizlonator 3y ago
Totally. The hamming weight thing this post does is available as an instruction on most cpus.
- emmelaich 3y ago
  Exposed as popcount() in recent versions of Python and C++.
corysama 3y ago
Same. I’m very happy about the addition of https://en.cppreference.com/w/cpp/numeric/countr_zero https://en.cppreference.com/w/cpp/numeric/countr_zero There’s a proposal to get them to work with std::bitset. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3103r0.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p31... Don’t know if it got anywhere. Meanwhile, you might appreciate the venerable https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
anonymoushn 3y ago
You end up using some of these tricks even if you can access ctz, because it's faster to mask off the lowest bit in a way that doesn't depend on the output of the ctz instruction.
- deleted 3y ago
  [deleted]
jandrewrogers 3y ago
At least on x86 processors, most idiomatic bit manipulation expressions like `word & -word` or `word & (word - 1)` compile to a single fast ALU instruction. __builtin_clz and similar are comparatively more expensive on many architectures.
ndesaulniers 3y ago
GCC now implements __builtin_ctzg for things like C23 _BitInt (and more). Makes implementing C23 stdbit.h more straightforward.

bawolff 3y ago

I was recently reading about Roaring https://roaringbitmap.org/ https://roaringbitmap.org/ which is a highly optimized compressed bitset implementation. I reccomend reading about it if you are interested in this sort of thing. The talk at https://roaringbitmap.org/talks/ https://roaringbitmap.org/talks/ is especially good.

halfcat 3y ago

Ah, brings back memories of chess programming where this stuff was discussed often. See [1] for more of this. I always found Kogge Stone [2] pretty cool, a kind of bit-twiddling flood-fill. [1] https://www.chessprogramming.org/Bit-Twiddling https://www.chessprogramming.org/Bit-Twiddling [2] https://www.chessprogramming.org/Kogge-Stone_Algorithm https://www.chessprogramming.org/Kogge-Stone_Algorithm

vjerancrnjak 3y ago
n-queens too, a simple example that can benefit from this bit trick. Eventually you're looking for free columns in the current row where queen can be put. Instead of going over all columns, with a few bit operations iteration can only go directly through free columns.

vanderZwan 3y ago

That was an enjoyable read, and all of these bit twiddling tricks are great. Having said that I'm fairly sure that using Math.clz32 is faster for finding the bit index than using the Hamming weight. That also lets you iterate from the most-to-least significant bit if you want. Can't blame the author for not trying that though, it's probably one of the most obscure and rarely used library functions in JavaScript. (I will bookmark this article for the next time I need to iterate over bitmaps LSB first though) [0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

dgacmu 3y ago
clz is faster in almost all contexts. There are some times when you're doing these operations in large vector types (like AVX), in parallel, when falling back to the SWAR techniques can actually be faster because of limited bandwidth on the port for micro ops in popcnt or clz. There's a lot of research into fast ways to do these in the practical compressed data structures community if folks like it.
- RaisingSpear 3y ago
  > There are some times when you're doing these operations in large vector types (like AVX), in parallel, when falling back to the SWAR techniques can actually be faster because of limited bandwidth on the port for micro ops in popcnt or clz. I'm doubtful of this in general. Some older processors did have a very slow BSF/BSR implementation, so it may be the case there, but I wouldn't generally stick with that assumption these days. (and it's most certainly not the case on AMD Zen, given all its ALUs can do these bit ops) AVX doesn't have lzcnt prior to AVX-512 CD, so it could make more sense there, though I'd imagine that abusing float conversion (convert to float, extract exponent) would still be faster.
  - dgacmu 3y ago
    Oh, I don't think it's a general principal, it's very processor architecture specific. But here's one example from earlier avx-supporting CPUs: http://0x80.pl/articles/sse-popcount.html http://0x80.pl/articles/sse-popcount.html

Robin_Message 3y ago

I don't understand how all that bit twiddling is faster in the 100% case (where the branch predictor should be hitting home runs.) I guess it means a js branch is very expensive even when predictable but that feels slightly unsatisfactory.

atq2119 3y ago
I agree it's quite surprising, but in hindsight it makes some sense: The original implementation has 2 branches per iteration: one for the loop, and one to test whether the bit is set or not. The optimized implementation has 1 branch per iteration. I doubt that the fact that it's JS matters all that much given that either loop is absolutely tiny once it's compiled down to optimized assembly.
- nwellnhof 3y ago
  But the test whether a bit is set should be perfectly predictable in the 100% density case.
- sfink 3y ago
  > I doubt that the fact that it's JS matters all that much given that either loop is absolutely tiny once it's compiled down to optimized assembly. It might matter. At least when run in the browser, JS needs to be interruptible (so pages don't hang on infinite loops), which is often done by checking a flag at the target of any backwards branch. So that's another (predictable) branch. And sometimes when you get enough branches, they have an effect even if they're near 100% predictable. I don't know if it's from branch aliasing, or using up general branch prediction resources, or prefetching / some other optimization giving up after too many branches, or what.
vanderZwan 3y ago
This is a pet peeve of mine: there is a table with benchmark nrs but no link to code to verify this. And in the case of JavaScript benchmarks, no explanation given for which JS engine was used either. So I just did it myself. Maybe I made a mistake in porting it but at least you can verify and fix the benchmarks yourself now in that case. Your intuition seems correct, because the optimized version is slower for me - both on Firefox nor on Chrome. But using the Math.clz32 version I suggested elsewhere is always faster. One other issue I have is with using () => {} as the callback. So I added a stateful callback with a small side-effect to verify whether or not this loop optimization even matters, or whether the callback overhead should be expected to dwarf it. The results do suggest optimizing the loop is worth it. I also tried using a Uint32Array backing array, which has identical performance! That is a good sign regarding plain array optimizations[1]. On lower values the optimized options are faster, as expected although the clz32 does significantly better, and in the case of Firefox helps it (almost) catch up to Chrome. [0] https://jsbenchit.org/?src=219dd9ed01e98533590fc8de40c886f4 https://jsbenchit.org/?src=219dd9ed01e98533590fc8de40c886f4 fully set [1] https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 fully set, typed array [2] https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e 50% randomly set [3] https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e 25% randomly set in lower half [4] https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 one random bit set per word [5] https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 one random bit set every two words [6] https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 empty bitset (sanity check)

modeless 3y ago

I once wrote a solver to calculate the answer to a bin packing problem where the number of bins was less than 32, so I just did the whole calculation by brute force inside 32 bit integers. Placing pieces in bins and moving pieces around and testing for collisions is super easy with bitwise operations. Even in JavaScript it was more than fast enough; the whole calculation certainly fits in cache; probably completely in registers actually. https://james.darpinian.com/pocket-palette.html https://james.darpinian.com/pocket-palette.html

tommiegannert 3y ago

Why is the 100% density speedup 1.8x? The hammingWeight seems like it should always be slower than going one-by-one in a fully-set set.