Cache-aware struct benchmarks: pointer-chasing staircase & AoS vs SoA

README.md

Cache-Aware Struct Benchmarks

Benchmarks demonstrating how struct size and memory layout affect performance due to CPU cache behavior. Companion code for the blog post Every byte matters.

Benchmarks

1. Pointer-Chasing (cache staircase)

Measures random-access latency as the working set grows past L1d → L2 → L3 → DRAM. Nodes are wired in a random permutation to defeat the hardware prefetcher.

bash run.sh          # runs benchmark, writes results.csv
python3 plot.py      # generates cache_staircase.png

2. AoS vs SoA

Compares Array-of-Structs vs Struct-of-Arrays when reading a single uint8_t field (like is_alive) across 1M items. Shows up to 31x speedup for SoA at large struct sizes.

bash run_aos_soa.sh      # runs benchmark, writes aos_soa_results.csv
python3 plot_aos_soa.py  # generates aos_vs_soa.png

Requirements

• GCC
• Python 3 with matplotlib (python3 -m pip install matplotlib)

System tested on

• Intel Core Ultra 7 165U
• L1d: 35 KiB/core, L2: 2 MiB/core-pair, L3: 12 MiB shared
• Cache line: 64 bytes, Page size: 4096 bytes

aos_soa.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

/*
 * AoS vs SoA benchmark.
 *
 * Compares iterating one field across 1M items when stored as:
 *   - Array of Structs (field buried in a large struct, strided access)
 *   - Struct of Arrays (field packed contiguously)
 *
 * Usage: ./aos_soa <struct_size_bytes>
 *
 * The "field of interest" is always a uint8_t (like is_alive) at offset 0.
 * struct_size controls how much padding follows (simulating a real struct).
 * SoA layout packs just the uint8_t fields contiguously.
 */

#define NUM_ITEMS (1 << 20)  /* 1M items */
#define NUM_ITERS 10
#define FIELD_SIZE 1

int main(int argc, char **argv)
{
    if (argc != 2) {
        fprintf(stderr, "usage: %s <struct_size>\n", argv[0]);
        return 1;
    }

    size_t struct_size = (size_t)atol(argv[1]);
    if (struct_size < FIELD_SIZE) {
        fprintf(stderr, "struct_size must be >= %d\n", FIELD_SIZE);
        return 1;
    }

    /* --- AoS layout --- */
    size_t aos_total = (size_t)NUM_ITEMS * struct_size;
    char *aos = (char *)malloc(aos_total);
    if (!aos) { fprintf(stderr, "malloc failed\n"); return 1; }

    for (size_t i = 0; i < NUM_ITEMS; i++) {
        uint8_t *field = (uint8_t *)(aos + i * struct_size);
        *field = (uint8_t)(i & 1);
    }

    /* --- SoA layout --- */
    uint8_t *soa = (uint8_t *)malloc((size_t)NUM_ITEMS * FIELD_SIZE);
    if (!soa) { fprintf(stderr, "malloc failed\n"); return 1; }

    for (size_t i = 0; i < NUM_ITEMS; i++)
        soa[i] = (uint8_t)(i & 1);

    volatile uint64_t sink = 0;

    /* --- Benchmark AoS --- */
    double best_aos = 1e18;
    for (int iter = 0; iter < NUM_ITERS; iter++) {
        struct timespec t0, t1;
        uint64_t sum = 0;

        clock_gettime(CLOCK_MONOTONIC, &t0);

        for (size_t i = 0; i < NUM_ITEMS; i++) {
            uint8_t val = *(volatile uint8_t *)(aos + i * struct_size);
            sum += val;
        }

        clock_gettime(CLOCK_MONOTONIC, &t1);
        sink += sum;

        double ns = (t1.tv_sec - t0.tv_sec) * 1e9 + (t1.tv_nsec - t0.tv_nsec);
        double ns_per = ns / NUM_ITEMS;
        if (ns_per < best_aos) best_aos = ns_per;
    }

    /* --- Benchmark SoA --- */
    double best_soa = 1e18;
    for (int iter = 0; iter < NUM_ITERS; iter++) {
        struct timespec t0, t1;
        uint64_t sum = 0;

        clock_gettime(CLOCK_MONOTONIC, &t0);

        for (size_t i = 0; i < NUM_ITEMS; i++) {
            uint8_t val = *(volatile uint8_t *)(soa + i);
            sum += val;
        }

        clock_gettime(CLOCK_MONOTONIC, &t1);
        sink += sum;

        double ns = (t1.tv_sec - t0.tv_sec) * 1e9 + (t1.tv_nsec - t0.tv_nsec);
        double ns_per = ns / NUM_ITEMS;
        if (ns_per < best_soa) best_soa = ns_per;
    }

    printf("%.2f,%.2f\n", best_aos, best_soa);

    (void)sink;
    free(aos);
    free(soa);
    return 0;
}

aos_soa_results.csv

chase.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

