Week 2 — Cache Effects in Particle Simulation

A hands-on investigation of Array of Structures (AoS) vs Structure of Arrays (SoA) memory layouts, and how access patterns interact with CPU cache behavior.

Setup

• Particle fields: x, y, vx, vy (all float) — 16 bytes per particle
• Workload: move each particle by its velocity, bounce off a 1000×1000 box
• Compiler: g++ -O2 -std=c++23
• Timing: std::chrono::steady_clock (monotonic, correct choice for measuring elapsed durations — high_resolution_clock is not guaranteed monotonic and is meant for timestamps, not interval measurement)
• Metric: particle-updates/sec = (particle count × steps) / elapsed seconds

Two variables were tested independently:

1. Layout: AoS (std::vector<Particle>) vs SoA (four parallel std::vector<float>)
2. Access pattern: fused (one pass touching all 4 fields) vs split (two passes, one for x/vx, one for y/vy)

Results

All numbers in millions of updates/sec.

Fused update (touches x, y, vx, vy every pass)

Particles	AoS	SoA
100,000	497	313
1,000,000	359	313

Split update (separate x-pass and y-pass)

Particles	AoS	SoA
100,000	304	301
1,000,000	222	282

Findings

1. There is no universal winner — layout choice changes what you're bottlenecked by.

When every pass needs every field (fused update), AoS wins at both scales. A Particle is 16 bytes, so 4 particles fit in one 64-byte cache line — a single fetch delivers everything the loop needs. SoA has no similar advantage here: it still touches all 4 arrays per iteration, but now as 4 separate memory streams instead of 1, which costs more instructions and address calculations even when everything is cache-resident.

2. AoS has a cache cliff. SoA is comparatively flat.

Going from 100k to 1M particles (1.6 MB → 16 MB of data), AoS's throughput drops ~28% in the fused case. SoA barely moves (313M → 313M). This is because AoS's cost structure is "cheap when hot, expensive when cold" — the whole 16-byte particle either arrives in one fast fetch or one slow ~100+ cycle trip to RAM, with almost nothing in between. SoA's cost is dominated by fixed per-iteration overhead (4 independent streams) that's present whether the data is hot or cold, so it never had as far to fall — helped further by modern CPUs overlapping multiple in-flight cache misses across independent streams (memory-level parallelism).

3. Splitting a full-field update into per-field passes hurts everyone, but hurts AoS far more.

Comparing fused vs. split at 1M particles:

	Fused	Split	Change
AoS	359M	222M	−38%
SoA	313M	282M	−10%

Splitting means doing two full traversals instead of one, which is inherently more work — both layouts get slower. But AoS degrades much more severely, because every split pass over AoS still drags unused fields (y/vy during the x-pass, and vice versa) into cache for nothing, and pays for it twice across two passes. SoA was already only fetching what each pass needed, so splitting costs it little beyond the unavoidable second traversal.

4. At small scale (100k), the two layouts converge regardless of access pattern.

When the whole dataset fits comfortably in cache, thrashing isn't happening either way, so the "wasted bytes per fetch" argument barely matters — see how close AoS and SoA are at 100k in the split case (304M vs 301M). The gap between layouts only opens up once the data exceeds cache capacity.

Practical takeaway

• Use AoS when a single operation needs every field of an object and your data comfortably fits in cache.
• Use SoA when different passes need different subsets of fields, or when your dataset is large enough to blow past cache regardless — it degrades more gracefully under both memory pressure and access-pattern fragmentation.
• Compiler optimization level (-O2/-O3 vs unoptimized) had a far bigger effect on throughput than layout choice did in this experiment — always benchmark with optimizations on, and keep flags consistent across comparisons.

Environment caveats

• Timed on a single machine/run; no warmup discard, no multiple trials averaged.
• No cache-miss counters were measured directly (e.g. via perf stat on Linux) — conclusions here are inferred from throughput scaling, not measured cache miss rates directly. That's a natural next step for more rigorous evidence.

Next steps

• Measure real cache-miss counts with perf stat -e cache-misses,cache-references
• Push particle count further to find where SoA's own throughput starts to bend
• Render 1M particles live with SDL2/Raylib (stretch goal)