В статье приводится краткое описание того, что такое кэш процессора, а также показывается, как из-за неправильной организации программного кода можно увеличить количество промахов кэша и, как следствие, увеличить время работы программы.
Ключевые слова: кэш процессора, кэш L1, кэш L2, эффективная разработка, бенчмарк.
Введение
Внимательно посмотрев на таблицу 1 «Задержки, которые должен знать каждый программист» [1], можно заметить, что скорость обращения к различной памяти сильно отличается. Нетрудно догадаться, что при составлении программ программисту необходимо как можно реже обращаться к «долгой» памяти и как можно чаще работать с «быстрой» памятью.
Таблица 1
Задержки, которые должен знать каждый программист (часть)
|
L1 cache reference |
0.5 ns |
|
Branch mispredict |
5 ns |
|
L2 cache reference |
7 ns |
|
Mutex lock/unlock |
25 ns |
|
Main memory reference |
100 ns |
|
... |
... |
Не все программисты работают с «очень долгой» памятью, например, огромными базами данных на магнитных лентах, и скорее всего эти разработчики знают, что прочитать один блок данных может занимать время, которое может ощутить человек (порядок нескольких секунд). Однако чаще всего ведется работа с более мелкими участками памяти (порядок нескольких мегабайт). И в этом случае незначительная вольность в работе с памятью становится не так заметна, хотя она может присутствовать.
В этой статье будет рассмотрены медленный и быстрый способ работы с памятью. Будет наглядно показано, насколько быстрее начинает работать программа, если свести количество обращений к медленной памяти к минимуму.
Кэш процессора
Согласно иерархической концепции организации компьютерной памяти [2], память компьютера может быть представлена в виде следующих уровней: регистры процессора, кэши процессора, оперативная память, и некоторые другие уровни (см. рис. 1).
Рис. 1. Иерархическая организация компьютерной памяти
Именно с кешами процессора работает программа, если ей необходимо небольшое количество памяти.
Обращение к разным уровням кэша занимает разное количество времени. Чтение какой-либо ячейки памяти происходит очень приближенно следующим образом (подробнее про порядок записи/чтения в кэшах рассказано в [3]):
- Проверим, есть ли данные в регистрах, если есть — поиск завершен.
- Проверим, есть ли данные в кэше L1, если есть — загрузим ячейку памяти в нужный регистр, поиск завершен.
- Проверим, есть ли данные в кэше L2, если есть — загрузим блок данных в кэш L1, а в регистр запишем необходимую ячейку.
- И так далее с последующими уровнями, пока не достигнем оперативной памяти.
Наличие необходимых данных в каком-либо уровне кэша называется попаданием в кэш. Отсутствие данных в кэше называется промахом.
Пример программы с большим и маленьким количеством промахов кэша
Приведем пример двух участков программы на языке Си, которые выполняют одну и ту же функцию, но одна из-за большого количества промахов кэша будет работать медленнее.
Идея заключается в суммировании элементов двумерного массива, представленного в виде линейного участка памяти [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 Мб.
Выводы
По результатам исследования можно сделать вывод, что необходимо писать программы учитывая объем памяти кэша процессора различных уровней. Правильная организация работы с памятью может в разы ускорить скорость работы программы.
Литература:
- Jonas Bonér Latency Numbers Every Programmer Should Know — Текст: электронный // Текстовый документ на гит репозитории — URL: https://gist.github.com/jboner/2841832 (дата обращения 28.04.2021)
- Branch misprediction. — Текст: электронный // Академик — интернет словарь. — URL: https://ru.wikipedia.org/wiki/Иерархия_памяти (дата обращения 29.04.2021)
- Кэш процессора. — Текст: электронный // Википедия свободная энциклопедия. — URL: https://ru.wikipedia.org/wiki/Кэш_процессора (дата обращения 29.04.2021)
- Динамическое выделение памяти, динамические массивы. — Текст электронный // Сообщество программистов С/С++. — URL: https://prog-cpp.ru/c-alloc/ (дата обращения 29.04.2021)
