Что именно делал компилятор: как ассемблер помогает разобраться в производительности кода на C++

Расскажу вам одну историю о том, как смог прокачаться в качестве C++-программиста. Мне в этом помогло не чтение стандарта. Я тогда ещё не понимал до конца метапрограммирование с использованием шаблонов (честно говоря, прямо сейчас эту тему изучаю). Нет, просветление наступило, когда я всмотрелся в целую простыню кода на ассемблере x86–64, но не запаниковал, а подумал: “O, нет, нет. ЧТО ТАМ сделал компилятор?”

Читать вывод компилятора — это не какое-то мистическое тёмное искусство, которое практикуют только подстриженные в барбершопах разработчики компиляторов, с закрытыми глазами разбирающиеся в выделении регистров. Это навык. Его можно усвоить, затем в нём напрактиковаться, и результат вас очень удовлетворит. Овладев этим умением, вы больше никогда не будете писать «умные» абстракции как раньше. 

Читая ассемблер, мы обращаем внимание на 4 вещи:

• Векторизован ли код?

• Есть ли в нём ветвления?

• Вызывает ли он другой код?

• Перезагружает ли он память?

Давайте разбираться.

Исходное положение: инструментарий для чтения ассемблера

Прямо сейчас вам понадобятся две вещи:

1. Compiler Explorer (godbolt.org)

Compiler Explorer — это бесплатный сайт, блестяще решающий ровно одну задачу: он берёт ваш код на C++, компилирует его в режиме реального времени с использованием любого компилятора и флагов на ваш выбор — и показывает вам ассемблер. Бок о бок с соответствующим C++.

Без преувеличения, это лучший инструмент в экосистеме C++, формально не входящий в экосистему C++.

2. Действительно важные флаги компилятора

Когда вы проверяете работу оживлённых участков кода, особенно важны следующие флаги:

# Рабочие лошадки-O2          # "Ускорь это, но без безумных импровизаций"-O3          # "Ускорь это, безумные импровизации в небольшом количестве допустимы"# Векторизация-march=native          # Используй все инструкции, поддерживаемые данным ЦП-march=x86-64-v3       # Нацеливаемся конкретно на AVX2 (отлично помогает портировать код)# Отладка оптимизатора-fopt-info-vec         # Когда что-нибудь векторизуешь – сообщи мне об этом-fopt-info-missed      # Сообщи мне, когда НЕ ОПТИМИЗИРОВАЛ, причём, громко# На локальной машине, для дальнейшей проверки:objdump -d -M intel your_binary | less

При помощи флага -march=native вы, в принципе, сообщаете: «компилятор, можешь пользоваться всеми фокусами из твоего арсенала, обещаю, что этот бинарник с моей машины никуда не денется». Для продакшена выбирайте что-то конкретное, а если хотите проверить, на что способен ваш ЦП — пользуйтесь  -march=native.

Читаем ассемблер без слёз: азбука

Примерно здесь в типичном туториале начинается отток читателей. Вам выдают триста строк на ассемблере AT&T, с синтаксисом, где повсюду рассыпаны знаки % — и вы закрываете вкладку. Мы же пойдём другим путём.

Две необходимые вещи, которые нужно напомнить об ассемблере x86–64 — и продолжим:

Синтаксис Intel лучше. Добавляйте к вашим флагам -masm=intel в GCC/Clang, либо просто воспользуйтесь выпадающим меню «Intel» в  Compiler Explorer. Оно читается слева направо.

Вот какие инструкции вы должны узнавать:

; Основыmov  rax, rbx        ; копируем rbx в raxadd  rax, 8          ; rax += 8cmp  rax, rbx        ; сравниваем, устанавливаем флагиjl   .loop           ; если меньше - переходим (цикл!); Памятьmov  rax, [rbx]      ; загружаем с адреса rbxmov  [rbx], rax      ; сохраняем по адресу rbx; Интересностиimul rax, rbx        ; Перемножение целых чиселvaddps ymm0, ymm1    ; Складываем одновременно 8 чисел с плавающей точкой (SIMD!)vmovups ymm0, [rsi]  ; Загружаем одновременно 8 чисел с плавающей точкой

