C++ Low-Latency Optimization: Mastering CPU Cache for Real Performance Gains

What CPU Cache Actually Does

CPU cache is high-speed memory integrated on the chip. Typical access latencies: L1 ~1 ns, L2 ~4 ns, L3 ~12 ns, main memory 60–100 ns. The cache hierarchy serves data from the fastest level first, falling back to slower levels on misses. Data moves in 64-byte cache lines. Cache effectiveness relies on two locality principles:

Temporal locality – recently accessed data is likely accessed again soon (e.g., loop variables, hot constants).

Spatial locality – accessing an address makes nearby addresses likely to be accessed next. Sequential array traversal exploits this because a single cache line loads 64 contiguous bytes.

Optimization means leveraging both localities so each 64-byte line brings data that will be used shortly. Random or strided access destroys locality, causing frequent main-memory round trips and order-of-magnitude slowdowns.

Case Studies: Common Cache Killers

Case 1: Row-Major vs Column-Major Traversal

C/C++ stores 2D arrays in row-major order: m[0][0], m[0][1], …, m[0][N-1], m[1][0]…. Row-wise iteration walks contiguous memory; column-wise jumps by a full row each step, thrashing the cache.

#include <chrono>
#include <cstdio>
#include <vector>

int main() {
    const int N = 4096;
    std::vector<std::vector<double>> m(N, std::vector<double>(N, 1.0));
    volatile double sink = 0;

    auto t0 = std::chrono::steady_clock::now();
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c) sink += m[r][c]; // row-major
    auto t1 = std::chrono::steady_clock::now();

    auto t2 = std::chrono::steady_clock::now();
    for (int c = 0; c < N; ++c)
        for (int r = 0; r < N; ++r) sink += m[r][c]; // column-major
    auto t3 = std::chrono::steady_clock::now();

    std::printf("row %.4f s | col %.4f s
",
        std::chrono::duration<double>(t1 - t0).count(),
        std::chrono::duration<double>(t3 - t2).count());
    return (int)sink;
}

Result (g++ -O2, 2 cores):

row 0.0640 s | col 0.1024 s   // column / row ≈ 1.6×

For larger matrices exceeding L3, the gap widens. The volatile sink prevents the compiler from optimizing away the memory accesses.

Rule: make the innermost loop stride the smallest so it follows contiguous memory.

Case 2: std::vector vs std::list – Same “Sequential” Access, 4.8× Difference

std::vector

elements are contiguous; std::list nodes are individually allocated and scattered. Traversing a list forces a pointer dereference per element, almost always missing cache.

#include <chrono>
#include <cstdio>
#include <vector>
#include <list>

int main() {
    const int N = 10000000;
    std::vector<int> v; v.reserve(N);
    for (int i = 0; i < N; ++i) v.push_back(i);

    std::list<int> l;
    for (int i = 0; i < N; ++i) l.push_back(i);

    volatile long long sink = 0;
    auto t0 = std::chrono::steady_clock::now();
    for (int x : v) sink += x;
    auto t1 = std::chrono::steady_clock::now();
    auto t2 = std::chrono::steady_clock::now();
    for (int x : l) sink += x;
    auto t3 = std::chrono::steady_clock::now();

    std::printf("vector %.4f s | list %.4f s
",
        std::chrono::duration<double>(t1 - t0).count(),
        std::chrono::duration<double>(t3 - t2).count());
    return (int)sink;
}

Result:

vector 0.0157 s | list 0.0752 s   // list / vector ≈ 4.8×

Default to std::vector; use linked structures only when frequent middle insert/delete is required. Similarly, std::map / std::set (red-black trees) scatter nodes – prefer sorted arrays or hash tables for hot traversal.

Case 3: False Sharing – Two Threads, Different Variables, 7× Slowdown

When two threads modify different variables that happen to share a 64-byte cache line, each write invalidates the line in the other core’s cache, causing ping-pong traffic.

#include <chrono>
#include <cstdio>
#include <thread>

struct FS { volatile long long a, b; };          // adjacent, same cache line
struct PS { volatile long long a; char pad[64]; volatile long long b; }; // separated

int main() {
    const int ITERS = 500000000;

    FS fs;
    auto t0 = std::chrono::steady_clock::now();
    std::thread t1([&]{ for (int i=0;i<ITERS;++i) fs.a += 1; });
    std::thread t2([&]{ for (int i=0;i<ITERS;++i) fs.b += 1; });
    t1.join(); t2.join();
    auto t1e = std::chrono::steady_clock::now();

    PS ps;
    auto t2s = std::chrono::steady_clock::now();
    std::thread t3([&]{ for (int i=0;i<ITERS;++i) ps.a += 1; });
    std::thread t4([&]{ for (int i=0;i<ITERS;++i) ps.b += 1; });
    t3.join(); t4.join();
    auto t2e = std::chrono::steady_clock::now();

    std::printf("adjacent %.4f s | padded %.4f s
",
        std::chrono::duration<double>(t1e - t0).count(),
        std::chrono::duration<double>(t2e - t2s).count());
    return 0;
}

