Cache-oblivious алгоритмы, PGO и production failures

Rust struct рефактор переместил один горячий field в конец 96-байтного struct. Никакого изменения алгоритма. Никакой новой работы. p99 latency на message-render пути вырос на 40%. Production outage, замаскированный под code cleanup.

Cache-oblivious алгоритмы

Cache-oblivious алгоритм performs well на каждом cache level — L1, L2, L3 — без знания конкретных размеров. Канонический пример — recursive blocked matrix multiply.

Наивный three-nested-loop matrix multiply имеет плохое cache behaviour, потому что inner loop exhausts cache level перед тем, как переходит к следующему. Recursive blocked версия делит матрицу на 4 sub-matrices и рекурсирует до base case. На каждом recursion level активная sub-matrix влезает в какой-то cache level естественно, хотя алгоритм не знает, в какой именно. Hardware adapts.

Тот же принцип применяется к:

• Cache-oblivious mergesort: рекурсивное разделение пополам держит active data в наименьшем доступном cache level.
• Cache-oblivious B-trees: van Emde Boas layout располагает уровни дерева так, что каждое half-tree влезает в cache level — нет pointer chasing за пределы level.
• FFT: recursive Cooley-Tukey естественно выравнивает butterfly groups с cache lines.
• Matrix transposition: наивный transpose cache-hostile; recursive blocked transposition достигает хорошей spatial locality на всех уровнях.

2–4x speedup над naive iteration часто доминирует cost любой сложности рекурсии.

Profile-guided optimisation (PGO)

Компиляторы улучшаются кардинально при наличии runtime frequency данных. Процесс:

1. Build с instrumentation (-fprofile-generate / clang -fprofile-instr-generate).
2. Run representative workload — это заполняет .profdata файл.
3. Rebuild с profile (-fprofile-use / -fprofile-instr-use).

Что PGO меняет:

• Inlining decisions: inline hot callees, не cold. Без PGO компилятор inline-ит по code size heuristics и часто ошибается.
• Branch layout: predicted-taken branches размещаются последовательно в памяти. Не-taken branches прыгают вперёд. Это держит hot path contiguous в instruction cache.
• Basic block reordering: hot basic blocks группируются в соседних pages, улучшая I-cache hit rate для common path.
• Function placement: functions, вызываемые вместе, размещаются рядом в binary — меньше I-TLB miss-ов.

Real workload speedups от PGO:

• Chrome: 10–15%.
• Firefox: 12–18% на JIT warmup.
• Postgres: 8–15% на OLTP benchmarks.
• Linux kernel (BOLT post-link optimisation): 3–8%.

PGO cost: build pipeline complexity и необходимость representative profiling workload. Profiling workload должен соответствовать production traffic — toy benchmark даёт плохие profiles и может ухудшить производительность.

Real production failures

Все три failure-а имеют одну форму: «маленький» code change переместил байты без изменения алгоритма. CPU заметил.

Discord 2023 — struct field reorder. Rust struct рефактор переместил горячий field (message_timestamp) с byte offset 0 на byte offset 72 в 96-байтном struct. Field пересёк cache-line boundary. Каждый render message list — горячий path в client — теперь загружал две cache lines вместо одной для этого field. p99 latency на message-render path вырос 40%. Rollback подтвердил причину. Фикс: переупорядочить struct fields так, чтобы горячие fields жили в первых 64 байтах (одна cache line). Правило: профилируй struct access patterns и ставь top-3 most-read fields первыми.

Mojang Minecraft Java Edition 2018 — HashMap → contiguous array. Внутренний entity tracker использовал HashMap<EntityID, EntityData> для хранения всех world entities. Entity simulation (movement, AI, collision) обращалась к этим entries в tight game-tick loop. HashMap-ные chained buckets разбрасывали EntityData structs по heap — каждый entity lookup был pointer chase в random allocation. Замена entity store на contiguous array (Entity Component System, ECS) дала 3–5x throughput на game-tick loop. Все entity component data стала sequential; prefetcher загружал следующую entity данные, пока CPU обрабатывал текущую. Discord 2024 game-server расширил этот паттерн на SIMD-aware ECS structs: ещё 2x на определённых simulation paths.

Bun 2024 — startup cold-path regression. Новая dependency добавила HashMap, инициализируемый при module load time. Из-за allocation order во время JIT warmup, backing array HashMap-а находился в середине hot-code region, evict-уя frequently-used JIT-compiled functions из L1 во время startup. Симптом — 30 ms startup regression, незаметный в micro-benchmarks, видимый в automated startup regression tests. Фикс: lazy-init HashMap-а (создать при первом использовании, не при module load). Паттерн: всё, аллоцированное на cold path и растущее со временем, может засорять cache для hot path. Lazy-init — стандартная митигация.

Структурный паттерн. Во всех трёх случаях:

1. «Рефактор» изменил byte offsets или allocation timing — алгоритм идентичен.
2. Hot path тихо пересёк cache-line или TLB boundary.
3. Regression появился как p99 growth или throughput drop, не crash или obvious error.
4. Root cause потребовал perf c2c или perf stat; code review бы не поймал.

Observability для cache и branch производительности

Базовый perf stat вызов:

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

Дополнительные инструменты:

• perf record + perf annotate: sample hot lines с source annotation.
• perf c2c: cache-line contention между cores — прямой инструмент для false sharing.
• Intel VTune / AMD uProf: per-line attribution, memory access patterns, NUMA topology view.
• BCC cachestat / llcstat: BPF-based, zero-instrumentation, production-safe sampling.
• ARM PMU + Apple Instruments: те же метрики на ARM; Instruments имеет “CPU Counters” template с MEMORY_CYCLES и LAST_LEVEL_CACHE_MISS.

Performance-engineering loop:

1. Measure с perf stat — 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. Matching fix: layout → SoA / struct split; branches → sort / branchless; bandwidth → non-temporal stores / compression; SIMD → AoS-to-SoA + autovectorise.
4. Re-measure — подтвердить улучшение, проверить новый 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