Array of Structs or Struct of Arrays

Two arrays can hold the same information and behave completely differently under the same loop. One is an array of records; the other is one array per field. The information is identical, the element count is identical, and the number of cache lines touched per iteration differs by a factor equal to the number of fields the loop ignores. Deciding between them is a question about which access pattern dominates, not about which layout is better in general.

Stride decides what a cache line delivers

Consider a record of three double fields plus a 32-bit identifier. The members occupy 28 bytes (24 + 4), and the struct’s alignment is 8 because its largest member is a double, so its size must be a multiple of 8; the compiler rounds it up to 32 with 4 bytes of trailing padding. An array of 1000 such records occupies 32000 bytes, 500 cache lines of 64 bytes each. A line therefore spans exactly two records.

A loop that sums the first field touches every line and uses 16 of each line’s 64 bytes — two doubles, one from each of the two records the line covers. The other 48 bytes are fetched and discarded. If the loop instead walks a separate array of 1000 doubles, the same 8000 bytes of useful data occupy 125 lines, and each line’s 64 bytes are all useful. The ratio is four to one in bytes fetched, and on a memory-bound loop that ratio is the runtime.

Struct-of-arrays is not a free transformation. Splitting changes the unit of access from a record to a field, so any operation that needs several fields of one record now issues several loads from different arrays. Those loads are independent and can issue in parallel, but each one touches a different cache line, so a loop that reads all fields of one record at a time now touches k lines per record instead of sharing one line between 64 / sizeof(record) records. For a record of four 8-byte fields, the array-of-structs form serves two records per line while the split form needs four lines to assemble one record: eight times the lines for the same total work.

The rule that follows is narrow but reliable. Layout should match the fields the hot loop actually touches, and the hot loop should be identified before the layout is chosen. The stride arithmetic that makes a record’s fields land where they do is the same arithmetic that turns two subscripts into one offset, as described in Row-Major Layout and the Address Arithmetic Behind Indexing.

Access pattern	Array of structs	Struct of arrays
Read all fields of one record	one line per record group	one line per field per record
Read one field of every record	full record fetched, most discarded	only the field’s bytes fetched
Insert or delete one record	one shift of whole records	one shift in each array
Vectorize the field operation	needs gather or shuffle	contiguous, directly loadable

Padding is part of the layout

The C standard leaves the bytes between a struct’s members unspecified, and the alignment rules typically insert padding so each member begins at an address that is a multiple of its alignment. A struct declared as char tag; double value; has 7 bytes of padding after tag on the common ABIs, so its size is 16 rather than 9. Reordering the members to double value; char tag; gives 16 as well because the struct’s own alignment is 8 and its size must be a multiple of it, but a struct of double a; double b; char tag; is 24 bytes with 7 wasted, while char tag; double a; double b; is also 24. Sorting members by decreasing alignment moves padding from between members to the end; it reduces the total only when the original ordering had interior padding that the sort removes, and it leaves the total unchanged when the padding was going to fall at the end anyway, as in these two 24-byte structs.

Padding inflates the stride, which inflates the number of lines a scan of 1000 records touches. The example above pays 32 bytes per record for 28 bytes of members, so the array is 14 percent larger than its data. Reordering members can move padding but cannot always remove it: a char followed by a double needs 7 bytes of padding somewhere before the double, because the double must begin at an address that is a multiple of 8, and the struct’s size must be a multiple of its own alignment so that an array of the struct keeps every element aligned. A struct of double a; double b; char tag; and one of char tag; double a; double b; are both 24 bytes; the padding has moved from the middle to the end, and the total is unchanged.

The size of the stride also decides whether an access straddles a line boundary. A record whose size divides 64 — 8, 16, 32, 64 bytes — starts every element at a line-relative offset that repeats, and never splits a single element across two lines. A 24-byte record splits some of them: with records starting at offsets 0, 24, 48, 8, 32, 56 within successive lines, the record at offset 48 spans bytes 48 through 71 of that line and therefore two lines, and the record at 56 does the same in the next. Two records in every eight straddle. The scan does not fetch extra bytes, because the neighbouring record uses the same two lines, but each straddling access consumes two cache ports instead of one and the line count in flight is momentarily higher. The effect is small next to the padding’s effect on total bytes, which is why record size is usually chosen for alignment and packing rather than for straddling.

