liveBook · Manning

Branch prediction

As explained in High Performance Unity Game Development

Branch prediction is processor hardware behavior that predicts the outcome of a conditional branch before it is resolved.

When a CPU reaches a conditional branch, it may predict which path to take before the condition is ready. A wrong prediction makes it discard work from the incorrect path and restart, costing performance. section 11.0

Predictable results are easier to predict than random ones, but a branch can still slow a loop even when its pattern is simple. Measure on the target device rather than assuming fewer calculations or an easy pattern will make code faster. section 11.0

Alive and dead enemies

Checking an alive flag for every enemy adds a branch whose result may become unpredictable as enemies die and respawn. Keeping alive and dead enemy indices in separate arrays avoids that per-enemy check, but the change should be guided by performance needs. section 6.1.5 section 11.7

Listing 11.4 Branch modulo test
using System;
using TMPro;
using UnityEngine;
 
public class BranchTest : MonoBehaviour
{
    public TextMeshProUGUI ResultText; #A
 
    public int NumIterations = 1000000; #B
    public int ArraySize = 4096; #C
 
    public int[] Array; #D
    public bool[] Mod2Array; #E
    public bool[] RandomArray; #F
 
    void Start()
    {
        Array = new int[ArraySize];
        Mod2Array = new bool[ArraySize];
        RandomArray = new bool[ArraySize];
 
        for (int i = 0; i < ArraySize; i++)
        {
            Array[i] = i; #G
            Mod2Array[i] = i % 2 != 0; #H
            RandomArray[i] = UnityEngine.Random.value > 0.5f; #I
        }
    }
 
    public void RunTest()
    {
        int result = branchTest(); #J
        Debug.Log("Result: " + result);
    }
 
    int branchTest()
    {
        int value = 0;
 
        double arrayTimeMod2 = 0.0d;
        double arrayTimeRandom = 0.0d;
 
        double time = 0.0d;
 
        for (int t = 0; t < NumIterations; t++)
        {
            time = Time.realtimeSinceStartupAsDouble;
            for (int i = 0; i < ArraySize; i++)
            {
                if (Mod2Array[i]) #K
                    value += Array[i];
                else
                    value += Array[i];
            }
            arrayTimeMod2 += Time.realtimeSinceStartupAsDouble - time;
 
 
            time = Time.realtimeSinceStartupAsDouble;
            for (int i = 0; i < ArraySize; i++)
            {
                if (RandomArray[i]) #L
                    value += Array[i];
                else
                    value += Array[i];
            }
            arrayTimeRandom += Time.realtimeSinceStartupAsDouble - time;
 
            GC.Collect(); GC.WaitForPendingFinalizers(); GC.Collect();
        }
 
        ResultText.text = "";
 
        ResultText.text += "True,False result: " + 
                           arrayTimeMod2.ToString("F4") + " seconds\n";
        ResultText.text += "Random result: " + 
                           arrayTimeRandom.ToString("F4") + " seconds\n";
 
        return value;
    }
}

Compare branch tests using alternating and random Boolean patterns while doing the same work for either result; measured results vary by device. section 11.1

How High Performance Unity Game Development covers it

How deep it goes
Explains pipeline flushing and compares branch patterns, while deferring CPU-specific prediction implementations.
Examples
Compares an unbranched loop with a simple conditional loop, alternating and random branch tests, and alive-enemy checks.
What you can do after
Evaluate branch costs by comparing predictable and unpredictable patterns on a target device.
How it connects
Connects conditional branches to CPU pipelines, branch misprediction, branchless programming, and data-oriented enemy storage.

Also explained in

Compare how 4 books explain branch prediction →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of High Performance Unity Game Development. The section links point to the parts of the book it draws on.