🖥 О последовательном доступе к данным и кэше ЦПУ

В прошлое воскресенье на LeetCode в качестве челленджа была задачка Largest Local Values in a Matrix. Несмотря на уровень Easy, она демонстрирует важность последовательного доступа к данным.

Суть задачи

Дана матрица MxM. Нужно найти максимальные значения во всех матрицах 3x3, которые получаются из исходной матрицы. Решение от LeetCode реализовано так (рис. 1):

1. Берётся матрица 3x3.
2. Последовательно обходятся элементы матрицы в поисках максимума.
3. goto п.1.

Что не так с решением?

Например, что столбцы [9, 6, 2] и [8, 2, 6] относятся к матрицам 0 и 1, и будут обработаны несколько раз. Оптимальный алгоритм вернёт правильное решение, обработав каждый столбец и строку лишь 1 раз. Реализовать такой алгоритм можно 2 способами:

1. Обход по столбцам слева направо, сверху вниз (рис. 2).
2. Обход по строкам сверху вниз, слева направо.

Что быстрее? Кажется, что обход по столбцам. Да, но не всегда.

Причём тут последовательный доступ и кэш ЦПУ?

Реализация кэша ЦПУ основана на концепции локальности данных. При обращении к данным высока вероятность, что:

1. Вскоре к данным обратятся снова. Поэтому-то они и сохраняются в кэш.
2. Могут обратиться и к соседним данным. Поэтому кэширование происходит блоками определённого размера (cache line) и в кэш попадают не только запрашиваемые данные, но и соседние байты памяти.

В общем случае, если поведение программы не укладывается в концепцию выше, то производительность снижается. Например, для алгоритма с обходом по строкам, при размере матрицы 2000+ элементов, количество промахов кэша увеличивается многократно (рис. 3), что приводит к ухудшению производительности (рис. 4). Объясняется это непоследовательным доступом. В кэш попадают ненужные даные, ведь используется только 3 элемента из строки.

Но интересно то, что обход по строкам быстрее, если матрица небольшая (рис. 5). В таком случае, в кэш попадает практически вся матрица. А найти max значение 3-х элементов одной строки быстрее, чем 3-х элементов из разных строк.