The Weird Concept of Branchless Programming (sanixdk.xyz)

I enjoyed reading the article, but I'm pretty thrown by the benchmarks and conclusion. All of the times are reported to a single digit of precision, but then the summary is claiming that one function shows an improvement while the other two are described as negligible. When all the numbers presented are "~5ms" or "~6ms", it doesn't leave me confident that small changes to the benchmarking might have substantially changed that conclusion.

This great video [0] demonstrates how CPU performance has only increased 1.5-2x over the past 15(!) years when executing extremely branchy code. Really shows you just how deep modern CPU pipelines have become.

The video also showcases a much more impressive branchless speedup: computing CRC checksums. Doing this naïvely with an if-statement for each bit is ~10x slower than doing it branchless with a single bitwise operation for each bit. The author of the article should consider showcasing this too, since it's a lot more impressive than the measly 1.2x speedup highlighted in the article. I assume the minimal/nonexistent speedups in the article are due to modern CPU branch prediction being quite good. But branch predictors inherently fail miserably at CRC because the conditional is on whether the input bit is 1 or 0, which is essentially random.

[0] https://www.youtube.com/watch?v=m7PVZixO35c

Great article, triggers some memories.

When you get to think about branchless programming, especially for SIMD optimizations in the real world, you always learn a lot and it’s as if you get a +1 level on your algorithmic skills. The hardest part then is make sure the tricks are clearly laidout so that someone else can take it from here next time

Article doesn’t mention this, but I’d consider neural networks a form of branchless programming. It’s all a bunch of multiply and threshold operations.

The article is easy to follow but I think the author missed the e point: branchless programming (a subset of the more known constant time programming) is almost exclusively used in cryptography only nowadays. As shown by the benchmarks in the article, modern branch predictors can easily achieve over 95% if not 99% precision since like a decade ago

This same blog posted yesterday and got flagged with “How I accidently created the fastest CSV parser ever made”

https://news.ycombinator.com/item?id=45400009

I’m amused to see a for loop in a function that is purportedly branchless

(not a critique)

I've always wondered if any CPUs have tried to reduce the branch penalty by speculatively executing both ways at once in parallel. You'd have two of everything (two pipelines, two ALUs, two sets of registers, etc.) and when you hit a conditional branch, instead of guessing which way to go, you'd essentially fork.

Obviously that requires a lot of extra transistors and you are doing computation that will be thrown away, so it's not free in terms of space or power/heat/energy. But perhaps it could handle cases that other approaches can't.

Even more of a wild idea is to pair up two cores and have them work together this way. When you have a core that would have been idle anyway, it can shadow an active core and be its doppelganger that takes the other branch. You'd need to have very fast communication between cores so the shadow core can spring into action instantly when you hit a branch.

My gut instinct is it's not worth it overall, but I'm curious whether it's been tried in the real world.

I think I'm getting too sensitive to AI-assisted articles. So many whimsical terms to make something "fun".

I used to do stuff like this (ok, not half as smart), but stopped around 2013 or so, as the distinction between "implementation defined" behavior (ok) and "undefined" behavior (not ok) started to matter and bite.

After thinking through this carefully, though, I do not see UB (except for signed overflow in a corner case):

Step 1, bit shift.

I understand that, until C++20, left shift of a signed int was UB. But this right shift appears to be implementation defined, which is ok if documented in the code.

Step 2: Add.

Then, (x + mask) is defined behavior (a) for positive x, since then mask=0, and (b) for most negative x, since then mask=-1. However, if x is numeric_limits::lowest, then you get signed integer overflow, which is UB.

Step 3, XOR.

Then the final XOR doesn't have UB AFAICT. It wouldn't be UB as of C++20, when signed integers became two's complement officially. It might have been implementation defined before then, which would be almost as good for something that ubiquitous, but I'm not sure.

Ok, so I think this does not involve UB except for an input of numeric_limits_lowest.

Sound about right?

To fix this, perhaps you would need to make that + an unsigned one?

It bothers me how hard you need to think to do this language lawyering. C++ is a system of rules. Computers interpret rules. The language lawyer should be a piece of software. I get it, not everything can be done statically, so, fine, do it dynamically? UBSan comes closest in practice, but doesn't detect everything. I understand formally modeled versions of C and C++ have been developed commercially, but these are not open source so they effectively do not exist. It's a strange situation.

