3 ms·
> With a binary search you basically get worst possible case for branch predictor, because if you're searching random values whether you go right/left on each r
by ignoramous 3y ago
> With a binary search you basically get worst possible case for branch predictor, because if you're searching random values whether you go right/left on each recursion level is basically random.
I think folks writing databases know a thing or two about writing faster search and sort algorithms.
- birdyrooster 3y agoWhy do you think that? Seems like a hard problem.
- anyfoo 3y agoI'm not sure what you are trying to say, given the context of what you quoted was. Binary search has optimal worst case runtime complexity, but for small tables it is, on real computers, overall still slower than a linear scan, which effectively has the worst worst case runtime complexity (unless you start to get pathological). This is because the constant in front of the runtime complexity, the one that O-notation explicitly ignores, starts to matter: Branch prediction and cache locality come into play. What exactly do you mean with "writing faster search and sort algorithms"?
- ignoramous 3y ago> What exactly do you mean with "writing faster search and sort algorithms"? - Branchless binary search: https://news.ycombinator.com/item?id=35737862 https://news.ycombinator.com/item?id=35737862 / https://news.ycombinator.com/item?id=14598098 https://news.ycombinator.com/item?id=14598098 - Static B-Trees for faster binary search: https://news.ycombinator.com/item?id=30376140 https://news.ycombinator.com/item?id=30376140 Presumably there's even more literature on the topic.
- anyfoo 3y agoThose are neat optimizations of the constant, but even with that, a linear scan can still be much faster under the right (and not unrealistic) circumstances. But I see now you were referring to the branch predictor part specifically, so all good.
- pkulak 3y agoWhich is why they use b-trees and not binary search.