Дорогой прыжок с GCC 5.4.0

Question

У меня была функция, которая выглядела так (показывая только важную часть):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

Написанная так, эта функция заняла ~34 мс на моей машине. После изменения условия на умножение bool (чтобы код выглядел так):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

время выполнения уменьшилось до ~19мс.

Использовался компилятор GCC 5.4.0 с -O3, и после проверки сгенерированного кода asm с помощью godbolt.org я обнаружил, что первый пример генерирует переход, а второй - нет. Я решил попробовать GCC 6.2.0, который также генерирует инструкцию перехода при использовании первого примера, но GCC 7, кажется, больше не генерирует ее.

Поиск такого способа ускорения кода был довольно ужасным и занял довольно много времени. Почему компилятор ведет себя так? Это предназначено, и это - что-то, что программисты должны высматривать? Есть ли еще что-то подобное?

РЕДАКТИРОВАТЬ: ссылка на Godbolt https://godbolt.org/g/5lKPF3

Answer 1

Логический оператор И (&&) использует оценку короткого замыкания, что означает, что второй тест выполняется только в том случае, если первое сравнение оценивается как истинное. Часто это именно та семантика, которая вам требуется. Например, рассмотрим следующий код:

if ((p != nullptr) && (p->first > 0))

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

Также возможно, что оценка короткого замыкания дает выигрыш в производительности в тех случаях, когда оценка условий является дорогостоящим процессом. Например:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

Если DoLengthyCheck1 не получается, нет смысла звонить DoLengthyCheck2,

Однако в полученном двоичном файле операция короткого замыкания часто приводит к двум ветвям, поскольку компилятору это самый простой способ сохранить эту семантику. (Вот почему, с другой стороны, оценка короткого замыкания может иногда препятствовать потенциалу оптимизации.) Это можно увидеть, посмотрев на соответствующую часть объектного кода, сгенерированного для вашего if заявление GCC 5.4:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

Вы видите здесь два сравнения (cmp инструкции) здесь, за каждым следует отдельный условный переход / ветвь (jaили прыгайте, если выше).

Общим правилом является то, что ветви медленные и поэтому их следует избегать в узких петлях. Это справедливо практически для всех процессоров x86, начиная со скромного 8088 (чье медленное время выборки и чрезвычайно небольшая очередь предварительной выборки [сравнимо с кэшем команд]) в сочетании с полным отсутствием предсказания ветвлений означало, что для взятых ветвей требовался сброс кеша) к современным реализациям (чьи длинные конвейеры делают неправильно предсказанные ответвления столь же дорогими). Обратите внимание на маленькое предостережение, которое я тут подсунул. Современные процессоры, начиная с Pentium Pro, имеют усовершенствованные механизмы прогнозирования филиалов, которые предназначены для минимизации затрат на филиалы. Если направление филиала может быть правильно предсказано, стоимость минимальна. В большинстве случаев это работает хорошо, но если вы попадаете в патологические случаи, когда предсказатель ветвления не на вашей стороне, ваш код может работать очень медленно. Это, вероятно, где вы находитесь здесь, так как вы говорите, что ваш массив не отсортирован.

Вы говорите, что тесты подтвердили, что замена && с * делает код заметно быстрее Причина этого очевидна, когда мы сравним соответствующую часть объектного кода:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Немного нелогично, что это может быть быстрее, так как здесь больше инструкций, но так иногда и работает оптимизация. Вы видите те же сравнения (cmp) делается здесь, но теперь каждому предшествует xor и сопровождается setbe, XOR - это просто стандартный трюк для очистки регистра. setbe является инструкцией x86, которая устанавливает бит на основе значения флага и часто используется для реализации кода без ответвлений. Вот, setbe обратная ja, Он устанавливает свой регистр назначения в 1, если сравнение было ниже или равно (так как регистр был предварительно обнулен, иначе будет 0), тогда как ja разветвленный, если сравнение было выше. Как только эти два значения были получены в r15b а также r14b регистры, они умножаются вместе с помощью imul, Умножение традиционно было относительно медленной операцией, но оно чертовски быстро на современных процессорах, и это будет особенно быстро, потому что оно умножает только два байтовых значения.

Вы могли бы так же легко заменить умножение с помощью побитового оператора AND (&), который не выполняет оценку короткого замыкания. Это делает код намного понятнее и является шаблоном, который обычно распознают компиляторы. Но когда вы делаете это со своим кодом и компилируете его с GCC 5.4, он продолжает излучать первую ветку:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

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

