Structure of Arrays vs Array of Structures Benchmark

Topic Overview

Layout Follows Access Pattern

Array of Structures (AoS) stores all fields per object together. Structure of Arrays (SoA) stores each field in its own contiguous array. Game engines and SIMD kernels prefer SoA when loops touch one field across many entities. AoS wins when you always load whole records together.

When Each Wins

Updating positions for 100k particles: SoA lets you vectorize x[], y[], z[] without gathering scattered fields. Printing full records: AoS avoids three pointer chases.

cCopy
Loading…

• SoA improves bandwidth when only one field is hot
• AoS can false-share if threads update different fields in the same struct
• Hybrid layouts (hot SoA, cold AoS) appear in ECS architectures
• Measure the actual loop you ship, not a synthetic mix

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will benchmark AoS vs SoA for a field-heavy update loop and report speedup. This exercise asks you to tie the winner to which fields the inner loop reads.

Your Task

A loop that updates only positions and velocities still drags every field of an array of structures (AoS) through the cache. A structure of arrays (SoA), or a hot/cold split, loads only the bytes the loop touches. Model all three layouts for a particle system, lay them out exactly as a C compiler would, and run the loop's address stream through a small LRU cache to see how many bytes each layout actually fetches.

Input

cCopy
Loading…

Layouts

• AoS: one struct with all fields in declaration order. Each field is aligned to its own size, and the struct size is rounded up to the largest field size. Particle i starts at i * sizeof(struct).
• SoA: one array per field, in declaration order. Each array starts on a cache-line boundary right after the previous one: array f is N * size(f) bytes, rounded up to a whole number of lines.
• split: a hot struct made of the loop's fields (in declaration order) and a cold struct of the rest, both laid out like AoS. Only the hot array is touched.

For each particle i = 0..N-1, the loop touches its fields in the order given. Each layout starts with an empty cache (set-associative, LRU, as in a real L1). Useful bytes = N times the sum of the touched fields' sizes.

Output

cCopy
Loading…

Bytes fetched = misses * LINE. The percentage is used / fetched, rounded half up to 1 decimal with integer arithmetic. The cold struct size is 0 when every field is hot. Errors: field NAME: size must be 1, 2, 4 or 8, loop: unknown field NAME, and run: need fields and a loop.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Compute struct offsets with real C alignment rules, so mixed sizes produce padding.
2. Feed each layout's address stream through the same cache model, and compare misses, not guesses.

Hidden tests cover mixed field sizes with padding, a loop that touches every field (AoS catches up), a single hot field, a small direct-mapped cache where the SoA arrays conflict with each other, and invalid field sizes and names.