Hacker News Reader

Comment by eloff | Hacker News Reader

Binary search can be implemented using conditional move instructions instead of branching. Given the branches are unpredictable, this yields a huge speedup. It can be implemented like this in pure C, if written in a way the compiler can recognize. In my experience this is the fastest binary search.

[1] https://pvk.ca/Blog/2012/07/03/binary-search-star-eliminates...

View on HN

Actually cmov-based searches often (usually?) result in a slowdown unless non-obvious measures are taken.

A cmov-based search has the problem that the probes for each level are data-depedent on the prior level. So you cannot get any memory-level parallelism, because the address to probe at level n+1 isn't known until the comparison at level n completes.

Branchy search is at least right half the time (in the worst case) on the next direction, 25% of the time for 2 levels down, etc. So it gets about 1 additional useful access in parallel, on average in the worst case, compared to cmov search.

Except for very small searches which fit in the L1 cache, where misprediction cost dominate overall time, branchy is competitive and often faster.

Now you can take countermeasures to this problem with the cmov search. One is to increase the arity of the search as in the OP, another is explicit software prefetching, etc, which might put cmov back on top.

This has all been assuming the worst case of totally unpredictable branches. Real world searches might be expected to be less-than-random as some elements are hotter than others, etc. Any predictability of the branches helps out for branchy search.

As usual, it depends. I was doing binary search within btree nodes, which means small arrays that fit into the cache. Branchless search performed best there. Actually even the btree search itself was branchless (if nodes were in memory) until the end, as the pointer to the next node was just loaded via an index calculation and the loop continued with a binary search of the next node. I did a little software prefetching as well once I had the pointer to the next node.

Yes, tightly packed nodes or nodes which are all in L1 is one place where plain cmov can win.

The sweet spot is pretty small though, because it is not only squeezed from above by branchy which wins for less cached data, but also from below by linear vectorized search. You can't always apply vectorized search (e.g. if the keys are not contiguous), but when you can it can win up to dozens of elements.

When you throw the possibility of predictability on top, where branchy wins, that's why I usually reject unconditional statements that "cmov gives a huge speedup".

That's why the fastest is branchless + eager prefetch + Eytzinger layout.

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.

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.

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.

Reply on news.ycombinator.com