Оба способа выглядят слишком сложными (и первый глючит при n> = 32) . Чтобы повысить bool до uint64_t 0 или 1, просто используйте приведение uint64_t(a) или C. Вам не нужно a ? 1ull : 0.
Простой способ без ветвления, вероятно, хорош, если только вы не ожидаете, что a будет сильно предсказуемым (например, обычно односторонним или коррелированным с более ранним ветвлением. история ветвей для индексации BHT / BTB.)
uint64_t hr2(uint64_t x, bool a, int n) {
return x | (uint64_t(a) << n);
}
Если вы хотите сделать это более сложным, чтобы избежать UB, когда n выходит за пределы диапазона, напишите свой C ++, чтобы таким же образом обернуть счет смены Инструкции сдвига x86 делают, поэтому компилятору не нужны никакие дополнительные инструкции.
#include <limits>
uint64_t hr3(uint64_t x, bool a, int n) {
using shiftwidth = decltype(x);
const int mask = std::numeric_limits<shiftwidth>::digits - 1;
// wrap the count to the shift width to avoid UB
// x86 does this for free for 32 and 64-bit shifts.
return x | (shiftwidth(a) << (n & mask));
}
Обе версии компилируются одинаково для x86 (потому что простая версия должна работать для всех входных данных без UB).
Это компилируется прилично, если у вас BMI2 (для сдвигов с переменным числом разовых операций на Intel), в противном случае это не очень хорошо. (https://agner.org/optimize/ и https://uops.info/) Но даже тогда есть пропущенные оптимизации от G CC:
# GCC9.2 -O3 -march=skylake
hr3(unsigned long, bool, int):
movzx esi, sil # zero-extend the bool to 64-bit, 1 cycle latency because GCC failed to use a different register
shlx rsi, rsi, rdx # the shift
mov rax, rsi # stupid GCC didn't put the result in RAX
or rax, rdi # retval = shift | x
ret
Это могло быть
# hand optimized, and clang 9.0 -O3 -march=skylake
movzx eax, sil # mov-elimination works between different regs
shlx rax, rax, rdx # don't need to take advantage of copy-and-shift
or rax, rdi
ret
Оказывается, что clang9.0 действительно испускает эту эффективную версию с -O3 -march=skylake или znver1. ( Godbolt ).
Это достаточно дешево (3 моп), к которому не стоит переходить, за исключением того, что нарушается зависимость данных от n в случае x и a могут быть готовы раньше, чем n.
Но без BMI2 сдвиг займет mov ecx, edx и 3-моп (для семейства Intel SnB) shl rax, cl. У AMD есть сдвиги с переменным числом единичных операций даже для устаревших версий, которые действительно записывают флаги (кроме случаев, когда CL = 0, и они должны оставить флаги неизменными; поэтому это стоит дороже для Intel). G CC все еще тупой и ноль простирается вместо RAX. Clang понимает это правильно (и использует преимущества неофициальной функции соглашения о вызовах, когда узкие аргументы функции являются знаковыми или расширяются от нуля до 32-битных, поэтому он может использовать mov вместо movzx) https://godbolt.org/z/9wrYEN
Clang компилирует if() в безветвление с использованием CMOV, так что это значительно хуже, чем в простой версии, использующей uint64_t(a) << n. Это пропущенная оптимизация, которая не компилирует мой hr1 так же, как мой hr3; они
G CC фактически разветвляются и затем используют mov reg, 1 / shl / или для if версии. Опять же, может скомпилировать его так же, как и hr3, если захочет. (Можно предположить, что a=1 подразумевает n<=63, в противном случае версия if будет иметь сдвиг UB.)
Пропущенная оптимизация в обоих случаях является невозможностью использования bts, который реализует reg |= 1<<(n&63)
Специально для g cc после ветвления, чтобы он знал, что он смещает постоянную 1, хвост функции должен быть bts rax, rdx, что составляет 1 моп с 1 c задержка на Intel, 2 моп на AMD Zen1 / Zen2. G CC и clang do знают, как использовать bts для простого случая постоянной времени компиляции a=1, хотя: https://godbolt.org/z/rkhbzH
Нет никакого способа, которым я знаю, чтобы держать G CC в руках или заставлять использовать bts в противном случае, и я бы не рекомендовал встроенную сборку для этого, если он не находится в самом критическом внутреннем l oop чего-либо и вы готовы проверить, что это не повредит другим оптимизациям, и поддерживать его. то есть просто нет.
Но в идеале G CC / clang будет делать что-то подобное, когда BMI2 недоступен:
# hand optimized, compilers should do this but don't.
mov rax, rdi # x
bts rdi, rdx # x | 1<<(n&63)
test sil, sil
cmovnz rax, rdi # return a ? x_with_bit_set : x;
ret
Не требует BMI2, но все еще только 4 мопа на Бродвеле и позже. (И 5 мопов на AMD Bulldozer / Zen). Задержки критического пути:
x -> retval: 2 цикла (через (MOV и BTS) -> CMOV) на Бродвеле и позже. 3 цикла на более ранних версиях Intel (2 uop cmov) и на любом AMD (2 uop BTS). n -> retval: аналогично x (через BTS -> CMOV). a -> retval: 2 цикла (через TEST -> CMOV) на Broadwell и более поздних версиях и на всех AMD. 3 цикла на более ранних Intel (2 мопов).
Это, очевидно, лучше, чем то, что clang излучает для любой версии без -march=skylake или другого BMI2, и даже лучше, чем то, что излучает G CC (если ветвление не оказывается хорошей стратегией).
Один из способов, которым clang будет использовать BTS:
Если мы замаскируем счетчик сдвигов для версии с ветвлением, тогда clang будет на самом деле ветвиться, и на ветви, где выполняется тело if, он реализует это с помощью bts как я описал выше. https://godbolt.org/z/BtT4w6
uint64_t hr1(uint64_t x, bool a, int n) noexcept
{
if (a) {
return x | (uint64_t(a) << (n&63));
}
return x;
}
clang 9.0 -O3 (без -march=)
hr1(unsigned long, bool, int):
mov rax, rdi
test sil, sil
je .LBB0_2 # if(a) {
bts rax, rdx # x |= 1<<(n&63)
.LBB0_2: # }
ret
Так что, если ветвление подходит для вашего варианта использования, то это способ написания хорошо компилируется с помощью clang.
Эти автономные версии могут в конечном итоге отличаться после встраивания в реального вызывающего.
Например, вызывающий может сохранить инструкцию MOV если он может иметь счет смены n уже в CL. Или решение о том, делать ли if-преобразование из последовательности if в последовательность без ветвей, может быть другим.
Или, если n является константой времени компиляции, это означает, что нам не нужен BMI2 для сохранить мопы на смену больше; немедленные сдвиги полностью эффективны на всех современных процессорах (single uop).
И, конечно, если a - постоянная времени компиляции, то либо ничего не нужно делать, либо оптимизировать до bts.
Дополнительная информация: см. Ссылки на производительность в { ссылка }, чтобы узнать, как решить, эффективен ли asm, взглянув на него.