Cache locality: when read order matters

Add a third case

The benchmark allocates an array of 32-byte records and sums one 64-bit field. It reads the records directly, through an ordered pointer array, and through a shuffled pointer array. Both pointer cases use the same compiled function; only the pointer values differ.

static uint64_t
sum_direct(const struct record *records, size_t count)
{
    uint64_t total = 0;
    size_t i;

    for (i = 0; i < count; ++i) {
        total += records[i].value;
    }
    return total;
}

static uint64_t
sum_indirect(const struct record *const *order, size_t count)
{
    uint64_t total = 0;
    size_t i;

    for (i = 0; i < count; ++i) {
        total += order[i]->value;
    }
    return total;
}

Each record appears exactly once in every scan. The unsigned sum has the same result in any order, so every timed run can be checked. Allocation, initialisation and shuffling happen before timing.

An ordered scan makes nearby bytes useful in quick succession and gives prefetchers a regular pattern. Shuffling can lose those advantages even though the allocation is unchanged. The ordered-pointer case is the useful control: it keeps indirection while restoring address order.

A sample run

This example was measured in a shared Linux virtual machine reporting an AMD EPYC 9V74 processor, using GCC 14.2 with -O3 -march=native. The process was pinned to one logical CPU. These are illustrative results from the article preparation environment, not measurements of a Walmgres production system.

The pointer arrays are additional: each contains one 8-byte pointer per record on this host. Both arrays are allocated, so the total allocations are 12, 48 and 192 MiB respectively. Each pointer scan reads only its own pointer array. All 81 timed checksums matched.

Shuffling is the largest change in this run. The difference also grows with the working set. That supports a narrow conclusion: preserving address order mattered for this read-only reduction.

These figures measure traversal throughput, not the latency of a single cache miss. Loads from different loop iterations can overlap; this is not a dependent pointer-chasing benchmark. Compiler optimisation also matters: the direct loop and the pointer loop need not generate equivalent instructions. There were no cache flushes between runs, and no hardware counters were collected. The timings do not separate cache, prefetching and address-translation effects.

Alignment does not fix the order

The record allocation starts at a 64-byte boundary in all three cases. That controls where the array begins; it does not make shuffled reads sequential.

Padding every record to a cache-line boundary is not a general solution either: it would enlarge this data set without changing the work. Here, an interesting next experiment would be to store the values separately, since the loop never reads the other fields. That would be a different layout, not a free improvement.

The useful comparison

The point is not that pointers are inherently slow. It is that changing a representation can also change the read order, the working set and the code the compiler emits. Adding the ordered-pointer case makes the experiment easier to interpret. Measure the path your program actually uses before changing the layout.