Trusting the C++ compiler to emit a specific instruction for guaranteed performance - cute, but not realistic.
replies(1):
Branches can be unpredictable and slow, no matter what instructions, (or tables, or whatever) are used to introduce the branch at question.
It is predictable nature of branching in this algo that makes the difference. Which makes me wonder...
EDIT: the cmov vs explicit branching story is a bit more complicated than just branch vs no branch.
It's true that the cmov instruction uses the CPU flags register (which I'm sure the CPU designers at Intel hate), but that doesn't mean that it branches.
You can achieve the same effect as cmov by using bitwise operations and a subtraction, though it'd just be a few cycles slower--but it would be even more clear that it doesn't branch.
A cmov doesn't affect the instruction pointer, so that 'executing the wrong instructions' condition is gone, but it still affects the output of all following instructions if they depend on the register it modifies. So you still have to worry about pipelined work being thrown away on a mispredict.
IMO, cmov was far more valuable back when it was new, because branches were more expensive then. IIRC it was added to x86 in something like the MMX or SSE1 era, so a very long time ago for very different processor architectures. It's still a useful instruction category to have, if only because it lets you produce smaller code (and smaller code is usually faster), but I expect the value is less significant than it used to be.
Incidentally I am curious whether Linus's position on cmov back in 2007 is one he still holds today, and whether his assertions hold up on a modern Intel or AMD CPU. https://yarchive.net/comp/linux/cmov.html
I think the branchless search in this blog post is faster simply because the inner loop is much smaller. The observation that it sometimes does extra comparisons explains why it is slower for an expensive comparison operator, because the advantage of the smaller loop is gone. I don't think it being "branchless" is terribly important in comparison. You could try to fudge an experiment to prove this by inserting extra instructions, but they would need to be ones that decode into actual executed uops, and you'd need to decide whether they should have dependencies or not.
In the bad old days when I got promoted to the programming team at a job they had me take a test, and one of the tasks was to write a transparent blit routine. The one I wrote was "branchless", but because cmov intrinsics weren't widely available I achieved this by using an array of pointers and selecting the array index based on the result of a comparison, something like:
unsigned char* src_dest[] = { src, dest };
for (...; ...; src_dest[0]++, src_dest[1]++)
*src_dest[1] = *src_dest[*src_dest[0] == transparent_value];
loop:
lea (%rdx,%rax,4),%rcx
cmp (%rcx),%esi
cmovg %rcx,%rdx
shr %rax
jne loop
Note that this tracer makes the assumption that all memory loads are in cache (otherwise the memory lookup will dominate). So bear that in mind for this code, especially since memory reads will likely dominate the cost of a binary search.
Regardless, it appears that the cost of conditional move is not the source of bottleneck.