Код, дружественный кешу
Вопрос
Объясните, как устроены кеши процессора и как писать код, который хорошо их использует. Приведите примеры из C++.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Кеш-линии 64 байта, иерархия L1/L2/L3 и задержки
Пространственная и временная локальность, префетчер
vector против list и map, плоские массивы, порядок обхода
AoS против SoA, горячие и холодные поля
False sharing и выравнивание alignas(64)
Блочная обработка (tiling) для больших матриц
Что могут спросить следом
- Почему двоичный поиск по большому массиву медленнее, чем кажется по асимптотике?
- Что такое TLB-промах?
Разбор
Процессор работает с памятью кеш-линиями по 64 байта через иерархию: L1 около наносекунды, L3 порядка десяти, оперативная память около ста. Поэтому важно, сколько линий мы затронем и предсказуем ли доступ. Пространственная локальность: читать подряд, тогда одна линия обслуживает несколько элементов, а префетчер подгружает следующие заранее. Отсюда std::vector вместо std::list и std::map, плоский массив вместо вектора векторов, обход матрицы по строкам. Временная локальность: работать с данными, пока они в кеше, например блочное умножение матриц. Раскладка данных: если цикл трогает одно поле, structure of arrays или вынесение редких полей в отдельную структуру. В многопоточном коде false sharing: разные потоки пишут в одну линию и мешают друг другу, лечится alignas(64) и локальными аккумуляторами. Проверяю гипотезы через perf stat, смотрю на cache-misses.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.