2 ms·
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
by rao-v 6mo ago
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.
- eggprices 6mo agoExcept on Apple, where binary search always wins. Does anyone know why?
- stephencanon 6mo agoPrior 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.
- BeetleB 6mo agoFor that machine and compiler version, yes.
- taeric 6mo agoI don't think std::find typically uses a sentinel, though?
- KalMann 6mo agoI don't really see how this implies the above commenter's statement is "simply not true".
- deleted 6mo ago[deleted]