4 ms·

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 tes

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.