News for hackers. Stuff that matters.

A comment on Binary Search: A new implementation that is up to 25% faster. Parent comment

Re:Binary Search: A new implementation that is up to 25% faster by pubby on Monday July 20, 2020 @12:36AM (#23894694)
The more recent results (by the same author) is this paper: https://arxiv.org/pdf/1509.05053.pdf

The conclusion is still that CMOV is best, but once the data stops fitting in the cache there's alternatives worth considering.

[ Parent | on HN ]
Re:Binary Search: A new implementation that is up to 25% faster by eloff on Monday July 20, 2020 @07:05PM (#23902813)
I just stumbled over this one independently while researching this topic some more, it's an interesting read, thanks for sharing.

> For readers only interested in an executive summary, our results are the following: For arrays small enough to be kept in L2 cache, the branch-free binary search code is the fastest algorithm. For larger arrays, the Eytzinger layout, combined with the branch-free prefetching search algorithm is the fastest general-purpose layout/search algorithm combination.

[ Parent | on HN ]