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

Ответ 1

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

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

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

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

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, то добавление является no-op; в противном случае он добавляет 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 ed вместе, а затем этот результат (который будет либо 0, либо 1) равен add ed до nontopOverlap. Если вам нужен бесплатный сервер, это практически гарантирует, что вы его получите.

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

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

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

Ответ 2

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

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

и

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

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

• 0 <= i и i < curr.size() являются истинными
• curr[i] < 479 - false
• i + shift < 0 или i + shift >= l.size() истинно

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

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

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

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

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

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

Ответ 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. В противном случае он оставляет функцию.

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

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

Ответ 4

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