3 ms·
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. Ac
by eloff 6y ago
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.
- BeeOnRope 6y agoYes, 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".