Branchless Programming with Python

Bonsai Tree

What is branchless programming, and how does it work? When we use statements like if, switches, conditional operators, and so on, if the CPU has more than one path it may follow, we have a branch. If there is an if statement, for example, the CPU anticipates (or better guesses) all potential code branching. By doing so, it wastes memory space for ones, and the CPU must flush the not-used route instructions after the execution of the supplied statement. And it’s a long process.

Output:

3
10

We can convert this piece of code into a branchless form, by the fact that a>b if True equals 1 else 0.

For the dry run, we choose to find out between 2 and 3 which one is greater.

return 2 * (2 > 3) + 3 * (2 <= 3)
return 2 * (0) + 3 * (1)
return 0 + 3
return 3

To show the generated byte code, you can use the disfunction from the sys module. Here is an example. I’ve omitted the function calls.

Output:

1073           0 LOAD_FAST                0 (a)
               2 LOAD_FAST                1 (b)
               4 COMPARE_OP               4 (>)
               6 POP_JUMP_IF_FALSE       12
1074           8 LOAD_FAST                0 (a)
              10 RETURN_VALUE
1076     >>   12 LOAD_FAST                1 (b)
              14 RETURN_VALUE
              16 LOAD_CONST               0 (None)
              18 RETURN_VALUE

And there we see the JUMP statement: 6 POP_JUMP_IF_FALSE 12. This indicates a branch: If FALSE, jump to 12. If not, continue.

Output:

1073           0 LOAD_FAST                0 (a)
               2 LOAD_FAST                0 (a)
               4 LOAD_FAST                1 (b)
               6 COMPARE_OP               4 (>)
               8 BINARY_MULTIPLY
              10 LOAD_FAST                1 (b)
              12 LOAD_FAST                0 (a)
              14 LOAD_FAST                1 (b)
              16 COMPARE_OP               1 (<=)
              18 BINARY_MULTIPLY
              20 BINARY_ADD
              22 RETURN_VALUE

The re-written program does not use branches anymore but the effect of the function is still the same!

What is the significance of this?

Writing branchless code can speed up the process. But we’re talking about fractions of a second here. If you’re doing anything in a loop and repeating it over and again, this might be intriguing. It is not important in “regular” day-to-day scripting. However, in intensive computational programmings, such as gaming or machine learning, it soon becomes a crucial factor. Especially if you have limited CPU and memory resources.

Data Science has a variety of sorting algorithms but the five most basic are here.

Check out my GitHub and Linkedin profile.