Cache and Memory Locality, Data Layout (AoS/SoA)

This chapter explains cache and memory locality and the critical data-layout choice between Array-of-Structs (AoS) and Struct-of-Arrays (SoA).

Why This Matters

Memory access, not instruction count, often dominates performance. How you lay out data determines cache hit rates and therefore speed. AoS vs. SoA is a single decision that can change performance by an order of magnitude.

Prerequisites

• c.cpu.3 — caches and cache lines.

Core Concept

Locality

• Temporal locality: recently accessed data is likely to be accessed again

soon.

• Spatial locality: data near recently accessed data is likely to be

accessed soon.

Caches exploit both. Contiguous, stride-1 access is ideal; large strides waste cache lines.

AoS vs. SoA

For a collection of objects with multiple fields:

• AoS (Array of Structs): struct P { float x, y, z; } points[N];

Each element's fields are contiguous.

• SoA (Struct of Arrays): struct P { float x[N], y[N], z[N]; } points;

Each field is a separate contiguous array.

Examples

AoS

struct Point { float x, y, z; };
struct Point points[N];

for (int i = 0; i < N; i++)
    points[i].x += 1.0f;   /* touches every field (x, y, z) for each i */

SoA

struct Points { float x[N], y[N], z[N]; } pts;

for (int i = 0; i < N; i++)
    pts.x[i] += 1.0f;      /* touches only x[]; y/z stay in cache */

If a loop uses only x, SoA keeps the working set dense and cache-friendly; AoS pulls in unused y/z, wasting bandwidth.

How It Works

When you access pts.x[i], the CPU fetches a cache line of consecutive x values. AoS interleaves y/z between the xs, so the same loop fetches three times as much data for one useful field. SoA gives dense access to the field you actually use.

Variations

Hybrid / blocked layouts

For some algorithms, block/tile data or use a hybrid to balance locality of different access patterns.

Hot/cold splitting

Move rarely used fields into a separate structure so hot fields stay dense.

Common Mistakes

• Always using AoS without considering access pattern.
• Assuming a struct's fields are always accessed together.
• Ignoring alignment/padding when computing layout size.

Undefined Behavior

• None inherent; layout is well-defined. (Packed structs with misaligned

access would be UB, but that is separate.)

Portability

• AoS/SoA are pure C design choices; cache behavior is hardware-specific but

the principle is universal.

Under the Hood

A cache line is ~64 bytes. SoA puts consecutive xs in the same lines; AoS interleaves fields. SIMD also benefits from SoA (contiguous lanes).

Practical Usage

• Choose SoA when a hot loop accesses only a subset of fields.
• Choose AoS when fields are always accessed together.
• Split hot and cold fields for large, long-lived structures.

Exercises

1. Benchmark a loop that touches one field in AoS vs. SoA and compare. 2. Explain why the AoS version fetches more cache lines. 3. Convert a struct-of-structs to SoA for a particle system.

Deep Challenge

Write a small particle-update loop in both AoS and SoA, benchmark with perf stat (cache misses), and explain the difference in terms of cache lines and memory bandwidth.

Related Concepts

• c.cpu.3 — caches.
• c.perf.5 — false sharing.
• c.perf.4 — SIMD.

References

• "What Every Programmer Should Know About Memory" (Ulrich Drepper), Intel/ARM

optimization guides.

Verification

• AoS/SoA locality reasoning is standard. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Cache locality
• [ ] Memory locality
• [ ] AoS vs. SoA
• [ ] Hot/cold splitting

Mastery levels