Benchmarking Cache Locality with Array Traversal Patterns

Hello. In the previous lesson, you traced how a C++ loop becomes loads, arithmetic, comparisons, and jumps at the assembly level. That view helps here: cache locality is not a property of a for loop’s syntax. It comes from the sequence of memory addresses generated by that loop.

This closes the C++ Execution and Hardware Foundations module with an experiment. You will benchmark two programs that compute the same matrix sum and perform the same number of logical element reads, but visit the elements in different orders. You will then connect the timing difference to cache lines, prefetching, and C++ row-major layout.

---

Same algorithmic work, different physical work

Suppose a matrix is stored in one contiguous std::vector<std::uint32_t> with $N$ rows and $N$ columns. We choose the conventional row-major mapping:

$$\text{element}(r,c)=\text{data}[r\cdot N+c]$$

The matrix is physically laid out as:

row 0: data[0], data[1], ..., data[N - 1]
row 1: data[N], data[N + 1], ...
...

Two nested loops can visit every element exactly once.

// Row-first traversal: the inner loop changes the column.
for (std::size_t row = 0; row < n; ++row) {
    for (std::size_t col = 0; col < n; ++col) {
        sum += data[row * n + col];
    }
}

// Column-first traversal: the inner loop changes the row.
for (std::size_t col = 0; col < n; ++col) {
    for (std::size_t row = 0; row < n; ++row) {
        sum += data[row * n + col];
    }
}

Both traverse $N^2$ values, use $O(1)$ additional space, and compute the same unsigned sum. Big-O notation therefore predicts no difference. The processor, however, does not fetch one uint32_t at a time from RAM. It normally fetches memory in cache lines: fixed-size nearby blocks, commonly 64 bytes on modern x86-64 systems.

A 64-byte line holds 16 values of type std::uint32_t.

• Row-first traversal reads adjacent values. Once a cache line containing data[0] arrives, the following 15 values are often already available. Hardware prefetchers can also recognize the forward stream and fetch later lines early.
• Column-first traversal jumps by $N$ elements between successive reads. For $N=4093$, that jump is $4093\cdot 4=16372$ bytes. Most of the line fetched for one element is not used until much later, after it may already have been evicted.

The issue is spatial locality: whether data likely to be used soon sits near data used now.

C++ built-in multidimensional arrays use row-major layout. A flat std::vector is simply one-dimensional, but the index formula you choose gives it a matrix layout. In this lesson, the formula $r\cdot N+c$ deliberately makes the vector row-major.

---

Why cache lines make adjacency valuable

A cache is a small, fast memory layer between CPU registers and main memory. When the CPU loads an address not currently in cache, it generally brings in the surrounding cache line as well.

For a row-major matrix of 32-bit values, a sequential scan behaves approximately like this:

1. Load the line containing elements 0 through 15.
2. Consume all 16 values before moving on.
3. Load the next line and again consume most or all of it.

A column traversal of a sufficiently large row-major matrix behaves differently:

1. Load one element from a line in row 0.
2. Jump to a distant line in row 1.
3. Continue through many rows.
4. Return to the neighboring element in row 0 only after traversing the rest of the matrix column.

The hardware may have had to load the original cache line again by then. The column traversal still reads each logical element once, but can cause substantially more cache traffic and gives prefetchers a much harder job.

Watch the following segments of C++ cache locality and branch predictability by mCoding. They give a compact hardware-level model before you perform the row-versus-column experiment.

The important caution is that “64-byte cache line” is a useful working model, not a universal C++ guarantee. Cache capacity, line size, associativity, prefetching behavior, CPU frequency, and virtualization all vary by machine. A benchmark should reveal the effect on your WSL environment rather than attempt to reproduce someone else’s exact timing.

For a detailed visual explanation of why loop order should match memory layout, read the performance section and benchmark discussion in Memory layout of multi-dimensional arrays.

---

Design the benchmark before writing it

A useful performance experiment controls what it can:

Design choice	Why it matters
One contiguous matrix	Prevents allocation layout or pointer chasing from becoming the main variable.
Identical values and dimensions	Ensures both functions solve the same computational problem.
Allocation and initialization outside timed regions	Measures traversal rather than std::vector allocation or filling.
Optimized compilation	Cache-sensitive loop behavior is often obscured by debug-mode stack traffic and unoptimized indexing.
Repeated measurements	Reduces the influence of scheduler interruptions and transient system activity.
Alternating test order	Avoids always giving one traversal the same warm-cache or CPU-frequency conditions.
A result used after timing	Prevents the compiler from deleting the traversal as dead work.

