Я пишу шахматный движок на c, и скорость важна. Шахматный движок основан на unsigned long long, который я буду обозначать как u64, и он сильно зависит от сканирования наименее значимых битов. До сих пор я использовал функцию gcc __builtin_ctzll, которая прекрасно справлялась со своей задачей. Однако я сгенерировал ассемблерный код для этой изолированной функции с помощью gcc -S -O2. Это дало мне следующее:
xorl %eax, %eax
rep bsfq %rdi, %rax
cltq
ret
Однако после некоторого расследования кажется, что код
rep bsfq %rdi, %rax
ret
делает то же самое в моей шахматной программе. Однако теперь он примерно на 20% медленнее. Это должно быть быстрее, потому что это меньше инструкций. Однако исходный __builtin_ctzll встроен в мой код c. Является ли это причиной того, что мой пользовательский код сборки работает медленнее, чем исходный? Потому что, когда я объявляю функцию ctzll, я, конечно, не могу объявить ее встроенной в c, если у меня нет определения (которого нет в ассемблере).
Есть ли другой способ оптимизировать инструкции по сборке или мне попробовать мой новый код сборки, встроенный в asm, непосредственно в c?
Причина xor
в том, что bsf
дает неопределенный результат, если ввод равен нулю.
Обратите внимание, что указание архитектуры процессора, поддерживающей tzcnt
, xor
исчезает.
Для эксперимента вы можете определить встроенную функцию следующим образом: static inline u64 ctzll(u64 a) { u64 q; asm ("rep bsf %1, %0" : "=r"(q) : "r"(a)); return (q); }
@Jester: gcc -O3 -march=skylake
не роняет xor
: godbolt.org/z/fPnz1Gox5. С другой стороны, __builtin_ctzll
задокументировано как возвращающий неопределенный результат, когда ввод равен 0, поэтому xor в принципе не нужен в любом случае, но я думаю, что gcc решает обработать его, возвращая 0. clang, с другой стороны, опускает xor на всех архитектурах, поэтому на более старых процессорах __builtin_ctzll(0)
вернет мусор.
@NateEldredge GCC иногда немного безмозглый: они тщательно избегают зависимости вывода для tzcnt
от универсального или Intel, но code-gen, похоже, не обращает внимания на истинную зависимость bsf
, если вы компилируете с -march=sandybridge
или чем-то, что не поддерживает TZCNT. (На практике процессоры Intel совместимы с тем, что документирует AMD: input = 0 оставляет вывод без изменений для bsf/bsr, поэтому, как и cmov, им нужно использовать dst reg в качестве входных данных.) godbolt.org/z/WcY3sManq показывает это, и что GCC также не знает об этом. что -march=skylake
исправила ложную зависимость для tz/lzcnt. Тоже загадочный cltq
О, cltq
необходим, потому что __builtin_ctzll
указано как возвращающее int
, а не long long
. И это просто неопределенный результат, а не поведение, на входе=0.
На самом деле они не эквивалентны. В частности, они отличаются в случае, когда %rdi равен 0.
Это полуопределенное поведение, когда bsf сохраняет предыдущий результат назначения, если вход равен 0: Почему имеет значение нарушение «выходной зависимости» LZCNT?
Это означает, что инструкция bsf имеет входную зависимость от своего выходного регистра. Обнуление выходного регистра явно разрывает эту зависимость и обеспечивает определение поведения в этом случае. В большинстве современных реализаций x86 обнуление с помощью xor происходит во время переименования регистра и разрывает цепочку зависимостей. Это означает, что сам xor фактически свободен. Это также означает, что bsf может быть отправлен исполнительным модулям без ожидания предыдущего использования регистра eax, что может привести к наблюдаемой вами разнице в производительности.
Однако более вероятно, что то, что вы вставили в короткую сборку, скрыло ее от оптимизатора, вынуждая оптимизатора делать неоптимальный выбор в том месте, где функция ранее была бы встроена.
Вы, вероятно, получите лучшую генерацию кода общий со встроенной функцией не из-за каких-либо деталей сборки, сгенерированной самой встроенной функцией, а потому, что компилятор знает, что делает встроенная функция. Он знает, что встроенная функция не имеет побочных эффектов и не обращается к памяти, поэтому может исключить повторные вызовы с одним и тем же аргументом. Он умеет «постоянно сворачивать» встроенную функцию, например, может заменить __builtin_ctzll(0x123400)
на 10. И так далее.
С другой стороны, при встроенном ассемблере вы сообщаете компилятору, какие регистры считываются, а какие записываются, но он должен делать консервативные предположения о том, что такое делает сборки. Он не может постоянно складываться через встроенную сборку. Он не может предполагать, что встроенная сборка всегда дает один и тот же результат для одних и тех же входных данных. И т. д.
Вы можете постоянно сворачивать (с некоторыми ограничениями) с помощью встроенной сборки. Смотрите последнюю часть моего ответа.
Вывод сначала, используйте __builtin_ctzll
без преобразования результата в 64-битный. Следующее может быть полезно, если вы хотите заставить компилятор использовать tzcnt
или если вы хотите сделать свой собственный встроенный.
Поскольку @user1937198 объяснил все основы, вот некоторый код, который является достаточно быстрым и переносимым.
static inline int u64_bsf(u64 x) {
u64 r = 0;
__asm__ ("rep bsfq\t%1, %0" : "+r"(r) : "r"(x));
return r;
}
/*
u64_bsf:
xorl %eax, %eax
rep bsfq %rdi, %rax
ret
*/
Вы можете изменить тип возвращаемого значения на unsigned
, если хотите. На большинстве платформ, включая x86, использование int
или unsigned
дает самый быстрый код (за исключением иногда индексов массива). В частности, на x86 использование 64-битных целых чисел вызывает программную эмуляцию в 32-битном режиме и больший размер кода (плюс более медленное деление) в 64-битном режиме. Ваше использование 64-битного возвращаемого типа также запутало компилятор, чтобы использовать избыточное cltq
(что является плохим выдуманным именем cdqe
в синтаксисе AT&T).
rep bsf
декодируется в tzcnt
на машинах, которые его поддерживают, а rep
отбрасывается на машинах, которые этого не делают. tzcnt
лучше тем, что (обычно) не использует выходной регистр в качестве входных данных (см. ответ @user1937198) и работает намного быстрее на процессорах AMD.
Если вы ориентируетесь на машины с tzcnt
, напишите
static inline int u64_tzcnt(u64 x) {
u64 r;
__asm__ ("tzcntq\t%1, %0" : "=r"(r) : "r"(x));
return r;
}
/*
u64_tzcnt:
tzcntq %rdi, %rax
ret
*/
Прочтите онлайн-документацию GCC, чтобы узнать о синтаксисе встроенного ассемблера (https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html).
В ответе @zwol упоминается постоянное свертывание. Вот окончательный код, который может обрабатывать постоянное распространение и встроен для непостоянного ввода.
static inline int u64_bsf(u64 x) {
if (__builtin_constant_p(x)) {
return __builtin_ctzll(x);
}
u64 r = 0;
__asm__ ("rep bsfq\t%1, %0" : "+r"(r) : "r"(x));
return r;
}
На данный момент я в основном переопределил __builtin_ctzll
, но вы всегда можете сделать свою собственную встроенную функцию таким образом.
Я действительно не вижу здесь смысла для __builtin_ctz
, но это удобный трюк для случаев, когда компилятор еще не имеет встроенной функции.
@zwol Да, я заметил, что повторно реализовал __builtin_ctz
после окончания этого поста. Я отредактировал пост, прояснив вашу точку зрения.
Частичный ответ, охватывающий то, чего не было в других существующих ответах, например, почему GCC, по-видимому, тратит впустую cltq
, почему помогает xor-zeroing и почему генерация кода GCC с другими параметрами, такими как -march=skylake
или -march=sandybridge
, не очень хороша.
cltq
(он же cdqe
) — это досадное последствие того, что __builtin_ctzll()
определяется как возвращающее int
, а не long long
.
bsf %rdi, %rax
либо записывает RAX с числом от 0..63, либо оставляет его без изменений (или на бумаге содержит неопределенное значение, но процессоры Intel в действительности совместимы с документами поведения AMD: оставить выходной регистр без изменений, если ввод был 0 для bsf
или bsr
, в отличие от tzcnt
/lzcnt
).
__builtin_ctzll()
разрешено возвращать только действительные значения int
, даже для ввода = 0. (GNU C определяет встроенная функция «Если x равна 0, результат не определена». Не «поведение», это не UB, вы все равно гарантированно получите некоторый 32-битное int
значение. )
Когда GCC не знает наверняка, что rep bsf
будет работать как tzcnt
, а не bsf
, он должен учитывать возможность того, что пункт назначения содержит старый мусор со старшими битами, которые не являются копиями бита 31, если вы вернете uint64_t
вместо unsigned
или int
. (Возврат более узкого типа оставляет вызывающей стороне возможность игнорировать высокий мусор.)
В этом случае, когда он также обнуляет место назначения с помощью операции xor, это гарантирует вывод 0
для ввода 0
, поэтому нет необходимости расширять знак. Если вы не хотите перестраховаться на случай, если Intel (или какой-либо программный эмулятор x86) перестанет делать то, что документирует AMD, и фактически выдаст что-то отличное от старого значения на input=0.
IIRC, rep bsf %edi, %eax
на Intel или AMD (не помню на каком) делает всегда усекает RAX до 32-бит, даже если оставляет EAX без изменений. А вот у другого поставщика нет. Так что забавный факт, если ориентироваться только на процессоры, которые выполняют это минимальное нулевое расширение, (uint64_t)(uint32_t)__builtin_ctz(x)
не потребуется никакой дополнительной работы.
bsf
всегда, tzcnt
иногдаGCC иногда немного тупит: они тщательно избегают зависимости вывода для tzcnt
от дженерика или Intel, но code-gen, похоже, не обращает внимания на истинную зависимость bsf
, если вы компилируете с -march=sandybridge
или чем-то, что не поддерживает TZCNT. (В этом случае только что использует bsf
без принудительного обнуления адресата.)
Таким образом, очевидно, что xor-zeroing dep-break был выполнен только в случае, если он работал как TZCNT на Intel. Что иронично, потому что bsf
всегда имеет выходную зависимость на всех процессорах, потому что на практике процессоры Intel совместимы с тем, что документирует AMD: input = 0 оставляет вывод без изменений для bsf/bsr. Так же, как и cmov, им нужно использовать dst reg в качестве входных данных.
https://godbolt.org/z/WcY3sManq показывает это, и что GCC также не знает, что -march=skylake
исправил ложную зависимость для tz/lzcnt. (Почему имеет значение нарушение «выходной зависимости» LZCNT?)
То, что в чем-то меньше инструкций, не означает, что это будет быстрее. Также вероятная причина, по которой у вас есть
cltq
, заключается в том, что у вас неправильный тип возвращаемого значения.xor
практически бесплатно.