Cpu Cache Opt

CPU Cache Optimization

Purpose

Guide agents through cache-aware programming: diagnosing cache misses with perf, data layout transformations (AoS→SoA), false sharing detection and fixes, prefetching, and cache-friendly algorithm design.

Triggers

• "My program has high cache miss rates — how do I fix it?"
• "What is false sharing and how do I detect it?"
• "Should I use AoS or SoA data layout?"
• "How do I measure cache performance with perf?"
• "How do I use __builtin_prefetch?"
• "My multithreaded program is slower than single-threaded due to cache"

Workflow

1. Measure cache performance

# Basic cache counters
perf stat -e cache-references,cache-misses,cycles,instructions ./prog

# L1/L2/L3 miss breakdown
perf stat -e \
    L1-dcache-load-misses,\
    L1-dcache-loads,\
    L2-dcache-load-misses,\
    LLC-load-misses,\
    LLC-loads \
    ./prog

# Cache miss rate = L1-dcache-load-misses / L1-dcache-loads
# > 5% is concerning; > 20% is severe

# False sharing detection
perf stat -e \
    machine_clears.memory_ordering,\
    mem_load_l3_hit_retired.xsnp_hitm \
    ./prog

2. Cache line basics

• Cache line size: 64 bytes on x86-64, ARM (most platforms)
• L1 cache: 32–64 KB, ~4 cycles latency
• L2 cache: 256 KB–1 MB, ~12 cycles latency
• L3 cache: 6–64 MB, ~40 cycles latency
• Main memory: ~200–300 cycles latency

// Check cache line size
long cache_line = sysconf(_SC_LEVEL1_DCACHE_LINESIZE);

// Align data to cache line
struct alignas(64) HotData {
    int counter;
    // ... 60 bytes of data that fit in one line
};

// C
typedef struct {
    int x;
} __attribute__((aligned(64))) AlignedData;

3. AoS vs SoA data layout

// AoS (Array of Structures) — default layout
struct Particle {
    float x, y, z;     // position (12 bytes)
    float vx, vy, vz;  // velocity (12 bytes)
    float mass;         // (4 bytes)
    int   flags;        // (4 bytes)
};
Particle particles[N];  // Bad for loops that only need position

// Problem: accessing particles[i].x loads x,y,z,vx,vy,vz,mass,flags
// But we only need x,y,z → 75% of loaded data is wasted

// SoA (Structure of Arrays) — cache-friendly for SIMD + sequential access
struct ParticlesSoA {
    float *x, *y, *z;
    float *vx, *vy, *vz;
    float *mass;
    int   *flags;
};

// Accessing x[i] for i=0..N loads 16 consecutive x values → 0% waste
// Also auto-vectorizes better

4. Common cache-unfriendly patterns

// BAD: random access (linked list traversal)
Node *node = head;
while (node) {
    process(node->data);
    node = node->next;  // pointer chasing = cache miss per node
}

// BETTER: pool allocate nodes contiguously
// Or: rewrite as contiguous array with indices

// BAD: stride > cache line in matrix traversal
for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
        sum += matrix[j][i];  // column-major access on row-major array

// GOOD: row-major access
for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
        sum += matrix[i][j];

// BAD: large struct with hot + cold fields
struct Record {
    int id;           // hot: accessed every iteration
    char name[128];   // cold: accessed rarely
    int value;        // hot
    char desc[256];   // cold
};

// GOOD: separate hot and cold data
struct RecordHot { int id; int value; };
struct RecordCold { char name[128]; char desc[256]; };
RecordHot hot_data[N];
RecordCold cold_data[N];

5. False sharing

False sharing occurs when two threads write to different variables that share a cache line, causing constant cache-line invalidations.

// BAD: counters likely on same cache line (8 bytes each, line = 64 bytes)
int counter_a;  // thread A's counter
int counter_b;  // thread B's counter

// Both on the same cache line → every write invalidates the other thread's cache

// GOOD: pad to separate cache lines
struct alignas(64) PaddedCounter {
    int value;
    char padding[60];  // Ensure next counter is on different cache line
};

PaddedCounter counters[NUM_THREADS];
// Thread i: counters[i].value++

// C++ standard approach
struct alignas(std::hardware_destructive_interference_size) PaddedCounter {
    int value;
};

6. Prefetching

Manual prefetch hints to hide memory latency:

#include <immintrin.h>  // or <xmmintrin.h>

// Prefetch for read (locality 0=non-temporal, 3=high temporal)
__builtin_prefetch(ptr, 0, 3);  // prefetch for read, high locality
__builtin_prefetch(ptr, 1, 3);  // prefetch for write, high locality

// SSE prefetch (x86)
_mm_prefetch((char*)ptr, _MM_HINT_T0);   // L1
_mm_prefetch((char*)ptr, _MM_HINT_T1);   // L2
_mm_prefetch((char*)ptr, _MM_HINT_T2);   // L3
_mm_prefetch((char*)ptr, _MM_HINT_NTA);  // non-temporal (streaming)

// Typical pattern: prefetch N iterations ahead
#define PREFETCH_DIST 8
for (int i = 0; i < N; i++) {
    if (i + PREFETCH_DIST < N)
        __builtin_prefetch(&data[i + PREFETCH_DIST], 0, 3);
    process(data[i]);
}

Prefetching rules:

• Prefetch too early = cache evicted before use
• Prefetch too late = no benefit
• Prefetch distance = memory latency / time per iteration (typically 8–32 elements)

7. Cache-friendly algorithm design

// Loop blocking / tiling for matrix operations
// Process cache-fitting blocks instead of full rows/columns
#define BLOCK 64  // tuned to L1 cache size

