For a proper/sane forward iterator, front[index] is the same thing as *(front + index) and front + index achieves the same as std::advance(front, index) (just not in place).

Or are you pointing out how first[length] and first += length + rem would technically result in advancing a forward iterator through to first + length twice? (Trivially fixed with a middle = first + length temporary variable btw).

Then you'll want to look at https://mhdm.dev/posts/sb_lower_bound/#prefetching

100mb is large enough that the branchy version turns out to have a slight advantage, more due to quirks of x86 (speculative execution) rather than being better.

So I spent too much time benchmarking:

    | Entries | gcc | gcc+pref. | clang | clang+pref. | clang -cmov | clang -cmov+pref. |
    |---------|-----|-----------|-------|-------------|-------------|-------------------|
    | 0.5     | 210 | 88        | 213   | 191         | 109         | 93                |
    | 1.0     | 231 | 107       | 235   | 211         | 134         | 112               |
    | 2.0     | 289 | 168       | 306   | 275         | 231         | 179               |
    | 5.0     | 369 | 231       | 389   | 343         | 338         | 239               |
    | 10      | 413 | 268       | 437   | 384         | 410         | 276               |
    | 25      | 469 | 311       | 490   | 435         | 506         | 318               |
    | 50      | 515 | 346       | 537   | 478         | 586         | 356               |
    | 100     | 564 | 387       | 588   | 522         | 670         | 399               |

Entries are in millions and times in ns per bsearch call. Prefetching does all the difference, but perhaps not for the right reason. On my machine (broadwell) the two prefetches that you suggested makes gcc emit the cmovb that clang with -cmov uses. The second one is enough to make it prefer cmovb but not the first one. Maybe a hand-hacked assembly loop based on the code gcc emits but without the prefetches would run even faster.

Thanks, updated the footnote.

Prefetching is the right tradeoff for large arrays. Addressed at the end of the article: https://mhdm.dev/posts/sb_lower_bound/#prefetching

It was meant to link to rust's binary search implementation. Updated to https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

Author here. I'm open to feedback and happy to answer questions.

Author here, I'm open to feedback and happy to answer questions.

Awesome game. Didn't think it was possible to LOSE at picking a password but there you have it. LOST at finding a 16m48s youtube video and a lovely passw0R.513mayIshellXXXV8pfxxtractAusingaporeRh8+ iamenough

When entering the chess game moves make sure to add `x` when taking a piece, `+` when checking, and `#` for checkmate.