Branchless Programming: Difference between revisions

From David's Wiki
Line 43: Line 43:
</syntaxhighlight>
</syntaxhighlight>


==Multiplications==
==Booleans==
Multiplications by booleans can be used instead of switch statements.
Multiplications by booleans can be used instead of switch statements.


Line 60: Line 60:
x = x + 10 * y - 10 * (1-y)
x = x + 10 * y - 10 * (1-y)
</syntaxhighlight>
</syntaxhighlight>
Similarly, instead of doing
<syntaxhighlight>
if age > 10:
  x+=1
</syntaxhighlight>
you can just write <code>x += age>10</code>.


These are micro optimizations but they are sometimes useful for speeding up GPU shaders.
These are micro optimizations but they are sometimes useful for speeding up GPU shaders.

Revision as of 19:39, 16 November 2023

The idea of branchless programming is to avoid if and for statements.
Typically, these statements require the CPU to perform branch prediction. If the CPU predicts incorrectly, it will have to discard all pipelined results and go down the other route. Furthermore warps on GPUs must all go through both branches if there are threads which go down each branch.

In general, I consider avoiding if statements to be a micro-optimization. You should just use if statements wherever the optimized alternative is less readable. Typically, this is fine for CPUs which are good at branch prediction.

Below are a few tricks to avoiding branches and if statements. In general, I would not refractor to improve performance through these micro-optimizations, only to improve readability.

Switch Statements

Technically, switch statements are still branches. However, they can lead to a negligible performance gains if there are lots of cases.
Only convert if statements to switch statements when they are significantly more readable in your scenario.

Polymorphism

Rather than do

def speak():
  if self.type == "bird":
    print("Chirp")
  elif self.type == "cat":
    print("Meow")

create separate classes for bird and cat each overriding the speak method.

Hash Maps

This is one way to simulate switch statements. Technically these do not have branching but will have a memory read which could be just as slow as a single branch.

# Cache the following at the start of your program or in the constructor
# Assume we have some functions batch_norm(), group_norm()
my_cache = {
  "batch_norm": batch_norm,
  "group_norm": group_norm,
  "identity": identity
}

# At runtime, you can do:
x = my_cache[operation](x)

Booleans

Multiplications by booleans can be used instead of switch statements.

Rather than doing

if age > 10:
  x = x + 10
else:
  x = x - 10

you can do

x = x + (20 * (age > 10) - 10)
# or
y = age > 10
x = x + 10 * y - 10 * (1-y)

Similarly, instead of doing

if age > 10:
  x+=1

you can just write x += age>10.

These are micro optimizations but they are sometimes useful for speeding up GPU shaders.

Resources