Result (g++ -O2 -pthread, 2 cores):

adjacent 0.9850 s | padded 0.1416 s   // adjacent / padded ≈ 7.0×

Fix: place frequently written fields on separate cache lines using alignas(64) or padding (e.g., char pad[64] ), or put hot fields in independent structs.

Practical C++ Optimization Patterns

(1) Pack Struct Fields by Access Frequency

Group hot fields together; avoid interleaving cold fields between them, which bloats the struct and reduces how many objects fit in a cache line.

// Bad: cold fields split hot ones, larger struct
struct Bad { char name[32]; double price; bool active; long long id; };

// Good: hot fields (id, price) contiguous at front
struct Good { long long id; double price; bool active; char name[32]; };

Good

achieves higher cache-line utilization when iterating over many objects.

(2) AoS → SoA (Array of Structures → Structure of Arrays)

If a loop only touches one field (e.g., all particles’ x), AoS drags unused fields ( y, z) into cache. SoA stores each field in its own contiguous array.

// AoS: traversing x pulls y,z along
struct Particle { float x, y, z; };
std::vector<Particle> particles;

// SoA: x, y, z each contiguous – scanning x is optimal
struct ParticleField { std::vector<float> x, y, z; };
ParticleField field;

SoA can yield multi-fold cache-hit improvements for single-field scans.

(3) Manual Prefetch with __builtin_prefetch

When access stride is regular but large, hardware prefetchers may lag. Insert explicit prefetch hints:

for (int i = 0; i < n; i += step) {
    __builtin_prefetch(&data[i + next_step]);
    process(data[i]);
}

Prefetch distance must match memory latency (typically a few iterations ahead). Misuse pollutes cache; treat as last resort after layout changes.

(4) Eliminate Pointer Chasing

Linked lists, tree nodes, and virtual-call chains force dependent loads that defeat spatial locality and hardware prefetch. Replace with contiguous arrays + indices.

// Anti-pattern: scattered heap nodes
struct NodeLinked { int data; NodeLinked* next; };

// Better: flat array + index
struct NodeFlat { int data; uint32_t next_idx; };

class FlatList {
public:
    std::vector<NodeFlat> nodes;
    uint32_t head_idx = UINT32_MAX;
    void push(int val) {
        nodes.push_back({val, head_idx});
        head_idx = static_cast<uint32_t>(nodes.size() - 1);
    }
};

All nodes reside in one contiguous vector; next_idx is an offset, not a pointer. The CPU prefetcher can pull subsequent nodes, drastically reducing cache misses.

Virtual functions aren’t forbidden – cold paths tolerate the indirection. std::variant::visit introduces branches; branch misprediction also costs cycles.

(5) Object Pools / Small-Object Buckets

High-frequency allocate/destroy of small objects benefits from a pool that keeps memory contiguous. Prefer LIFO (stack) discipline so the most recently freed object is reused next, preserving locality.

#include <vector>
#include <cstddef>
#include <cassert>

template <typename T, size_t CAP = 1024>
class LifoObjectPool {
public:
    LifoObjectPool() { storage.reserve(CAP); }

    T* alloc() {
        if (!free_stack.empty()) {
            T* p = free_stack.back();
            free_stack.pop_back();
            return p;
        }
        storage.emplace_back();
        return &storage.back();
    }

    void free(T* p) {
        assert(p >= &storage[0] && p <= &storage.back());
        p->~T();
        free_stack.push_back(p);
    }

private:
    std::vector<T> storage;
    std::vector<T*> free_stack;
};

struct Session { uint64_t id; };
void demo() {
    LifoObjectPool<Session> pool;
    Session* s1 = pool.alloc();
    s1->id = 1001;
    pool.free(s1);
    Session* s2 = pool.alloc(); // reuses s1’s address – cache friendly
}

The underlying vector provides contiguous storage; the LIFO free_stack ensures recently freed slots are reused first. No delete returns memory to the heap, avoiding fragmentation and cache pollution.

Ordinary free-list pools that reuse randomly degrade locality. Bucket allocators mainly reduce lock contention and fragmentation, not inherently cache-friendly. Profile with perf before hand-rolling a pool.

Verify with Data, Not Gut Feeling

Cache optimization’s first principle: keep data close to the CPU, maximize cache hits . Measure, don’t guess.

# Count cache misses
perf stat -e cache-misses,cache-references ./your_program

// Or use RDTSC for per-operation cycles
static inline uint64_t rdtsc() {
    unsigned int lo, hi;
    __asm__ __volatile__("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | lo;
}

Baseline first, then optimize, then re-run. If cache-misses drops and latency drops with it, the optimization hit the mark. If unchanged, the bottleneck lies elsewhere – don’t waste effort.

In practice: make access sequential, iterate in memory order, prefer std::vector; colocate data used together – order struct fields by frequency, switch to SoA for single-field scans; isolate per-thread writes with alignment/padding to kill false sharing; always quantify with perf. Next time code “looks fine but runs 5× slower,” check whether the data is actually in cache.