Cache-oblivious algorithms, PGO, and production failures

A Rust struct refactor moved one hot field to the end of a 96-byte struct. No algorithmic change. No added work. p99 latency on the message-render path grew 40%. A production outage disguised as a code cleanup.

Cache-oblivious algorithms

A cache-oblivious algorithm performs well at every cache level — L1, L2, L3 — without knowing the specific sizes. The canonical example is recursive blocked matrix multiply.

The naive three-nested-loop matrix multiply has poor cache behaviour because the inner loop exhausts a cache level before moving on. The recursive blocked version divides the matrix into four sub-matrices and recurses until a base case. At each recursion level, the active sub-matrix fits in some cache level naturally, even though the algorithm doesn’t know which one. The hardware adapts.

The same principle applies to:

• Cache-oblivious mergesort: recursive halving keeps active data in the smallest available cache level.
• Cache-oblivious B-trees: van Emde Boas layout arranges tree levels so that each half-tree fits in a cache level — no pointer chasing past the level boundary.
• FFT: recursive Cooley-Tukey naturally aligns butterfly groups with cache lines.
• Matrix transposition: naive transposition is cache-hostile; recursive blocked transposition achieves good spatial locality at all levels.

The 2–4x speedup over naive iteration often dominates whatever code complexity the recursion adds.

Profile-guided optimisation (PGO)

Compilers improve dramatically when given runtime frequency data. The process:

1. Build with instrumentation (-fprofile-generate / clang -fprofile-instr-generate).
2. Run a representative workload — this populates a .profdata file.
3. Rebuild with the profile (-fprofile-use / -fprofile-instr-use).

What PGO changes:

• Inlining decisions: inline hot callees, don’t inline cold ones. Without PGO, compilers inline based on code size heuristics and often get it wrong.
• Branch layout: predicted-taken branches are placed sequentially in memory. Non-taken branches jump forward. This keeps the hot path contiguous in the instruction cache.
• Basic block reordering: hot basic blocks are grouped in nearby pages, improving I-cache hit rate for the common path.
• Function placement: functions called together are placed near each other in the binary — fewer I-TLB misses.

Real workload speedups from PGO:

• Chrome: 10–15% on typical pages.
• Firefox: 12–18% on JIT warmup.
• Postgres: 8–15% on OLTP benchmarks.
• Linux kernel (BOLT post-link optimisation, similar concept): 3–8%.

PGO cost: build pipeline complexity and the need for a representative profiling workload. The profiling workload must match production traffic — a toy benchmark gives bad profiles and can hurt performance.

Real production failures

These failures all share the same shape: a “small” code change moved bytes around without changing the algorithm. The CPU noticed.

Discord 2023 — struct field reorder. A Rust struct refactor moved a hot field (message_timestamp) from byte offset 0 to byte offset 72 in a 96-byte struct. The field crossed a cache-line boundary. Every render of a message list — the hottest path in the client — now loaded two cache lines instead of one to get that field. p99 latency on the message-render path grew 40%. Rollback confirmed the cause. Fix: reorder struct fields so the hot fields live in the first 64 bytes (one cache line). Rule of thumb: profile your struct access patterns and put the top-3 most-read fields first.

Mojang Minecraft Java Edition 2018 — HashMap → contiguous array. The internal entity tracker used a HashMap<EntityID, EntityData> to store all world entities. Entity simulation (movement, AI, collision) accessed these entries in a tight game-tick loop. The HashMap’s chained buckets scattered EntityData structs across the heap — each entity lookup was a pointer chase to a random allocation. Replacing the entity store with a contiguous array (Entity Component System architecture, ECS) gave 3–5x throughput on the game-tick loop. Every entity’s component data was now sequential; the prefetcher loaded the next entity’s data while the CPU processed the current one. Discord’s 2024 game-server work extended this pattern to SIMD-aware ECS structs: further 2x on certain simulation paths.

Bun 2024 — startup cold-path regression. A new dependency added a HashMap initialised at module load time. Due to allocation order during JIT warmup, the HashMap’s backing array landed in the middle of the hot-code region, evicting frequently-used JIT-compiled functions from L1 during startup. The symptom was a 30ms startup regression — invisible in micro-benchmarks, visible in automated startup regression tests. Fix: lazy-init the HashMap (create on first use, not at module load). Pattern: anything allocated on a cold path that grows over time can pollute cache for the hot path. Lazy-init is the standard mitigation.

The structural pattern. In all three cases:

1. A “refactor” changed byte offsets or allocation timing — the algorithm was identical.
2. The hot path silently crossed a cache-line or TLB boundary.
3. The regression appeared as p99 growth or throughput drop, not as a crash or obvious error.
4. Root cause required perf c2c or perf stat to surface; code review would not have caught it.

Observability for cache and branch performance

The essential perf stat invocation:

perf stat -e \
  cache-misses,cache-references,\
  branch-misses,branches,\
  cycles,instructions \
  -- ./your_binary

Further tools:

• perf record + perf annotate: sample hot lines with source annotation. Shows which load instruction accumulates the most cycles.
• perf c2c: reports cache-line contention between cores — the direct tool for false sharing.
• perf top: live per-symbol miss attribution.
• Intel VTune / AMD uProf: per-line attribution, memory access patterns, NUMA topology view. Requires platform-specific tools.
• BCC cachestat / llcstat: BPF-based, zero-instrumentation, production-safe sampling. Reports L1/LLC hit rates system-wide or per-process without rebuilding the binary.
• ARM PMU + Apple Instruments: same metrics on ARM; Instruments has “CPU Counters” template with MEMORY_CYCLES and LAST_LEVEL_CACHE_MISS.

The performance-engineering loop:

1. Measure with perf stat — get IPC, miss rates, branch miss rate.
2. Identify dominant cost: cache miss (layout problem), branch miss (prediction problem), low IPC from bandwidth (data volume problem), low IPC from instruction issue (SIMD opportunity).
3. Choose matching fix: layout → SoA / struct split; branches → sort / branchless; bandwidth → non-temporal stores / compression; SIMD → AoS-to-SoA + autovectorise.
4. Re-measure — confirm improvement, check for new bottleneck.

Performance counter stats for './hot_loop':

     5,238,194,672      cycles
     2,094,127,491      instructions             #  0.40 insn per cycle
       413,824,917      branches
       105,209,832      branch-misses            # 25.42% of all branches
       684,283,194      cache-references
       287,401,952      cache-misses             # 41.99% of all cache refs
        12,498,373      LLC-loads
         5,927,491      LLC-load-misses          # 47.43% of all LL-cache hits

         2.851 seconds time elapsed