News for hackers. Stuff that matters.
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?