Sequential Scans, Hardware Prefetch, and the Page Walk

A loop that adds one to every element of a 1 GiB array reads 1 GiB and writes 1 GiB. The arithmetic is trivial, so the runtime is set by the path between the load instruction and the memory cell. That path has four stages worth separating: the L1 data cache, the further cache levels, the translation from virtual to physical address, and the main memory itself. Each stage has a different cost, and the shape of the loop decides which stage is the bottleneck.

The line, not the element

Data moves between memory and cache in 64-byte lines on the mainstream x86-64 and AArch64 designs. A load of one 4-byte integer brings 64 bytes into L1. The next fifteen consecutive integers are then served from L1 at a cost of a few cycles each, while the first access to each line costs tens of cycles even when the line is in L2, and around a hundred or more when it must come from DRAM.

A sequential scan of 1 GiB therefore issues about 16.8 million line fills. The per-element cost is the per-line cost divided by sixteen, which is why the line size is the number that matters for any contiguous traversal and the element size is not. A scan of doubles gets eight elements per line; a scan of chars gets 64. The total traffic is the same 1 GiB either way, so the two scans differ in instruction count and in the number of loop iterations, not in bytes fetched.

Whether a line is brought in on demand or ahead of time is decided by the hardware prefetcher. Current server and desktop cores contain stream prefetchers that watch the sequence of addresses requested and, on detecting a constant stride, issue requests for subsequent lines before the demand loads reach them. A stride of one line is the easiest pattern to detect; a stride of a few lines is still detected; a stride that jumps by a page or by a random offset is not. The prefetcher’s accuracy determines whether the demand load waits for DRAM latency or finds the line already in flight.

Two things defeat it. A chain of dependent loads — each address computed from the value loaded by the previous one, as in a linked list — gives the prefetcher no address to predict, so every load pays full latency. And a scan with a large constant stride still triggers prefetching, but the prefetched lines are consumed one element at a time, so the bandwidth cost is not reduced; this is the column-traversal case described in Row-Major Layout and the Address Arithmetic Behind Indexing.

Software prefetch as a latency hiding tool

Hardware prefetchers cover the simple cases. Where the access pattern is known to the program but not detectable by the hardware, a prefetch instruction issues the request early. On x86-64 the instruction is prefetcht0, which prefetches into all cache levels; prefetcht1 prefetches into the second level and higher, prefetcht2 into the third level and higher or an implementation-specific level, and prefetchnta requests a non-temporal hint that pushes the line into a non-temporal structure and minimises cache pollution. These are hints: the hardware may ignore any of them.

/* Prefetch 8 lines (128 floats) ahead so the demand load finds the line in flight. */
#define DIST_LINES   8
#define FLOATS_LINE 16

void scale(float *restrict a, size_t n, float k) {
    for (size_t i = 0; i < n; i++) {
        size_t ahead = i + DIST_LINES * FLOATS_LINE;
        if (ahead < n)
            __builtin_prefetch(&a[ahead], 1, 3);   /* 1 = prepare for write */
        a[i] *= k;
    }
}

The distance is the tuning parameter, and it has an optimum that depends on the memory latency and the loop’s issue rate. Too small and the prefetch arrives after the demand load has already stalled; too large and the prefetched line is evicted before use, or the prefetch stream saturates the fill buffers and displaces useful requests. Issuing one prefetch per iteration is redundant for a line that has already been requested by the previous fifteen iterations, and a loop that emits a line’s worth of them has to be structured either to prefetch only when i starts a new line (i % 16 == 0) or to stride the loop by a line at a time. On a loop where the hardware prefetcher already works, an explicit prefetch adds instructions and buys nothing, which is why the instruction is a hint and why adding it indiscriminately can slow a loop down.

A prefetch of an address that is not mapped is architecturally permitted to be dropped rather than fault. That is what makes it safe to prefetch past the end of a buffer, but it also means a prefetch that crosses into unmapped memory does nothing at all, so a loop that prefetches one element beyond the array’s last line gains nothing for the boundary iterations.

The page walk behind every miss

Caches are indexed by physical address on most designs, or by a virtual address with physical tagging; either way a miss requires the physical address, which requires a translation. Translations are cached in the translation lookaside buffer, and the TLB holds on the order of a thousand to a few thousand entries on typical cores.

