Максим Байтович – От транзистора до трансформера. Настольная книга программиста (страница 3)
Вспомним простейший цикл из прошлой лекции: выбрать команду, расшифровать, исполнить, записать. Пока команда идёт через эти стадии, остальные узлы простаивают. Конвейер — это способ загрузить их все: на одном такте одна команда исполняется, следующая в это время расшифровывается, третья выбирается из памяти. Как на сборочной линии: каждая станция делает свой шаг, и с линии каждые такт сходит готовая команда, хотя каждая отдельная команда тратит несколько тактов. Пропускная способность вырастает в несколько раз при той же частоте — и без роста напряжения и тепла.
Но конвейер хруп. Он даёт полную скорость, только пока команды идут ровным потоком, как вагоны. Стоит потоку споткнуться — и вся линия останавливается. Спотыкания бывают трёх родов, и инженеры называют их конфликтами. Первый — конфликт по данным: команде нужен результат предыдущей, который ещё не готов. Второй — по структуре: две команды хотят одну и ту же шину или память. Третий, самый дорогой, — конфликт управления: программа дошла до ветвления, и неизвестно, какую ветку брать следующей, а конвейер уже должен загружать следующие команды и не может ждать.
С конфликтом по данным справляются просто: либо ждут, вставляя «пузырь» — пустой такт, либо пересылают результат напрямую из стадии исполнения в следующую команду, минуя регистр. Это называется пересылкой, и современные процессоры делают её почти всегда, так что зависимость по данным, отстоящим на две-три команды, почти бесплатна. Конфликт по структуре лечат дублированием шин и раздельными кэшами команд и данных. А вот конфликт управления — это то, где начинается настоящее волшебство и где ваш код может выиграть или потерять в разы.
Смотрите, в чём проблема. Около каждой пятой команды в типичной программе — ветвление. Когда конвейер доходит до него, следующие команды ещё не известны, но конвейер пустым быть не может — он теряет такты. Инженеры спросили: а что если угадывать? Если ветвь шла в одну сторону несколько раз подряд, вероятно, пойдёт туда и снова. Процессор заводит таблицу предсказаний, смотрит в неё и заряжает в конвейер команды с угаданного адреса. Если угадал — конвейер ни на такт не остановился. Если не угадал — всё, что успело загрузиться по неверной ветке, нужно выбросить, и конвейер начинает заново. Цена промаха — десяток-другой потерянных тактов.
Теперь посчитаем, почему это важно для вас. Допустим, предсказатель угадывает девять из десяти ветвей. Тогда на каждых десяти ветвях один промах ценой, скажем, пятнадцать тактов. Это в среднем полтора такта сверху на ветвь — заметная надбавка, но терпимая. А теперь представьте код, где ветвление зависит от данных, которые невозможно предсказать, — например, сравнение со случайным порогом. Тогда угадывание падает до половины, и вы платите промахами постоянно. Именно это и случилось у моего студента: перемешанные данные сделали ветвление непредсказуемым, и половина конвейера уходила в сброс. Отсюда первое правило: горячие циклы любят предсказуемые ветви.
Второе правило следует из того же: данные, идущие ровным потоком, дружат не только с предсказателем, но и с памятью. Процессор не ждёт данные пассивно — он заранее тянет их в ближний кэш, предполагая, что вы пойдёте дальше по тому же адресу. Ровный порядок — предсказуемые адреса — попадание в кэш. Перемешанный порядок — промахи и ожидание. Два механизма, предсказание ветвей и предвыборка данных, оба построены на одной вере: будущее похоже на прошлое. Ваш код либо подтверждает эту веру, и тогда машина летит, либо разрушает её, и тогда машина спотыкается на каждом шагу.
Отсюда практические выводы, которые я прошу запомнить. Во-первых, в горячем коде предпочитайте данные, идущие последовательно, а структуры — компактные и выровненные. Во-вторых, если у вас есть ветвление, зависящее от данных, и вы знаете, что одна ветка сильно вероятнее, скажите об этом прямо: во многих языках есть подсказки ветвления, а иногда выгоднее переписать ветвление в арифметику без перехода. В-третьих, не бойтесь измерять: счётчики промахов предсказателя и промахов кэша есть в каждом современном процессоре, и profiler умеет их показывать.
Здесь уместно перейти к тому, что происходит, когда конвейера и предсказания мало, — к спекуляции и внеочередному исполнению. Идея: пока команда ждёт данные из памяти, процессор не обязан стоять — он может исполнять следующие команды, которые от этих данных не зависят, а результат придержать и подставить, когда данные придут. Для этого он переименовывает регистры, чтобы не затереть то, что ещё нужно, и ведёт учёт, какие команды завершены, но ещё не «обнародованы». Если спекуляция пошла по неверной ветке, все её результаты просто отбрасываются, и архитектурное состояние не меняется. Машина выглядит последовательной, а внутри — хаос из сотен команд, и это нормально.
Заметьте красивую симметрию: снаружи процессор — это скучный автомат, исполняющий команды строго по порядку. Внутри — параллельный, спекулятивный, переименовывающий регистры хаос, который лишь в конце притворяется последовательным. Граница между ними — договор, называемый архитектурным состоянием. Пока договор держится, программа корректна. Нарушить его может ошибка в железе, и такие ошибки — самые громкие аппаратные баги последних лет — возникают именно на этой границе, когда спекуляция оставляет след там, где следа быть не должно. Мы вернёмся к этому в лекции про безопасность.
И последнее, что связывает эту лекцию с вашей повседневностью, — почему мы не гоним частоту, а добавляем ядра. Конвейер и спекуляция дают выигрыш, пока программа умеет их кормить. Но у последовательного кода есть предел: часть команд зависит от предыдущих, и эту часть невозможно ускорить никаким конвейером. Когда упёрлись в этот предел и в тепловую стену, индустрия пошла вширь: больше ядер, каждое со своим конвейером. Поэтому современный выигрыш даёт не «более быстрый цикл», а «больше независимых потоков работы». Отсюда вывод для вас: параллелизм — это не мода, а единственный оставшийся способ тратить транзисторный бюджет, и код, который его не использует, оставляет половину машины без работы.
Домашнее задание — три измерения, от простого к сложному. Первое: найдите в своём профиле-анализаторе счётчик промахов предсказателя ветвлений и снимите его для двух версий одного цикла — с предсказуемым и со случайным ветвлением. Второе: прогоните один и тот же обход массива в прямом и в случайном порядке и сравните время и промахи кэша. Третье: запустите свою программу на одном ядре и на всех, посмотрите на ускорение и честно посчитайте, какая доля кода осталась последовательной. Эти три числа скажут вам о вашей программе больше, чем любые бенчмарки из интернета.
Лекция 04. Иерархия памяти: кэш, латентность, локальность
Начну с цифры, которая переворачивает представление о скорости. Операция в регистре процессора занимает около одного такта. Чтение из ближнего кэша — несколько тактов. Из дальнего кэша — десятки. Из оперативной памяти — сотни. Это не градация «быстро–медленно», это разные порядки величин: если обращение к регистру — это секунда, то обращение в память — это несколько дней. Программа, которая постоянно ходит в память, — это программа, которая большую часть времени ждёт. Вся эта лекция — о том, как устроена лестница, по которой данные спускаются к процессору, и как не заставлять её подниматься лишний раз.
Почему вообще нужна лестница, а не одна быстрая память? Потому что быстрые ячейки дорогие и крупные, а дешёвые — медленные. Инженеры давно поняли, что можно обмануть эту дилемму, если использовать свойство реальных программ — локальность. Программа обращается не ко всей памяти равномерно, а к небольшим участкам, и недавно использованное скорее всего использует снова, а рядом с использованным скорее всего лежит нужное дальше. Первое называется временной локальностью, второе — пространственной. Если это так, держим малый быстрый слой рядом с вычислителем для горячих данных, а большой медленный — для остальных. Так рождается пирамида: регистры, несколько уровней кэша, оперативная память, и дальше — диски и сеть.
Важно понять единицу, которой память разговаривает с процессором, — линию кэша. Процессор не тянет из памяти один байт: он тянет блок, обычно шестьдесят четыре байта, и кладёт его в кэш. Поэтому, если вы читаете массив подряд, первое обращение стоит сотни тактов, а следующие десятки элементов — почти бесплатно, потому что они приехали вместе с первым. Это и есть эксплуатация пространственной локальности. А если вы ходите по массиву большими прыжками, то на каждый прыжок тянете новую линию и выбрасываете предыдущую, и платите полную цену за каждый элемент. Отсюда первое правило: порядок обхода данных решает.
Здесь я показываю классический эксперимент, который прошу вас повторить. Возьмите двумерный массив и просуммируйте его двумя способами: по строкам и по столбцам. В одном языке и с одними данными разница достигает десятков раз, хотя число операций одинаково. Причина в том, как массив лежит в памяти: подряд по строкам. Обход по строкам тянет линию и использует её целиком. Обход по столбцам берёт из каждой линии один элемент и выбрасывает её. Машина одна и та же, данные одни и те же, а скорость разная — вся разница в локальности. Этот пример объясняет больше, чем любые лекции о микрооптимизациях.