7 ms·

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

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.

atq2119 3y ago
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.
- nwellnhof 3y ago
  But the test whether a bit is set should be perfectly predictable in the 100% density case.
- sfink 3y ago
  > 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.
vanderZwan 3y ago
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 https://jsbenchit.org/?src=219dd9ed01e98533590fc8de40c886f4 fully set [1] https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 fully set, typed array [2] https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e 50% randomly set [3] https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e 25% randomly set in lower half [4] https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 one random bit set per word [5] https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 one random bit set every two words [6] https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 empty bitset (sanity check)
- Robin_Message 3y ago
  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.

atq2119 3y ago

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.

nwellnhof 3y ago
But the test whether a bit is set should be perfectly predictable in the 100% density case.
sfink 3y ago
> 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.

vanderZwan 3y ago

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 https://jsbenchit.org/?src=219dd9ed01e98533590fc8de40c886f4 fully set [1] https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 https://jsbenchit.org/?src=b82e3a2e9631f5e781fc9ff796072985 fully set, typed array [2] https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e https://jsbenchit.org/?src=2dc59964ac15bbc22d58f1f9ee0a6d3e 50% randomly set [3] https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e https://jsbenchit.org/?src=3faa2eb84da523890923549c3b316f2e 25% randomly set in lower half [4] https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 https://jsbenchit.org/?src=646bf8088d0cd2808e236518b7eaa944 one random bit set per word [5] https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 https://jsbenchit.org/?src=4982f7e3557153267e23b4a88732d6a4 one random bit set every two words [6] https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 https://jsbenchit.org/?src=e4ac3cb90b4a395dd7a873fd51267d48 empty bitset (sanity check)

Robin_Message 3y ago
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.