Как заставить использование cmov в gcc и VS
У меня есть эта простая функция-член бинарный поиск, где lastIndex, nIter а также xi являются членами класса:
uint32 scalar(float z) const
{
uint32 lo = 0;
uint32 hi = lastIndex;
uint32 n = nIter;
while (n--) {
int mid = (hi + lo) >> 1;
// defining this if-else assignment as below cause VS2015
// to generate two cmov instructions instead of a branch
if( z < xi[mid] )
hi = mid;
if ( !(z < xi[mid]) )
lo = mid;
}
return lo;
}
И gcc, и VS 2015 переводят внутренний цикл с помощью ветви потока кода:
000000013F0AA778 movss xmm0,dword ptr [r9+rax*4]
000000013F0AA77E comiss xmm0,xmm1
000000013F0AA781 jbe Tester::run+28h (013F0AA788h)
000000013F0AA783 mov r8d,ecx
000000013F0AA786 jmp Tester::run+2Ah (013F0AA78Ah)
000000013F0AA788 mov edx,ecx
000000013F0AA78A mov ecx,r8d
Есть ли способ, без написания встроенного ассемблера, чтобы убедить их использовать именно 1 comiss инструкция и 2 cmov инструкции?
Если нет, может кто-нибудь предложить, как написать шаблон ассемблера gcc для этого?
Обратите внимание, что я знаю, что существуют варианты алгоритма бинарного поиска, когда компилятору легко генерировать свободный от ветвления код, но это не вопрос.
Спасибо
2 ответа
Как сказано в комментариях, нет простого способа заставить то, что вы просите, хотя кажется, что последние (>4.4) версии gcc уже оптимизируют его, как вы сказали. Редактировать: интересно, серия gcc 6, кажется, использует ветку, в отличие от серий gcc 5 и gcc 7, которые используют два cmov,
Обычный __builtin_expect вероятно, не может многое сделать, чтобы использовать gcc cmov, При условии cmov обычно удобно, когда трудно предсказать результат сравнения, в то время как __builtin_expect говорит компилятору, каков вероятный результат - так что вы просто подтолкнете его в неправильном направлении.
Тем не менее, если вы обнаружите, что эта оптимизация чрезвычайно важна, ваша версия компилятора обычно ошибается, и по какой-то причине вы не можете помочь ей с PGO, соответствующий шаблон сборки gcc должен выглядеть примерно так:
__asm__ (
"comiss %[xi_mid],%[z]\n"
"cmovb %[mid],%[hi]\n"
"cmovae %[mid],%[lo]\n"
: [hi] "+r"(hi), [lo] "+r"(lo)
: [mid] "rm"(mid), [xi_mid] "xm"(xi[mid]), [z] "x"(z)
: "cc"
);
Используемые ограничения:
hiа такжеloв список "записи" переменных, с+rограничение какcmovможет работать только с регистрами в качестве целевых операндов, и мы условно перезаписываем только один из них (мы не можем использовать=, поскольку это подразумевает, что значение всегда перезаписывается, поэтому компилятор может предоставить нам другой целевой регистр, чем текущий, и использовать его для обращения к этой переменной после нашегоasmблок);midнаходится в списке "чтения",rmкакcmovможет принимать регистр или операнд памяти в качестве входного значения;xi[mid]а такжеzнаходятся в списке "прочитано";zимеет особыйxограничение, которое означает "любой регистр SSE" (требуется дляucomissпервый операнд);xi[mid]имеетxm, как второйucomissоперанд позволяет оператору памяти; учитывая выбор междуzа такжеxi[mid]Я выбрал последний как лучший кандидат для того, чтобы быть взятым непосредственно из памяти, учитывая, чтоzуже находится в регистре (из-за соглашения о вызовах System V - и все равно будет кэшироваться между итерациями) иxi[mid]используется только в этом сравнении;
cc(регистр FLAGS) находится в списке "clobber" - мы делаем clobber флаги и больше ничего.
Как уже отмечал Matteo Italia, такое избегание инструкций условного перемещения - это особенность GCC версии 6. Однако он не заметил, что он применяется только при оптимизации для процессоров Intel.
С GCC 6.3, когда нацелен на процессоры AMD (т.е. -march= любой из k8, k10, opteron, amdfam10, btver1, bdver1, btver2, btver2, bdver3, bdver4, znver1 и, возможно, другие), вы получите именно тот код, который вы хотите:
mov esi, DWORD PTR [rdi]
mov ecx, DWORD PTR [rdi+4]
xor eax, eax
jmp .L2
.L7:
lea edx, [rax+rsi]
mov r8, QWORD PTR [rdi+8]
shr edx
mov r9d, edx
movss xmm1, DWORD PTR [r8+r9*4]
ucomiss xmm1, xmm0
cmovbe eax, edx
cmova esi, edx
.L2:
dec ecx
cmp ecx, -1
jne .L7
rep ret
При оптимизации для любого поколения процессоров Intel GCC 6.3 избегает условных перемещений, предпочитая явную ветвь:
mov r9d, DWORD PTR [rdi]
mov ecx, DWORD PTR [rdi+4]
xor eax, eax
.L2:
sub ecx, 1
cmp ecx, -1
je .L6
.L8:
lea edx, [rax+r9]
mov rsi, QWORD PTR [rdi+8]
shr edx
mov r8d, edx
vmovss xmm1, DWORD PTR [rsi+r8*4]
vucomiss xmm1, xmm0
ja .L4
sub ecx, 1
mov eax, edx
cmp ecx, -1
jne .L8
.L6:
ret
.L4:
mov r9d, edx
jmp .L2
Вероятное обоснование этого решения по оптимизации заключается в том, что условные перемещения довольно неэффективны на процессорах Intel. CMOV имеет задержку в 2 такта на процессорах Intel по сравнению с задержкой в 1 такт на AMD. Кроме того, в то время как CMOV инструкции декодируются в несколько µop (по крайней мере, два без возможности объединения µop) на процессорах Intel из-за требования, что один µop имеет не более двух входных зависимостей (условный ход имеет как минимум три: два операнда и флаг), процессоры AMD могут реализовать CMOV с одной макрооперацией, так как их дизайн не имеет таких ограничений на входные зависимости одной макрооперации. Таким образом, оптимизатор GCC заменяет ветви условными перемещениями только на процессорах AMD, где это может привести к выигрышу в производительности - не на процессорах Intel и не при настройке универсального x86.
(Или, может быть, разработчики GCC только что прочитали печально известную речь Линуса.:-)
Интересно, однако, что когда вы указываете GCC настраиваться на процессор Pentium 4 (и по какой-то причине вы не можете сделать это для 64-битных сборок - GCC говорит вам, что эта архитектура не поддерживает 64-битную версию, несмотря на то, что безусловно, процессоры P4, которые реализовали EMT64), вы получаете условные ходы:
push edi
push esi
push ebx
mov esi, DWORD PTR [esp+16]
fld DWORD PTR [esp+20]
mov ebx, DWORD PTR [esi]
mov ecx, DWORD PTR [esi+4]
xor eax, eax
jmp .L2
.L8:
lea edx, [eax+ebx]
shr edx
mov edi, DWORD PTR [esi+8]
fld DWORD PTR [edi+edx*4]
fucomip st, st(1)
cmovbe eax, edx
cmova ebx, edx
.L2:
sub ecx, 1
cmp ecx, -1
jne .L8
fstp st(0)
pop ebx
pop esi
pop edi
ret
Я подозреваю, что это связано с тем, что неправильное прогнозирование ветвлений в Pentium 4 является настолько дорогим из-за его чрезвычайно длинного конвейера, что вероятность единственного неверно предсказанного перехода перевешивает любые незначительные выгоды, которые вы можете получить от разрыва зависимостей, переносимых циклами, и незначительного увеличения задержки от CMOV, Другими словами, на P4 неправильно предсказанные ветви стали намного медленнее, но задержка CMOV не изменился, так что это смещает уравнение в пользу условных ходов.
При настройке на более поздние архитектуры, от Nocona до Haswell, GCC 6.3 восходит к своей стратегии предпочтения ветвей над условными перемещениями.
Таким образом, хотя это выглядит как серьезная пессимизация в контексте тесного внутреннего цикла (и мне бы это тоже выглядело так), не спешите отмахиваться от него без эталона, чтобы подтвердить свои предположения, Иногда оптимизатор не так глуп, как кажется. Помните, что преимущество условного хода состоит в том, что оно позволяет избежать штрафа за неправильные прогнозы ветвления; недостаток условного перемещения состоит в том, что он увеличивает длину цепочки зависимостей и может потребовать дополнительных затрат, поскольку на x86 допускаются только условные перемещения регистр-регистр. В этом случае все уже зарегистрировано, но есть еще длина цепочки зависимостей, которую необходимо учитывать. Агнер Фог в своей Оптимизации подпрограмм на языке ассемблера дает нам следующее практическое правило:
[W] можно сказать, что условный переход быстрее, чем условный переход, если код является частью цепочки зависимостей, а уровень прогнозирования лучше, чем 75%. Условный переход также предпочтителен, если мы можем избежать длинных вычислений... когда выбран другой операнд.
Вторая часть этого здесь не применима, но первая применима. Здесь определенно существует цепочка зависимостей, переносимая циклами, и, если вы не попадете в действительно патологическую ситуацию, которая нарушает предсказание ветвления (которая обычно имеет точность>90%), ветвление может на самом деле быть быстрее. На самом деле Агнер Фог продолжает:
Цепочки зависимостей, переносимые циклами, особенно чувствительны к недостаткам условных перемещений. Например, [этот код]
// Example 12.16a. Calculate pow(x,n) where n is a positive integer double x, xp, power; unsigned int n, i; xp=x; power=1.0; for (i = n; i != 0; i >>= 1) { if (i & 1) power *= xp; xp *= xp; }работает более эффективно с ветвью внутри цикла, чем с условным перемещением, даже если ветвь плохо предсказана. Это связано с тем, что условное перемещение с плавающей запятой добавляет к цепочке зависимостей, переносимых циклом, и потому что реализация с условным перемещением должна вычислить все
power*xpзначения, даже когда они не используются.Другим примером цепочки зависимостей, переносимых циклами, является бинарный поиск в отсортированном списке. Если элементы для поиска случайным образом распределены по всему списку, тогда коэффициент предсказания ветвлений будет близок к 50%, и будет быстрее использовать условные перемещения. Но если элементы часто находятся близко друг к другу, так что скорость прогнозирования будет лучше, тогда более эффективно использовать условные переходы, чем условные перемещения, потому что цепь зависимостей разрывается каждый раз, когда делается правильный прогноз ветвления.
Если элементы в вашем списке на самом деле случайные или близкие к случайным, то вы станете жертвой повторного сбоя предсказания ветвления, и условные перемещения будут быстрее. В противном случае, в том, что, вероятно, является более распространенным случаем, прогнозирование ветвлений будет успешным>75% времени, так что вы получите выигрыш в производительности от ветвления, в отличие от условного перемещения, которое расширит цепочку зависимостей.
Это трудно рассуждать теоретически, и еще сложнее правильно угадать, поэтому вам нужно сравнить его с реальными числами.
Если ваши тесты подтвердят, что условные перемещения действительно будут быстрее, у вас есть несколько вариантов:
- Обновите GCC до более поздней версии, например 7.1, которая генерирует условные перемещения в 64-разрядных сборках даже при использовании процессоров Intel.
- Скажите GCC 6.3, чтобы оптимизировать ваш код для процессоров AMD. (Возможно, даже просто оптимизировать один конкретный модуль кода, чтобы минимизировать глобальные эффекты.)
Станьте действительно креативными (и уродливыми и, возможно, непереносимыми), написав некоторый бит-код в C, который выполняет операции сравнения и установки без ветвей. Это может заставить компилятор выдавать инструкцию условного перемещения, или он может заставить компилятор выдать серию команд с изменением битов. Вы должны были бы проверить выходные данные, чтобы быть уверенными, но если ваша цель на самом деле просто избежать штрафов за неверное предсказание ветвлений, то любой из них будет работать.
Например, что-то вроде этого:
inline uint32 ConditionalSelect(bool condition, uint32 value1, uint32 value2) { const uint32 mask = condition ? static_cast<uint32>(-1) : 0; uint32 result = (value1 ^ value2); // get bits that differ between the two values result &= mask; // select based on condition result ^= value2; // condition ? value1 : value2 return result; }который вы бы затем вызвали внутри вашего внутреннего цикла следующим образом:
hi = ConditionalSelect(z < xi[mid], mid, hi); lo = ConditionalSelect(z < xi[mid], lo, mid);GCC 6.3 производит следующий код для этого при нацеливании на x86-64:
mov rdx, QWORD PTR [rdi+8] mov esi, DWORD PTR [rdi] test edx, edx mov eax, edx lea r8d, [rdx-1] je .L1 mov r9, QWORD PTR [rdi+16] xor eax, eax .L3: lea edx, [rax+rsi] shr edx mov ecx, edx mov edi, edx movss xmm1, DWORD PTR [r9+rcx*4] xor ecx, ecx ucomiss xmm1, xmm0 seta cl // <-- begin our bit-twiddling code xor edi, esi xor eax, edx neg ecx sub r8d, 1 // this one's not part of our bit-twiddling code! and edi, ecx and eax, ecx xor esi, edi xor eax, edx // <-- end our bit-twiddling code cmp r8d, -1 jne .L3 .L1: rep retОбратите внимание, что внутренний цикл полностью не имеет ответвлений, а это именно то, что вы хотели. Это может быть не так эффективно, как два
CMOVинструкции, но это будет быстрее, чем хронически неверно предсказанные ветки. (Само собой разумеется, что GCC и любой другой компилятор будет достаточно умен, чтобы встроитьConditionalSelectфункция, которая позволяет нам писать это вне строки для удобства чтения.)
Однако то, что я определенно не рекомендую, это переписать любую часть цикла с использованием встроенной сборки. Все стандартные причины применяются для избежания встроенной сборки, но в этом случае даже стремление к повышению производительности не является веской причиной для ее использования. С большей вероятностью вы запутаете оптимизатор компилятора, если попытаетесь добавить встроенную сборку в середину этого цикла, что приведет к тому, что код подпаритета окажется хуже, чем тот, который вы получили бы в противном случае, если бы вы просто оставили компилятор на его собственных устройствах., Возможно, вам придется написать всю функцию во встроенной сборке, чтобы получить хорошие результаты, и даже в этом случае возможны побочные эффекты, когда оптимизатор GCC попытается встроить функцию.
Как насчет MSVC? Ну, разные компиляторы имеют разные оптимизаторы и, следовательно, разные стратегии генерации кода. Вещи могут начать становиться действительно ужасными очень быстро, если вы настроены на то, чтобы уговорить всех целевых компиляторов испустить определенную последовательность кода сборки.
В MSVC 19 (VS 2015) при 32-разрядном таргетинге вы можете написать код так, как вы это делали, чтобы получить инструкции условного перемещения. Но это не работает при построении 64-битного бинарного файла: вместо этого вы получаете ветви, как в GCC 6.3 для Intel.
Однако есть хорошее решение, которое хорошо работает: используйте условный оператор. Другими словами, если вы напишите код так:
hi = (z < xi[mid]) ? mid : hi;
lo = (z < xi[mid]) ? lo : mid;
тогда VS 2013 и 2015 всегда будут излучать CMOV инструкции, создаете ли вы 32-разрядный или 64-разрядный двоичный файл, оптимизируете ли вы размер (/O1) или скорость (/O2) и оптимизируете ли вы для Intel (/favor:Intel64) или AMD (/favor:AMD64).
Это не может привести к CMOV инструкции обратно на VS 2010, но только при сборке 64-битных двоичных файлов. Если вам нужно убедиться, что этот сценарий также генерирует код без ответвлений, вы можете использовать ConditionalSelect функция.