The final point follows directly from the optimization rules explored in the previous lesson. If a function computes a sum that nobody observes, an optimizer is allowed to remove the entire loop. Here, every timed call contributes to a volatile output sink, while the matrix itself remains non-volatile. Making the input matrix volatile would change normal memory-access optimization and would no longer represent ordinary C++ data processing.

We also use std::uint64_t for the accumulator. Unsigned arithmetic has defined wraparound behavior, unlike signed overflow. With the dimensions recommended below, the sum remains representable anyway, but the type keeps the benchmark’s intended semantics clear.

---

WSL lab: benchmark row-major versus column-major traversal

Create a file named locality.cpp.

#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <vector>

#if defined(__GNUC__) || defined(__clang__)
#define NOINLINE __attribute__((noinline))
#else
#define NOINLINE
#endif

using SumFunction = std::uint64_t (*)(
    const std::uint32_t* data,
    std::size_t n);

// Observable destination for benchmark results.
// The input data is intentionally not volatile.
volatile std::uint64_t sink = 0;

NOINLINE std::uint64_t sum_by_row(
    const std::uint32_t* data,
    std::size_t n) {

    std::uint64_t sum = 0;
    const std::uint32_t* p = data;

    for (std::size_t row = 0; row < n; ++row) {
        for (std::size_t col = 0; col < n; ++col) {
            sum += *p++;
        }
    }

    return sum;
}

NOINLINE std::uint64_t sum_by_column(
    const std::uint32_t* data,
    std::size_t n) {

    std::uint64_t sum = 0;

    for (std::size_t col = 0; col < n; ++col) {
        const std::uint32_t* p = data + col;

        for (std::size_t row = 0; row < n; ++row) {
            sum += *p;
            p += n;
        }
    }

    return sum;
}

double time_one(
    SumFunction function,
    const std::uint32_t* data,
    std::size_t n,
    std::size_t repeats) {

    using Clock = std::chrono::steady_clock;

    std::uint64_t checksum = 0;
    const auto start = Clock::now();

    for (std::size_t i = 0; i < repeats; ++i) {
        checksum ^= function(data, n) + i;
    }

    const auto stop = Clock::now();

    // Makes the computed result observable outside the timed functions.
    sink = checksum;

    const std::chrono::duration<double, std::milli> elapsed = stop - start;
    return elapsed.count() / static_cast<double>(repeats);
}

double median(std::vector<double> values) {
    std::sort(values.begin(), values.end());
    return values[values.size() / 2];
}

int main(int argc, char** argv) {
    const std::size_t n =
        (argc >= 2) ? std::stoull(argv[1]) : 4093;

    if (n == 0 || n > 10000) {
        throw std::runtime_error("Choose a matrix dimension from 1 to 10000.");
    }

    const std::size_t count = n * n;
    std::vector<std::uint32_t> matrix(count);

    for (std::size_t i = 0; i < count; ++i) {
        matrix[i] = static_cast<std::uint32_t>(i);
    }

    const std::uint64_t expected = sum_by_row(matrix.data(), n);
    const std::uint64_t column_check = sum_by_column(matrix.data(), n);

    if (expected != column_check) {
        throw std::runtime_error("Traversal functions disagree.");
    }

    // Aim for roughly this many logical element reads per timed sample.
    // Small matrices need many passes; large matrices need only one.
    constexpr std::size_t target_elements = 64ULL * 1024 * 1024;
    const std::size_t repeats =
        std::max<std::size_t>(1, target_elements / count);

    constexpr int rounds = 7;
    std::vector<double> row_times;
    std::vector<double> column_times;
    row_times.reserve(rounds);
    column_times.reserve(rounds);

    // Alternate order to reduce systematic first-versus-second bias.
    for (int round = 0; round < rounds; ++round) {
        if (round % 2 == 0) {
            row_times.push_back(
                time_one(sum_by_row, matrix.data(), n, repeats));
            column_times.push_back(
                time_one(sum_by_column, matrix.data(), n, repeats));
        } else {
            column_times.push_back(
                time_one(sum_by_column, matrix.data(), n, repeats));
            row_times.push_back(
                time_one(sum_by_row, matrix.data(), n, repeats));
        }
    }

    const double row_ms = median(row_times);
    const double column_ms = median(column_times);

    const double logical_gib =
        static_cast<double>(count * sizeof(std::uint32_t)) /
        (1024.0 * 1024.0 * 1024.0);

    std::cout << std::fixed << std::setprecision(3);
    std::cout << "Matrix: " << n << " x " << n
              << " (" << logical_gib << " GiB logical reads per pass)\n";
    std::cout << "Repeats per timed sample: " << repeats << '\n';
    std::cout << "Correct sum: " << expected << '\n';
    std::cout << "Row traversal median:    " << row_ms << " ms"
              << "  (" << logical_gib / (row_ms / 1000.0)
              << " GiB/s)\n";
    std::cout << "Column traversal median: " << column_ms << " ms"
              << "  (" << logical_gib / (column_ms / 1000.0)
              << " GiB/s)\n";
    std::cout << "Column / row slowdown:   "
              << column_ms / row_ms << "x\n";
    std::cout << "Sink: " << sink << '\n';
}

