Skip to content
Tutorials Center
My learning

Topics

Lesson 152 of 171 ยท Modern C++ and Beyond

Cache-Friendly Code

Learn why memory layout often matters more than instructions. Understand CPU caches and cache lines, spatial and temporal locality, array of structs versus struct of arrays, and hot/cold splitting.

Two loops can do exactly the same arithmetic and differ in speed by a factor of ten or more. The difference is rarely the arithmetic. It is how far the processor must reach into memory to fetch the numbers. A modern CPU can perform several operations per nanosecond, but fetching a value from main memory takes on the order of 100 nanoseconds. That is hundreds of operations' worth of waiting. Most programs are not limited by how fast the CPU computes. They are limited by how fast data arrives.

CPUs hide this delay with caches: small, fast memories that hold recently used data. Code that uses the cache well runs fast; code that fights it stalls. In this lesson you will learn how caches work, what locality means, and how data-oriented design arranges data to fit the cache: the contrast between array of structs (AoS) and struct of arrays (SoA), traversal order, and splitting hot and cold data. You will run a small cache simulator, so every number printed here is exact and repeatable. This lesson builds on Memory Layout, Vectors and Writing Fast C++.

The memory hierarchy

flowchart TD
    R["Registers<br/>about 1 cycle"] --> L1["L1 cache (about 32 KB)<br/>about 4 cycles"]
    L1 --> L2["L2 cache (256 KB to 2 MB)<br/>about 12 cycles"]
    L2 --> L3["L3 cache (several MB, shared)<br/>about 40 cycles"]
    L3 --> RAM["Main memory (GBs)<br/>about 200+ cycles"]

Each level is larger and slower than the one above. The numbers are typical orders of magnitude, not exact values for any one CPU.

When your program reads an address, the CPU looks in L1 first, then L2, then L3, then RAM. A hit in L1 is almost free; a trip to RAM can cost 50 times more. The CPU does not fetch single bytes. It transfers whole cache lines, which are 64 bytes on virtually all modern x86 and ARM processors. Read one int, and the 15 neighbors in the same 64-byte line arrive for free.

Two consequences follow:

  • Spatial locality: if you use an address, you will probably use nearby addresses soon. Data that is stored together and used together is cheap.
  • Temporal locality: if you use an address, you will probably use it again soon. Keep a working set small enough to stay in the cache.

The hardware also has a prefetcher that notices sequential access and fetches the next lines before you ask. Contiguous arrays, which a std::vector is, play to all of these strengths. A linked list, where each node is a separate allocation, plays to none of them.

Arrays of structs and structs of arrays

Suppose you simulate particles. The natural way to write it is a struct per particle and a vector of them:

C++
struct Particle {
    float x, y, z;
    float vx, vy, vz;
    int id;
    bool alive;
};
std::vector<Particle> particles;   // array of structs (AoS)

Now a pass that needs only x for every particle (say, to find the leftmost one). Each Particle takes 32 bytes after padding, so one cache line holds two particles, yet the loop wants only 4 of each 32 bytes. Seven eighths of every line it loads is wasted.

The alternative stores each field in its own array:

C++
struct Particles {                  // struct of arrays (SoA)
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<int> id;
    std::vector<bool> alive;        // or std::vector<char>
};

A pass over x now reads only x values, 16 per cache line, with no waste.

flowchart LR
    subgraph aos["AoS: one particle after another"]
        A1["x y z vx vy vz id alive"] --- A2["x y z vx vy vz id alive"] --- A3["x y z ..."]
    end
    subgraph soa["SoA: one field after another"]
        S1["x x x x x x x x ..."]
        S2["y y y y y y y y ..."]
        S3["vx vx vx vx vx vx ..."]
    end

A loop over only x touches every cache line in AoS but only the first row in SoA.

You can count the effect exactly. The program below places both layouts at 64-byte-aligned addresses and counts how many distinct cache lines a pass over x touches:

C++ Counting cache lines: AoS versus SoA

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

For a pass that only needs x, SoA moves about eight times less memory. That ratio is also roughly the speed-up you can expect once the data no longer fits in the cache, plus more, because SoA data lets the compiler use SIMD instructions (several floats per instruction) on a contiguous array, as discussed in Compiler Flags and Optimization.

When AoS is the better choice

SoA is not always better. If a loop uses all the fields of each element, as in "update position from velocity", the AoS layout brings in everything you need with one line fetch, while SoA must stream from several arrays at once. AoS is also simpler: one object, one index, easy to insert, remove and pass around. Choose by looking at how the data is accessed:

Access pattern Better layout
Loops touch one or two fields of many elements SoA
Loops use every field of one element at a time AoS
Only some fields are used together Group them (AoSoA or hot/cold split)
Elements are added and removed constantly in the middle AoS or handles, with care

The method of arranging data around its use rather than around real-world objects is called data-oriented design. Ask "what does this loop read and write?" before asking "what is this thing?".

Traversal order matters

Two-dimensional arrays in C++ are stored row-major: m[r][c] and m[r][c + 1] are adjacent. Visiting in storage order is sequential. Visiting down a column jumps by a whole row each time:

C++
for (int r = 0; r < rows; ++r)
    for (int c = 0; c < cols; ++c)
        sum += m[r][c];       // fast: walks memory in order

