Cache locality

Why this matters

Two loops can do the same number of steps and still differ by a factor of a hundred in speed. The cause is not the arithmetic. The cause is where the data sits in memory and in what order the processor asks for it.

This lesson takes two containers that hold the same numbers: an array, which keeps its items side by side, and a linked list, which keeps each item in its own separate block. You will time a full pass over both and see why the list is so much slower. The row-major layout lesson earlier in this module makes the same point for two-dimensional arrays, so the idea will already be familiar if you read it.

You do not need to know anything about processor hardware for this lesson. The few hardware terms are defined the first time they appear.

Memory is far away from the processor

A processor does arithmetic on numbers held in its registers. A register is a tiny storage slot inside the processor itself. Numbers in a program live in main memory, which is the RAM chip on the board. Reading a number from main memory is much slower than adding two registers together, so processors keep a copy of recently used memory in a much smaller and faster store called the cache.

The cache is not one number at a time. When the processor needs one value, it loads the whole block of memory that contains that value. The block is called a cache line. On the test machine used for this lesson, getconf LEVEL1_DCACHE_LINESIZE reports 64, so a cache line is 64 bytes.

An int takes 4 bytes on the common compilers. One cache line therefore holds 16 ints. If your loop reads them in order, the first read loads the line, and the next 15 reads find their values already in the cache. The processor has done one slow trip to main memory for 16 values.

The processor also tries to guess the next block it will need. When it sees reads that step through memory at a steady gap, it starts loading the next blocks early. This guess is called prefetching. It works well for arrays, because the next item is always a fixed distance away.

Arrays keep neighbours together

An array stores its items one after another in a single block of memory. If the first item is at address 1000 and each int takes 4 bytes, the items sit at 1000, 1004, 1008, and so on. Nothing separates them.

Here is a tiny example. The array holds the values 10, 20, 30 and 40:

address:  1000   1004   1008   1012
value:      10     20     30     40

A loop that adds up the array reads 1000, then 1004, then 1008, then 1012. All four sit in the same cache line, so one slow trip brings all four values in. The processor then does the additions without waiting.

Linked lists scatter their items

A linked list stores each item in its own node. A node holds a value and the address of the next node. Each node is a separate allocation made with new, and the allocator can place it anywhere that has free space. Here is the node type used in the lesson:

struct Node {
    int value;   // the number stored in this node
    Node* next;  // the address of the next node, or nullptr at the end
};

On a 64-bit system, the int takes 4 bytes, the compiler adds 4 bytes of padding so the pointer starts on an 8-byte boundary, and the pointer takes 8 bytes. A node is 16 bytes. That is small. The problem is not the size of a node. The problem is where the next node sits.

Suppose the nodes are scattered like this:

address:  1000 (value 10, next = 5040)
address:  2120 (value 40, next = nullptr)
address:  3488 (value 20, next = 1000)
address:  5040 (value 30, next = 2120)

To walk the list, you start at the head, which is 3488 in this example. You read the value 20 and the pointer 1000. Only after that read finishes do you know the next address. Then you read 1000, which gives the pointer 5040. Then you read 5040, and so on.

Each step needs a value from the step before it. The processor cannot ask for node number three until node two has arrived. Each node is in a different cache line, so each step is a slow trip to main memory. The processor cannot predict the jumps, because they do not follow a steady gap, so prefetching does not help. This chain of reads, where each address comes from the last read, is called pointer chasing.

A linked list of 1,000,000 nodes therefore makes about 1,000,000 slow trips. An array of 1,000,000 ints makes about 62,500 trips, because each trip brings in 16 values. The count of additions is the same, but the count of trips is very different.

The timing program

The best way to see the difference is to time it. The program below builds an array and a linked list with the same values. Then it adds up every value both ways, many times over, and prints the time per item.

Two details matter. First, the nodes are linked in a random order, so walking the list jumps around memory. Second, the sums are printed and compared, so the compiler cannot skip the loops as if they did nothing.

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
 
struct Node {
    int value;
    Node* next;
};
 
