Fastest branchless binary search

Isn't this definition the crux of it? If you redefine everything as a Branch™, even things that are not branches, then you can definitely precompute some Branch™es.

But the sort of non-Branch™ branch elimination is talking about actually branching computation routes in code due to an if/else statement or similar, is it not?

That would still be useful to do in your world of Branch™es, just only the Branch™es that try and compute the results of more than one future at the same time (i.e. branches).

You're going down the wrong path, again, as Intel did with Itanium.

We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run in parallel. Multiply can be issued on pipeline0, pipeline1, or pipeline5.

If there are 3 multiply instructions, all three pipelines (p0, p1, and p5) all get issued a multiply on _THIS_ clock tick.

----------

The analysis must be dynamic because instructions such as "mov" can take a variable amount of time: loading data from L1 cache is 4-clock ticks, L2 cache is 40 clock ticks, L3 cache is ~150 clock ticks, and RAM is 400+ clock ticks.

That means a "lazy" strategy, where you analyze the state of the pipeline "as late as possible" before making a decision wins out. If you do pre-analysis (ie: what Intel's compiler was supposed to do with Itanium), you pretty much lose out on all variable-time instructions (ex: cache vs RAM).

If you know for certain that you have no memory-operations, then you probably should use a GPU instead of a CPU.

---------

    theLoop: 
    mov ebx, eax[ecx] ; y = array[x]
    add ebx, edx ; y += z
    add ecx, 4
    cmp ecx, 
    jnz theLoop

"add ecx, 4" can actually be done right now in parallel. You split ecx into two registers (ecx-old and ecx-new). You issue "mov ebx, eax[ecx-old]", and then you can execute future instructions with ecx-new. If the next loop is branch predicted (as would be the case in binary search, since you almost always loop), the pipeline/branch prediction stuff works together and you can execute mov ebx, eax[ecx0], mov ebx, eax[ecx1], mov ebx, eax[ecx2], mov ebx, eax[ecx3]... all in parallel (!!!!), as ecx3 gets branch predicted and multiple loops start running in parallel..

Its not hard, its not very difficult analysis, its low power. Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on.

----------

Furthermore, most code with branches can seemingly be replaced with branchless code (ex: cmov instructions, min instruction, max instruction, etc. etc.)

So instead of magic compilers trying to solve an unsolvable problem (how do you schedule memory load/stores to keep the processor busy even though you don't know how long any memory operation takes...)... you write a magic compiler that solves a very easy to solve problem. (IE: convert the branchy-if statement into a branchless max or branchless cmov instruction instead).

--------

EDIT: I added "theLoop:" to the assembly above, because I realized that "branches" can be beneficial in the face of OoO / Tomasulo's algorithm. "Executing future loops" before the 1st loop is done is very beneficial.

It might be stateless, but it depends on many things unknown at compile time.

One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found.

Another one is micro-architecture, most notably cache hierarchy, and composition of EUs inside codes. If you switch to ISA with instructions resembling the micro-ops of the current CPUs, you’ll have to re-compile for every micro-architecture. However, this one is technically solvable with JIT compiler in OSes, like current GPUs where programs ship in byte code formats (DXBC, SPIR-V, NVPTX) then user-mode half of GPU driver recompiles into actual hardware instructions.

Another huge one, other CPU threads are running unknow code. Even if you drop hyper-threading making cores independent, there’re still resources shared across the complete chip: L3 cache, off-chip memory, I/O bandwidth, and electricity i.e. thermals.

The IPC crowd reasons that if they can get a higher IPC value, then the process guys can crank the clock and everybody wins. The thoughput crowd takes the more pragmatic approach that Moore's law is dead and making silicon clock faster melts it so being clever in the ISA wins the day. Both camps have had successes and setbacks over the last 20 years.

I am really enjoying the RISC-V stuff which is getting back into this level of question with regard to CPU architectures. Also a good place to look if you want to catch up on what "modern" superscalar ideas are being added with support of instruction set flexibility. My guess is that wins the game in the long run.

[1] This was in the early oughts so could have been HotChips, Microprocessor Forum, or HPC workshops.

And I don't just mean decode, fetch, and execute. If your computer has independent ALU and Shifting units, you can potentially be shifting something as you are also adding. Have a dedicated Adder and a Multiplication unit? No reason you can't try and do both as the same time.

This directly leads to wanting multiple instructions in flight at the same time, which means you have to be able to fetch and decode instructions faster than you are processing them. Also naturally leads to situations where you want to reorder so that the N Add instructions don't keep you from seeing an independent Shift that you could do in the same time.

You can think that things are more complicated than they need to be. And, you may not even be wrong. But a ton of engineering is going into making what we have. If you think you can make something a ton faster by not doing it this way, probably a good thing to dig into how accurate that claim is.

Transmeta's translation did not somehow eliminate branch costs.

In fact I distinctly remember a comp.arch thread and post from Linus himself while he worked at Transmeta that paraphrased was "the cpu's job is to generate cache misses as fast as possible."

Compulsory misses are a thing. No form of JIT is capable of eliminating them. Capacity misses are inevitable in the real world, even with the monster caches we have now.

Itanium thought it could eliminate branch costs with static analysis. How did that work out?

I really wish programmers would actually read a book about computer architecture before they so confidently conclude that it's simple to build things better than state of the art processors. You are underestimating the scale of smart that has gone into current processors by at least 7 orders of magnitude in my opinion.

Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

At TigerBeetle, we have our own branchless implementation here:

https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...

Oodles and oodles of undefined behaviour, for example.

C ain't clean.

https://algorithmica.org/en/eytzinger

100mb is large enough that the branchy version turns out to have a slight advantage, more due to quirks of x86 (speculative execution) rather than being better.

            let mid = left + size / 2;

[2] https://web.archive.org/web/20230709221353/https://doc.rust-...

[3] https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779

I assume purely random, but if these 8-byte strings were anything but pure information, modern branch predictors can sniff their way to better performance than cmov pretty easily.

I will say that if this is the case, there are probably much better versions of binary search out there for primitive types. I made one just screwing around with SIMD that's 3x faster than std::lower_bound until becoming memory bound:

https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...

Inlining seems like a natural application: Inlining is perhaps the most critical optimization to get right, and getting it right is a complex balance of frequency of use vs. added code bloat and associated further optimization cost. Having more than one bit of branch-likelihood as input to these decisions could easily be helpful.

I also tried (and failed) to use expect with probability to generate a cmov, but in retrospect it is obvious: the parameter is not the prediction probability, but the taken/not-taken probability, and even a branch that goes either way with 50% probability can still be predicted perfectly (for example a branch that switches every other iteration), so the parameter can't be used to decide between predication and prediction.

edit: what we really need is an [[unpredictable]] attribute.

Not sure how consistent this is across architectures, and how useful it still is. But at least it used to be a thing

TL;DR: you can generate different, and more efficient code if you know how much it is going to be mispredicted.

Or are you pointing out how first[length] and first += length + rem would technically result in advancing a forward iterator through to first + length twice? (Trivially fixed with a middle = first + length temporary variable btw).

The junior employees I have had to deal with tended to build towering abstractions that no one really needed, rather than optimising hot loops.

https://github.com/ehrmann/branchless-binary-search/blob/mas...

People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.

    More branchless, more better?
    Short answer: no. This section can be skipped but here’s the long answer: For n elements where 2k <= n < 2k+1 sb_lower_bound will always do k+1 comparisons. On a 64-bit machine that means at most 64 iterations of the while (length > 0) loop. So it’s possible to write a “fully branchless” version that doesn’t have the length check by using a switch with intentional fall-through.
    
    size_t length = last - first;
    size_t rem;
    switch(std::bit_width(length)) {
       case 64:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
       case 63:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
       // ...
       case 1:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
    }
    return first;
    
    If you’re not familiar with switch, think of it as a jump into code. In our case to the exact place from which there are exactly the right number of comparisons left to do.
    
    “Is it any faster?” No. Modern x86 processors handle loop conditions well as they’re predictable; we’re very likely to remain in the loop. And that’s good especially because it saves us from writing templates or macros or copy-paste-edit the 64 cases.