Представьте, что ваш код работает на 30% быстрее, при этом вы почти его не меняли. Звучит как магия — на самом деле нет, если учитывать архитектуру процессора при проектировании приложения и структур данных. 

Привет! Я Александр Шакмаев — технический лидер в Cloud.ru. В статье предлагаю разобраться, как небольшие изменения, основанные на знании архитектуры процессора, могут привести к значительному ускорению Go. Готовы раскрыть потенциал вашего кода? Тогда переходите под кат.

Сразу начну с примера. Объявим структуру Person, в которой будут описаны возраст и имя пользователя. Задача которую поставил бизнес — посчитать средний возраст пользователей, которых, например, очень много. Задача эта вполне тривиальная, поэтому создадим обычный слайс структур Person размерностью count, сложим общий возраст и разделим на размерность.

Рассмотрим ещё варианты кода — в правой части изображения, с точки зрения бизнес-логики, мы сделали все то же самое, только описали не слайс структур, а признаки (тот же самый возраст, то же самое имя) в самой структуре — создали структуру слайсов: 

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

Почему так происходит? Давайте разбираться.

Что я понимаю под гармонией железа и кода

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

С одной стороны, задача разработчика — писать дружелюбный для процессора код. С другой — важно балансировать, чтобы в итоге не стать hardware-инженерами. Это также, как у гонщиков — им не нужно быть механиками, но важно хотя бы на базовом уровне понимать, что происходит под капотом, когда они нажимают на педаль газа.

Разберем самый удачный, на мой взгляд, пример того, как железо живет в гармонии с кодом — это B-Tree индекс. 

На картинке частный случай индекса Balanced Tree — он со шпиндельными дисками на «ты». Наверное, многие знают, что этот индекс повсеместно используется в базах данных. Когда мы работаем с БД в highload-проектах, использовать их на шпиндельных дисках SAS — самая частая рекомендация. Кроме того, что они быстрее и надежнее обычных SATA, а алгоритм чтения/записи устроен так, что работает сразу с сектором или блоком. 

Алгоритм индекса Balanced Tree максимально приближенно отражает то, как работает диск с точки зрения размещения данных:

• минимальное количество механического перемещения головок ПО для доступа к области диска;

• оптимизация случайных I/O-операций за счет сбалансированной структуры, т. е. случайные операции чтения/записи сведены к минимуму. 

Если сомневаетесь в моих словах, можете изучить вопрос подробнее.

В гармонии с процессором

С дисками понятно, а что с процессором? Почему код, который мы разбирали в самом начале, работал быстрее для варианта со структурой слайсов? Чтобы ответить на этот вопрос, начнем с истоков.

Самое важное для нас на схеме, это что есть кэш L1, L2 и общий L3. Здесь L1 и L2 находятся прямо на кристалле, который максимально близко к самим регистрам. Естественно, есть основная память. 

Давайте бегло взглянем на пирамиду памяти:

Наверное, очевидно, что самый быстрый кэш — это L1. Основная память в 100 раз медленнее, но она и самая большая (у всего свои плюсы и минусы). Раз L1 — самый быстрый, значит для разработки высокопроизводительных систем нам важно максимально быстро попадать в этот уровень кэша и, желательно, сразу всеми данными, которые планируем обработать. Как программисты могут повлиять на этот процесс?

Что такое принцип локальности: разбираем на примерах

Возможно, вы уже слышали о принципе локальности. Звучит он примерно так: 

Если есть ссылка на конкретную ячейку памяти, вполне вероятно, что:

• в ближайшем будущем снова будет указана ссылка на ту же ячейку — это временная локальность;

• с большой долей вероятности процессор будет обращаться к ее соседним ячейкам.

Вот как это может выглядеть:

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

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

Но на самом ли деле мы бежим по слайсу? Как мы себе это представляем в голове, а что происходит с точки зрения процессора?

Дело в том, что цикл не совсем «бежит» по слайсу. Посмотрим на код ассемблера (для компилятора на ARM):

В 56-й строчке видно, что на самом деле происходит адресация с использованием смещения и смещение базового адреса. Здесь регистр R0 — это базовый адрес, а R1<<3 означает, что мы смещаемся влево на три бита. Если бы здесь был вывод ассемблерного кода для архитектуры x86, то было бы эквивалентное умножение на восемь, потому что это 64-битная архитектура. 

Со смещением разобрались, но как данные попадают в кэш L1 и как можно положить туда максимально больше необходимых данных? Чтобы разобраться, вспомним, как данные попадают в кэш.

Строка кэша

Наверняка многие знают про кэшлайн — строку, которую процессор копирует за один проход. Это непрерывный объект (непрерывный блок памяти), который существует в парадигме общения процессора с памятью (не путайте с машинным словом).

Ниже очень упрощенно и схематично показано, как в памяти располагается слайс с int32, но это в ОЗУ:

А что в кэше? Если упростить, то кэш для архитектуры Intel x86 выглядит вот так:

На схеме размер кэша 64 килобайта, а длина кэш-линии — 64 байта. Для того, чтобы вычитать что-то из ОЗУ, процессор будет делать это по кэш-линиям — согласно архитектуре и иерархии уровней кэша. 

А теперь посмотрим в упрощенном виде, что происходит, когда случаются кэш-промахи: 

Здесь цифры 1, 2, 3, 4 — это то, что успело попасть в кэш-линию первой итерации копирования данных. На схеме есть серые клетки, потому что наше приложение не единственное в работе процессора, есть другие программы, другие потоки.

Кэш-промах (cache-miss) — это ситуация, когда данных, которые нужны процессору, в кэше нет, что заставляет его обращаться к более медленной памяти, например, оперативной. Пример ARM:

