在__uint128_t上最有效的popcount？

Question

我需要以最有效（最快）的方式来弹出大小为128位的无符号变量。

• 操作系统：Linux / Debian 9
• 编译器：GCC 8
• 处理器：Intel 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;
}

这样，尽管我不知道它是否合法（是吗？（编辑：是：使用“ union”？在整数和数组之间键入修剪）），但我会避免这种转变。

Answer 1

使用GCC和clang，如果删除，则两个函数都将编译为相同的asmstatic inline，并且可能等效地内联。

我建议使用unsigned，因为sizeof(uint_fast8_t)在x86-64 Linux上= 1。这些_fast类型提出了“针对什么目的快速”的问题；fast8非常适合数组中的紧凑存储，它fast32是一种64位类型，可以避免为指针数学避免重做符号或零扩展名，但浪费了数组中的空间。

clang知道两个popcnt结果的和适合一个8位整数而没有溢出，因此即使将结果加到unsigned计数器中，它也可以优化零扩展，但gcc不能。（例如，将返回类型更改为unsigned，您将获得一条额外的movzx eax, dil指令。）硬件popcnt指令产生的结果正确地零扩展到64位，但是分配给uint_fast8_taka uint8_t则明确要求编译器将结果截断为8位。

x86-64 System V ABI允许在args和返回值中包含大量垃圾，因此当返回类型较窄时，该函数的独立版本可以允许将其包含在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可以通过同时执行两个popcnts来避免异或归零lea eax, [rdi + rsi]。但是您说了一些关于数组的内容，因此，如果数据来自内存，则GCC通常会先进行移动加载，然后再进行popcnt以避免错误的依赖关系。（为什么打破LZCNT的“输出依赖关系”很重要？）或者实际上，它将对目标进行异或为零，然后使用内存源popcnt，它的代码大小可能会稍微小一些。

我不相信__builtin_popcountll，因为它使用long long而不是uint64_t。我认为创建一个处理位并使用非固定宽度的类型的函数很疯狂。我不知道海湾合作委员会的人们在想什么。

它实际上使用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 );将始终安全地计算的低64位。nunsigned long long

我正在使用一个很大的静态数组。我是否需要关心缓存，还是GCC会为我处理？我认为这只是malloc和类似问题。GCC在编译时就知道该数组，因此它可以比我做得更好。

GCC（几乎？）将永远不会重新排列循环以更改内存访问模式。静态数组与malloced内存没有实质性区别。他们不会免费保持高速缓存。看到每个程序员应该了解的内存信息吗？了解更多。

但是，如果您只是顺序地遍历内存并弹出整个数组，那么是否执行此操作__uint128_t并不重要。

clang将使用AVX2 自动向量化__builtin_popcntll或_mm_popcnt_u64在阵列上vpshufb（作为半字节LUT），这在包括Broadwell在内的Intel CPU上非常有用。请参阅使用AVX-512或AVX-2对大数据计数1位（填充计数）

但是不幸的是，使用包装函数来解决一系列__uint128_t失败。请参阅Godbolt链接中的最后2个功能。