Fastest branchless binary search
Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture?<p>The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it&#x27;s not a very stateful algorithm.<p>This is how Transmeta Crusoe CPUs worked. Imagine NOT caring that you have a branch.<p>After all, if you think about it, all operations are branches. Down to bitwise operations and summing two numbers. It&#x27;s branching in the ALU, carry bits and what not. You can&#x27;t compute absolutely anything without looking at the state of one or more bits, and making a decision that changes the outcome. But the reason those branches don&#x27;t hurt performance is that they&#x27;re not branches on the main pipeline. These local branches have a very short (or non-existent) &quot;pipeline&quot;. And the main pipeline is therefore not affected, despite the actual state of the system is.