/*
 * Pointer-chasing benchmark.
 *
 * Allocates N nodes of a given size, chains them in a random permutation,
 * then chases pointers and measures nanoseconds per access.
 * Reads every cache line in each node to measure full-struct access cost.
 *
 * Usage: ./chase <node_size_bytes> <working_set_bytes> <num_chases>
 */

struct node {
    struct node *next;
};

static void shuffle(uint32_t *arr, size_t n)
{
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = (size_t)rand() % (i + 1);
        uint32_t tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

int main(int argc, char **argv)
{
    if (argc != 4) {
        fprintf(stderr, "usage: %s <node_size> <working_set_size> <num_chases>\n", argv[0]);
        return 1;
    }

    size_t node_size = (size_t)atol(argv[1]);
    size_t ws_size = (size_t)atol(argv[2]);
    size_t num_chases = (size_t)atol(argv[3]);

    if (node_size < sizeof(struct node)) {
        fprintf(stderr, "node_size must be >= %zu\n", sizeof(struct node));
        return 1;
    }

    size_t n = ws_size / node_size;
    if (n < 2) {
        fprintf(stderr, "working set too small for node size\n");
        return 1;
    }

    char *arena = (char *)malloc(n * node_size);
    if (!arena) {
        fprintf(stderr, "malloc failed for %zu bytes\n", n * node_size);
        return 1;
    }
    memset(arena, 0, n * node_size);

    uint32_t *order = (uint32_t *)malloc(n * sizeof(uint32_t));
    for (size_t i = 0; i < n; i++)
        order[i] = (uint32_t)i;

    srand(42);
    shuffle(order, n);

    for (size_t i = 0; i < n; i++) {
        struct node *cur = (struct node *)(arena + order[i] * node_size);
        struct node *nxt = (struct node *)(arena + order[(i + 1) % n] * node_size);
        cur->next = nxt;
    }

    free(order);

    /* warm up */
    struct node *p = (struct node *)arena;
    for (size_t i = 0; i < n; i++)
        p = p->next;

    /* timed pointer chase */
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);

    volatile uint64_t checksum = 0;

    p = (struct node *)arena;
    for (size_t i = 0; i < num_chases; i++) {
        char *base = (char *)p;
        uint64_t sum = 0;
        for (size_t off = 0; off < node_size; off += 64)
            sum += *(volatile uint64_t *)(base + off);
        checksum += sum;

        p = p->next;
        __asm__ volatile("" : "+r"(p));
    }

    clock_gettime(CLOCK_MONOTONIC, &t1);

    double elapsed_ns = (t1.tv_sec - t0.tv_sec) * 1e9 + (t1.tv_nsec - t0.tv_nsec);
    double ns_per_chase = elapsed_ns / (double)num_chases;

    printf("%.2f\n", ns_per_chase);
    (void)checksum;

    free(arena);
    return 0;
}

plot.py

#!/usr/bin/env python3
import csv
import sys
from collections import defaultdict

def main():
    results_file = sys.argv[1] if len(sys.argv) > 1 else "results.csv"

    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt
    import matplotlib.ticker as ticker

    data = defaultdict(lambda: ([], [], []))
    with open(results_file) as f:
        reader = csv.DictReader(f)
        for row in reader:
            ns = int(row["node_size"])
            ws = int(row["working_set"])
            latency = float(row["ns_per_chase"])
            num_monsters = ws // ns
            data[ns][0].append(num_monsters)
            data[ns][1].append(latency)
            data[ns][2].append(ws)

    colors = {64: "#e74c3c", 128: "#3498db", 256: "#2ecc71", 512: "#9b59b6"}

    def fmt_count(x, pos):
        if x >= 1_000_000:
            return f"{x/1_000_000:.0f}M"
        if x >= 1_000:
            return f"{x/1_000:.0f}K"
        return f"{x:.0f}"

    fig, (ax_top, ax_bot) = plt.subplots(2, 1, figsize=(12, 10), sharex=True,
                                          gridspec_kw={"height_ratios": [1, 1.2]})

    # --- Top: zoomed into L1/L2/L3 region (0-60 ns) ---
    for ns in sorted(data.keys()):
        monsters, latencies, _ = data[ns]
        label = f"{ns}B Monster"
        ax_top.plot(monsters, latencies, "o-", label=label,
                    color=colors.get(ns, None), linewidth=2, markersize=5)

    ax_top.set_ylim(0, 60)
    ax_top.set_ylabel("Latency (ns / lookup)", fontsize=12)
    ax_top.set_title("Random Access Latency vs Number of Monsters",
                     fontsize=14)
    ax_top.legend(fontsize=10, loc="upper left")
    ax_top.grid(True, alpha=0.3)
    ax_top.text(0.98, 0.95, "Zoomed in", transform=ax_top.transAxes,
                ha="right", va="top", fontsize=10, fontstyle="italic", color="black")

    # --- Bottom: full range showing DRAM cliff ---
    for ns in sorted(data.keys()):
        monsters, latencies, _ = data[ns]
        label = f"{ns}B Monster"
        ax_bot.plot(monsters, latencies, "o-", label=label,
                    color=colors.get(ns, None), linewidth=2, markersize=5)

    ax_bot.set_ylabel("Latency (ns / lookup)", fontsize=12)
    ax_bot.set_xlabel("Number of Monsters", fontsize=12)
    ax_bot.grid(True, alpha=0.3)

    ax_bot.set_xscale("log", base=2)
    ax_bot.xaxis.set_major_formatter(ticker.FuncFormatter(fmt_count))

    plt.tight_layout()
    plt.savefig("cache_staircase.png", dpi=150)
    print("Saved cache_staircase.png")

