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

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

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

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

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, имеют усовершенствованные механизмы прогнозирования филиалов, которые предназначены для минимизации затрат на филиалы. Если направление филиала может быть правильно предсказано, стоимость минимальна. В большинстве случаев это работает хорошо, но если вы попадаете в патологические случаи, когда предсказатель ветвления не на вашей стороне,Ваш код может быть очень медленным . Это, вероятно, где вы находитесь здесь, так как вы говорите, что ваш массив не отсортирован.

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

    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что здесь выполняется то же сравнение ( ), но теперь каждому предшествует a, xorа затем a 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 стал еще умнее. Теперь он генерирует практически идентичный код (исключая небольшую перестановку инструкций) для вышеприведенного трюка в качестве исходного кода. Итак, ответ на ваш вопрос: «Почему компилятор так себя ведет?» вероятно потому что они не идеальны! Они пытаются использовать эвристику для генерации наиболее оптимального кода, но не всегда принимают лучшие решения. Но, по крайней мере, они могут стать умнее со временем!

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

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

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

(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) {
    // ...

&&Оператор осуществляет оценку короткого замыкания. Это означает, что второй операнд оценивается, только если первый опрашивает 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. В противном случае он выходит из функции.

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

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

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