c - `__uint128_t` 上最有效的 popcount ？

Question

我需要以最有效(最快)的方式弹出一个 128 位大小的无符号变量。

操作系统:Linux/Debian 9

编译器:GCC 8

CPU:英特尔 i7-5775C

虽然如果解决方案更便携，那就更好了。

首先，GCC中有两种类型，分别是 __uint128_t和 unsigned __int128 .我猜他们最终是一样的，并且认为没有理由写丑陋的 unsigned __int128东西，所以虽然它应该是新类型，但我更喜欢第一种，它更类似于标准 uint64_t .此外，英特尔还有 __uint128_t这是使用它的另一个原因(便携性)。

我编写了以下代码:

#include <nmmintrin.h>
#include <stdint.h>

static inline   uint_fast8_t    popcnt_u128 (__uint128_t n)
{
    const uint64_t      n_hi    = n >> 64;
    const uint64_t      n_lo    = n;
    const uint_fast8_t  cnt_hi  = _mm_popcnt_u64(n_hi);
    const uint_fast8_t  cnt_lo  = _mm_popcnt_u64(n_lo);
    const uint_fast8_t  cnt     = cnt_hi + cnt_lo;

    return  cnt;
}

这是绝对最快的选择吗？

编辑:

我想到了另一个选择，它可能(或不是)更快:

#include <nmmintrin.h>
#include <stdint.h>

union   Uint128 {
    __uint128_t uu128;
    uint64_t    uu64[2];
};

static inline   uint_fast8_t    popcnt_u128 (__uint128_t n)
{
    const union Uint128 n_u     = {.uu128   = n};
    const uint_fast8_t  cnt_a   = _mm_popcnt_u64(n_u.uu64[0]);
    const uint_fast8_t  cnt_b   = _mm_popcnt_u64(n_u.uu64[1]);
    const uint_fast8_t  cnt     = cnt_a + cnt_b;

    return  cnt;
}

这样，虽然我不知道它是否合法(是吗？ (编辑:它是:Type punning between integer and array using `union`?))，我会避免这种转变。

Answer 1

使用 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又名 uint8_t明确要求编译器将结果截断为 8 位。

x86-64 System V ABI 允许 args 和返回值中的高垃圾，因此当返回类型很窄时，函数的独立版本可以允许进位到 EAX 的高位。

I would avoid the shift.

移位仅存在于 C 源代码中 .在 asm 中，高/低半部分将存储在单独的 64 位寄存器或单独的内存源操作数中。

来自 the Godbolt compiler explorer

# 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 可以通过在适当的位置执行两个 popcnt 并使用 lea eax, [rdi + rsi] 来避免异或归零。 .但是你说了一些关于数组的事情，所以如果数据来自内存，那么 GCC 通常会 mov-load 然后 popcnt 到位以避免错误的依赖。 ( Why does breaking the "output dependency" of LZCNT matter? ) 或者实际上，它将对目标进行异或零处理，然后使用内存源 popcnt，这可能会稍微小一些代码大小。

I don't trust __builtin_popcountll because it uses long long instead of uint64_t. I think it is insane to create a function that deals with bits and uses a type that isn't of fixed width. I don't know what GCC people were thinking about.

它实际上使用 unsigned long long , 未签名 long long ;那太疯狂了。
unsigned long long至少是 64 位，并且 uint64_t要求正好是 64 位。 (实际上，仅存在于类型为 64 位且无填充的 C 实现中；对它的支持是可选的)。我不确定 GNU C 是否支持任何目标，其中 unsigned long long不是 64 位，或者哪里 uint64_t不可用。甚至 int64_t ，这也需要是 2 的补码。 (如果 GCC 支持任何非 2 的补码目标，则为 IDK。)

您可以将输入转换为 uint64_t以确保没有设置更高的位。来自 uint64_t 的隐式转换至 unsigned long long即使在 ULL 的平台上，也不会设置任何额外的位比 64 位宽。

例如 __builtin_popcountll( (uint64_t)n );将始终安全地计算 n 的低 64 位，不考虑unsigned long long的宽度.

I'm using a very big static array. Do I have to care about cache, or does GCC handle that for me? I thought that was only a problem with malloc and that stuff. GCC knows the array at compile time, so it can do that better than me.

GCC 将(几乎？)永远不会重新安排您的循环以更改内存访问模式。静态数组与 malloc 没有本质区别编辑内存;他们不会免费在缓存中保持热度。见 What Every Programmer Should Know About Memory?了解更多。

但是，如果您只是在内存中顺序循环并对整个数组进行 popcount，那么是否使用 __uint128_t 进行操作实际上并不重要。或不。

clang 将自动矢量化 __builtin_popcntll或 _mm_popcnt_u64在带有 AVX2 的阵列上 vpshufb (作为半字节 LUT)，这在包括 Broadwell 在内的 Intel CPU 上都很好。见 Counting 1 bits (population count) on large data using AVX-512 or AVX-2

但不幸的是，将您的包装函数用于 __uint128_t 的数组打败了那个。请参阅 Godbolt 链接中的最后 2 个函数。