Обратите внимание на последнюю группу — инструкции, начинающиеся с v и использующие такие регистры как ymm0 — в соответствии с тем, как у вас работает векторизация. Если вы их видите, это значит, что ваш компилятор одновременно оперирует 8 числами с плавающей точкой  (или 4 числами двойной точности или 16 короткими числами). А когда вы их не видите, тогда как ожидаете увидеть… тут и начинается самое интересное.

Пример 1: цикл, который не поддаётся векторизации (и почему)

Начнём с классического примера. Вы пишете совершенно нормальную функцию:

// Версия 1: безобидный циклvoid scale(float* data, float factor, int n) {    for (int i = 0; i < n; i++) {        data[i] *= factor;    }}

Просто! Умножаем каждый элемент на коэффициент. Конечно же, компилятор справляется с этим красиво, правда?

Компилируем с -O2 -march=x86-64-v3. Вот что получается (в сокращении):

; фактический вывод - O2 без ограничения.loop:    vmovss  xmm1, dword ptr [rdi + rax*4]   ; загружаем ОДНО float    vmulss  xmm1, xmm1, xmm0                ; умножаем ОДНО float    vmovss  dword ptr [rdi + rax*4], xmm1   ; сохраняем ОДНО float    inc     rax    cmp     rax, rdx    jl      .loop

По одному. Числу с плавающей точкой. За операцию. Работаем с регистрами xmm, а не ymm. Этот код скалярный, а не векторизованный. Компилятор обрабатывает за итерацию одно число с плавающей точкой, а не восемь.

Почему? Поскольку data — это float*. Компилятор обеспокоен совмещением имён (aliasing). Что будет, если factor каким-то образом окажется в той же самой области памяти, что и data? Что, если, изменив data[0], мы тем самым изменим и значение factor? Это маловерятно, но, чисто технически, в стандарте это разрешено, поэтому компилятору приходится действовать осторожно.

«Но это же безумие», — скажете вы, — «я бы так никогда не сделал». Но компилятор об этом не знает, так как вы ему не сообщили.

Правильно:

// Версия 2: с __restrict__ (или restrict в C99)void scale(float* __restrict__ data, float factor, int n) {    for (int i = 0; i < n; i++) {        data[i] *= factor;    }}

Вы сообщаете: «Обещаю, что эти указатели совмещаться не будут. Слово чести.”

Теперь посмотрим ассемблер:

; С __restrict__ - мы теперь cooking.loop:    vmovups ymm1, ymmword ptr [rdi + rax]   ; Загружаем ВОСЕМЬ чисел с плавающей точкой    vmulps  ymm1, ymm1, ymm0                ; Перемножаем ВОСЕМЬ чисел с плавающей точкой    vmovups ymmword ptr [rdi + rax], ymm1   ; Сохраняем ВОСЕМЬ чисел с плавающей точкой    add     rax, 32                         ; Продвигаемся на 32 байта (8 чисел с плавающей точкой)    cmp     rax, rcx    jl      .loop

ymm регистры. vmulps (умножаем упакованные значения с плавающей точкой). Теперь компилятор обрабатывает 8 чисел с плавающей точкой за каждую итерацию. Всего один символ (__restrict__) даёт восьмикратное улучшение производительности данного цикла.

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

Пример 2. Распознаём встраивание функций (или его подозрительное отсутствие)

Вот функция:

struct Vec3 {    float x, y, z;    float dot(const Vec3& other) const {        return x * other.x + y * other.y + z * other.z;    }};float compute(const Vec3& a, const Vec3& b) {    return a.dot(b);}

Как вы думаете, что произойдёт при -O2?

Хочется надеяться, что компилятор встроит dot в compute, и у вас получится плотная компактная последовательность операций сложения и умножения. Давайте проверим:

compute(Vec3 const&, Vec3 const&):    vmovss  xmm0, dword ptr [rdi]        ; a.x    vmulss  xmm0, xmm0, dword ptr [rsi] ; * b.x    vmovss  xmm1, dword ptr [rdi + 4]   ; a.y    vfmadd231ss xmm0, xmm1, dword ptr [rsi + 4]  ; += a.y * b.y    vmovss  xmm1, dword ptr [rdi + 8]   ; a.z    vfmadd231ss xmm0, xmm1, dword ptr [rsi + 8]  ; += a.z * b.z    ret

