Comment by BeeOnRope | Hacker News Reader

Comment by BeeOnRope | Hacker News Reader

Parent Full thread

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.

Reply on news.ycombinator.com