// Sum every value two ways and print the time per item in nanoseconds.
void measure(int n, bool shuffled) {
    const int rounds = 100'000'000 / n;
 
    std::vector<int> array(n);
    for (int i = 0; i < n; ++i) array[i] = i % 100;
 
    std::vector<Node*> nodes(n);
    for (int i = 0; i < n; ++i) nodes[i] = new Node{i % 100, nullptr};
 
    std::vector<int> order(n);
    for (int i = 0; i < n; ++i) order[i] = i;
    if (shuffled) {
        std::mt19937 rng(42);
        std::shuffle(order.begin(), order.end(), rng);
    }
    for (int i = 0; i + 1 < n; ++i) nodes[order[i]]->next = nodes[order[i + 1]];
    Node* head = nodes[order[0]];
 
    using Clock = std::chrono::steady_clock;
 
    auto t0 = Clock::now();
    long long sum_array = 0;
    for (int r = 0; r < rounds; ++r)
        for (int i = 0; i < n; ++i) sum_array += array[i];
    auto t1 = Clock::now();
 
    long long sum_list = 0;
    for (int r = 0; r < rounds; ++r)
        for (const Node* p = head; p != nullptr; p = p->next) sum_list += p->value;
    auto t2 = Clock::now();
 
    double items = static_cast<double>(n) * rounds;
    double array_ns = std::chrono::duration<double, std::nano>(t1 - t0).count() / items;
    double list_ns = std::chrono::duration<double, std::nano>(t2 - t1).count() / items;
    std::printf("%9d items, shuffled=%d: array %6.2f ns/item, list %7.2f ns/item, sums match: %s\n",
                n, shuffled ? 1 : 0, array_ns, list_ns,
                sum_array == sum_list ? "yes" : "no");
 
    for (Node* p = head; p != nullptr;) {
        Node* next = p->next;
        delete p;
        p = next;
    }
}
 