With 4 KiB pages, 1 GiB spans 262144 pages. The TLB cannot hold them, so a scan of 1 GiB walks page tables continuously: each new page needs a translation, and a TLB miss costs a page-table walk of several memory accesses, which on current hardware is on the order of tens to a couple of hundred cycles when the walk hits in cache and more when it does not. Since a page holds 64 lines and each line is consumed by sixteen 4-byte elements, the TLB miss is amortized over 1024 elements — but it is a real cost per page, and it competes with the data traffic for the same memory path.

Huge pages reduce the page count by a factor of 512 (2 MiB pages) or 262144 (1 GiB pages). A 1 GiB region mapped with 2 MiB pages needs 512 translations, which fits in the TLB comfortably. The scan then pays one translation per 2 MiB instead of one per 4 KiB, and the page-table walk disappears from the profile.

/* Ask the kernel for huge pages for a large scan buffer. */
void *p = mmap(NULL, len,
               PROT_READ | PROT_WRITE,
               MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
               -1, 0);
if (p == MAP_FAILED) {
    /* Huge pages unavailable or the pool is exhausted; fall back. */
    p = mmap(NULL, len, PROT_READ | PROT_WRITE,
             MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
}

The flag requires a configured huge-page pool on Linux, and the allocation is rounded to the huge-page size, so a request for 3 MiB with 2 MiB pages consumes 4 MiB. Transparent huge pages, where the kernel coalesces ordinary anonymous mappings without an explicit request, avoid the pool requirement but make the outcome dependent on the kernel’s heuristics and on fragmentation; madvise with MADV_HUGEPAGE marks a range for the kernel to consider, without guaranteeing the result. Either way the effect is the same: fewer translations, less page-walk work, and a scan that is bound by data traffic rather than by address translation.

Where a scan stops being sequential

The word “sequential” describes the address stream, not the loop. Three patterns look linear in the source and are not linear in memory.

Strided access. A loop stepping by 32 elements over 4-byte elements visits one line per iteration and uses 4 of its 64 bytes. The prefetcher follows the stride and the traffic is 16 times the useful data. This is the layout problem, and the fix is a change of layout or a tiling of the loop, as set out in Array of Structs or Struct of Arrays.

Multiple concurrent streams. A loop that reads from four arrays and writes to a fifth maintains five address streams. The prefetcher tracks a limited number of streams per core, and each additional stream competes for the fill buffers and the cache. Past a handful of streams, the hardware stops tracking new ones and the demand loads stall again.

Indirect access. An array of indices used to gather elements — out[i] = table[idx[i]] — produces a data-dependent address stream. The prefetcher cannot predict table[idx[i]], so every gather pays full latency unless the indices themselves happen to be sequential, in which case the prefetcher follows the index array and not the gather.

Non-temporal stores are the counterpart for the write side. A loop that writes an array once and never reads it again does not benefit from the line being resident in cache; the write allocates a line, dirties it, and later writes it back, so the traffic is a read-for-ownership plus a writeback even though only a write was needed. A streaming store instruction writes the line without reading it, eliminating the read-for-ownership traffic. The condition is strict: the line must be written completely, and it must not be read again before it is evicted, or the store’s benefit becomes a cost.

The bound that a scan can reach

The upper limit for a sequential scan is the bandwidth of the memory path, not the instruction throughput of the core. A single core on a current server can sustain a fraction of the socket’s total bandwidth because it has a limited number of outstanding misses; multiple cores scanning in parallel can saturate the socket, at which point adding cores does not reduce the time.

The practical consequence is that a scan of a large array has a floor on its runtime proportional to the number of bytes and inversely proportional to the achievable bandwidth, and no amount of loop unrolling or prefetch tuning moves that floor. What tuning can do is make the scan reach the floor. The difference between a scan at half the achievable bandwidth and one at the floor is usually one of the three patterns above: an unaligned access pattern, too many streams, or a page-translation cost that the huge-page mapping would have removed.

For data that is read once and discarded, the entire cache hierarchy is overhead: the line is fetched into L1, consumed, and evicted without reuse. Whether that overhead is worth avoiding depends on whether the data will be touched again before eviction, which is a property of the workload rather than of the array. The alternative layout that packs more useful bytes per line, for types narrower than a byte boundary, is covered in Bit-Packed Integer Arrays and Vectorized Decoding.