void matrix_mult_blocked(float *C, float *A, float *B, int N) {
    for (int i = 0; i < N; i += BLOCK)
    for (int k = 0; k < N; k += BLOCK)
    for (int j = 0; j < N; j += BLOCK)
    // Inner block fits in L1 cache
    for (int ii = i; ii < i + BLOCK && ii < N; ii++)
    for (int kk = k; kk < k + BLOCK && kk < N; kk++)
    for (int jj = j; jj < j + BLOCK && jj < N; jj++)
        C[ii*N+jj] += A[ii*N+kk] * B[kk*N+jj];
}

For perf cache event reference and false sharing detection patterns, see references/cache-counters.md.

Related skills

• Use skills/profilers/linux-perf for perf stat and perf record cache measurements
• Use skills/profilers/valgrind — cachegrind simulates cache behaviour
• Use skills/low-level-programming/simd-intrinsics — SoA layout pairs with SIMD vectorization
• Use skills/low-level-programming/memory-model for false sharing in concurrent contexts

Cache Performance Counters Reference

perf stat Cache Events

Generic (portable across CPUs)

perf stat -e cache-references,cache-misses ./prog

x86 Intel PMU Events

# Full L1/L2/L3 breakdown
perf stat -e \
    L1-dcache-loads,L1-dcache-load-misses,\
    L1-dcache-stores,L1-dcache-store-misses,\
    L2-dcache-loads,L2-dcache-load-misses,\
    LLC-loads,LLC-load-misses,LLC-stores,LLC-store-misses \
    ./prog

# Advanced Intel events (Skylake/Icelake)
perf stat -e \
    mem_load_retired.l1_miss,\
    mem_load_retired.l2_miss,\
    mem_load_retired.l3_miss,\
    mem_inst_retired.all_loads,\
    mem_load_l3_hit_retired.xsnp_hitm \
    ./prog

False Sharing Detection

# HITM = cache line modified and hit in another core (false sharing indicator)
perf stat -e \
    mem_load_l3_hit_retired.xsnp_hitm,\
    mem_load_l3_miss_retired.remote_hitm,\
    machine_clears.memory_ordering \
    ./prog

High xsnp_hitm or remote_hitm = false sharing.

ARM Cache Events

# ARM64 cache events
perf stat -e \
    L1-dcache-load-misses,\
    L1-dcache-loads,\
    cache-misses,cache-references \
    ./prog

# ARM PMU specific
perf stat -e \
    r0003,\   # L1D_CACHE
    r0006,\   # BUS_ACCESS
    r0017     # L2D_CACHE
    ./prog

Interpreting Cache Rates

valgrind cachegrind

# Simulate cache behaviour (no real hardware needed)
valgrind --tool=cachegrind --cache-sim=yes \
         --I1=32768,8,64 --D1=32768,8,64 \
         --LL=6291456,12,64 \
         ./prog

# Annotate source with cache events
cg_annotate cachegrind.out.* --auto=yes

# Compare two runs
cg_diff cachegrind.out.before cachegrind.out.after

Output format:

=============================================================
I   refs:      1,234,567
I1  misses:        1,234
LLi misses:          123
I1  miss rate:      0.10%
LLi miss rate:      0.01%

D   refs:      2,345,678  (1,234,567 rd + 1,111,111 wr)
D1  misses:       23,456  (   12,345 rd +    11,111 wr)
LLd misses:        2,345  (    1,234 rd +     1,111 wr)
D1  miss rate:      1.00% (    1.00% + 1.00%)
LLd miss rate:      0.10% (    0.10% + 0.10%)

Struct Layout Analysis

# GCC: show struct padding
gcc -g -O0 -Wpadded src/hot.c 2>&1 | grep "Wpadded"

# pahole tool: show struct layout
pahole -C MyStruct ./myapp

# Output:
struct MyStruct {
    int                        x;        /*     0     4 */
    /* XXX 4 bytes hole, try to pack */
    double                     y;        /*     8     8 */
    int                        z;        /*    16     4 */
    /* size: 24, cachelines: 1 */
};

Cache-Friendly Allocation Patterns

// Aligned allocation for cache lines
#include <stdlib.h>

// C11
void *buf = aligned_alloc(64, 1024 * sizeof(float));

// POSIX
void *buf;
posix_memalign(&buf, 64, 1024 * sizeof(float));

// C++ (C++17)
#include <memory>
auto buf = std::make_unique<float[]>(1024);  // heap, may not be aligned
// Or:
alignas(64) float buf[1024];  // Stack aligned

// Custom aligned allocator for STL containers
template<typename T, size_t Align = 64>
struct AlignedAllocator {
    using value_type = T;
    T* allocate(size_t n) {
        return static_cast<T*>(aligned_alloc(Align, n * sizeof(T)));
    }
    void deallocate(T* p, size_t) { free(p); }
};

std::vector<float, AlignedAllocator<float>> vec(1024);

Hardware Prefetcher Behavior

Modern CPUs have hardware prefetchers that detect:

• Sequential access patterns (stride 1)
• Constant stride patterns (stride 2, 4, ...)
• Pointer chasing (limited)

Hardware prefetcher cannot help with:

• Irregular access (random, linked list traversal)
• Access pattern dependent on computed index

When to use manual prefetch:

• Stride known at compile time but too large for hw prefetcher
• Pointer chasing through linked data structures
• Software pipeline with known future addresses

// Linked list prefetch pattern
Node *next = head;
while (next) {
    Node *curr = next;
    next = curr->next;
    if (next) __builtin_prefetch(next, 0, 1);  // Prefetch next node
    process(curr->data);
}