int main() {
    for (int n : {1'000, 10'000, 100'000, 1'000'000, 10'000'000}) measure(n, true);
    measure(1'000'000, false);
}

The function measure does one size at a time. It makes rounds passes so that each size adds up exactly 100 million items in total. That keeps the total work equal, so the per-item times can be compared across sizes.

The array part is a plain indexed loop. The list part follows p->next until it reaches nullptr. The -> operator means "follow the pointer, then read the field", as covered in the pointer lessons earlier in this module.

The last loop deletes every node. The lesson on leaks covers why this matters: every new needs a matching delete, or the memory is lost until the program ends.

Compile and run it with optimization turned on:

g++ -std=c++20 -Wall -O2 locality.cpp -o locality
./locality

The -O2 flag asks the compiler to optimize the code. Without it, the array loop also runs much slower for reasons that have nothing to do with memory, so the comparison would mislead you. The common section below shows that case.

On the test machine, which had an AMD Ryzen 7 260 processor with a 16 MiB L3 cache, the program printed this:

     1000 items, shuffled=1: array   0.22 ns/item, list    0.92 ns/item, sums match: yes
    10000 items, shuffled=1: array   0.25 ns/item, list    3.24 ns/item, sums match: yes
   100000 items, shuffled=1: array   0.30 ns/item, list   19.70 ns/item, sums match: yes
  1000000 items, shuffled=1: array   0.22 ns/item, list  139.70 ns/item, sums match: yes
 10000000 items, shuffled=1: array   0.24 ns/item, list  170.32 ns/item, sums match: yes
  1000000 items, shuffled=0: array   0.22 ns/item, list    1.42 ns/item, sums match: yes

Your numbers will differ. The processor, the memory and the compiler all change the figures. The pattern is what to look for.

Worked example: the same list, two layouts

The last row of the output is the key one. It uses the same million-node list twice. The first time, the nodes were linked in a random order, and the list took 139.70 ns per item. The second time, the nodes were linked in the order they were created, and the list took 1.42 ns per item. That is about 100 times faster.

Nothing about the list changed except the order of the next pointers. When the nodes were created one after another, the allocator usually placed them one after another in memory. Walking the list then moved forward through memory in small steps, and the cache lines were reused. When the nodes were linked at random, every step landed in a different place.

This shows that the number of nodes is not the whole story. A list of a million nodes can be fast or slow depending on where its nodes live. The lesson is not that linked lists are always slow. The lesson is that the array keeps its order in memory by design, while the list gives you no such promise.

Worked example: when everything fits in the cache

Look at the first two rows. With 1,000 items, the list takes 0.92 ns per item, against 0.22 ns for the array. The gap is about four times. With 1,000,000 items the gap is about 600 times.

The reason is size. A list of 1,000 nodes holds about 16 KB of node data, which fits in the cache. Once the first pass has loaded the nodes, the later passes find them already in the cache, and the random order costs little. A list of 1,000,000 nodes takes about 16 MB, which is larger than the processor's fast caches. Each pass has to fetch the nodes again from main memory, and the random order makes each fetch a separate trip.

So a random-order list is slow mainly when it is too large to fit in the cache. Small lists can hide the problem, which is why a test with 10 items can look fine while a test with a million items is very slow.

The 10,000,000 row takes 170 ns per item, only somewhat more than the 1,000,000 row, even though the list is ten times larger. The processor's cache cannot hold any of it in either case, so the cost per item stays about the same. Numbers like these come from a single run, and a second run on the same machine gave 228 ns for the 10,000,000 row. Treat any one figure as a rough guide.

Worked example: the same loop without optimization

The timing program ran with -O2. Here is the same program built with no optimization:

g++ -std=c++20 -Wall -O0 locality.cpp -o locality0
./locality0

Its output for the 1,000,000-item rows was:

  1000000 items, shuffled=1: array   3.04 ns/item, list  132.25 ns/item, sums match: yes
  1000000 items, shuffled=0: array   2.74 ns/item, list    1.42 ns/item, sums match: yes

The list rows barely changed. The array row went from 0.22 ns to about 3 ns per item, which is about 14 times slower. With -O2, the compiler can add several numbers in one instruction, and the array loop gets faster. The list loop cannot be helped that way, because each step must wait for the pointer from the step before. So the optimized build makes the gap between array and list wider. A benchmark run without optimization tells you about the unoptimized code, not about the memory layout.

Common mistakes

Timing a loop whose result is never used

If the program never prints or uses the sum, the compiler may decide the loop does nothing and remove it. The timer then shows a tiny number that means nothing. The program above prints both sums and checks that they match, which keeps the loops in the compiled code. A common habit is to print a result or store it in a volatile variable.

Comparing builds with different optimization levels

Comparing an array timed at -O2 with a list timed at -O0 gives a false result. Use the same flags for both. The two outputs above show the array dropping from about 3 ns to 0.22 ns when the optimizer is turned on, while the list stays near 130 ns.

Trusting a single run

Run the program several times before drawing a conclusion. On the test machine, the 1,000,000-item random list took 139.70 ns in one run and 129.89 ns in another, both built with -O2. The order of magnitude was stable, but the exact figure was not. Small differences between two runs say nothing.

Assuming the list is slow in every case

The list with nodes linked in creation order took 1.42 ns per item. A list built by appending nodes one at a time can often be fast in practice, because the allocator places them close together. The slowness comes from the random order, and real programs can have either pattern. Measure the program you actually have.

Using a list where an array would keep the data together

If you loop over the same data many times, or the data is large, an array or std::vector is usually the better choice. The vectors lesson in the arrays module covers how a vector grows. The lesson on linked lists in this course covers when a list is still the right tool, such as frequent insertion in the middle.

Practice

Exercise 1: Predict the gap

Without running anything, predict which of these gives the bigger gap between array and list: a list of 1,000 random nodes, or a list of 10,000,000 random nodes. Explain why in two sentences.

Show the answer

The 10,000,000-node list gives the bigger gap, in the sense that the list is much slower relative to the array. A list of 1,000 nodes is about 16 KB and fits in the cache, so after the first pass the random order costs little. A list of 10,000,000 nodes is far larger than the cache, so every step is a fetch from main memory.

Exercise 2: Count the matches in a list

Write a function int count_above(const Node* head, int limit) that returns how many nodes have a value greater than limit. Use a loop, not recursion.

Show the answer

int count_above(const Node* head, int limit) {
    int count = 0;
    for (const Node* p = head; p != nullptr; p = p->next) {
        if (p->value > limit) ++count;
    }
    return count;
}

The loop starts at the head and follows next until the pointer is nullptr. Each node is visited once.

Exercise 3: Explain a strided read

A std::vector<int> holds 1,000,000 values. Compare a loop that adds every value with a loop that adds only every sixteenth value (a strided loop, which steps through memory by a fixed gap). Which one touches more cache lines, and why?

Show the answer

Both loops touch about the same number of cache lines. Sixteen ints take 64 bytes, which is one cache line. Reading every sixteenth value means each read lands in a different line, so the loop reads one new line per addition. The full loop reads each line once, and it reads 16 values from each line. The strided loop does 16 times fewer additions, but it still makes almost as many trips to memory.

Exercise 4: Copy the list into a vector first

Write a function long long sum_list(const Node* head) that copies the values into a std::vector<int> first and then adds up the vector. Explain why this is not faster than adding while walking the list, even when the list is large.

Show the answer

long long sum_list(const Node* head) {
    std::vector<int> values;
    for (const Node* p = head; p != nullptr; p = p->next) values.push_back(p->value);
    long long total = 0;
    for (int v : values) total += v;
    return total;
}

The first loop still walks the list, so it still makes one slow trip per node. The second loop adds work on top of that walk. In a test with a million nodes, the copy version took about three times as long as the walk alone (5.5 ms against 1.7 ms). The real gain comes from keeping the data in an array from the start.

Exercise 5: Read a benchmark

A colleague reports that a loop over std::vector<int> takes 3 ns per item and a loop over a list takes 130 ns per item, both at 1,000,000 items. What two questions would you ask before you trust the report?

Show the answer

Ask which optimization flags were used, because the array figure changes by about 14 times between -O0 and -O2. Ask whether the list nodes were linked in random order or in creation order, because that changes the list figure by about 100 times. Ask how many runs were made and whether the sums were checked.

Summary

• A processor loads memory in cache lines of 64 bytes, so neighbouring items are cheap to read together.
• An array keeps its items side by side, so a loop over it makes few trips to main memory.
• A linked list needs each address from the node before it, so walking a randomly linked list makes one slow trip per node.
• The same list can be fast or slow depending on where its nodes sit in memory.
• Benchmarks must use the same optimization level for every case, print their results, and be run more than once.