if __name__ == "__main__":
    main()

plot_aos_soa.py

#!/usr/bin/env python3
import csv
import sys

def main():
    results_file = sys.argv[1] if len(sys.argv) > 1 else "aos_soa_results.csv"

    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt
    import numpy as np

    sizes = []
    aos_times = []
    soa_times = []

    with open(results_file) as f:
        reader = csv.DictReader(f)
        for row in reader:
            sizes.append(int(row["struct_size"]))
            aos_times.append(float(row["aos_ns"]))
            soa_times.append(float(row["soa_ns"]))

    fig, ax = plt.subplots(figsize=(12, 7))

    x = np.arange(len(sizes))
    w = 0.35
    ax.bar(x - w/2, aos_times, w, label="Array of Structs (AoS)", color="#e74c3c")
    ax.bar(x + w/2, soa_times, w, label="Struct of Arrays (SoA)", color="#2ecc71")
    ax.set_xticks(x)
    ax.set_xticklabels([f"{s}B" for s in sizes], rotation=45, ha="right")
    ax.set_ylabel("Latency (ns / item)", fontsize=12)
    ax.set_xlabel("Struct Size", fontsize=11)
    ax.set_title("AoS vs SoA: Reading is_alive (1 byte) Across 1M Monsters",
                 fontsize=14)
    ax.legend(fontsize=10)
    ax.grid(axis="y", alpha=0.3)

    for i, (a, s) in enumerate(zip(aos_times, soa_times)):
        speedup = a / s if s > 0 else 0
        ax.text(i - w/2, a + 0.3, f"{speedup:.0f}x", ha="center", va="bottom",
                fontsize=9, fontweight="bold", color="#c0392b")

    plt.tight_layout()
    plt.savefig("aos_vs_soa.png", dpi=150)
    print("Saved aos_vs_soa.png")

if __name__ == "__main__":
    main()

results.csv

run.sh

#!/usr/bin/env bash
set -euo pipefail

cd "$(dirname "$0")"

gcc -O2 -o chase chase.c -lrt

NODE_SIZES="64 128 256 512"
NUM_CHASES=10000000
RESULTS="results.csv"

echo "node_size,working_set,ns_per_chase" > "$RESULTS"

for node_size in $NODE_SIZES; do
    echo "=== node_size=${node_size} ==="

    ws=2048
    max_ws=$((512 * 1024 * 1024))

    while [ "$ws" -le "$max_ws" ]; do
        n_nodes=$((ws / node_size))
        if [ "$n_nodes" -lt 2 ]; then
            ws=$((ws * 2))
            continue
        fi

        chases=$NUM_CHASES
        if [ "$ws" -gt $((64 * 1024 * 1024)) ]; then
            chases=$((NUM_CHASES / 10))
        fi
        if [ "$ws" -gt $((256 * 1024 * 1024)) ]; then
            chases=$((NUM_CHASES / 50))
        fi

        declare -a times=()
        for trial in 1 2 3; do
            t=$(./chase "$node_size" "$ws" "$chases")
            times+=("$t")
        done

        median=$(printf '%s\n' "${times[@]}" | sort -g | sed -n '2p')

        ws_human=$(numfmt --to=iec "$ws" 2>/dev/null || echo "${ws}")
        echo "  ws=${ws_human}  => ${median} ns/chase"
        echo "${node_size},${ws},${median}" >> "$RESULTS"

        unset times
        ws=$((ws * 2))
    done
done

echo ""
echo "Results written to $RESULTS"

run_aos_soa.sh

#!/usr/bin/env bash
set -euo pipefail

cd "$(dirname "$0")"

gcc -O2 -o aos_soa aos_soa.c -lrt

SIZES="4 8 16 32 64 128 256 512 1024"
RESULTS="aos_soa_results.csv"

echo "struct_size,items_per_cacheline,aos_ns,soa_ns,speedup" > "$RESULTS"

for sz in $SIZES; do
    result=$(./aos_soa "$sz")
    aos_ns=$(echo "$result" | cut -d, -f1)
    soa_ns=$(echo "$result" | cut -d, -f2)
    items_per_cl=$((64 / sz > 0 ? 64 / sz : 1))
    if [ "$sz" -gt 64 ]; then
        items_per_cl=0
    fi
    speedup=$(python3 -c "print(f'{${aos_ns} / ${soa_ns}:.1f}')")
    echo "  struct=${sz}B  AoS=${aos_ns} ns  SoA=${soa_ns} ns  (${speedup}x faster)"
    echo "${sz},${items_per_cl},${aos_ns},${soa_ns},${speedup}" >> "$RESULTS"
done

echo ""
echo "Results written to $RESULTS"