Hardware prefetcher, TLB и memory-level parallelism

Graph traversal. Graph влезает в L2 — 4 MB, L2 4 MB. Каждый узел в cache. Но loop всё равно медленный. Hardware prefetcher знает, что cache line загружена — и всё равно не помогает. Почему?

Hardware prefetcher: типы и поведение

Современные CPU имеют несколько hardware prefetchers:

1. Sequential prefetcher — детектирует forward strides. Кикается после 2–3 consecutive cache misses в одном направлении; раз активен, prefetches до 16 lines вперёд. Defeat: random access, слишком длинный stride.

2. Stride detector — ловит паттерны «каждый N-й байт». Работает для arr[i*4] — stride 4. Defeat: irregular stride.

3. Content-based prefetcher (на некоторых chips) — следует pointer-like значениям. Ограниченный; pointer chaining всё равно defeat-ит его.

Помогать prefetcher-у:

• Hot loop stride ≤ 256 байт, consistent.
• Избегай conditional access patterns в inner loop.

Defeating prefetcher:

• Pointer chaining: A.next.next.next — каждый следующий адрес зависит от предыдущего result.
• Random array access (hash probing, graph traversal).

Software prefetch

Когда hardware не может предсказать паттерн, но разработчик может:

// prefetch данные за N итераций вперёд
__builtin_prefetch(&data[i + 8], 0, 1);  // GCC/Clang

Полезно для graph traversals, где следующий узел data-dependent. Hint CPU загрузить следующий узел, пока обрабатываешь текущий.

TLB и page-level locality

За пределами L1/L2/L3 существует ещё один уровень: Translation Lookaside Buffer (TLB) — кеш virtual-to-physical address translations.

CPU работает с virtual addresses. Для доступа к памяти нужно перевести virtual address в physical. Этот перевод — page walk через page tables в RAM. TLB кеширует результаты последних переводов.

TLB miss → page walk → 5–50 циклов задержки.

По умолчанию pages 4 KB. L1 TLB обычно: 32–64 entries (covers ~256 KB). L2 TLB: 512–4096 entries.

Workload, трогающий random pages (каждая ~4 KB), blow out TLB даже если данные влезают в L3.

Huge pages

Huge pages снижают TLB pressure резко:

• Standard page: 4 KB. TLB entry covers 4 KB.
• Huge page (x86): 2 MB = 512 × standard. Один TLB entry covers в 512x больше.
• 1 GB pages: 262 144 × standard. Один entry covers 1 GB.

Для high-perf кода, трогающего гигабайты — databases, ML inference, image processing — huge pages могут дать 10–20% speedup независимо от cache locality.

Linux: madvise(MADV_HUGEPAGE) или /sys/kernel/mm/transparent_hugepage/enabled = always. jemalloc и mimalloc поддерживают huge pages автоматически.

Memory-level parallelism (MLP)

Современные CPU могут иметь 8–16 cache misses outstanding одновременно. Это out-of-order execution: CPU issue-ит несколько loads не дожидаясь предыдущих.

Independent loads получают full MLP:

// CPU может issue все 4 loads параллельно
float a = arr[idx_a];  // miss → outstanding
float b = arr[idx_b];  // miss → outstanding  
float c = arr[idx_c];  // miss → outstanding
float d = arr[idx_d];  // miss → outstanding
// Latency: 1 miss ≈ 100 нс (не 4 × 100 нс)

Dependent-load chains полностью defeat MLP:

// Каждый load ждёт result предыдущего
Node *p = head;          // miss 1 → 100 нс
p = p->next;             // miss 2 → нужен result miss 1
p = p->next;             // miss 3 → нужен result miss 2
// Latency: N × 100 нс

Linked list traversal — worst case: одна pointer chase = одна serialized miss = 100 нс. 1 млн узлов → 100 мс, независимо от cache size.

Non-temporal stores

Streaming через гигабайты памяти (memcpy-like workloads) не benefit-ит от кеширования — данные read once и discarded. Non-temporal store инструкции bypass cache и пишут directly в memory:

// x86: non-temporal store, обходит кеш
_mm_stream_ps(&dst[i], val);     // SSE
_mm256_stream_ps(&dst[i], val);  // AVX2

// GCC/Clang:
__builtin_nontemporal_store(val, &dst[i]);

Для bandwidth-bound workloads (DB scans, log processing) non-temporal stores улучшают sustained bandwidth на 20–30% — L3 не засоряется one-shot data.

Cache associativity и conflict misses

Caches не fully associative — каждая cache line может быть placed только в нескольких specific ways (обычно 8–16 way для L1). Если много hot addresses случайно map в тот же set, они evict друг друга — conflict misses.

Классический пример: stride pattern, совпадающий с cache size modulo.

Митигация: pad data structures на extra cache line для разрыва alignment patterns. cachegrind reports D1mr/D1mw (L1 miss rate) per source line, экспонируя conflict misses.