Выбор ответа Middle Производительность и кеш спрашивают часто обновлено
Обход матрицы по строкам и столбцам
Вопрос
Матрица std::vector<double> размера 8000 × 8000 хранится по строкам. Почему обход for j ... for i ... a[i * n + j] медленнее, чем for i ... for j ...?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: По столбцам каждое обращение попадает в новую кеш-линию. По строкам соседние итерации читают соседние адреса: одна кеш-линия обслуживает 8 элементов double, и предвыборка работает идеально.
Варианты ответа
- По столбцам каждое обращение попадает в новую кеш-линиюправильный ответ
- Компилятор не умеет оптимизировать вложенные циклы с
jснаружи - Умножение
i * nдороже при внешнемj, его нельзя вынести из цикла - Разницы в скорости нет: оба обхода читают одни и те же элементы
Разбор
По строкам соседние итерации читают соседние адреса: одна кеш-линия обслуживает 8 элементов double, и предвыборка работает идеально. По столбцам шаг 64 000 байт, каждое обращение промах, а матрица целиком в кеш не помещается. Разница может быть в разы.
- Компиляторы иногда переставляют циклы (loop interchange), но полагаться на это нельзя, и причина замедления именно в памяти.
- Стоимость умножения одинакова.
- Разница огромная на больших матрицах.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.