for (int c = 0; c < cols; ++c)
    for (int r = 0; r < rows; ++r)
        sum += m[r][c];       // slow: stride = one whole row

To make the cost measurable without a stopwatch (whose result changes on every run), the next program simulates a small cache: 256 lines of 64 bytes, which is 16 KB, with least-recently-used replacement. It feeds the cache the addresses each loop would use for a 512 by 512 matrix of int:

C++ A tiny cache simulator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Row by row, each 64-byte line holds 16 ints, so 1 access in 16 misses (6.25%). Column by column, each access lands on a different line, and a pass down one column touches 512 distinct lines, more than the 256 the cache can hold. By the time the loop moves to the next column, the lines it needs have been evicted, so every access misses. This is exactly why matrix code and image processing loops put the column index in the innermost loop. Real caches are set-associative and have several levels, so absolute numbers differ, but the pattern is the same.

Hot and cold data

Not every field is used on every pass. A game object might have a position that is updated every frame and a name and a description that are read once a minute. If both live in the same struct, the cold data dilutes every cache line the hot loop reads. Split them:

C++
struct EnemyHot  { float x, y; float health; int state; };   // 16 bytes, used every frame
struct EnemyCold { std::string name; std::string description; int lootTableId; };

std::vector<EnemyHot>  hot;     // dense, scanned each frame
std::vector<EnemyCold> cold;    // same index as hot[i], rarely touched

The same reasoning drives these habits:

  • Reorder members from largest to smallest so padding shrinks (the layout rules are in Memory Layout).
  • Use smaller types when the range allows: a state enum as std::uint8_t, an index as std::uint32_t instead of a 64-bit pointer.
  • Replace pointers with indexes into a contiguous array. Pointers are 8 bytes and point anywhere; indexes are smaller and keep neighbors together.
  • Prefer contiguous containers. std::vector and std::array beat std::list and node-based std::map for iteration, often by a wide margin, even when the big-O cost says otherwise. See Deque and List and Unordered Map for the trade-offs.
  • Avoid chasing pointers in hot loops. A std::vector<std::unique_ptr<Shape>> means every element is a separate allocation and a likely cache miss; storing shapes by value, grouped by type, is faster when you can.

One last trap: false sharing

When two threads write to two variables that happen to share a cache line, the cores keep invalidating each other's copy of the line, and the threads slow down even though they never touch the same variable. This is false sharing. The fix is to pad or align hot per-thread data to its own line:

C++
struct alignas(64) PerThreadCounter {
    std::uint64_t value = 0;     // sits alone in its own 64-byte line
};
std::vector<PerThreadCounter> counters(thread_count);

The standard offers std::hardware_destructive_interference_size in <new> for the line size, though many projects simply write 64. More on threads in Threads and Atomics.

Measure before you change

Layout changes can make a program faster and harder to read. Before you restructure anything:

  1. Profile. Find the loops that actually dominate the run time (perf, Visual Studio profiler, Instruments, VTune). Cache-miss counters (perf stat -e cache-misses) show whether memory is the real bottleneck.
  2. Benchmark in a realistic size. Layout effects appear only when the data is bigger than the cache. A test with 100 elements tells you nothing. Use a benchmark library or the loops from Writing Fast C++, and run each version several times.
  3. Simulate when you want to understand. Tools such as Cachegrind (valgrind --tool=cachegrind) count simulated misses, the same idea as the model above.
  4. Change one thing at a time, and keep the simpler code unless the numbers justify the complex one.

Do not give up readable code for a guess. The big wins usually come from a small number of loops over large arrays. Everywhere else, clear code is the better choice.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the size of a cache line on most modern x86 and ARM CPUs?

    Memory moves between cache levels in 64-byte lines. Reading one int brings in its neighbors too.
  2. 2. A loop reads only the x field of one million 32-byte Particle structs stored in a std::vector. Why is this slower than reading a std::vector<float> of the same x values?

    The loop needs 4 of every 32 bytes. The other 28 bytes are loaded in the same cache lines and thrown away, wasting memory bandwidth.
  3. 3. Why is traversing a row-major 2D array column by column slow for large arrays?

    Elements of one column are a row apart in memory. A pass over a column touches more lines than the cache holds, so each access is a miss.
  4. 4. When can an array of structs be the better layout than a struct of arrays?

    If every field is needed, one cache line fetch of the struct brings in everything. SoA would have to stream from several arrays at once.
  5. 5. What is false sharing?

    Cores keep invalidating each other's copy of the shared line even though the variables are distinct. Aligning each hot variable to its own 64-byte line fixes it.

Summary

  • CPUs are far faster than main memory. Caches bridge the gap by storing recently used 64-byte cache lines.
  • Spatial locality (using neighbors) and temporal locality (reusing data soon) are what make code cache-friendly; contiguous containers like std::vector provide the first for free.
  • AoS is natural and good when loops use all fields; SoA wins when loops use only a few fields of many elements, and it enables SIMD.
  • Traverse multi-dimensional arrays in storage order: with row-major C++ arrays, the last index goes in the innermost loop.
  • Split hot and cold data, shrink types, reorder members to reduce padding, and use indexes instead of pointers.
  • Align per-thread data to separate cache lines to avoid false sharing.
  • Measure first: profile, use realistic data sizes, change one thing at a time, and keep readable code where the numbers do not demand otherwise.

Next: Project: Grade Book, where you put your skills together in a complete program.