An algorithm can have the right asymptotic complexity and still make poor use of a processor. Two loops may both perform one operation per record, yet one walks compact contiguous values while the other chases pointers through objects whose mostly unused fields occupy each fetched cache line. The arithmetic count is similar; the amount of data moved and the delay between dependent loads are not.
Data-oriented design starts from that observation. It organizes representation and execution around the operations that dominate a workload, rather than assuming one object shape is equally suitable for every operation. The thesis is not that structures of arrays always beat objects. It is that locality is a property of an access pattern and a layout together. Measure the hot pattern, increase useful work per fetched line, and preserve another representation when different operations need different shapes.
Start With the Access Pattern, Not the Type Diagram
Object-oriented models often group fields because they describe one conceptual entity. That is valuable for ownership and API clarity, but the processor does not fetch concepts. It fetches blocks of nearby bytes through a hierarchy, predicts sequential access, and waits when a needed address depends on a previous load. A layout should therefore be evaluated against a particular loop.
Write down the hot operation before changing storage:
- Which fields does one iteration read and write?
- In what order are records visited?
- How large is the active set relative to the relevant caches?
- Are addresses contiguous, strided, indexed, or pointer-linked?
- Is the loop limited by computation, memory bandwidth, or load latency?
- Does another operation need a conflicting layout?
Suppose a simulation updates positions from velocities for every active particle. The hot loop reads positionX, positionY, velocityX, and velocityY, then writes two positions. Names, colors, ownership metadata, and timestamps are cold for this operation. If every particle object interleaves all those fields, the update moves bytes it will not use. If objects are separately allocated, the collection may also load pointers before reaching payloads.
Temporal locality means data is reused before it leaves a fast level of storage. Spatial locality means nearby bytes are likely to be used soon. They are consequences of execution order. A compact array gives spatial opportunity, but a random permutation can defeat it. Conversely, a small repeatedly traversed object graph can have good temporal locality after warming even if its layout is irregular.
Do not infer the limiting resource from source aesthetics. A contiguous rewrite cannot help much when expensive arithmetic, branch misprediction, locks, or I/O dominate. Use hardware counters where available, plus elapsed time and bandwidth estimates, to test the locality hypothesis.
Count Useful Bytes per Fetched Line
Cache lines are the unit of transfer between several cache levels on common processors, although exact line size and hierarchy are platform properties. The useful question is not merely how many lines exist; it is what fraction of each transferred line the loop consumes before eviction.
Consider an illustrative 64-byte line and a 64-byte particle record. If the update uses four 8-byte numeric fields from that record, at most 32 of the 64 bytes are directly useful to this loop, before considering alignment or write traffic. If the record is 128 bytes because it embeds cold metadata, the loop may touch two lines to obtain the same values. With separate dense arrays for each hot numeric field, every fetched line can contain eight values used by consecutive iterations.
A rough layout efficiency for a loop can be expressed as
This is a diagnostic model, not a direct speedup formula. Hardware prefetching, write allocation, cache reuse, vector width, alignment, translation lookaside buffers, and concurrent traffic all influence actual cost. A low useful-byte ratio supports a layout hypothesis; it does not predict an exact runtime improvement.
Working-set size matters too. A layout difference may be invisible on 1,000 records because both forms remain cached, then become important when millions of records stream from memory. Benchmark across the cardinality transition instead of reporting only one convenient size. Include key distributions: random indexed access has different behavior from a sequential scan over the same arrays.
Indirection consumes locality in two ways. Loading a pointer or reference costs bandwidth, and the target may be unrelated to adjacent targets. Dependent pointer chains are especially difficult to overlap because the next address is unknown until the current node arrives. Arrays of indices can be more compact and permit relocation, but a random index sequence still produces scattered payload access. Layout and visit order must be designed together.
Work Through Array of Structures Versus Structure of Arrays
An array of structures (AoS) stores all fields for record 0, then all fields for record 1. A structure of arrays (SoA) stores one dense array per field. Here is a TypeScript version using typed arrays so numeric storage is explicit:
type Particle = {
positionX: number;
positionY: number;
velocityX: number;
velocityY: number;
color: number;
ownerId: number;
};
function updateObjects(particles: Particle[], deltaSeconds: number): void {
for (const particle of particles) {
particle.positionX += particle.velocityX * deltaSeconds;
particle.positionY += particle.velocityY * deltaSeconds;
}
}
type ParticleColumns = {
positionX: Float64Array;
positionY: Float64Array;
velocityX: Float64Array;
velocityY: Float64Array;
color: Uint32Array;
ownerId: Uint32Array;
};
function updateColumns(particles: ParticleColumns, deltaSeconds: number): void {
const count = particles.positionX.length;
if (
particles.positionY.length !== count ||
particles.velocityX.length !== count ||
particles.velocityY.length !== count
) {
throw new Error('particle columns have different lengths');
}
for (let index = 0; index < count; index += 1) {
particles.positionX[index] =
particles.positionX[index]! + particles.velocityX[index]! * deltaSeconds;
particles.positionY[index] =
particles.positionY[index]! + particles.velocityY[index]! * deltaSeconds;
}
}
The column layout lets the update stream only the four hot arrays; color and ownerId are not touched. Dense homogeneous storage may also make vectorization easier for an optimizing compiler. The example does not claim that this TypeScript loop is universally faster. Runtime object representation, JIT decisions, bounds-check elimination, typed-array semantics, and target hardware all require measurement.
SoA changes invariants. Every column must have the same logical length, and insertion, deletion, and compaction must update all columns consistently. Passing one particle to an API is less natural because its fields live in separate arrays. Stable identity cannot be the array offset if compaction moves records; use an ID-to-index table with generation counters or another stale-handle defense.
AoS remains strong when operations commonly consume most fields of one record, records are individually created and destroyed, or domain behavior is central. A hybrid array-of-structures-of-arrays groups small blocks: each block stores columns for perhaps dozens of records. It preserves vector-friendly local runs while limiting bookkeeping and supporting block-level movement. Hot/cold splitting is another hybrid: keep a compact hot record together and move rarely accessed metadata behind an identifier.
The correct comparison includes total workflow cost. A columnar update that requires expensive conversion before and after every call may lose overall. Keep data in its hot representation across a phase, or batch enough work to amortize transformation.
Change Traversal Order Before Rebuilding Everything
Layout transformations are not the only locality tool. Traversing an existing layout in storage order can produce much of the benefit with less disruption. A row-major matrix stores adjacent columns of one row together. Iterating rows outside and columns inside follows contiguous addresses; reversing the loops visits with a stride equal to row width.
For a matrix with rows by columns elements stored at index row * columns + column, a sequential traversal is:
function sumRows(values: Float64Array, rows: number, columns: number): number {
if (values.length !== rows * columns) throw new Error('invalid matrix shape');
let total = 0;
for (let row = 0; row < rows; row += 1) {
const start = row * columns;
for (let column = 0; column < columns; column += 1) {
total += values[start + column]!;
}
}
return total;
}
Some algorithms need both row and column reuse, so neither complete traversal order is ideal. Blocking, or tiling, partitions work into submatrices sized so repeatedly used pieces remain in cache during the inner computation. Matrix multiplication is the classic example, but the principle applies to image filters, spatial processing, and joins: consume a manageable tile thoroughly before moving on.
Choose tile size empirically and account for all simultaneously active arrays. A tile that fits one input but not the second input and output does not fit the working set. Hard-coding one size for every architecture can regress another machine; provide conservative defaults and tune only where deployment hardware is controlled.
Sorting work can improve locality when semantic order is flexible. Grouping requests by shard, entity index, or spatial cell turns random access into runs. The sort has a cost and adds delay, so it is suitable when a batch is already available and the saved work exceeds reordering overhead. Preserve externally visible ordering through sequence IDs when required.
Batch Work and Keep Hot Loops Simple
Batching amortizes fixed costs and exposes a longer regular loop to the processor. Instead of resolving one identifier, updating one record, and emitting one result repeatedly, collect a bounded batch, resolve identifiers together, process dense indexes, then restore result order. Database and network batching have additional semantics, but within a process the same principle reduces call overhead and improves reuse.
Archetype or component grouping applies this to heterogeneous entities. Rather than store every possible component in one sparse object, group entities that share the fields needed by a system. A movement phase scans groups containing position and velocity; a rendering phase scans position and visual data. Moving an entity between groups costs copying, so the design works best when component changes are less frequent than scans.
Keep the hot loop free from unpredictable side paths. First classify or partition records, then run specialized loops for common cases. This can improve instruction behavior as well as data locality. However, duplicating business logic across specialized paths creates correctness risk. Isolate the transformation and retain one source of truth for semantics, with tests comparing specialized and reference implementations.
Prefetchers favor regular streams but cannot rescue every pattern. Software prefetching is platform-specific and can waste bandwidth or evict useful data if issued too early. Compressing indexes from 64 to 32 bits can increase useful density when the domain bound permits it, but overflow checks become part of the invariant. Representation decisions should make bounds explicit rather than relying on current small data.
Multithreaded batching introduces write ownership. Threads updating different fields on the same cache line can cause coherence traffic even though there is no logical data race, a phenomenon commonly called false sharing. Partition output so workers write disjoint line ranges, and measure padding carefully because added space can damage capacity locality. Executor design is separate; the data contract should simply expose partitions that do not overlap.
Account for Tradeoffs and Failure Modes
Data-oriented layouts exchange some local simplicity for throughput on specific paths. The costs are real:
- Parallel arrays can drift in length or index meaning unless mutation is centralized.
- Compaction improves density but invalidates raw indexes and may make deletion expensive.
- Duplicating read-optimized representations requires a synchronization rule and memory budget.
- Sorting or batching improves locality while increasing per-item waiting time.
- Compressed fields save bandwidth but add encode/decode work and may lose precision.
- Specialized layouts can leak hardware assumptions into domain code and complicate debugging.
- Optimizing a cold scan adds complexity without changing user-visible performance.
Encapsulate representation behind operations that preserve its invariants. A ParticleStore can own all columns, allocate slots, map stable IDs, compact storage, and expose a narrowly scoped iteration view. Do not return columns that callers can resize independently. Validate lengths and generation values at development boundaries.
Sometimes two representations are justified. A transactional object model can remain authoritative while a compact snapshot serves analytics or simulation. Define whether the snapshot is immutable, incrementally updated, or rebuilt at phase boundaries. Measure synchronization and peak-memory cost. “Denormalize for speed” without freshness and ownership rules creates subtle correctness bugs.
Locality optimizations can also move pressure elsewhere. Dense compaction consumes CPU, a larger batch raises peak memory, and a columnar format may worsen individual point lookups. Evaluate latency distribution, throughput, memory, and maintenance burden together. A change that improves a synthetic scan but delays interactive updates may be wrong for the product.
Benchmark the Memory Hypothesis Honestly
Design the benchmark around a falsifiable claim: “For particle counts larger than the last-level cache working set, separating hot numeric columns will reduce bytes moved per update and lower update time without increasing full-frame memory beyond the budget.” Then choose data sizes below, around, and above the expected cache transition.
Run equivalent semantics. Initialize both layouts from the same deterministic values, apply the same number of updates, and compare checksums within an appropriate floating-point tolerance. Include conversion time if the real workflow converts every frame; exclude it only if the representation persists across many updates. Include allocation and compaction phases when they occur on the critical path.
For a JIT runtime, warm each implementation, avoid interleaving them in one contaminated process unless the harness is designed for it, consume outputs, and inspect optimization or deoptimization when available. Randomize process order across repeated rounds. Pin runtime, flags, CPU limits, and power policy. Report distributions and raw samples, never only the fastest run.
Use counters to test mechanism where the platform permits: cache misses, instructions, cycles, memory bandwidth, branch misses, and vector instructions. Counter names and interpretation vary by processor, virtualization can restrict them, and multiplexed events add error. Elapsed time remains the outcome; counters explain why it changed. A lower miss count with unchanged time may mean misses were overlapped or another resource now dominates.
Guard against artificial locality. A microbenchmark that repeats the same tiny array measures a permanently hot working set. One that randomizes every access may defeat the production’s natural ordering. Reproduce active-set size, update/read ratio, sparsity, deletion pattern, and batch size. Label all example numbers as illustrative unless they come from a documented run.
Verify Correctness and Operational Value
Representation changes deserve stronger correctness tests than ordinary refactoring because indexing errors can silently associate fields with the wrong entity. Build a simple reference implementation and compare it with the optimized layout over generated operation sequences: insert, update, remove, compact, and resolve stable IDs. Assert column lengths, free-list integrity, generation checks, and deterministic iteration where promised.
Test boundaries around empty storage, one record, capacity growth, maximum index, deleted handles, and movement between groups. For matrix or tiled algorithms, compare small random shapes with a straightforward implementation, including dimensions that are not multiples of tile size. Run sanitizers or bounds-checking modes in languages that provide them.
At rollout, compare complete-workflow metrics on a canary: time in the target phase, total frame or request latency, CPU per completed unit, memory, allocation, and correctness counters. Watch cold operations that use the same data. Keep a switch to use the reference path for diagnosis until confidence is established, but avoid maintaining two mutable implementations indefinitely without equivalence tests.
Encode a stable regression check after accepting the change. Structural checks can assert compact field widths and bounded columns; a controlled benchmark can detect a major traversal regression. Production telemetry should verify that the optimized phase still matters as workloads evolve.
The enduring method is to follow the data. Name the hot operation, calculate what bytes it actually uses, align layout and traversal so nearby fetched data becomes useful work, and batch enough execution to preserve reuse. Then measure the mechanism and the full workflow under representative cardinality. Data-oriented design is not a rejection of good domain models. It is the recognition that one semantic entity may need more than one physical shape when performance depends on how its data moves.