В данном примере я использовал Apple M1 Max — у него кэш-линия 128 байт. В такой ситуации этот вариант отработал бы быстрее, потому что процессору не нужно бегать, например, в ОЗУ и потом помещать информацию в кэш L1. Размер кэша здесь сильно больше, поскольку он вмещает сразу все данные. И это как раз отражает общую разницу архитектур. 

Подытожим:

1. Процессор копирует в кэш сразу блок данных из основной памяти по строкам — это называется кэш-линией. 

2. Строка кэша (кэш-линия) — это непрерывный сегмент памяти определенного размера. Важно помнить, что существуют кэш-промахи.

3. Размер строки кэша бывает разный, но обычно:

• 64 байта для Intel,

• 128 байт для Apple M1 Max.

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

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

Наши эксперименты

В своей практике я несколько раз встречался с таким вопросом: а что там с односвязным списком? Мы же можем заменить им массивы? Чтобы на него ответить, проведем эксперимент:

Представим, что мы описываем односвязный список, в котором будет храниться значение int64. Следующее в этой структуре значение — это ссылка на следующую ноду. Оба этих значения — 64 бита, поэтому в памяти они располагаются друг за другом одинаковыми по размеру блоками. 

Справа на картинке мы бежим по такому же слайсу (блокам одинакового размера), просто увеличенному в два раза. Чтобы получить значение int64, мы будем специально прыгать через элемент, имитируя движение по односвязному списку. Интересно, что будет быстрее — левая или правая часть? Давайте посмотрим:

Правая, конечно, сильно быстрее, причем по той же самой причине — есть пространственная локальность. Если посмотреть ассемблерный код, мы увидим, что на самом деле мы просто сдвигаемся по адресу, где живет массив, и считываем данные. 

Другой интересный пример с обратной итерацией: два варианта кода с одномерным массивом, где мы суммируем элементы слайсов. Они абсолютно одинаковые за исключением того, что мы бежим по слайсу в разные стороны:

Почему скорость работы одинаковая? Связано ли это с тем, что в обоих примерах присутствует пространственная локальность? Давайте посмотрим на вывод ассемблерного кода:

Здесь мы видим код для примера с обычной итерацией, где бежали от нуля — есть смещение на три бита по памяти и операция сложения:

А в примере с обратной итерацией заметно, что в 56-й строчке мы наблюдаем то же самое смещение реализации принципа локальности по расстоянию. А затем идет исключение и в 60-й строке мы видим операцию SUB — т. е. вычитание. 

Какие выводы из этого мы можем сделать:

1. Кэши процессора очень быстрые.

2. CPU использует сразу строку кэша, чтобы поместить ее в кэш.

3. Можно помочь процессору быстрее выполнять наши данные. Для этого учитывайте принципы:

• локальность по времени,

• локальность по расстоянию.

Как все работает на примерах с реальными данными

Выравнивание структур

Заезженный пример, но важный для понимания того, что происходит под капотом. Разберем его со стороны скорости работы приложения, а не со стороны очевидной экономии памяти.

Объявим структуру. Она не выровнена — мы и в первом машинном слове решили объявить bool, и в третьемl, хотя могли все поместить в одно машинное слово. В этом случае эта структура займет 24 байта, потому что здесь 3 машинных слова по 8 байт (64 бита — это 8 байт).

С выровненной структурой всё намного лучше — она весит 16 байт. Видно, что два булевых значения поместились сразу в одно машинное слово. Бенчмарки показывают, что это микро-оптимизация: 

Зачем вообще мы разбираем микрооптимизацию? Обратите внимание на изначальную постановку вопроса: почему именно быстрее? Обычно говорят, что выравнивание экономит память. И это действительно так — у нас меньше кэш-линий. А когда меньше кэш-линий, процессор реже бегает в медленную память. 

Разница в предполагаемом количестве необходимых кэш-линий ощутима. И для того, чтобы еще нагляднее показать «почему быстрее», будем использовать инструмент профилирования. Для Apple — Xcode Instruments, для Linux — perf stat, а для Intel — утилиту Vtune.

И вот какую ситуацию с кэш-промахами мы видим: 

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

И вот теперь мы наконец можем ответить на вопрос «Почему быстрее?». Да потому, что процессору нужно заметно меньше кэш-линий. И меньше промахов в кэше — это, конечно, только одна из причин. Но она понятна нам в контексте того, чтобы обратиться к принципам оптимизации производительности. 

Структура со слайсами

Вернемся к примеру, который был в самом начале статьи. Напомню, что у нас есть структура, которая описывает признаки пользователя. И есть структура, которая описывает массивы этих признаков. Задача — получить средний возраст пользователей. Вариант решения бизнес-задачи со структурой слайсов работает быстрее. Почему? 

Если упрощенно, то в памяти это выглядело бы так: 

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

Надеюсь, с принципом работы всё понятно. Разберемся с применимостью такого подхода. В случае, если прирост производительности будет значительным, рефакторинг кода однозначно будет оправдан. 

Снова посмотрим на код: 

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

Но, нет — мы видим, что структура слайсов и памяти всё равно занимает меньше:

Очевидные плюсы такого подхода:

• простой рефакторинг,

• прирост скорости и экономия памяти,

• сохранение читаемости кода.

Выводы

Какие выводы из всего описанного выше можно сделать?

• Проектировать код и структуру данных под процессор не сложно с точки зрения того, как «хотел бы этого от нас процессор» (в зависимости от бизнес-условий).

• Принцип локальности помогает выжать из процессора максимум.

• Если рефакторинга становится слишком много, стоит взвесить возможный прирост производительности и трудозатраты команды разработки. 

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