Встраивание сборки в C

Я пишу шахматный движок на 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?

То, что в чем-то меньше инструкций, не означает, что это будет быстрее. Также вероятная причина, по которой у вас есть cltq, заключается в том, что у вас неправильный тип возвращаемого значения. xor практически бесплатно.

Jester 03.04.2022 15:30

Причина xor в том, что bsf дает неопределенный результат, если ввод равен нулю.

Jester 03.04.2022 15:35

Обратите внимание, что указание архитектуры процессора, поддерживающей tzcnt, xor исчезает.

Jester 03.04.2022 15:40

Для эксперимента вы можете определить встроенную функцию следующим образом: static inline u64 ctzll(u64 a) { u64 q; asm ("rep bsf %1, %0" : "=r"(q) : "r"(a)); return (q); }

fuz 03.04.2022 16:26

@Jester: gcc -O3 -march=skylake не роняет xor: godbolt.org/z/fPnz1Gox5. С другой стороны, __builtin_ctzll задокументировано как возвращающий неопределенный результат, когда ввод равен 0, поэтому xor в принципе не нужен в любом случае, но я думаю, что gcc решает обработать его, возвращая 0. clang, с другой стороны, опускает xor на всех архитектурах, поэтому на более старых процессорах __builtin_ctzll(0) вернет мусор.

Nate Eldredge 03.04.2022 19:10

@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

Peter Cordes 04.04.2022 04:33

О, cltq необходим, потому что __builtin_ctzll указано как возвращающее int, а не long long. И это просто неопределенный результат, а не поведение, на входе=0.

Peter Cordes 04.04.2022 04:47
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
7
111
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

На самом деле они не эквивалентны. В частности, они отличаются в случае, когда %rdi равен 0.

Это полуопределенное поведение, когда bsf сохраняет предыдущий результат назначения, если вход равен 0: Почему имеет значение нарушение «выходной зависимости» LZCNT?

Это означает, что инструкция bsf имеет входную зависимость от своего выходного регистра. Обнуление выходного регистра явно разрывает эту зависимость и обеспечивает определение поведения в этом случае. В большинстве современных реализаций x86 обнуление с помощью xor происходит во время переименования регистра и разрывает цепочку зависимостей. Это означает, что сам xor фактически свободен. Это также означает, что bsf может быть отправлен исполнительным модулям без ожидания предыдущего использования регистра eax, что может привести к наблюдаемой вами разнице в производительности.

Однако более вероятно, что то, что вы вставили в короткую сборку, скрыло ее от оптимизатора, вынуждая оптимизатора делать неоптимальный выбор в том месте, где функция ранее была бы встроена.

Вы, вероятно, получите лучшую генерацию кода общий со встроенной функцией не из-за каких-либо деталей сборки, сгенерированной самой встроенной функцией, а потому, что компилятор знает, что делает встроенная функция. Он знает, что встроенная функция не имеет побочных эффектов и не обращается к памяти, поэтому может исключить повторные вызовы с одним и тем же аргументом. Он умеет «постоянно сворачивать» встроенную функцию, например, может заменить __builtin_ctzll(0x123400) на 10. И так далее.

С другой стороны, при встроенном ассемблере вы сообщаете компилятору, какие регистры считываются, а какие записываются, но он должен делать консервативные предположения о том, что такое делает сборки. Он не может постоянно складываться через встроенную сборку. Он не может предполагать, что встроенная сборка всегда дает один и тот же результат для одних и тех же входных данных. И т. д.

Вы можете постоянно сворачивать (с некоторыми ограничениями) с помощью встроенной сборки. Смотрите последнюю часть моего ответа.

xiver77 03.04.2022 17:05
Ответ принят как подходящий

Вывод сначала, используйте __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 03.04.2022 17:17

@zwol Да, я заметил, что повторно реализовал __builtin_ctz после окончания этого поста. Я отредактировал пост, прояснив вашу точку зрения.

xiver77 03.04.2022 18:30

Частичный ответ, охватывающий то, чего не было в других существующих ответах, например, почему 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?)

Другие вопросы по теме