CPU caches and data-oriented design in C++

Why memory access patterns decide how fast code runs, what cache lines are, and how contiguous containers and structs of arrays speed up hot loops.

A processor can add two numbers in well under a nanosecond, but fetching a value from main memory takes around 100. Small, fast caches close to each core hide that gap, and they move memory in fixed blocks called cache lines: 64 bytes on x86 and most ARM chips. Read one int and its neighbors come along for free; processors also prefetch the next lines when you walk memory in order.

• Contiguous containers win. A std::vector keeps elements side by side; a std::list or std::map scatters nodes across the heap, so walking one is a chain of cache misses. A vector often beats a list even where Big-O favors the list.
• Loop in storage order. A 2D array is stored row by row, so the inner loop should walk along a row. Summing a large grid column by column can be ten times slower or more than row by row.
• Struct of arrays (one array per field) beats an array of structs when hot loops touch only a few fields of many objects, because every byte loaded is used. That's the core idea of data-oriented design.
• False sharing: two threads writing different variables in the same cache line slow each other down. Give such data its own line with alignas(64).

Caches make performance hard to guess, so measure before and after with a profiler.

Example

#include <iostream>
#include <set>

int main() {
    // Which 64-byte cache lines do the reads touch? Row by row vs column by column,
    // over an 8 x 16 grid of 4-byte ints stored row by row.
    const int rows = 8, cols = 16, line = 64;
    std::set<int> first4_row, first4_col;
    for (int k = 0; k < 4; k++) {
        first4_row.insert((0 * cols + k) * 4 / line);   // walk along row 0
        first4_col.insert((k * cols + 0) * 4 / line);   // walk down column 0
    }
    std::cout << "4 reads along a row touch " << first4_row.size() << " line(s)\n";
    std::cout << "4 reads down a column touch " << first4_col.size() << " line(s)\n";
    std::cout << "the whole grid is " << rows * cols * 4 / line << " lines\n";
    return 0;
}

Output:

4 reads along a row touch 1 line(s)
4 reads down a column touch 4 line(s)
the whole grid is 8 lines

Practice it

• Lesson: Performance and the machine