This is simply not true - if you look at this article’s excellent benchmarking, linear search falls behind somewhere around 200-400 elements.
replyIn general I love this article, it took what I’ve often wondered about and did a perfect job exploring with useful ablation studies.
I don't really see how this implies the above commenter's statement is "simply not true".
replydeleted
replyI don't think std::find typically uses a sentinel, though?
replyFor that machine and compiler version, yes.
replyExcept on Apple, where binary search always wins. Does anyone know why?
replyPrior 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.
replyThat's not what the article is about.
reply