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".
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".