4 ms·
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 "sma
by taeric 7mo ago
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 7mo agoThis 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 7mo agoExcept on Apple, where binary search always wins. Does anyone know why?
- stephencanon 7mo 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 7mo agoFor that machine and compiler version, yes.
- taeric 7mo agoI don't think std::find typically uses a sentinel, though?
- KalMann 7mo agoI don't really see how this implies the above commenter's statement is "simply not true".
- deleted 7mo ago[deleted]
- SuperV1234 7mo agoThat's not what the article is about.
- taeric 7mo agoFair. I had meant my point to be an "in addition" and a pointer to more fun things to look up on it.