Branch Optimization

Branch Optimization

---

Prerequisites

---

1. Branch Optimization

Modern CPUs use branch prediction to guess the next execution path.

👉 If prediction is correct → fast
👉 If prediction fails → pipeline flush → huge performance penalty

A mispredicted branch can cost 10~20+ cycles

1. Can this branch be removed?
2. If not, can it be made predictable?
3. Can it be converted to branchless logic?

2. Methods of Branch Optimization

2-1. Branch Minimization

❌ Branch-heavy code

if (x > 0) 
    sum += x;

if (x > y) 
    result = a;
else 
    result = b;

• Branch may be unpredictable
• Causes pipeline stalls

✔ Branchless version

sum += (x > 0) * x;

• (x > 0) → 0 or 1
• Eliminates branch

int flag = (x > y);  // 0 or 1
result = flag * a + (1 - flag) * b;

• No branch misprediction
• Better SIMD/vectorization
• Stable performance

Condition	Recommendation
Unpredictable branch	Use branchless
Tight loop	Prefer branchless
SIMD/vectorization	Required

2-2. Make it predictable on Branch

if (likely(x > 0))
{
    // hot path
}

Compilers may optimize based on probability

// ✔ Better
if (x == 0) 
{
    // common case
} 
else {
    // rare case
}

❌ Bad ordering

if (x != 0) 
{
    // rare case
} 
else 
{
    // common case
}