Никакой инструкции call. Никакого перехода к Vec3::dot. Функция была полностью встроена — она просто загружает, умножает и умножает-складывает с однократным округлением (vfmadd231ss). Компилятор как насквозь увидел всю вашу абстракцию и выдал именно то, что автор в данном случае написал бы на ассемблере вручную.

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

А теперь рассмотрим такой пример встраивания. Добавим attribute((noinline)) к dot (или просто сделаем её virtual):

compute(Vec3 const&, Vec3 const&):    ; ... сохраняем регистры, устанавливаем кадр вызова ...    call    Vec3::dot(Vec3 const&) const    ; ... восстанавливаем регистры ...    ret

Вот ваш call. Внезапно у вас возникают издержки на вызов функции, исчезает всяческая возможность просачивания оптимизаций из окружающего кода в его внутренние механизмы, а также потенциально при возврате функции могут неправильно прогнозироваться ветвления. Всё — за скалярное произведение трёх чисел с плавающей точкой.

Урок: virtual даром не даётся. Равно как нельзя просто так помещать тела функций в файлы  .cpp, когда компилятор не может увидеть их на месте вызова. Компилятор может встраивать только то, что может видеть.

Пример 3. Неправильно скомпонованная структура, погубившая производительность

Эта проблема гораздо тоньше, и это мой любимый класс багов, поскольку в исходном коде они не видны.

// Казалось бы, безобидная структураstruct Particle {    bool  active;    // 1 байт    float x, y, z;  // 12 байт    float vx, vy, vz; // 12 байт    int   id;        // 4 байта};void update(Particle* particles, int n, float dt) {    for (int i = 0; i < n; i++) {        if (!particles[i].active) continue;        particles[i].x += particles[i].vx * dt;        particles[i].y += particles[i].vy * dt;        particles[i].z += particles[i].vz * dt;    }}

Выглядит нормально. Скомпилируем это. Рассмотрим ассемблер.

Вы уже видите: никакой векторизации. Компилятор не может векторизовать сразу множество структур Particle, так как active — это булево значение bool внутри структуры. В цикле есть ветвление, причём, данные x, y, z от разных частиц не лежат непрерывно — частично они дозаполнены нулями, а также между ними есть другие поля. Авто-векторизатор на этом сдаётся.

Вероятно, sizeof(Particle) имеет размер 32 байта, поскольку здесь применяется выравнивание. Итак, x  частицы 0 находится со сдвигом  4, x частицы 1 — со сдвигом 36, x частицы 2 — со сдвигом 68… эти участки не образуют в памяти непрерывную область. А для SIMD нужны непрерывные данные.

Правильно: используем структуру массивов  (SoA), а не массив структур (AoS)

// Реорганизовано в духе дата-ориентированного проектированияstruct ParticleSystem {    bool*  active;    float* x;    float* y;    float* z;    float* vx;    float* vy;    float* vz;    int*   id;    int    count;};void update(ParticleSystem& ps, float dt) {    for (int i = 0; i < ps.count; i++) {        if (!ps.active[i]) continue;        ps.x[i] += ps.vx[i] * dt;        ps.y[i] += ps.vy[i] * dt;        ps.z[i] += ps.vz[i] * dt;    }}

Теперь все значения x расположены непрерывно. Все значения vx расположены непрерывно. Векторизатор может одновременно загрузить 8 значений x, одновременно 8 значений vx, перемножить их и добавить обратно. Ассемблер преображается из грустных скалярных загрузок в славные упакованные SIMD.

А если полностью отделить массив active и обрабатывать его в рамках предварительного прохода, потенциально можно вообще удалить ветку из внутреннего цикла.

На взгляд человека исходный код C++ выглядит хуже. Ассемблер кажется радикально лучше. Именно к такому компромиссу подталкивает нас дата-ориентированное проектирование, а чтобы проверить, насколько нам это преобразование подходит, нужно прочитать ассемблер.  

Пример 4. Небольшое изменение, а вывод совершенно другой

Покажу вам ещё одну вещь, которая по-прежнему вызывает у меня улыбку.

// Версия Aint sum_array(const int* arr, int n) {    int total = 0;    for (int i = 0; i < n; i++) {        total += arr[i];    }    return total;}

Скомпилировано с опцией -O3 -march=x86-64-v3:

