4 ms·

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 bi

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/Reference/Global_Objects/Math/clz32 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

dgacmu 3y ago
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.
- RaisingSpear 3y ago
  > 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.
  - dgacmu 3y ago
    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 http://0x80.pl/articles/sse-popcount.html
    - RaisingSpear 3y ago
      POPCNT doesn't exist in AVX prior to Icelake, so using other techniques there is sensible. Also, that's POPCNT, not LZCNT.
- vanderZwan 3y ago
  > 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?

dgacmu 3y ago

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.

RaisingSpear 3y ago
> 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.
- dgacmu 3y ago
  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 http://0x80.pl/articles/sse-popcount.html
  - RaisingSpear 3y ago
    POPCNT doesn't exist in AVX prior to Icelake, so using other techniques there is sensible. Also, that's POPCNT, not LZCNT.
vanderZwan 3y ago
> 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?