← Labscache-03Memory hierarchy●●○○

AoS vs SoA — line utilization decides bandwidth (and a trap)

cache/03_aos_soa.cneeds: tools/bench.h, tools/pin.sh, perf2 steps

0/2 steps

what this lab teaches

The same 8M records as an Array of Structs (32-byte Order) and as a Struct of Arrays (one array per field), under three access patterns: field sum ONE field across all records -> SoA should win all-fields touch every field of every record -> both stream everything random read whole records in random order -> AoS should win plus a trap that catches most people the first time: a loop that "should be bandwidth-bound" is actually bound by a floating-point dependency chain, and the layout change cannot show its full benefit until the compiler is allowed to reassociate.

evidence to leave with

SoA 2x on a field scan, 4.3x with -ffast-math (addsd chain proven in asm); AoS 2x on random records

first, get the code

run this

$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs

then build it

run this

$ cd cache && ./build.sh

produces bin/03_aos_soa [field|all-fields|random|all]

walk it, one step at a time

run this

$ ../tools/pin.sh -q ./bin/03_aos_soa

what it printed on the machine that wrote this lab

AoS: sum one field             17.58 ms   2.096 ns/rec      3.8 GB/s useful
SoA: sum one field              8.78 ms   1.047 ns/rec      7.6 GB/s useful
AoS: touch all fields          27.19 ms   3.241 ns/rec      6.5 GB/s useful
SoA: touch all fields          15.50 ms   1.847 ns/rec     11.4 GB/s useful
AoS: random record            157.53 ms  18.779 ns/rec      1.1 GB/s useful
SoA: random record            334.67 ms  39.896 ns/rec      0.5 GB/s useful
("useful GB/s" counts only the bytes the loop needed, not the lines it
 actually moved.)

run this

$ ../tools/pin.sh -q perf stat -e cycles:u,instructions:u,L1-dcache-loads:u,L1-dcache-load-misses:u ./bin/03_aos_soa field

what it printed on the machine that wrote this lab

       225,439,202      cpu_core/cycles/u
       403,963,143      cpu_core/instructions/u          #    1.79  insn per cycle
        16,926,793      cpu_core/L1-dcache-loads/
         1,510,460      cpu_core/L1-dcache-load-misses/  #    8.92% of all L1-dcache accesses

how to read it

field: AoS reads 32-byte records to use 8 bytes: 4x the line traffic. 8M x 32 B in 17.6 ms = 15.5 GB/s of lines: AoS is at this laptop's bandwidth ceiling (lab 01 measured ~15 GB/s). SoA moves 4x fewer bytes, yet is only 2x faster, 1.05 ns per record. Why not 4x? THE TRAP: look at the SoA loop's asm: addsd (%rdi,%rax,8),%xmm0 ; addsd 0x8(%rdi,%rax,8),%xmm0 ; ... (8 per iteration) Eight scalar double adds into ONE register: a dependency chain. Adding doubles in a different order changes rounding, so without permission the compiler must keep the program order, and the loop is bound by the FP-add latency (2 cycles on this core: 1.05 ns), not by memory.

run this

$ clang -O2 -g -ffast-math 03_aos_soa.c -o bin/03_aos_soa.fast && ../tools/pin.sh -q ./bin/03_aos_soa.fast field

what it printed on the machine that wrote this lab

AoS: sum one field             17.26 ms   2.057 ns/rec      3.9 GB/s useful
SoA: sum one field              4.03 ms   0.481 ns/rec     16.6 GB/s useful

With reassociation allowed the loop becomes packed `addpd` into several accumulators, and SoA now runs at 16.6 GB/s useful: the full 4.3x that the layout promised. AoS did not move: it was bandwidth-bound already. Lesson: a layout change only pays when the loop is bound by the thing the layout fixes. Check what the loop is bound by first (codegen lab 02 shows the -Rpass remarks and the pragma that allows reassociation for one loop instead of the whole program). all-fields: both layouts read every byte. SoA still wins 1.75x: four sequential streams with unit stride vectorize and prefetch well; AoS handles 32-byte structs with mixed types, less vectorizable. random: AoS 18.8 ns, SoA 39.9 ns. One random record is ONE line in AoS and FOUR lines (four arrays) in SoA: SoA loses 2x. Random access by record wants the record together.

the rules

