У меня была функция, которая выглядела так (показывая только важную часть):
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. Часто это именно та семантика, которая вам требуется. Например, рассмотрим следующий код:Вы должны убедиться, что указатель ненулевой, прежде чем разыменовать его. Если бы это не было оценкой короткого замыкания, у вас было бы неопределенное поведение, потому что вы бы разыменовывали нулевой указатель.
Также возможно, что оценка короткого замыкания дает выигрыш в производительности в тех случаях, когда оценка условий является дорогостоящим процессом. Например:
Если
DoLengthyCheck1
не получается, нет смысла звонитьDoLengthyCheck2
.Однако в результирующем двоичном файле операция короткого замыкания часто приводит к двум ветвям, поскольку компилятору это самый простой способ сохранить эту семантику. (Вот почему, с другой стороны, оценка короткого замыкания может иногда препятствовать потенциалу оптимизации.) Это можно увидеть, посмотрев соответствующую часть объектного кода, сгенерированного для вашего
if
утверждения в GCC 5.4:Здесь вы видите два сравнения (
cmp
инструкции), каждое из которых сопровождается отдельным условным переходом / переходом (ja
или переходом, если указано выше).Общим правилом является то, что ветви медленные и поэтому их следует избегать в узких петлях. Это справедливо практически для всех процессоров x86, начиная со скромного 8088 (чье медленное время выборки и чрезвычайно малая очередь предварительных выборок [сравнимо с кэшем команд]) в сочетании с полным отсутствием предсказания ветвлений означало, что для взятых ветвей требовался сброс кеша ) к современным реализациям (чьи длинные конвейеры делают неправильно предсказанные ответвления столь же дорогими). Обратите внимание на маленькое предостережение, которое я тут подсунул. Современные процессоры, начиная с Pentium Pro, имеют усовершенствованные механизмы прогнозирования филиалов, которые предназначены для минимизации затрат на филиалы. Если направление филиала может быть правильно предсказано, стоимость минимальна. В большинстве случаев это работает хорошо, но если вы попадаете в патологические случаи, когда предсказатель ветвления не на вашей стороне,Ваш код может быть очень медленным . Это, вероятно, где вы находитесь здесь, так как вы говорите, что ваш массив не отсортирован.
Вы говорите, что тесты подтвердили, что замена на
&&
a*
делает код заметно быстрее. Причина этого очевидна, когда мы сравним соответствующую часть объектного кода:Немного нелогично, что это может быть быстрее, так как здесь больше инструкций, но так иногда работает оптимизация. Вы видите,
cmp
что здесь выполняется то же сравнение ( ), но теперь каждому предшествует a,xor
а затем asetbe
. XOR - это просто стандартный трюк для очистки регистра. Этоsetbe
инструкция x86, которая устанавливает бит на основе значения флага и часто используется для реализации кода без ответвлений. Здесьsetbe
обратное значениеja
. Он устанавливает регистр назначения на 1, если сравнение было ниже или равно (так как регистр был предварительно обнулен, иначе будет 0), тогда какja
разветвленное, если сравнение было выше. После того, как эти два значения были получены вr15b
иr14b
регистры, они умножаются вместе с помощьюimul
. Умножение традиционно было относительно медленной операцией, но оно чертовски быстро на современных процессорах, и это будет особенно быстро, потому что оно умножает только два байтовых значения.Вы могли бы также легко заменить умножение на побитовый оператор AND (
&
), который не выполняет оценку короткого замыкания. Это делает код намного понятнее и является шаблоном, который обычно распознают компиляторы. Но когда вы делаете это со своим кодом и компилируете его с GCC 5.4, он продолжает излучать первую ветку:Нет технической причины, по которой он должен был генерировать код таким образом, но по какой-то причине его внутренняя эвристика говорит ему, что это быстрее. Вероятно, было бы быстрее, если бы предсказатель ветвления был на вашей стороне, но, скорее всего, он был бы медленнее, если предсказание ветвления не удавалось чаще, чем успешное.
Новые поколения компиляторов (и других компиляторов, таких как Clang) знают это правило и иногда используют его для генерации того же кода, который вы искали бы при ручной оптимизации. Я регулярно вижу, как Clang переводит
&&
выражения в один и тот же код, который был бы создан, если бы я использовал&
. Ниже приведен соответствующий вывод из GCC 6.2 с вашим кодом с использованием обычного&&
оператора:Обратите внимание, насколько это умно ! Он использует подписанные условия (
jg
иsetle
) в отличие от неподписанных условий (ja
иsetbe
), но это не важно. Вы можете видеть, что он по-прежнему выполняет сравнение и ветвление для первого условия, как и в более старой версии, и использует ту жеsetCC
инструкцию для генерации кода без ответвлений для второго условия, но он стал намного эффективнее в том, как он выполняет приращение. , Вместо второго избыточного сравнения, чтобы установить флаги дляsbb
операции, он использует знания, которыеr14d
будут равны либо 1, либо 0, чтобы просто безоговорочно добавить это значениеnontopOverlap
. Еслиr14d
равно 0, то добавление не работает; в противном случае он добавляет 1, точно так же, как это должно быть.GCC 6.2 фактически производит более эффективный код, когда вы используете
&&
оператор короткого замыкания, чем побитовый&
оператор:Ветвь и условный набор все еще там, но теперь он возвращается к менее умному способу приращения
nontopOverlap
. Это важный урок того, почему вы должны быть осторожны, пытаясь превзойти ваш компилятор!Но если вы сможете с помощью тестов доказать, что код ветвления на самом деле медленнее, то стоит заплатить, чтобы попытаться превзойти ваш компилятор. Вы просто должны сделать это с тщательной проверкой разборки и быть готовым пересмотреть свои решения при обновлении до более поздней версии компилятора. Например, ваш код может быть переписан как:
Здесь вообще нет никаких
if
заявлений, и подавляющее большинство компиляторов никогда не подумают об испускании кода ветвления для этого. GCC не является исключением; все версии генерируют что-то похожее на следующее:Если вы следовали предыдущим примерам, это должно показаться вам знакомым. Оба сравнения сделаны в внеофисному образом, промежуточные результаты
and
ред вместе, и затем этот результат (который будет либо 0 , либо 1)add
ред кnontopOverlap
. Если вам нужен код без ответвлений, это фактически гарантирует, что вы его получите.GCC 7 стал еще умнее. Теперь он генерирует практически идентичный код (исключая небольшую перестановку инструкций) для вышеприведенного трюка в качестве исходного кода. Итак, ответ на ваш вопрос: «Почему компилятор так себя ведет?» вероятно потому что они не идеальны! Они пытаются использовать эвристику для генерации наиболее оптимального кода, но не всегда принимают лучшие решения. Но, по крайней мере, они могут стать умнее со временем!
Один способ взглянуть на эту ситуацию состоит в том, что код ветвления имеет лучшую производительность в лучшем случае . Если прогноз ветвления успешен, пропуск ненужных операций приведет к немного более быстрому времени выполнения. Однако код без ответвлений имеет лучшую производительность в худшем случае . Если прогноз ветвления не удался, выполнение нескольких дополнительных инструкций по мере необходимости, чтобы избежать ветвления, определенно будет быстрее, чем ошибочно предсказанная ветвь. Даже самым умным и умным компиляторам будет нелегко сделать этот выбор.
И на ваш вопрос о том, нужно ли программистам следить за этим, ответ почти наверняка нет, за исключением определенных горячих циклов, которые вы пытаетесь ускорить с помощью микрооптимизаций. Затем вы садитесь с разборкой и находите способы ее настройки. И, как я уже говорил, будьте готовы вернуться к этим решениям при обновлении до более новой версии компилятора, поскольку он может либо сделать что-то глупое с вашим хитрым кодом, либо изменить настолько оптимистическую эвристику, что вы сможете вернуться назад. чтобы использовать ваш оригинальный код. Тщательно комментируйте!
источник
j*
инструкций), поэтому в этом случае он будет быстрее. [продолжение]Важно отметить, что
и
не семантически эквивалентны! В частности, если у вас когда-нибудь возникнет ситуация, когда:
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 в ситуации, в которой это не требуется.Короче говоря, оригинальный фрагмент кода предлагает меньше возможностей для оптимизации, чем последний. (конечно, признает ли компилятор возможность, это совершенно другой вопрос)
Вы можете исправить оригинальную версию, выполнив
источник
shift
(иmax
) здесь есть UB ...&&
Оператор осуществляет оценку короткого замыкания. Это означает, что второй операнд оценивается, только если первый опрашиваетtrue
. Это, безусловно, приводит к скачку в этом случае.Вы можете создать небольшой пример, чтобы показать это:
Выход на ассемблере можно найти здесь .
Вы можете увидеть сгенерированный код, сначала вызывая
f(x)
, затем проверяя вывод и переходя к оценке того,g(x)
когда это былоtrue
. В противном случае он выходит из функции.Использование «логического» умножения вместо этого заставляет каждый раз вычислять оба операнда и, таким образом, не требует скачка.
В зависимости от данных, скачок может вызвать замедление, потому что это нарушает конвейер ЦП и другие вещи, такие как спекулятивное выполнение. Обычно помогает прогнозирование ветвлений, но если ваши данные случайные, мало что можно предсказать.
источник
&&
оператора, умножение может быть лениво вычислено либо с первым, либо со вторым аргументом, что дает больше свободы для оптимизации.0 * f()
иf
наблюдаете поведение, компилятор должен вызвать его. Разница в том, что оценка короткого замыкания обязательна,&&
но допустима, если она может показать, что она эквивалентна*
.Это может быть связано с тем, что при использовании логического оператора
&&
компилятор должен проверить два условия для успешного выполнения оператора if. Однако во втором случае, поскольку вы неявно преобразуете значение типа int в тип bool, компилятор делает некоторые предположения на основе передаваемых типов и значений, а также (возможно) одного условия перехода. Также возможно, что компилятор полностью оптимизирует JMP с помощью битовых сдвигов.источник