Re:Binary Search: A new implementation that is up to 25% faster
by eloff on Monday July 20, 2020 @09:17AM
(#23897490)
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.
[ Parent
| on HN ]
Re:Binary Search: A new implementation that is up to 25% faster
by BeeOnRope on Monday July 20, 2020 @10:11AM
(#23898014)
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".