Beautiful branchless binary search

Trusting the C++ compiler to emit a specific instruction for guaranteed performance - cute, but not realistic.

I don't think it is the instruction that makes the difference. Cmov is a branch either way.

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.

Cmov doesn't branch. A branch refers specifically to the program counter ending up in more than one possible place after an instruction has executed. It is this behavior that mucks with the CPU state and slows everything down.

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.

Thank you for this comment! I was sitting here, metaphorically scratching my head, trying to figure out how the hell you can call this branchless when there's clearly an `if` in there:

        for (step /= 2; step != 0; step /= 2) {
        if (compare(begin[step], value))
            begin += step;
        }

Your comment, especially this part, made it click for me:

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