L1. Lay data out for the loop that dominates: scans of a few fields -> SoA; random access to whole records -> AoS; both -> AoSoA (blocks of 8-16 records in SoA form) or a hot/cold split (hot fields in a compact array, cold fields elsewhere). L2. Before crediting a layout change, confirm the loop is memory-bound (bytes moved / time near the machine's bandwidth). If it isn't, find the real bound: an FP chain, a branch, a division. L3. "Useful bytes / time" is the honest bandwidth metric; lines moved / time is the ceiling. The gap between them is your waste.

take it further

1. Add an AoSoA layout (struct of 8-record blocks) and run all three patterns: it should sit between the two extremes everywhere. 2. Make `price` a float and `qty` an int16_t: the record shrinks to 24 or 16 bytes. Re-measure the AoS field sum: line traffic drops with size. 3. `perf stat -e L1-dcache-load-misses:u` on `random` for both layouts: SoA should show ~4x the misses per record. ============================================================

read the source · cache/03_aos_soa.c

#include "../tools/bench.h"
#define N (8u << 20)                                   /* 8M records */
typedef struct { uint64_t id; double price; int32_t qty; uint8_t side; uint8_t pad[11]; } Order;   /* 32 bytes */
typedef struct { uint64_t *id; double *price; int32_t *qty; uint8_t *side; } Book;                /* SoA */

__attribute__((noinline)) static double aos_sum_price(const Order *o, size_t n) { double s = 0; for (size_t i = 0; i < n; i++) s += o[i].price; return s; }
__attribute__((noinline)) static double soa_sum_price(const double *p, size_t n) { double s = 0; for (size_t i = 0; i < n; i++) s += p[i]; return s; }
__attribute__((noinline)) static uint64_t aos_touch_all(Order *o, size_t n) { uint64_t s = 0; for (size_t i = 0; i < n; i++) { o[i].qty += 1; o[i].price *= 1.0001; s += o[i].id ^ o[i].side; } return s; }
__attribute__((noinline)) static uint64_t soa_touch_all(Book *b, size_t n) { uint64_t s = 0; for (size_t i = 0; i < n; i++) { b->qty[i] += 1; b->price[i] *= 1.0001; s += b->id[i] ^ b->side[i]; } return s; }
__attribute__((noinline)) static uint64_t aos_random(const Order *o, const uint32_t *ix, size_t n) { uint64_t s = 0; for (size_t i = 0; i < n; i++) { const Order *r = &o[ix[i]]; s += r->id + (uint64_t)r->qty + (uint64_t)r->side + (uint64_t)r->price; } return s; }
__attribute__((noinline)) static uint64_t soa_random(const Book *b, const uint32_t *ix, size_t n) { uint64_t s = 0; for (size_t i = 0; i < n; i++) { uint32_t k = ix[i]; s += b->id[k] + (uint64_t)b->qty[k] + (uint64_t)b->side[k] + (uint64_t)b->price[k]; } return s; }

static void row(const char *name, uint64_t ns, size_t n, size_t bytes_touched) {
    printf("%-26s %9.2f ms  %6.3f ns/rec  %7.1f GB/s useful\n", name, (double)ns / 1e6, (double)ns / (double)n, (double)bytes_touched / ((double)ns / 1e9) / 1e9);
}
int main(int argc, char **argv) {
    const char *mode = argc > 1 ? argv[1] : "all";
    Order *o = (Order *)malloc(N * sizeof *o);
    Book b = { malloc(N * 8), malloc(N * 8), malloc(N * 4), malloc(N) };
    uint32_t *ix = (uint32_t *)malloc(N * 4);
    uint64_t seed = 42;
    for (size_t i = 0; i < N; i++) {
        o[i].id = i; o[i].price = 100.0 + (double)(i % 1000); o[i].qty = (int32_t)(i % 7); o[i].side = (uint8_t)(i & 1);
        b.id[i] = i; b.price[i] = o[i].price; b.qty[i] = o[i].qty; b.side[i] = o[i].side;
        ix[i] = (uint32_t)(bench_rand(&seed) % N);
    }
    int all = !strcmp(mode, "all"); uint64_t t0; double d; uint64_t u;
    if (all || !strcmp(mode, "field")) {
        t0 = bench_ns(); d = aos_sum_price(o, N); BENCH_KEEP(d); row("AoS: sum one field", bench_ns() - t0, N, N * 8);
        t0 = bench_ns(); d = soa_sum_price(b.price, N); BENCH_KEEP(d); row("SoA: sum one field", bench_ns() - t0, N, N * 8);
    }
    if (all || !strcmp(mode, "all-fields")) {
        t0 = bench_ns(); u = aos_touch_all(o, N); BENCH_KEEP(u); row("AoS: touch all fields", bench_ns() - t0, N, N * 21);
        t0 = bench_ns(); u = soa_touch_all(&b, N); BENCH_KEEP(u); row("SoA: touch all fields", bench_ns() - t0, N, N * 21);
    }
    if (all || !strcmp(mode, "random")) {
        t0 = bench_ns(); u = aos_random(o, ix, N); BENCH_KEEP(u); row("AoS: random record", bench_ns() - t0, N, N * 21);
        t0 = bench_ns(); u = soa_random(&b, ix, N); BENCH_KEEP(u); row("SoA: random record", bench_ns() - t0, N, N * 21);
    }
    return 0;
}

◇

Finish the lab: write the evidence note

A lab is done when you can say what it showed on your machine — not when you have read it.