Step 1 of 5

Caches and contiguous memory

Big-O tells you how work grows with the input. It says nothing about the constant factor, and on modern hardware that factor is decided mostly by memory. A processor can do an addition in well under a nanosecond, but fetching a value from main memory takes on the order of 100 nanoseconds. To hide that gap, every core has small, fast caches:

Memory moves into the caches in fixed blocks called cache lines: 64 bytes on x86 and most ARM chips (Apple's M-series use 128). Read one int, and its 15 neighbors arrive in the same line for free. Processors also prefetch: when they notice you walking through memory in order, they fetch the next lines before you ask.

So the fastest code reads memory sequentially, using every byte of each line it pays for. This program counts how often two traversals of the same grid have to move to a new cache line:

#include <iostream>

int main() {
    const int n = 64;                                   // a 64 x 64 grid of 4-byte ints, stored row by row
    auto line_of = [](int index) { return index * 4 / 64; };
    int row_switches = 0, col_switches = 0, last = -1;
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++) {
            int line = line_of(r * n + c);
            if (line != last) row_switches++;
            last = line;
        }
    last = -1;
    for (int c = 0; c < n; c++)
        for (int r = 0; r < n; r++) {
            int line = line_of(r * n + c);
            if (line != last) col_switches++;
            last = line;
        }
    std::cout << n * n << " reads: row by row changes line " << row_switches
              << " times, column by column " << col_switches << " times\n";
}

4096 reads: row by row changes line 256 times, column by column 4096 times

Row by row, each 64-byte line serves 16 reads. Column by column, every single read lands in a different line. On real hardware the difference is dramatic: summing a 4096 × 4096 grid of ints took 10 ms row by row and 155 ms column by column (GCC -O2 on a 4-core Linux machine). Same algorithm, same number of additions, 15 times slower.

What this means for your code

• Contiguous containers win. std::vector and std::array keep elements side by side. A std::list or std::map scatters nodes around the heap, so walking one is a chain of cache misses. That's why a vector often beats a list even where Big-O favors the list.
• Loop in storage order. For a 2D grid stored row by row, the inner loop should walk along a row.
• Keep hot data small. The less memory a loop touches, the more of it fits in the caches.
• Measure. Caches make performance hard to guess; profile before and after (the Pro Track's performance project does exactly this).

Your turn: write distinct_lines(offsets, line_size), the number of different cache lines a list of byte offsets touches (offset / line_size is the line number), and column_sums(grid, rows, cols), the sum of each column of a row-major grid. Compute the column sums with the row as the outer loop, adding each row into a vector of sums, so memory is read in order.

Next: Arrays of structs vs structs of arrays