С GCC и clang, обе ваши функции компилируются в идентичный asm , если вы удалите static inline, и предположительно будут встроены эквивалентно.
Я бы предложил использовать unsigned, потому что sizeof(uint_fast8_t) = 1 в x86-64 Linux. Типы _fast задают вопрос «с какой целью поститься»; fast8 хорош для компактного хранения в массивах, fast32 - это 64-битный тип, который, возможно, избегает повторения знака или расширения нуля для математики указателя, но тратит пространство в массиве.
clang знает, что сумма двух результатов popcnt помещается в 8-разрядное целое число без переполнения, поэтому он может оптимизировать удаление нуля, даже если вы суммируете результат в счетчик unsigned, но gcc этого не делает. (например, измените тип возвращаемого значения на unsigned, и вы получите дополнительную инструкцию movzx eax, dil.) Аппаратная инструкция popcnt дает результат, который корректно расширяется от нуля до 64-битного, но присваивается uint_fast8_t aka uint8_t явно просит компилятор обрезать результаты до 8-битных.
x86-64 System V ABI допускает большое количество мусора в аргументах и возвращаемых значениях, поэтому, когда тип возвращаемого значения является узким, автономная версия функции может разрешать перенос в старшие биты EAX.
Я бы избежал сдвига.
Сдвиг существует только в источнике C . В asm верхние / нижние половины будут храниться в отдельных 64-битных регистрах или в отдельных операндах источника памяти.
С Проводник компилятора Godbolt
# gcc8.3 -O3 -march=haswell for the union and the shift version
popcnt_u128:
xor eax, eax # break popcnt's false dependency on Intel CPUs
popcnt rsi, rsi # _mm_popcnt_u64(n_hi);
popcnt rax, rdi # popcnt(lo)
add eax, esi # clang uses add al,cl and doesn't avoid false deps except in a loop
ret # return value in AL (low 8 bits of EAX)
GCC мог бы избежать обнуления по xor, выполнив оба popcnts и используя lea eax, [rdi + rsi]. Но вы сказали что-то о массиве, так что если данные поступают из памяти, то GCC будет обычно перемещаться-загружаться и затем вставляться на место, чтобы избежать ложной зависимости. ( Почему нарушение «выходной зависимости» LZCNT имеет значение? ) Или на самом деле, оно обнулит целевое значение и затем использует popcnt источника памяти, который может быть немного меньшего размера кода.
Я не доверяю __builtin_popcountll, потому что он использует long long вместо uint64_t. Я думаю, что безумно создавать функцию, которая работает с битами и использует тип, который не имеет фиксированной ширины. Я не знаю, о чем думали люди из GCC.
На самом деле используется unsigned long long, без подписи long long; что было бы безумием.
unsigned long long равно не менее 64 бит, а uint64_t должно быть точно 64 бит. (И фактически существует только в реализациях C, которые имеют тип, который точно 64-битный без дополнения; поддержка для него является необязательной). Я не уверен, поддерживает ли GNU C какие-либо цели, где unsigned long long не 64 бит или где uint64_t недоступно. Или даже int64_t, который также должен быть дополнением 2. (IDK, если GCC поддерживает любые цели, не являющиеся дополнением к 2).
Вы можете привести входы к uint64_t, чтобы убедиться, что не установлены более высокие биты. Неявное преобразование из uint64_t в unsigned long long не будет устанавливать никаких дополнительных битов, даже на платформе, где ULL шире, чем 64 бита.
например. __builtin_popcountll( (uint64_t)n ); всегда безопасно посчитает младшие 64 бита n, независимо от ширины unsigned long long.
Я использую очень большой статический массив. Должен ли я заботиться о кеше или GCC справится с этим для меня? Я думал, что это проблема только с malloc и тому подобным. GCC знает массив во время компиляции, поэтому он может делать это лучше меня.
GCC (почти?) Никогда не переставит ваши циклы, чтобы изменить шаблоны доступа к памяти. Статические массивы существенно не отличаются от malloc ed памяти; они не остаются горячими в кеше бесплатно. См. Что должен знать каждый программист о памяти? , чтобы узнать больше.
Но если вы просто последовательно зацикливаетесь в памяти и попонируете целый массив, тогда не имеет значения, делаете ли вы это с __uint128_t или нет.
clang автоматически векторизует __builtin_popcntll или _mm_popcnt_u64 по массиву с AVX2 vpshufb (в качестве клочка LUT), что хорошо для процессоров Intel, включая Broadwell.См. Подсчет 1 бита (подсчет населения) для больших данных с использованием AVX-512 или AVX-2
Но, к сожалению, использование вашей функции-оболочки для массива __uint128_t опровергает это.См. Последние 2 функции в ссылке Godbolt.