Bytes Fetched per Field: Layout as a Bandwidth Decision

A traversal that reads one field of one million records moves the same number of logical bytes whether those records are laid out one way or another. What differs is the number of physical bytes the memory system must transfer, and that number is set by the cache line, not by the field width. On the common architectures a cache line is 64 bytes, and a cache miss brings in all 64 whether the code wanted 4 of them or 64. Layout is therefore a bandwidth decision before it is anything else.

The effect is large enough to invert intuitions. A structure that is smaller in total can be slower to traverse than a larger one, because the smaller structure interleaves the fields that are read with fields that are not. Conversely, splitting a structure into parallel arrays can turn a memory-bound loop into a compute-bound one without changing a single algorithm.

The arithmetic of a wasted fetch

Consider a record with a 4-byte key, an 8-byte value, and a 32-byte descriptive string, giving 44 bytes that the compiler pads to 48 for alignment. In an array of such records, four records share three cache lines: 192 bytes of transfer for 192 bytes of record. A loop that sums only the 8-byte value field touches every line of every record, so it transfers 48 bytes per record to consume 8.

The efficiency of that loop is 8/48, about 17 percent. If the values were stored in a separate array of 8-byte elements, a cache line would hold eight values and the loop would consume all 64 bytes it transferred, an efficiency of 100 percent. The logical work is identical; the number of lines the loop must wait for is six times smaller.

The general formula for a strided access pattern is worth writing down, because it predicts the whole family of effects. If a loop reads a field of width w from records of stride s, and the records are contiguous, then the number of lines touched per record is:

lines_per_record = (ceil(s / 64) * 64) / min(s, 64)   -- when s < 64 this is 1
useful_fraction  = w / max(s, 64)

Two regimes follow. When the stride is smaller than a line, every record shares lines with its neighbours and the useful fraction is w / 64. When the stride exceeds a line, each record starts its own line and the useful fraction is w / s, worse still. The best case for any layout is that the field width equals the stride, which is exactly what an array of the field achieves.

Where array-of-structs wins

The interleaved layout is not a mistake. It is optimal for the access pattern that reads all fields of a record together, which is the common case for object-oriented code and for anything that processes a record as a unit: deserialising a message, validating a row, copying a node. When all 48 bytes are needed, a 48-byte record uses 48 of every 64 transferred, and the separate-arrays layout would require three separate streams, three sets of pointer arithmetic, and three times as many distinct cache lines in flight.

Interleaving also reduces the number of distinct memory streams. A prefetcher tracks a bounded number of streams, typically a handful per core, and each additional array is another stream. A structure-of-arrays traversal of eight fields creates eight streams and may exceed what the prefetcher can follow, which can make the theoretically better layout perform worse in practice. This is the main reason the answer to “which layout” is a function of the field access pattern rather than a universal rule.

The third advantage of interleaving is allocation simplicity: one allocation per record, one lifetime, one free. Splitting into parallel arrays means either a fixed capacity chosen up front or a growth path that must keep all arrays in step.

Where splitting pays

Splitting pays when a hot loop reads a strict subset of fields. The pattern is common: a physics step that reads positions and velocities but not names, a filter that reads a flag but not the payload, a sort that compares keys and then permutes everything. In each case the fields outside the subset are pure overhead during the traversal, and their cost is proportional to their size.

The classic mitigation keeps the hot fields in a compact array and the cold fields elsewhere, referenced by index rather than by pointer. The hot array is then a dense stream of exactly the bytes the loop needs, and the cold data is touched only when a record is selected. This is the structure the “hot/cold splitting” optimisation in some compilers performs automatically, and it is the same idea as columnar storage in analytical databases.

Splitting also changes the number of memory requests in flight that the hardware can sustain. A dense stream of 8-byte values lets the loop issue a load every few cycles, and the out-of-order engine can have many such loads outstanding. The limit becomes the number of line fill buffers and the memory-level parallelism available, not the loop’s arithmetic. The consequences of that limit are worked through in Dependent Loads and the Cost of Pointer Chasing.

A worked layout change

The following pair of structures computes the same total. The first is a record-per-entity layout; the second splits the two fields the loop reads into their own arrays.

#include <stddef.h>
#include <stdlib.h>