Compile with optimization enabled:

g++ -std=c++20 -O3 -march=native -DNDEBUG \
    -Wall -Wextra -Wpedantic \
    locality.cpp -o locality

Run a size sweep:

for n in 64 128 256 512 1024 2048 4093; do
    ./locality "$n"
done

The default larger size, $4093\times 4093$, uses roughly 64 MiB for matrix values. The non-power-of-two dimension also avoids making the experiment depend too heavily on a particular cache-set mapping. If the difference remains small at the largest size and your WSL memory allocation permits it, try 6001, which uses roughly 137 MiB.

Record the median values in a compact table:

Dimension $N$	Matrix footprint	Row traversal	Column traversal	Column/row slowdown
64	16 KiB
256	256 KiB
1024	4 MiB
4093	about 64 MiB

The reported GiB/s is logical read throughput: matrix bytes divided by measured time. It is useful for comparing the two versions, but it is not a direct measurement of physical DRAM bandwidth. The column traversal can fetch the same cache line multiple times, so its real data movement may be larger than its logical input size suggests.

---

Interpret the result carefully

A common result is that small matrices show little difference, while the gap grows once the active data no longer fits comfortably in a nearby cache. Do not expect a universal ratio. Your result is affected by:

• CPU model and cache hierarchy;
• WSL virtualization and activity on the Windows host;
• background processes;
• compiler version and vectorization choices;
• memory frequency and CPU frequency scaling;
• whether the matrix fits in some level of cache.

The core conclusion does not depend on a particular slowdown factor:

With row-major storage, making the column index change in the innermost loop creates contiguous accesses. Making the row index change in the innermost loop creates a large stride.

You can make one controlled follow-up measurement that separates part of the contiguous-access advantage from compiler vectorization. Build a second executable with auto-vectorization disabled:

g++ -std=c++20 -O3 -march=native -DNDEBUG \
    -fno-tree-vectorize \
    -Wall -Wextra -Wpedantic \
    locality.cpp -o locality_no_vector

./locality_no_vector 4093

The row traversal should usually remain faster even without auto-vectorization, because it still uses cache lines and prefetching efficiently. If the gap changes, that difference reflects an additional advantage of contiguous data: it is easier for the compiler to process adjacent values using SIMD instructions.

Your previous assembly-reading workflow can validate the intended access patterns. Generate optimized assembly and inspect the two functions:

g++ -std=c++20 -O3 -march=native -S locality.cpp -o locality.s

In the row traversal, look for a pointer or index advancing through nearby addresses. In the column traversal, look for an increment based on $N$, representing the row-to-row stride. The exact registers and instructions will vary, but the address progression is the essential evidence.

---

Benchmarking discipline beyond this lab

This hand-written harness deliberately has few dependencies. In production performance work, a dedicated framework such as Google Benchmark handles calibration, repeated runs, reporting, and warm-up more systematically.

Read these targeted parts of the Google Benchmark User Guide after completing the lab.

A benchmark result is credible when you can state:

1. What changed: only traversal order.
2. What stayed fixed: matrix values, dimensions, arithmetic, and logical work.
3. Why the work was not optimized away: the result was used observably.
4. How variance was handled: repeated samples, medians, and alternating order.
5. What hardware mechanism plausibly explains the difference: cache-line utilization and predictable access.

---

Takeaways

• Big-O complexity does not describe cache behavior. Two $O(N^2)$ traversals can have dramatically different wall-clock times.
• A row-major matrix places elements from the same row next to one another in memory.
• For row-major data, a row-first traversal provides strong spatial locality; a column-first traversal has a stride of $N$ elements.
• Caches fetch lines of adjacent bytes, so sequential code tends to use more of each fetched line and helps hardware prefetchers.
• Sound benchmarking requires optimized builds, identical inputs, work that cannot disappear, repeated timing, and careful interpretation.
• The most reliable performance rule is not “always use rows first.” It is: make the innermost traversal dimension match the physical layout of the data.

You have now completed the C++ execution and hardware foundations module. The next module shifts to Java object-oriented design, beginning with how constructors, access control, and validated methods preserve a class invariant.