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