Iterating over bit sets quickly | Hacker News Reader

Iterating over bit sets quickly

alexharri.com

70 pointsliamswayne24 comments

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/Refe...

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.

> 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.

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

POPCNT doesn't exist in AVX prior to Icelake, so using other techniques there is sensible. Also, that's POPCNT, not LZCNT.

> There's a lot of research into fast ways to do these in the practical compressed data structures community if folks like it.

Hi, I'm folks who like it :). Any (other) keywords and authors I should search for?

I was recently reading about Roaring 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/ is especially good.

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

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

[2] https://www.chessprogramming.org/Kogge-Stone_Algorithm

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.

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.

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.

But the test whether a bit is set should be perfectly predictable in the 100% density case.

> 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.

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 fully set

[1] https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 fully set, typed array

[2] https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e 50% randomly set

[3] https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e 25% randomly set in lower half

[4] https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 one random bit set per word

[5] https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 one random bit set every two words

[6] https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 empty bitset (sanity check)

Thank you! And thanks for suggesting and checking Math.clz32, it makes sense that would be fast as it's a single instruction vs a pile of bit twiddling.

I wonder what OP was measuring.

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.

Totally. The hamming weight thing this post does is available as an instruction on most cpus.

Exposed as popcount() in recent versions of Python and C++.

Same. I’m very happy about the addition of 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/p31... Don’t know if it got anywhere.

Meanwhile, you might appreciate the venerable https://graphics.stanford.edu/~seander/bithacks.html

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.

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.

GCC now implements __builtin_ctzg for things like C23 _BitInt (and more). Makes implementing C23 stdbit.h more straightforward.

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.

Reply on news.ycombinator.com