Just the other day I considered writing something branchless and said, "nah", because of uncertainty around UB. How much performance is being left on the table around the world because of similar thinking, driven by the existence of UB?

Maybe I was supposed to write OCaml or Pascal or Rust.

    cargo miri run

In the part about "abs", there's an assembly breakdown:

mov eax, edi

sar eax, 31

mov ecx, eax

add edi, ecx

xor eax, edi

Has this been generated by a C compiler? If yes, it's a bit puzzling, because can't you remove "mov ecx, eax", replace "add edi, ecx" by "add edi, eax" and have the exact same result?

The ARM instruction set used to make all instructions conditional to avoid the need for branching, but has now moved away from that since the branch prediction is so good nowadays.

I need something like this for a switch() command (technically a list of arbitrary functions). Sort of like up to N branches in one step.

The idea is to take some number of inputs A, B, C, ... and conceptually perform all of the possible functions simultaneously, then keep the one that's desired and throw the rest away. For any arbitrary logic. Ideally using fewer operations than all of that, but that's optional. Driven by one variable, it would look like:

  // branch version
  switch(var1)
  {
    case 1:
      var4 = var2 + var3;
      break;
    case 2:
      var4 = var2 - var3;
      break;
    case 3:
      var4 = var2 * var3;
      break;
    case 4:
      var4 = var2 / var3;
      break;
    // ...
    default:
      var4 = 0; // optional and arbitrary
      break;
  }
  
  // branchless version
  var4 = magic(var1, var2, var3);

I don't know how to do this outside of programmable hardware like an FPGA. The problem is that it's extremely challenging to write/solve the formulas that map ordinary arithmetic and bitwise functions to the larger set of functions.

So for now, I may just use a switch() command in a shader and let it figure out any reusable logic internally. I don't know if shaders have come far enough to allow that performantly, or if they end up just calculating everything and throwing away the paths not taken. Which would suggest that the max speed would be O(1/N) for the number of cases.

Does anyone know? Maybe truth tables? Or a SAT solver? I'm also not sure how this would work for floating point, but that's optional too.

Edit: I updated the cases to show how var1 controls the math performed on var2, var3 and var4.

    var4 = (var1==1)*(var2+var3) | (var1==2)*(var2-var3) | ...

Just so you know, the "return x < 0 ? -x : x;" compiles into

    abs_branch:
        mov     eax, edi
        neg     eax
        cmovs   eax, edi
        ret

on x64, and into

    abs_branch:
        srai    a5,a0,31
        xor     a0,a5,a0
        sub     a0,a0,a5
        ret

on RISC-V if you use a C compiler with a half-decent codegen. And "branchy" clamp() translates into

    clamp:
        cmp     edi, edx
        mov     eax, esi
        cmovle  edx, edi
        cmp     edi, esi
        cmovge  eax, edx
        ret

Seriously, the automatic transformation between ?: and if-then-else (in both directions) is quite well studied by now. And if you try to benchmark difference between branching and branchless implementations, please make sure that the branches you expect are actually there in the compiler's output.

This is just cutesy on CPUs, but is a big part of GPU programming.

Another interesting take is how GPUs handle branching (latest NVidia GPUs in particular - see the register interconnect and how they swap threads without saving registers).

Branchless programming tactics also avoid security issues around timing side channels leaking predicate bits, which is somewhat interesting.

Is cmov branchless, or just branching by another name?

Interesting article. I remember have solved a leetcode problem called "Trapping Rain Water" https://leetcode.com/problems/trapping-rain-water/descriptio...

On leetcode the "elegant" and fastest solution was something like this:

  class Solution {
  public:
    int trap(vector<int>& height) {
        int i = 1;
        int n = height.size();
        int j = n - 1;
        int leftmax = height[0];
        int rightmax = height[n - 1];
        int tw = 0;
        while (i <= j) {
            if (leftmax <= rightmax) {
                if (leftmax > height[i]) {
                    tw += leftmax - height[i];
                } else {
                    leftmax = height[i];
                }
                i++;
            } else {
                if (rightmax > height[j]) {
                    tw += rightmax - height[j];
                } else {
                    rightmax = height[j];
                }
                j--;
            }
        }
        return tw;
    }
  };

