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

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

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

С таким же успехом вы могли бы заменить умножение побитовым оператором И (&), который не выполняет оценку короткого замыкания. Это делает код более понятным и обычно распознается компиляторами. Но когда вы делаете это со своим кодом и компилируете его с 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, компилятор делает некоторые предположения на основе передаваемых типов и значений вместе с (возможно) одним условием перехода. Также возможно, что компилятор полностью оптимизирует jmps с битовыми сдвигами.