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