Что такое cache locality и почему важно?

Cache locality — обращение к данным, близким в памяти или используемым повторно, что снижает cache misses. Два вида: spatial (соседние байты грузятся одной cache line) и temporal (повторное использование недавних данных). Cache line — 64 байта, miss в 100–300 раз дороже L1 hit.

// Vector: один непрерывный блок → отлично для кэша
std::vector<int> v(N);
for (int x : v) sum += x;        // prefetcher грузит следующие line-ы

// List: узлы разбросаны по heap → много misses
std::list<int> l;
for (int x : l) sum += x;        // каждый узел — отдельный miss

• AoS vs SoA — struct{float x,y,z;} arr[N] vs struct{float x[N],y[N],z[N];}; для обработки одного поля всех элементов SoA лучше.
• Даже O(n²) cache-friendly может обогнать O(n log n) с cache-misses при средних n.