[patrulek]

You can utilize MLP (memory-level parallelism) and reduce memory latency by reading whole 8 bytes of next_j at every iteration. Just do something like

`uint64_t packed_next_j = *(uint64_t*)(&next_j[i])`

and then just shift right to find proper j. This way you remove dependency on previous iteration. Did you tried that?

[purplesyringa]

The right-shift is the problem. You need to shift right by `j * 8`, which itself requires a shift to compute (`j << 3`), so you have two shifts on the critical path, resulting in a latency of 2 cycles. It's better than a load, but it's still noticeable.

[patrulek]

2 cycles vs ~5 cycles is still nice improvement plus its more deterministic (but not that fast in optimistic case; better in pessimistic case) than `if` appraoch and probably easier to "invent" and reason about. Definitely not that cool as your `if` solution though :)

[OptionOfT]

Don't you need the previous iteration to find out how much you need to shift right?

[patrulek]

Yes you need, but the initial problem here were sequential loads from L1 into registers.