My solution was this:

  class Solution {
  public:
    int trap(const vector<int>& height) {
        int mx = 0;
        long long sum = 0;

        for (const auto h : height) {
            mx = max(mx, h);
            sum += mx - h;
        }

        int rMx = 0, h, i;

        for (i = height.size() - 1; (h = height[i]) != mx; --i) {
            rMx = max(h, rMx);
            sum += rMx;
        }

        return sum - (height.size() - 1 - i) * mx;
    }
  };

However, I compiled and run some benchmarks on my local machine, and it turned out while on average my solution was slower, but in the worst case it was beating that solultion. My solution was less sensitive to the random input and the degradation was far less dramatic, around 2x, while that solution degraded much much more. I also thought that it was probably caused by the fact that my solution seem to be more predictable for the CPU branch predictor than that one, despite that it iterates twice.

  class Solution:
    def trap(self, height: List[int]) -> int:
      l,r,s = [*accumulate(height,max),[*accumulate(height[::-1],max)],len(height)
      return sum(max(0, min(l[i], r[s-i-1])-height[i]) for i in range(s))

I kind of like branchless programming, because in SIMD programming, some of its concepts are directly borrowed from branchless techniques, for example using bit masks to represent which vector to enable scatter and gather for.

For example, I can give it an array A and a vector V and a mask which output another vector O, then if the specific position i in the bit mask is 1, then O[i] will pick this element from A[V[i]], otherwise just A[i].

In Python this may sound like [A[V[i]] if M[i] else V[i] for i in range(len(V))], so it is very branchy, but in SIMD this would just be a bunch of SIMD operations without branch!

Speaking of which, this is particularly informative about what "branchless programming" really are: https://en.m.wikipedia.org/wiki/Predication_(computer_archit...

If you want to learn about the ultimate form of branchless programming, check out Church encoding: https://en.m.wikipedia.org/wiki/Church_encoding and https://gautier.difolco.dev/2025-09/extreme-branchless-expr-...

I was an APL programmer for many years and I insisted on writing as much of my code as possible without branches. Fortunately, it was reasonably easy to do in that language, if sometimes resulting in very cryptic code

I’m a big advocate of branchless programming — keeping configurations to a minimum and maintaining as much linear flow as possible, with little to no cfg-driven branching.

Why? I once took over a massive statistics codebase with hundreds of configuration variables. That meant, in theory, upwards of 2^100 possible execution paths — a combinatorial explosion that turned testing into a nightmare. After I linearized the system, removing the exponential branching and reducing it to a straightforward flow, things became dramatically simpler. What had once taken years to stabilize, messy codebase, became easy to reason about and, in practice, guaranteed bug-free.

Some people dismissed the result as “monolithic,” which is a meaningless label if you think about it. Yes, the code did one thing and only one thing —- but it did that thing perfectly, every single time. It wasn’t pretending to be a bloated, half-tested “jack of all trades” statistics library with hidden modes and brittle edge cases.

I’m proud of writing branchless (or “monolithic” code if you prefer). To me, it’s a hallmark of programming maturity -- choosing correctness and clarity over endless configurability, complexity and hidden modes.

Shameless plug, but a while back, I implemented a "branchless" (I think it actually branches, but not in the usual sense) binary search in C. It was just a POC to see if 1) I could be clever enough with bitwise operators to do it and 2) someday write a SIMD binary search.

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

Some safety critical real time systems have strict time predictability requirements. This means that the whole loop should pass in exactly X microsecond, not more not less. For this, all the programming should be pretty much branchless.

For instance, all the sorting algorithm turn to, effectively, bubble sort since without branches, you always go with the worst case - and the sorting complexity is always the O(n^2). But it's okay, since the algorithm becomes predictable. You just swap a conditional swap:

    if a < b then swap(a, b)

with arithmetic swap:

    c = (a+b)/2
    d = |a-b|/2
    a = c + d 
    b = c - d

and that's it.

In the partition example isn’t the for loop condition a branch technically?