От транзистора до трансформера. Настольная книга программиста

Домашнее задание — три измерения, от простого к сложному. Первое: найдите в своём профиле-анализаторе счётчик промахов предсказателя ветвлений и снимите его для двух версий одного цикла — с предсказуемым и со случайным ветвлением. Второе: прогоните один и тот же обход массива в прямом и в случайном порядке и сравните время и промахи кэша. Третье: запустите свою программу на одном ядре и на всех, посмотрите на ускорение и честно посчитайте, какая доля кода осталась последовательной. Эти три числа скажут вам о вашей программе больше, чем любые бенчмарки из интернета.

Лекция 04. Иерархия памяти: кэш, латентность, локальность

«Преждевременная оптимизация — корень всех зол, но преждевременный пессимизм о памяти — корень всех тормозов.» — из лекции

Начну с цифры, которая переворачивает представление о скорости. Операция в регистре процессора занимает около одного такта. Чтение из ближнего кэша — несколько тактов. Из дальнего кэша — десятки. Из оперативной памяти — сотни. Это не градация «быстро–медленно», это разные порядки величин: если обращение к регистру — это секунда, то обращение в память — это несколько дней. Программа, которая постоянно ходит в память, — это программа, которая большую часть времени ждёт. Вся эта лекция — о том, как устроена лестница, по которой данные спускаются к процессору, и как не заставлять её подниматься лишний раз.

Почему вообще нужна лестница, а не одна быстрая память? Потому что быстрые ячейки дорогие и крупные, а дешёвые — медленные. Инженеры давно поняли, что можно обмануть эту дилемму, если использовать свойство реальных программ — локальность. Программа обращается не ко всей памяти равномерно, а к небольшим участкам, и недавно использованное скорее всего использует снова, а рядом с использованным скорее всего лежит нужное дальше. Первое называется временной локальностью, второе — пространственной. Если это так, держим малый быстрый слой рядом с вычислителем для горячих данных, а большой медленный — для остальных. Так рождается пирамида: регистры, несколько уровней кэша, оперативная память, и дальше — диски и сеть.

Важно понять единицу, которой память разговаривает с процессором, — линию кэша. Процессор не тянет из памяти один байт: он тянет блок, обычно шестьдесят четыре байта, и кладёт его в кэш. Поэтому, если вы читаете массив подряд, первое обращение стоит сотни тактов, а следующие десятки элементов — почти бесплатно, потому что они приехали вместе с первым. Это и есть эксплуатация пространственной локальности. А если вы ходите по массиву большими прыжками, то на каждый прыжок тянете новую линию и выбрасываете предыдущую, и платите полную цену за каждый элемент. Отсюда первое правило: порядок обхода данных решает.

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