Array of Structs, or Struct of Arrays?
The same particles can be one array of records or several parallel arrays of fields. Which is faster depends entirely on whether your loop reads most fields of a few records, or one field of many — and the difference is how much of each cache line you actually use.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Array of structs: fetch everything, use a little
In the array-of-structs layout, each particle's fields sit adjacent to one another and particles follow one after the next. A loop that reads every field of each particle — an integration step updating position from velocity — is ideally served: everything it needs arrives together and every fetched byte is used.
A loop that reads only one field is served badly. Summing every particle's x coordinate touches four bytes from each 16-byte record, so three quarters of every cache line fetched is discarded. The memory system does the same work either way; the useful fraction is what changes.
The layout below shows one cache line under this arrangement for a loop that only wants x.
Sixteen of sixty-four bytes carry data the loop wants. The scan pays four times the memory traffic it needs, and only four x values are available per line for vectorising.
Struct of arrays: fetch exactly what the loop reads
In the struct-of-arrays layout, all x values are contiguous, all y values are contiguous, and so on. The same x-summing loop now uses every byte of every line it fetches — sixteen values per line instead of four, so a quarter of the memory traffic for the same result.
The second benefit is vectorisation. Sixteen consecutive floats can be loaded into vector registers directly, so the loop can process several elements per instruction. In the array-of-structs layout the x values are strided rather than contiguous, which either prevents vectorisation entirely or forces expensive gather operations — see Auto-Vectorization: Verify, Do Not Assume.
The cost is symmetrical. A loop that needs all four fields of one particle now touches four separate arrays, so it fetches four cache lines instead of one and loses the locality the record layout provided. Neither arrangement is universally better; each is optimal for a different access pattern.
Every byte fetched is a value the loop consumes, and sixteen contiguous floats are directly loadable into vector registers.
Choosing, and the middle ground
The decision rule is simple once stated: lay data out along the axis you iterate. If loops sweep many entities touching few fields, use struct of arrays. If loops touch one entity and use most of its fields, use array of structs. If both patterns exist, the hot one wins, and if they are equally hot you may need both representations or a hybrid.
The common hybrid is to split hot fields from cold ones: keep the few fields that hot loops read in one dense array and move the rest into a parallel structure. This captures most of the benefit without the full ergonomic cost of decomposing every field, and it is often the right pragmatic answer.
This is the same reasoning that produces columnar storage in analytical databases. A query reading two columns of a hundred-column table should not pay to fetch the other ninety-eight, which is exactly the array-of-structs problem at disk scale — and the same solution applies. Transactional workloads reading whole rows favour row storage for the same reason array-of-structs favours whole-record access.
| Access pattern | Better layout | Real-world instance |
|---|---|---|
| Many entities, few fields each | Struct of arrays | Columnar analytics storage, SIMD physics |
| One entity, most of its fields | Array of structs | Row-oriented OLTP, object-per-entity code |
| Both, one clearly hotter | Optimise for the hot one | Hot/cold field splitting |
| Both, equally hot | Hybrid or duplicate representation | Materialised views, dual storage |
| Vectorising a per-field computation | Struct of arrays | Contiguous lanes without gathers |
| Frequent insertion and deletion of entities | Array of structs | Keeping parallel arrays in sync is error-prone |
Key points
- A cache line is fixed size; the layout decides what fraction of each fetched line the loop actually uses.
- Array of structs suits loops that touch most fields of one entity; struct of arrays suits loops sweeping one field across many.
- Struct of arrays also enables straightforward vectorisation, because the values a loop wants are contiguous.
- The rule is to lay data out along the axis you iterate, and to optimise for the hot loop when both patterns exist.
- Columnar versus row-oriented database storage is the same trade-off at a different scale.
Struct Layout & Padding
Change an input and watch which number moves — and which one refuses to.
Each field must sit at an address that is a multiple of its size, so the compiler inserts padding to get there. Twenty-four bytes to hold fourteen bytes of data, and in an array of a million records that is ten megabytes of nothing.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Loop → address stride: array of structs strides by the record size; struct of arrays strides by the field size.
- 2Stride → cache lines: a larger stride means fewer useful elements per fetched line.
- 3Line → useful bytes: the ratio of field size to record size sets the fraction of each line the loop consumes.
- 4Contiguity → vector loads: struct of arrays presents consecutive values that load directly into vector registers; strided fields require gathers or prevent vectorisation.
- 5Bandwidth → throughput: for a bandwidth-bound scan, throughput scales roughly with the useful fraction of each line.
- • "Struct of arrays is the fast layout." It is faster for field-wise sweeps and slower for whole-entity access. Neither is universally better.
- • "The compiler will transform this for me." Some compilers can perform limited structure splitting, but it is fragile and not something to rely on.
- • "This is a micro-optimisation." It changes memory traffic by an integer factor on large scans, which is a first-order effect for anything data-heavy.
Consequences, controls and cost
- • A field-scanning loop over array-of-structs data can move several times the memory it needs.
- • Vectorisation frequently fails to apply to array-of-structs code, or applies with expensive gather instructions.
- • Converting layout can produce large speedups with no change to the algorithm, which makes it easy to overlook when profiling by function.
- • Identify the hottest loop and lay the data out along the axis it iterates.
- • Split hot fields from cold ones as a lower-cost middle ground when full decomposition is too invasive.
- • Prefer struct of arrays for numeric data you intend to vectorise.
- • Keep array of structs where entities are created and destroyed frequently, since parallel arrays must be kept consistent.
- • Compute the useful fraction directly: field size divided by record size gives the share of each line the scan consumes.
- • Measure cache misses and achieved bandwidth for the hot loop before and after converting the layout.
- • Check whether the loop vectorised, using compiler optimisation reports rather than assuming it did.
- • Struct of arrays fragments an entity across several arrays, which hurts readability and makes creation and deletion more error-prone.
- • Maintaining two representations doubles memory and introduces a synchronisation obligation.
- • Hot/cold splitting adds an indirection for cold-field access, which is fine until a formerly cold field becomes hot.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDUses a 64-byte line and a 16-byte record for the arithmetic. Line size is MICROARCH-SPECIFIC and record size depends on the ABI's padding rules; the ratio argument is unaffected.