[taeric]

If you are talking smaller arrays, linear search with a sentinel value at the end is already tough to beat. The thing that sucks about that claim, is that "smaller" is such a nebulous qualifier that it is really hard to internalize.

[rao-v]

This is simply not true - if you look at this article’s excellent benchmarking, linear search falls behind somewhere around 200-400 elements.

In general I love this article, it took what I’ve often wondered about and did a perfect job exploring with useful ablation studies.

[KalMann]

I don't really see how this implies the above commenter's statement is "simply not true".

[taeric]

I don't think std::find typically uses a sentinel, though?

[BeetleB]

For that machine and compiler version, yes.

[eggprices]

Except on Apple, where binary search always wins. Does anyone know why?

[stephencanon]

Prior to the current generation Intel designs, Apple’s branch predictor tables were a good deal larger than Intel’s IIRC, so depending on benchmarking details it’s plausible that Apple Silicon was predicting every branch perfectly in the benchmark, while Intel had a more real-world mispredict rate. Perf counters would confirm.

[SuperV1234]

That's not what the article is about.

[taeric]

Fair. I had meant my point to be an "in addition" and a pointer to more fun things to look up on it.