Branchless programming

Branchless programming is a programming technique in which the program always runs the same commands in the same order. Practical uses for branchless programming consists of : code that needs to deal with unpredictable data, GPU programming, SIMD, constant-time code for cryptography; (esoteric uses) and languages which are so bad at conditionals that branchless programming is far easier.

Branchless programming often utilizes predication which Wikipedia defines as "predication is a feature that provides an alternative to conditional transfer of control, as implemented by conditional branch machine instructions" . Which means logic controls the state of the program rather than modification of an instruction pointer.

Programming without branches

There are many ways to program without branches. This section lists many of them. You can even combine these to get more advanced branchless logic.

Boolean logic

Boolean logic is inherently branchless as there is no instruction pointer. Things are just executed.

Bitwise logic

Bitwise logic is used in many places in the real world to create branchless programming as it is an optimization in compilers and can save on time when predictive branching fails.

Mathematic logic

Math can also be used to preform tasks without branching. As an example here is an equality statement without the use of the equals sign or any conditionals.

diff = a - b
is_equal = 1 - (2 * diff * diff) // (diff * diff + 1)

However, this implementation assumes division by zero equals 0.

That is just one example. There are many other things you can do with plain math, such as extracting digits, getting the length of integers and more.

Branchless Paradigm

The branchless paradigm is when an entire program is written using branchless programming making use of no statements to control program flow. This can be because a programming language constricts a user in such a way that this is the only way to write a program or in another case where the programmer simply wants to do it that way.

An example of the paradigm

A famous example of something that is branchless is the Cyclic tag system. This is because it runs instructions one after another. Things are only appended when an input bit is read in as a one. The bits do not change the order the rules are applied so it is branchless.

Nuances with the paradigm

There are things to note when trying to define the branchless paradigm. A gray area arises when we try to define such a paradigm. There are things that are clearly branchless but making a fitting definition for it is not the simplest solution

State machines encoded branchlessly

You can encode state machines in a branchless manner.

while(true) 
{ 
    A if x == 1; 
    B if x == 1; 
    C if X == 1; 
    D if X == 2; 
    E if X == 2; 
    F if X == 2; 
    G if X == 3; 
    … 
} 

Now this raises an argument, should this count as branchless or not? These are all predicates and all instructions are ran in order. But this obviously is branching because it mimics a state machine at the same time.

Angelic non-deterministic Turing machines are branchless

Angelic non-deterministic Turing machines are branchless because they simulate every path and only pick one that actually works. This logic can also be brought into quantum physics to say that quantum physics is also branchless.

See more

• Branchless Algorithms