Re:Binary Search: A new implementation that is up to 25% faster
by nightcracker on Monday July 20, 2020 @06:35AM
(#23896483)
That's why the fastest is branchless + eager prefetch + Eytzinger layout.
[ Parent
| on HN ]
Re:Binary Search: A new implementation that is up to 25% faster
by BeeOnRope on Monday July 20, 2020 @10:06AM
(#23897977)
The fastest depends largely on predictability. If it is totally unpredictable I find that prefetch roughly ties with increasing the arity (indeed, the effect is similar when you consider how it all plays out).
If there is a moderate amount of predictability I don't think you can beat branchy.
If you can change the layout, it's a while different game. You could write a paper or two on it and people have.