News for hackers. Stuff that matters.
Re:Iterating over Bit Sets Quickly by atq2119 on Sunday February 25, 2024 @12:16AM (#39497889)
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.

Re:Iterating over Bit Sets Quickly by nwellnhof on Sunday February 25, 2024 @09:15AM (#39500991)
But the test whether a bit is set should be perfectly predictable in the 100% density case.
Re:Iterating over Bit Sets Quickly by sfink on Sunday February 25, 2024 @10:07PM (#39507247)
> 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.