The Weird Concept of Branchless Programming

Summary

home blogs about THE WEIRD CONCEPT OF 'BRANCHLESS PROGRAMMING'2025-07-08 01:37 • 19+ min read • #c #branchlessDISCLAIMERSIf you came for readable code, sorry, branchless programming is basically code golf with caffeine.Code examples are going to be ran in C code.Drastic measures (e.g. -O3 -ffast-math -march=native -fomit-this-entire-function) were taken.0×00 FUNKY INTRODUCTIONModern CPUs are predictive creatures. They guess what you're about to do, like a nosy algorithm trying to sell you sneakers after you Googled "foot pain." Branch predictors make CPUs fast by speculating on branches... until they guess wrong and everything grinds to a halt for 15,20 cycles.Branchless programming is how we get around this: we rewrite our code to not branch at all. Instead of jumping to conclusions, we manipulate bits like 1980s assembly gremlins.WHAT IS A BRANCHWhat is a branch first of all?In a program, you may observe parts like this:if (condition), then ... elif (condition), then ... else ... fi This block of instructions is a collection of three branches. Each if, elif, and else represents a possible execution path the CPU can take depending on the evaluation of the conditions. At runtime, only one of these paths is taken, and the others are skipped. This choice , this deviation in the control flow , is what we call a branch.In terms of machine code, a branch is often implemented as a jump (jmp, je, jne, etc.). These are instructions that tell the CPU: “if this condition holds, skip to label X; otherwise, keep going.” That jump disrupts the nice linear stream of instruction execution, forcing the CPU to guess where you’re going next.Here’s a simple ASCII representation of how this decision tree looks: [Condition A] | +-----+------+ Yes No | | [Block A] [Condition B] | +-----+------+ Yes No | | [Block B] [Block C] From a CPU perspective, each conditional check and potential jump is a “fork in the road.” If your code has a predictable pattern (e.g., always taking the same branc...