Новые поколения компиляторов (и других компиляторов, таких как Clang) знают это правило и иногда используют его для генерации того же кода, который вы искали бы при ручной оптимизации. Я регулярно вижу перевод Clang && выражения к тому же коду, который был бы испущен, если бы я использовал &, Ниже приведен соответствующий вывод из GCC 6.2 с вашим кодом, использующим обычный && оператор:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

Обратите внимание, насколько это умно! Использует подписанные условия (jg а также setle) в отличие от неподписанных условий (ja а также setbe), но это не важно. Вы можете видеть, что он по-прежнему выполняет сравнение и ветвление для первого условия, как в старой версии, и использует те же setCC Инструкция для генерации кода без ответвлений для второго условия, но она стала намного более эффективной в том, как она выполняет приращение. Вместо второго, избыточного сравнения, чтобы установить флаги для sbb операция, она использует знание того, что r14d будет либо 1, либо 0, чтобы просто безоговорочно добавить это значение в nontopOverlap, Если r14d равен 0, тогда добавление не используется; в противном случае он добавляет 1, точно так же, как это должно быть.

GCC 6.2 фактически производит более эффективный код, когда вы используете короткое замыкание && оператор, чем побитовый & оператор:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

Ветвь и условный набор все еще там, но теперь он возвращается к менее умному способу приращения nontopOverlap, Это важный урок того, почему вы должны быть осторожны, пытаясь превзойти ваш компилятор!

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

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

Здесь нет if утверждение здесь вообще, и подавляющее большинство компиляторов никогда не будут думать об испускании кода ветвления для этого. GCC не является исключением; все версии генерируют что-то похожее на следующее:

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

Если вы следовали предыдущим примерам, это должно показаться вам знакомым. Оба сравнения выполняются без ветвления, промежуточные результаты andвместе, а затем этот результат (который будет 0 или 1) addед nontopOverlap, Если вам нужен код без ответвлений, это фактически гарантирует, что вы его получите.

GCC 7 стал еще умнее. Теперь он генерирует практически идентичный код (исключая небольшую перестановку инструкций) для вышеприведенного трюка в качестве исходного кода. Итак, ответ на ваш вопрос: "Почему компилятор так себя ведет?" вероятно потому что они не идеальны! Они пытаются использовать эвристику для генерации наиболее оптимального кода, но не всегда принимают лучшие решения. Но, по крайней мере, они могут стать умнее со временем!

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

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

Answer 2

Важно отметить, что

(curr[i] < 479) && (l[i + shift] < 479)

а также

(curr[i] < 479) * (l[i + shift] < 479)

не семантически эквивалентны! В частности, если у вас когда-либо возникла ситуация, когда:

• 0 <= i а также i < curr.size() оба верны
• curr[i] < 479 ложно
• i + shift < 0 или же i + shift >= l.size() правда

тогда выражение (curr[i] < 479) && (l[i + shift] < 479) гарантированно будет определенным логическим значением. Например, это не вызывает ошибку сегментации.

Однако в этих обстоятельствах выражение (curr[i] < 479) * (l[i + shift] < 479) неопределенное поведение; разрешено вызывать ошибку сегментации.

Это означает, что для исходного фрагмента кода, например, компилятор не может просто написать цикл, который выполняет как сравнения, так и and операция, если компилятор также не может доказать, что l[i + shift] никогда не вызовет segfault в ситуации, когда этого не требуется.

Короче говоря, оригинальный фрагмент кода предлагает меньше возможностей для оптимизации, чем последний. (конечно, признает ли компилятор возможность, это совершенно другой вопрос)

Вы можете исправить оригинальную версию, выполнив

bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
    // ...

Answer 3

&& оператор осуществляет оценку короткого замыкания. Это означает, что второй операнд оценивается только если первый true, Это, безусловно, приводит к скачку в этом случае.

Вы можете создать небольшой пример, чтобы показать это:

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

Выход на ассемблере можно найти здесь.

Вы можете увидеть сгенерированный код первых звонков f(x), затем проверяет вывод и переходит к оценке g(x) когда это было true, В противном случае он покидает функцию.

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

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

Answer 4

Это может быть потому, что когда вы используете логический оператор && компилятор должен проверить два условия для успешного выполнения оператора if. Однако во втором случае, поскольку вы неявно преобразуете значение типа int в тип bool, компилятор делает некоторые предположения на основе передаваемых типов и значений, а также (возможно) одного условия перехода. Также возможно, что компилятор полностью оптимизирует JMP с помощью битовых сдвигов.