Vectorization wants contiguity

A SIMD register on x86-64 with AVX2 is 256 bits, holding four doubles or eight 32-bit integers. A vector load instruction requires its operand to be contiguous in memory. Loading field x from four consecutive array-of-structs records requires either four scalar loads and a shuffle into the register, or a gather instruction whose per-element latency on typical hardware is several times that of a contiguous load.

With the split layout, field x of four consecutive records is exactly 32 contiguous bytes, aligned if the array is aligned, and one load instruction suffices. This is the mechanical reason numerical kernels that operate on one coordinate at a time prefer parallel arrays, and why the classic BLAS interface takes separate vectors rather than an array of vector types.

The split also helps when the field’s width differs from the record’s. A struct holding three 32-bit counters and one 64-bit accumulator has a 24-byte stride with 8 bytes of padding if the accumulator is last, and splitting lets the three counters form a contiguous array of 32-bit values, four bytes per record, which a 256-bit AVX2 register loads eight at a time with a plain vector load; the accumulator gets its own array of 64-bit values, four per register.

/* Split layout: one array per field, each independently vectorizable. */
typedef struct {
    size_t n;
    float *x, *y, *z;      /* each length n, allocated separately */
} points_soa;

float dot_pair(const points_soa *p, size_t i, size_t j) {
    return p->x[i] * p->x[j] + p->y[i] * p->y[j] + p->z[i] * p->z[j];
}

The indirection through three pointers costs one extra load per array base, amortized over the whole loop. It also costs the compiler’s ability to prove the arrays do not alias unless the pointers are declared restrict or the compiler can see the allocation. Aliasing analysis is what decides whether the loop vectorizes at all, so the split layout’s advantage is contingent on telling the compiler the arrays are disjoint.

Where the split hurts

The costs are real and appear in three places.

Allocation and ownership. Splitting one allocation into k allocations means k failure paths, k sizes to track, and k pointers to free. A single array of records is one allocation and one free. For a container that grows, the split layout either allocates k buffers in lockstep, doubling all of them together, or lets them diverge, which produces inconsistent capacities and a much harder invariant. Most general-purpose containers therefore store records, and the split layout appears in domain-specific code where the field count is fixed.

Insertion and removal. Removing record i from an array of records shifts (n − i − 1) * sizeof record bytes once. Removing it from a split layout shifts the same number of elements in each of k arrays, touching k separate memory regions. The total bytes moved is similar; the number of distinct streams is larger, and each shift has its own loop overhead.

Locality of one record. Any operation that walks a linked structure or follows a reference to a record now needs several loads to assemble the record. If the record is a node in a graph or a tree, the split is usually wrong, because the access pattern is “one node, all fields”.

The hybrid: hot fields out, cold fields in

The layouts are not exclusive. A common arrangement keeps the fields the scan touches in parallel arrays and the remaining fields in a separate array of records indexed by the same position. The scan reads only the hot arrays; code that needs the full record assembles it from both. This is the same partition as a column store’s hot and cold columns, applied at the granularity of a struct.

The partition has to be stable. Moving a field between the hot and cold side changes the layout of every accessor, so it is a change to the interface, not an internal detail. In a codebase where the layout is private, the partition can be tuned against the actual access pattern; where the layout is exposed as a public struct, it is effectively frozen.

Measuring the choice honestly

The comparison above is about bytes fetched and instructions issued, both of which can be reasoned about from the record size and the loop. Converting that reasoning into a runtime claim requires measurement, and measurement of memory-bound code is easy to get wrong: the working set must exceed the last-level cache for the bandwidth difference to appear, the array must be aligned so that no access straddles unnecessarily, and the loop must not be optimized away. A working set that fits in L2 will show little difference between the layouts, because both are served from cache and the byte-count argument no longer governs; the cache, prefetch and page behaviour that decides this is set out in Sequential Scans, Hardware Prefetch, and the Page Walk.

The one prediction that survives without measurement is directional: a loop that uses a strict subset of each record’s fields fetches fewer bytes from a split layout, in proportion to the fraction of the record the loop uses. Everything else — how much of that saving reaches the clock — depends on whether the loop was bound by memory traffic in the first place. The same argument about bytes per line recurs when the element size is not a whole number of bytes, in Bit-Packed Integer Arrays and Vectorized Decoding, where the packing is chosen to make every byte in a line useful.