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

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

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

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

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

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

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

Конец ознакомительного фрагмента.

Текст предоставлен ООО «Литрес».

Прочитайте эту книгу целиком, купив полную легальную версию на Литрес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.