CPU Cache and Branch Prediction in C++ Data Structures

Modern high-performance C++ applications are increasingly bottlenecked by hardware microarchitecture rather than raw algorithmic complexity. This article explores how CPU instruction caches (I-cache) and branch target buffers (BTB) dictate data structure design in C++. By examining the hidden costs of dynamic dispatch, code bloating, and unpredictable control flow, we demonstrate why traditional object-oriented structures are often replaced by data-oriented paradigms, compile-time polymorphism, and contiguous memory layouts to maximize hardware throughput.

The Hardware Reality: I-Cache and Branch Targets

Processors execute code via deep pipelines. To maintain execution speed, the CPU relies on two critical instruction-side mechanisms:

1. Instruction Cache (L1i): A dedicated, high-speed on-chip cache (typically 32 KB to 64 KB per core) that stores frequently executed machine instructions. If a loop’s code footprint exceeds L1i capacity, the CPU stalls while fetching instructions from slower L2/L3 caches or main memory.
2. Branch Target Buffer (BTB): A specialized cache used by the branch prediction unit to predict the destination address of indirect jumps and calls before they are executed.

When a branch target cannot be predicted—or when instructions must continually be fetched from distant memory—the processor pipeline stalls, incurring penalties ranging from 15 to 20 clock cycles per misprediction.

Why Traditional Polymorphism Degrades Instruction Locality

Classic object-oriented design in C++ relies on dynamic dispatch:

struct Entity {
    virtual void update() = 0;
};

void updateAll(const std::vector<Entity*>& entities) {
    for (auto* e : entities) {
        e->update(); // Indirect branch via vtable pointer
    }
}

This pattern creates two severe instruction-side issues:

• Indirect Branch Mispredictions: Calling e->update() requires dereferencing the object’s vptr to access the vtable, then jumping to the resolved function address. If entities contains a heterogeneous mix of derived classes (e.g., Monster, Projectile, Player), the target address changes continuously. The BTB fails to establish a consistent pattern, causing frequent branch mispredictions.
• I-Cache Thrashing: Each derived class executes a completely different block of machine code. Iterating through varied objects pulls distinct function implementations into the L1i cache, evicting the instructions of the previous class. The CPU spends significant cycles loading code rather than executing work.

C++ Design Adaptations for Instruction Locality

To mitigate branch target penalties and instruction cache misses, modern C++ designs favor architectures that preserve predictable execution paths and compact instruction footprints.

1. Entity Component Systems (ECS) and Type-Sorted Arrays

Instead of storing heterogeneous pointers in a single container, data is grouped by concrete type:

struct World {
    std::vector<TransformComponent> transforms;
    std::vector<PhysicsComponent> physics;
};

By processing one array of identical types at a time, the CPU runs the exact same instruction sequence thousands of times in a tight loop. The instructions remain resident in L1i, and branch targets remain completely static, eliminating BTB pressure.

2. Static Polymorphism via Concepts and CRTP

When polymorphism is required, moving it from runtime to compile time eliminates indirect branches:

template <typename T>
void updateEntity(T& entity) {
    entity.update(); // Direct call, resolved at compile time
}

The Curiously Recurring Template Pattern (CRTP) and C++20 Concepts enable inlining. The compiler substitutes direct function jumps or inlines the body entirely into the call site, converting indirect pointer lookups into deterministic, zero-overhead instructions.

3. Variant Collections with Sorting

When heterogeneity is mandatory, std::variant paired with std::visit provides a value-semantic alternative to class hierarchies. However, naive visitation inside a loop still causes indirect branches via jump tables:

std::vector<std::variant<Warrior, Mage, Rogue>> party;

// Problematic: BTB misses if types are randomly distributed
for (auto& member : party) {
    std::visit([](auto& character) { character.act(); }, member);
}

To eliminate branch misses, the data structure is sorted by the variant's active index prior to execution:

std::sort(party.begin(), party.end(), [](const auto& a, const auto& b) {
    return a.index() < b.index();
});

Sorting groups identical variants together. The branch predictor encounters the same jump target consecutively for dozens or hundreds of iterations, reducing misprediction rates to near zero.

4. Structure-of-Arrays (SoA) for Control Flow Reduction

Conditional logic inside tight loops strains the branch predictor:

// Array of Structures (AoS)
struct Particle {
    float x, y, z;
    bool isActive;
};

If isActive is checked per particle, an unpredictable distribution stalls the pipeline. Refactoring into a Structure-of-Arrays isolates the active members:

struct ParticleSystem {
    std::vector<float> posX, posY, posZ;
    size_t activeCount; // Only active particles are stored up to activeCount
};

By reorganizing data so that inactive elements are partitioned out, the updating loop runs without conditional checks. Eliminating branches entirely removes the need for BTB evaluation and keeps the machine code minimal and cache-friendly.

Summary of Architectural Guidelines