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.
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 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.
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)
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 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.
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.
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.
Oh and same for saturating arithmetic.
Meanwhile, you might appreciate the venerable https://graphics.stanford.edu/~seander/bithacks.html
[1] https://www.chessprogramming.org/Bit-Twiddling
[2] https://www.chessprogramming.org/Kogge-Stone_Algorithm
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...
There's a lot of research into fast ways to do these in the practical compressed data structures community if folks like it.
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.
Hi, I'm folks who like it :). Any (other) keywords and authors I should search for?
I guess it means a js branch is very expensive even when predictable but that feels slightly unsatisfactory.
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.
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.
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)
I wonder what OP was measuring.
https://james.darpinian.com/pocket-palette.html