; Векторизованный цикл редукции.loop:    vpaddd  ymm0, ymm0, ymmword ptr [rdi + rax]  ; складываем 8 целых чисел одновременно     add     rax, 32    cmp     rax, rdx    jl      .loop; Сумма ymm0 по горизонтали...vextracti128 xmm1, ymm0, 1vpaddd       xmm0, xmm0, xmm1vphaddd      xmm0, xmm0, xmm0vphaddd      xmm0, xmm0, xmm0vmovd        eax, xmm0ret

Красиво. За одну итерацию складывается 8 целых чисел, а в конце суммируем по горизонтали.

А теперь — то самое «небольшое изменение»:

// Версия B – переполнение знаковых целых приводит к неопределённому поведению! // Компилятор ЗНАЕТ, что сумма не может приводить к критичным вариантам переполнения, // но такое впечатление складывается у него именно из-за неопределённого поведения int sum_array(const int* arr, int n) {    int total = 0;    for (int i = 0; i < n; i++) {        total += arr[i];        if (total < 0) break;  // При переполнении экстренно выходим    }    return total;}

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

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

Как именно пользоваться этим на практике

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

1. Сначала профилируем. Находим, где у нас горячие точки. Под Mac для этого применяются  perf, VTune, Instruments — у вас на платформе могут быть другие инструменты. На данном этапе ищем тот 1% кода, на выполнение которого уходит 50% времени.

2. Изучаем эти горячие точки. Вставляем их в Compiler Explorer. Далее проверяем:

• Используются ли во внутренних циклах xmm (скаляр) в случаях, когда вы ожидаете ymm (вектор)?

• Видите ли вы инструкции call в большем количестве, чем ожидали? (может быть, встраивание не сработало)

• Есть ли внутри цикла ветвление, которого там быть не должно?

• Происходят ли операции загрузки и сохранения многократно с одними и теми же данными? (Может быть, подвёл анализ совмещения имён)

3. Измените что-то одно. Перекомпилируйте. Сравните. Это самое важное умение. Ровно одно изменение. Потом смотрим, пошло ли это на пользу ассемблеру. Не гадаем, проверяем.

4. Измеряйте. Если ассемблер выглядит лучше, это ещё не гарантирует, что он работает быстрее. Эффекты кэширования, неупорядоченное выполнение, предсказание ветвлений — всё это может смазать показатели, которые интуитивно выводятся по внешнему виду ассемблера. Всегда расставляйте бенчмарки, пользуйтесь при этом реалистичными объёмами данных.

Редфлаги, на которые следует обращать внимание при работе с ассемблером

Вот краткая сводка тех вещей, которые должны вас насторожить:

Вместо заключения

Компилятор C++ вам не враг. Его правильнее сравнить с чрезвычайно талантливым коллегой, который слегка перестраховывается. Он невероятно помогает вам — объединяет операции умножения, разматывает циклы, выполняет по восемь операций за раз — но лишь при условии, что всё это определённо безопасно. Чем дальше, тем сильнее ваша задача сводится к тому, чтобы уверить в этом компилятор.

restrict. Единообразно скомпонованные структуры. Тела функций хорошо видны. Расточительные ветвления в горячих циклах по возможности не допускаются. Ничто из этого не является экзотикой. Но вам ни за что не узнать, когда именно вам всё это понадобится, пока вы не посмотрите, что именно выдаёт вам компилятор.

Ассемблер не врёт. Врут ваши абстракции. Если вы стремитесь к высокой производительности, но не заглядываете в ассемблер, то вы оптимизируете вслепую.

Начните с одной функции. Откройте Compiler Explorer. Нажмите -O2. Посмотрите, что там. Возможно, вы ужаснётесь. Или восхититесь. Как бы то ни было, вы станете понимать ваш код так полно как никогда ранее.

И знаете, что ещё? Есть что-то глубоко приятное в том, когда смотришь на vmulps ymm0, ymm0, ymm1 — восемь операций умножения одновременно, полученных из простого *=в вашем C++ — и думаете: ого. А ведь получилось.

Приложение: полезные ссылки

• Compiler Explorer — теперь вы здесь живёте

• Руководства по оптимизации от Эгню Фога — библия по оптимизации для x86

• Выступление Мэтта Годболта на CppCon talk “What Has My Compiler Done for Me Lately?” вдохновившее целое поколение разработчиков всматриваться в ассемблер

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