struct entity {
    int   id;
    float x, y, z;        /* position: read by the step */
    float vx, vy, vz;     /* velocity: read by the step */
    char  name[32];       /* read only on selection */
    int   flags;
};                        /* 4 + 24 + 32 + 4 = 64 bytes, padded to 64 */

/* Record layout: each entity is exactly one cache line, of which 24 bytes
   are position and velocity. */
void step_a(struct entity *e, size_t n, float dt)
{
    for (size_t i = 0; i < n; i++) {
        e[i].x += e[i].vx * dt;
        e[i].y += e[i].vy * dt;
        e[i].z += e[i].vz * dt;
    }
}

struct positions { float *x, *y, *z; };
struct velocities { float *vx, *vy, *vz; };

/* Split layout: 24 bytes of useful data per entity, spread over six dense
   streams. */
void step_b(struct positions p, struct velocities v, size_t n, float dt)
{
    for (size_t i = 0; i < n; i++) {
        p.x[i] += v.vx[i] * dt;
        p.y[i] += v.vy[i] * dt;
        p.z[i] += v.vz[i] * dt;
    }
}

step_a transfers 64 bytes per entity to use 24. step_b transfers 48 bytes per entity in three line-sized chunks per array pair, and every byte of each chunk is consumed. The split version also gives the prefetcher six regular streams with unit stride, which is the pattern prefetchers handle best; the record version gives one stream with a stride of 64 bytes, which is also prefetchable but carries the wasted 40 bytes.

The split has a cost that the record version does not: six allocations instead of one, and six pointers to keep valid. If the entity count grows, all six arrays must grow together, and a growth that reallocates only some of them leaves the structure inconsistent. That coupling is the reason production code often keeps a single arena for the whole set and allocates the arrays from it, a pattern covered in Geometric Growth and the Cost of Copying.

Partial reads and the cost of a single field

A subtler case is a loop that reads one field but with an irregular index, such as a gather over a permutation. Here the layout matters less than the access pattern: if the indices are random over a working set larger than the cache, every access is a miss regardless of layout, and the useful fraction of the line is irrelevant because the line is fetched for one use only. This is the regime where layout changes stop helping and the only remaining lever is reducing the number of independent misses or their dependency structure.

The boundary between the two regimes is the working set size, which is why layout tuning without a working set measurement tends to produce disappointing results. A structure-of-arrays rewrite of a loop whose working set fits in L2 changes nothing, because the misses were not happening. The measurement that distinguishes the cases is described in Working Set Size and the Miss-Rate Cliff.

Alignment, padding, and false sharing

Layout decisions interact with alignment in two ways that are easy to get wrong. The first is padding inside a structure: reordering fields from largest to smallest often removes holes, and a structure with three 8-byte fields, two 4-byte fields, and one 2-byte field can frequently be shrunk by a third without changing any field’s type. The second is the position of a structure within a line: a record that straddles two lines costs two fetches per access instead of one, and a structure whose size is not a divisor of 64 will straddle for some subset of its instances.

The extreme case is a hot field that shares a line with a field written by another thread. Both threads then contend for the same line even though they touch disjoint bytes, and the coherence protocol transfers the line on every write. This is false sharing, and its cost is not bandwidth but serialisation: each transfer is a coherence transaction with a latency in the tens to low hundreds of cycles. Padding a per-thread counter out to a full line is the standard fix, and it is a layout change of exactly the kind described above, applied to the problem of write ownership rather than read volume.

Choosing a layout from the access pattern

The decision procedure is short. Enumerate the loops that touch the structure and the fields each reads. If one loop reads most fields of most records, keep the interleaved layout. If a hot loop reads a small subset, and the working set exceeds the last-level cache, split that subset out. If the working set fits in cache, neither change matters and the simpler layout is correct.

Two numbers make the decision concrete: the useful fraction w / 64 for the interleaved layout, and the stream count for the split layout. A split that raises the useful fraction from 0.2 to 1.0 and keeps the stream count under the prefetcher’s limit is a clear win. A split that raises the fraction but creates twelve streams, or that fragments a single allocation into twelve, may not be.

The last consideration is the one most often skipped: the layout that is fastest for the hot loop is usually not the layout that is cheapest to build and destroy. Construction touches every field, so it prefers interleaving; traversal prefers splitting. Where the two conflict, the resolution is to build into the split form directly rather than to build a record array and convert, since the conversion touches every byte of both layouts and pays the full bandwidth cost of each.