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.
Either way, it seems that the wisdom has change since the last time I wrote and read assembly. Cmov used to be slow. It seems that the current answer is "it depends".
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];
cmovne rax, rdx
jmp rax
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.
Note that it's not a comparison on A and B, it's a comparison on A - B, which must not overflow.
Great point that memory reads are going to dominate a binary search - at that point the CPU will be spending a lot more time waiting for memory than it is spending executing your branches or cmovs.
Branches in general are cheaper now (since they are generally predicted better), but mispredicted branches are more expensive. They are similar in terms of cycles (IIRC Pentium 4 and Skylake are both typically around 20 cycles if you don't get second-order effects tacked on), but you generally get a lot more done in those cycles on a newer CPU, so they are much more important than they used to be. And a binary search will, almost by definition, tend to have 50% mispredicted branches on the compare (i.e., entirely unpredictable, so no better than random chance).
for (step /= 2; step != 0; step /= 2) {
if (compare(begin[step], value))
begin += step;
}
> 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.
BTW, I hate how the author doesn't use braces with this `if` statement. Many a production bug, including one in OSX, as I recall, have occurred because someone didn't want to type a couple extra characters.
bool b = compare(begin[step], value);
begin += (step * b);