В статье приводится краткое описание того, что такое кэш процессора, а также показывается, как из-за неправильной организации программного кода можно увеличить количество промахов кэша и, как следствие, увеличить время работы программы.

Ключевые слова: кэш процессора, кэш L1, кэш L2, эффективная разработка, бенчмарк.

Введение

Внимательно посмотрев на таблицу 1 «Задержки, которые должен знать каждый программист» [1], можно заметить, что скорость обращения к различной памяти сильно отличается. Нетрудно догадаться, что при составлении программ программисту необходимо как можно реже обращаться к «долгой» памяти и как можно чаще работать с «быстрой» памятью.

Таблица 1

Задержки, которые должен знать каждый программист (часть)

Не все программисты работают с «очень долгой» памятью, например, огромными базами данных на магнитных лентах, и скорее всего эти разработчики знают, что прочитать один блок данных может занимать время, которое может ощутить человек (порядок нескольких секунд). Однако чаще всего ведется работа с более мелкими участками памяти (порядок нескольких мегабайт). И в этом случае незначительная вольность в работе с памятью становится не так заметна, хотя она может присутствовать.

В этой статье будет рассмотрены медленный и быстрый способ работы с памятью. Будет наглядно показано, насколько быстрее начинает работать программа, если свести количество обращений к медленной памяти к минимуму.

Кэш процессора

Согласно иерархической концепции организации компьютерной памяти [2], память компьютера может быть представлена в виде следующих уровней: регистры процессора, кэши процессора, оперативная память, и некоторые другие уровни (см. рис. 1).

Рис. 1. Иерархическая организация компьютерной памяти

Именно с кешами процессора работает программа, если ей необходимо небольшое количество памяти.

Обращение к разным уровням кэша занимает разное количество времени. Чтение какой-либо ячейки памяти происходит очень приближенно следующим образом (подробнее про порядок записи/чтения в кэшах рассказано в [3]):

1. Проверим, есть ли данные в регистрах, если есть — поиск завершен.
2. Проверим, есть ли данные в кэше L1, если есть — загрузим ячейку памяти в нужный регистр, поиск завершен.
3. Проверим, есть ли данные в кэше L2, если есть — загрузим блок данных в кэш L1, а в регистр запишем необходимую ячейку.
4. И так далее с последующими уровнями, пока не достигнем оперативной памяти.

Наличие необходимых данных в каком-либо уровне кэша называется попаданием в кэш. Отсутствие данных в кэше называется промахом.

Пример программы с большим и маленьким количеством промахов кэша

Приведем пример двух участков программы на языке Си, которые выполняют одну и ту же функцию, но одна из-за большого количества промахов кэша будет работать медленнее.

Идея заключается в суммировании элементов двумерного массива, представленного в виде линейного участка памяти [4]. Параметр «size» — размер смещения в таком массиве, т. е. номер строки/столбца к которой мы обращаемся.

В первом случае мы чаще обращаемся к соседним участкам памяти:

for (int i = 0; i < size; ++i)

for (int j = 0; j < size; ++j)

sum += array [i * size + j];

Во втором — мы чаще обращаемся к отдаленным участкам памяти (различия в строке с обращением к элементу массива):

for (int i = 0; i < size; ++i)

for (int j = 0; j < size; ++j)

sum += array [i + size * j];

Запустим тест для разных значений size и построим график полученных зависимостей (рис. 2).

Рис. 2. Зависимость времени выполнения программы от размера смещения в линейно-двумерном массиве

Из графика видно, что начиная с размера смещения примерно 1250 байт влияние промахов кеша на скорость работы программы становится значительным. Из-за промахов тратится примерно в 2 раза больше времени на выполнение задачи. 1250 байт примерно соответствуют размеру кэша уровня L2 на компьютере, на котором проводилось тестирование — 1 Мб.

Выводы

По результатам исследования можно сделать вывод, что необходимо писать программы учитывая объем памяти кэша процессора различных уровней. Правильная организация работы с памятью может в разы ускорить скорость работы программы.

Литература:

1. Jonas Bonér Latency Numbers Every Programmer Should Know — Текст: электронный // Текстовый документ на гит репозитории — URL: https://gist.github.com/jboner/2841832 (дата обращения 28.04.2021)
2. Branch misprediction. — Текст: электронный // Академик — интернет словарь. — URL: https://ru.wikipedia.org/wiki/Иерархия_памяти (дата обращения 29.04.2021)
3. Кэш процессора. — Текст: электронный // Википедия свободная энциклопедия. — URL: https://ru.wikipedia.org/wiki/Кэш_процессора (дата обращения 29.04.2021)
4. Динамическое выделение памяти, динамические массивы. — Текст электронный // Сообщество программистов С/С++. — URL: https://prog-cpp.ru/c-alloc/ (дата обращения 29.04.2021)