Mediumperformance
Что такое cache locality и как она влияет на производительность?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Cache locality — близость обращений к памяти в кэше процессора (L1/L2/L3). Cacheline обычно 64 байта: чтение одного байта подтягивает всю линию. Spatial locality — данные рядом (массив); temporal locality — повторное обращение к тем же данным.
// vector: непрерывная память — cacheline подгружается и используется
std::vector<int> v(100000);
long sum = 0;
for (int x : v) sum += x; // быстро: линейный обход, cache-friendly
// list: узлы раскиданы по куче — cache miss на каждом узле
std::list<int> l(100000);
for (int x : l) sum += x; // медленно: каждый узел — cache missПоэтому vector быстрее list на обходе. Layout влияет: AOS (array of struct) vs SOA (struct of array) — для векторных операций SOA лучше. В performance-критичном коде layout данных часто важнее алгоритма.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.