Вы значительно недооцениваете стоимость пропуска филиала . Требуется несколько циклов для восстановления после обнаружения пропадания ветви (много стадий конвейера после выборки / декодирования ветви). Что именно происходит, когда процессор Skylake неправильно предсказывает ветвь? .
И по какой-то причине вы предполагаете, что неправильное предположение не переходит к более поздним инструкциям (здесь не показано).
Плюс, добавление подсчета команд очень далеко от точности для оценки пропускной способности или затрат на задержку . Некоторые инструкции имеют более или менее задержку; например, многие современные процессоры x86 имеют нулевую задержку mov
. ( Может ли MOV x86 действительно быть "бесплатным"? Почему я вообще не могу воспроизвести это? ). Для пропускной способности, однако, mov
все еще стоит пропускную способность внешнего интерфейса.
См. Какие соображения относятся к прогнозированию задержки для операций на современных суперскалярных процессорах и как я могу вычислить их вручную? о том, как на самом деле выполнить статический анализ, чтобы выяснить, насколько быстро некоторые код будет работать на современном x86 (в правильно предсказанном случае). Спойлер: это сложно, и иногда то, что оптимально для пропускной способности, не оптимально для задержки, поэтому выбор зависит от окружающего кода. (Работа с независимыми данными по сравнению с длинной цепью, где выход одного является входом для следующего.)
cmov
- это 2 мопа на Intel до Broadwell, а управляющие зависимости находятся вне критического пути (благодаря умозрительному выполнению). Таким образом, с правильным прогнозом, ветвистый код может быть превосходным по сравнению с наличием зависимости от данных для выбора правильного результата после вычисления обоих (http://yarchive.net/comp/linux/cmov.html). Вот пример, где cmov
была пессимизация: флаг оптимизации gcc -O3 делает код медленнее, чем -O2 .
Если предсказание ветвлений не удается в 50% случаев (т. Е. Не лучше, чем шанс!), Цикл, включающий версию cmov
, может быть примерно в 10 раз быстрее.
@ Реальные тесты Mysticial для ветвлений и ветвлений показывают коэффициент ускорения в 5 раз для безветвлений при этом условии по случайному (не отсортированному) массиву:
if (data[c] >= 128)
sum += data[c];
Почему быстрее обрабатывать отсортированный массив, чем несортированный массив? . (С отсортированными данными в этом случае ветвление лишь немного быстрее. Очевидно, что некоторые другие узкие места мешали ветвлению работать намного быстрее на Nehalem Мистиалиса.)
50% вероятности неверного прогнозирования ветвей будет абсолютно ужасным, почти наихудшим. Даже 20% действительно плохо; современные предсказатели ветвей смехотворно хороши, если в истории ветвей есть какой-либо паттерн. например Skylake может полностью предсказать ветвление в BubbleSort по 12 элементам, если оно выполняется многократно с одними и теми же входными данными каждый раз как часть микробенчмарка.
Но зацикливание случайных данных может быть крайне непредсказуемым.
Ваш исходный код - это все изображения, поэтому я не могу скопировать / вставить его в проводник компилятора Godbolt (https://godbolt.org/) и посмотреть, что делают современные gcc и clang при компиляции с -O3
. Я подозреваю, что будет более эффективным, чем пример кода, который вы показываете: похоже, много mov
, и cmov
должен иметь возможность использовать флаги, установленные sub
. Это то, что я ожидал (или, по крайней мере, надеюсь) из вашей absdiff
функции:
# loading args into registers not shown, only necessary with crappy stack-args calling conventions
# branchless absdiff. Hand-written.
# Compilers should do something like this if they choose branchless at all.
# inputs in x=%edi, y=%esi
mov %edi, %eax
sub %esi, %eax # EAX= x-y
sub %edi, %esi # ESI= y-x
cmovg %esi, %eax # if(y>x) eax=y-x
# result in EAX
На Бродвелле / Скайлэйке или Райзене:
- обе
sub
инструкции могут выполняться в одном и том же цикле (поскольку mov
имеет нулевую задержку, при условии успешного удаления mov).
cmovg
имеет входы, готовые цикл после этого, и выдает результат еще в 1 цикле.
Итак, у нас есть 4 мопа с задержкой в 2 цикла от x и y до готовности. Haswell и более ранние версии - это дополнительные операции с дополнительным циклом задержки, поскольку cmov
имеет 3 входа, а более ранние процессоры Intel не могут декодировать команды с 3 входами в один UOP.
Вывод компилятора, который вы показываете, довольно плох; слишком много mov
и используя отдельный cmp
. cmp
- это просто sub
, который записывает только флаги, а не операнд целочисленного регистра, и нам уже нужен результат sub
.
Если у вас есть компилятор, который выдает что-то подобное с включенной полной оптимизацией, вместо того, что я показал выше, сообщите об ошибке пропущенной оптимизации.
Как говорит @ Ped7g, компиляторы могут использовать безветвление для if()
или ветвление для троичного, если они решат. Если вы имеете дело с элементами массива, а не с локальными переменными, тернар имеет тенденцию помогать, потому что безоговорочная запись переменной позволяет компилятору оптимизировать, не беспокоясь о том, чтобы наступить на то, что делает другой поток. (т.е. компилятор не может изобрести записи в потенциально общие переменные, но троичный оператор всегда пишет.)
как заставить использовать cmov в gcc и VS
AVX-512 и ветвление