News for hackers. Stuff that matters.
Re:Iterating over Bit Sets Quickly by kccqzy on Saturday February 24, 2024 @02:51PM (#39494619)
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.

Re:Iterating over Bit Sets Quickly by corysama on Saturday February 24, 2024 @03:34PM (#39494931)
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

Re:Iterating over Bit Sets Quickly by pizlonator on Saturday February 24, 2024 @03:23PM (#39494850)
Totally. The hamming weight thing this post does is available as an instruction on most cpus.
Re:Iterating over Bit Sets Quickly by emmelaich on Saturday February 24, 2024 @10:06PM (#39497223)
Exposed as popcount() in recent versions of Python and C++.
Re:Iterating over Bit Sets Quickly by anonymoushn on Saturday February 24, 2024 @05:24PM (#39495671)
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.
Re:Iterating over Bit Sets Quickly by jandrewrogers on Saturday February 24, 2024 @06:06PM (#39495966)
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.
Re:Iterating over Bit Sets Quickly by ndesaulniers on Saturday February 24, 2024 @08:40PM (#39496823)
GCC now implements __builtin_ctzg for things like C23 _BitInt (and more). Makes implementing C23 stdbit.h more straightforward.
Re:Iterating over Bit Sets Quickly by bawolff on Saturday February 24, 2024 @02:58PM (#39494671)
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.
Re:Iterating over Bit Sets Quickly by halfcat on Saturday February 24, 2024 @04:32PM (#39495310)
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

Re:Iterating over Bit Sets Quickly by vjerancrnjak on Saturday February 24, 2024 @06:03PM (#39495951)
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.
Re:Iterating over Bit Sets Quickly by vanderZwan on Saturday February 24, 2024 @05:12PM (#39495595)
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...

Re:Iterating over Bit Sets Quickly by dgacmu on Saturday February 24, 2024 @09:27PM (#39497061)
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.

Re:Iterating over Bit Sets Quickly by RaisingSpear on Sunday February 25, 2024 @04:23AM (#39499177)
> 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.

Re:Iterating over Bit Sets Quickly by dgacmu on Sunday February 25, 2024 @08:36AM (#39500744)
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
Re:Iterating over Bit Sets Quickly by RaisingSpear on Monday February 26, 2024 @03:32AM (#39508837)
POPCNT doesn't exist in AVX prior to Icelake, so using other techniques there is sensible. Also, that's POPCNT, not LZCNT.
Re:Iterating over Bit Sets Quickly by vanderZwan on Monday February 26, 2024 @02:32AM (#39508504)
> 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?

Re:Iterating over Bit Sets Quickly by Robin_Message on Saturday February 24, 2024 @05:35PM (#39495749)
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.

Re:Iterating over Bit Sets Quickly by atq2119 on Sunday February 25, 2024 @12:16AM (#39497889)
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.

Re:Iterating over Bit Sets Quickly by nwellnhof on Sunday February 25, 2024 @09:15AM (#39500991)
But the test whether a bit is set should be perfectly predictable in the 100% density case.
Re:Iterating over Bit Sets Quickly by sfink on Sunday February 25, 2024 @10:07PM (#39507247)
> 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.

Re:Iterating over Bit Sets Quickly by vanderZwan on Monday February 26, 2024 @05:54AM (#39509816)
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)

Re:Iterating over Bit Sets Quickly by Robin_Message on Monday February 26, 2024 @02:59PM (#39516101)
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.

Re:Iterating over Bit Sets Quickly by modeless on Sunday February 25, 2024 @01:04AM (#39498110)
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

Re:Iterating over Bit Sets Quickly by tommiegannert on Sunday February 25, 2024 @03:33AM (#39498820)
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.