c++ - 在一个位置或更低的位置计数设置位的有效方法是什么？

Question

在给定std::bitset<64> bits的情况下设置了任意数量的位，并且设置了位位置X(0-63)

最有效的方法是对X或更低位置的位数进行计数，或者如果未设置X的位，则返回0是最有效的方法

注意:如果该位置1，则返回值始终至少为1

蛮力方式很慢:

int countupto(std::bitset<64> bits, int X)
{
  if (!bits[X]) return 0;
  int total=1;
  for (int i=0; i < X; ++i)
  {
    total+=bits[i];
  }
  return total;
}

count()的 bitset methof将为您提供所有位的 popcount，但 bitset不支持范围

注意:这不是 How to count the number of set bits in a 32-bit integer?的副本，因为它询问所有位，而不是0到X的范围

Answer 1

此C++使g++发出very good x86 ASM (godbolt compiler explorer)。我希望它也可以在其他64位体系结构上有效地进行编译(如果有供std::bitset::count使用的HW popcount，否则它将始终很慢；例如，请确保使用g++ -march=nehalem或更高版本，或者如果您不想使用-mpopcnt如果可以将代码限制为仅在支持该x86指令的CPU上运行，请启用其他功能):

#include <bitset>

int popcount_subset(std::bitset<64> A, int pos) {
  int high_bits_to_eliminate = 63 - pos;
  A <<= (high_bits_to_eliminate & 63);  // puts A[pos] at A[63].

  return (A[63]? ~0ULL : 0) & A.count();  // most efficient way: great code with gcc and clang
  // see the godbolt link for some #ifdefs with other ways to do the check, like
    // return A[BSET_SIZE-1] ? A.count() : 0;
}

在32位体系结构上，这可能不是最佳选择，因此，如果需要进行32位构建，请比较其他替代方案。

，这将适用于其他大小的位集，只要您对硬编码的 63做一些处理，并将移位计数的 & 63掩码更改为更常规的范围检查。为了获得奇特大小的位集的最佳性能，请对目标计算机的 size <= register width进行专门化的模板功能。在这种情况下，将位集提取为适当宽度的 unsigned类型，然后移至寄存器的顶部而不是位集的顶部。

您可能希望这也会为 bitset<32>生成理想的代码，但事实并非如此。 gcc/clang仍在x86-64上使用64位寄存器。

对于大的位集，将整个对象移位要比仅对包含 pos的单词下面的单词进行弹出计数并在该单词上使用该单词慢。 (如果您可以假设SSSE3而不是 popcnt insn硬件支持或针对32位目标，则这是矢量化popcount真正在x86上的亮点。AVX2256位 pshufb是执行批量popcount的最快方法，但是如果没有AVX2，我认为64位 popcnt很漂亮接近于128位 pshufb实现。有关更多讨论，请参见评论。)

如果您具有64位元素的数组，并且想要分别计算每个位置中某个位置以下的位，那么您绝对应该使用SIMD 。该算法的移位部分是矢量化的，而不仅仅是popcnt部分。对全零寄存器使用 psadbw，以在基于 pshufb的popcnt单独生成每个字节的位数之后，对64位块中的水平和字节进行水平求和。 SSE/AVX没有64位算术右移，但是您可以使用另一种技术来混合每个元素的高位。

我是怎么想到的:

您要使编译器输出的asm指令将:

从64bit值

中删除不需要的位

测试所需的最高位。

popcount。

根据测试结果返回0或popcount。 (无分支或分支实现都有优势。如果分支是可预测的，则无分支实现往往会变慢。)

进行 的明显方法1 是生成一个掩码( (1<<(pos+1)) -1)并对其进行 &。一种更有效的方法是通过 63-pos左移，将要打包的位保留在寄存器的顶部。

将您要测试的位放在寄存器的最高位还有一个有趣的副作用。测试符号位，而不是任何其他任意位，只需较少的指令。算术右移可以将符号位广播到寄存器的其余部分，从而实现比平时更高效的无分支代码。

进行 popcount 是一个广为讨论的问题，但实际上是难题的棘手部分。在x86上，它具有非常有效的硬件支持，但仅在最近使用的硬件上才如此。在Intel CPU上， popcnt指令仅在Nehalem及更高版本上可用。我忘了AMD增加支持的时间。

因此，为了安全地使用它，您需要使用不使用 popcnt的后备资源来进行CPU调度。或者，制作独立的/不依赖于某些CPU功能的二进制文件。

没有 popcnt指令的popcount可以通过几种方法来完成。一个使用SSSE3 pshufb来实现4位LUT。当在整个阵列上使用时，这是最有效的，而不是一次使用单个64b。标量bithack可能是这里最好的，并且不需要SSSE3(因此可以与具有64位但不包含pshufb的古老AMD CPU兼容)。

比特广播:
(A[63]? ~0ULL : 0)要求编译器将高位广播到所有其他位位置，以便将其用作AND掩码，以将popcount结果归零(或不归零)。请注意，即使对于较大的位集大小，它仍然仅掩盖了 popcnt的输出，而不是位集本身，因此 ~0ULL很好，我使用ULL来确保不再要求编译器仅将该位广播到ab的低32b。注册(例如，在Windows上使用 UL)。

可以通过算术右移63来完成此广播，算术右移高位副本。

clang从原始版本生成了此代码。在Glenn对 4 的不同实现提出了一些建议之后，我意识到我可以通过编写更像我想要的ASM的源代码来使gcc转向clang的最佳解决方案。显然，更直接要求算术右移的 ((int64_t)something) >> 63并不是严格可移植的，因为带符号的右移是 implementation-defined as either arithmetic or logical。该标准未提供任何可移植的算术右移运算符。 (不过，它不是 undefined behaviour。)幸运的是，编译器足够聪明:一旦给了足够的提示，gcc就会找到最佳方法。

此源代码使用gcc和clang在x86-64和ARM64上编写了出色的代码。两者都只是对popcnt的输入使用算术右移(因此，该移位可以与popcnt并行运行)。它也可以在带有gcc的32位x86上很好地编译，因为屏蔽仅发生在32位变量上(添加了多个popcnt结果之后)。该函数的其余部分在32位(当位集大于寄存器时)令人讨厌。

带有gcc的原始三元运算符

用gcc 5.3.0 -O3 -march=nehalem -mtune=haswell编译(较旧的gcc，如4.9.2，仍会发出此代码):

; the original ternary-operator version.  See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
    ; input bitset in rdi, input count in esi (SysV ABI)
    mov     ecx, esi    ; x86 variable-count shift requires the count in cl
    xor     edx, edx    ; edx=0 
    xor     eax, eax    ; gcc's workaround for popcnt's false dependency on the old value of dest, on Intel
    not     ecx         ; two's complement bithack for 63-pos (in the low bits of the register)
    sal     rdi, cl     ; rdi << ((63-pos) & 63);  same insn as shl (arithmetic == logical left shift)
    popcnt  rdx, rdi
    test    rdi, rdi    ; sets SF if the high bit is set.
    cmovs   rax, rdx    ; conditional-move on the sign flag
    ret

有关gcc使用 -x == ~x + 1 2的补码身份的背景信息，请参见 How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results?。 (并且 Which 2's complement integer operations can be used without zeroing high bits in the inputs, if only the low part of the result is wanted?切线地提到 shl掩盖了移位计数，因此我们只需要 ecx的低6位来保存 63 - pos。主要是因为我最近写了它，而且仍然在阅读此段落的任何人都可能觉得它有趣。)

在内联时，其中一些指示将消失。 (例如，gcc首先会在ecx中生成计数。)

通过使用Glenn的乘法运算而不是三元运算符想法(由 USE_mul启用)，gcc可以

    shr     rdi, 63
    imul    eax, edi

最后而不是 xor/ test/ cmovs。

Haswell perf analysis, using microarch data from Agner Fog(多版本):

mov r,r:1个融合域uop，0个延迟，无执行单元

xor -zeroing:1个融合域uop，无执行单元

not:p0/p1/p5/p6 1 uop，1c延迟，每0.25c吞吐量1个

shl(又名sal)，其中cl计数:p0/p6为3 uops:2c延迟，每2c吞吐量1。 (奇怪的是，Agner Fog的数据表明IvyBridge仅需2 oups。)

popcnt:1 uop for p1，3c延迟，每1c吞吐量1

shr r,imm:p0/p6为1 uop，延迟为1c。每0.5c吞吐量1个。

imul r,r:p1为1uop，延迟为3c。

不计算ret

总计:

9个融合域uops，可以在2.25个周期内发行(理论上； uop缓存行效果通常会稍微影响前端的瓶颈)。

p0/p6的4微妙(移位)。 p1为2 oups。 1个any-ALU端口uop。可以每2c执行一次(使移位端口饱和)，因此前端是最严重的瓶颈。

延迟:从准备好位集到获得结果的关键路径: shl(2)-> popcnt(3)-> imul(3)。总共 8个周期。或准备好 pos时的9c，因为 not为其额外的1c延迟。

最佳 bitbroadcast的 版本将 shr替换为 sar(相同的性能)，并使用 imul替换 and(延迟为1c，而不是3c，可在任何端口上运行)。因此，唯一的性能变化是 ，将关键路径延迟减少到6个周期。吞吐量仍然是前端的瓶颈。能够在任何端口上运行的 and没什么区别，除非您将其与端口1上出现瓶颈的代码混合在一起(而不是在紧密循环中查看仅运行此代码的吞吐量)。

cmov(三元运算符)版本:11个融合域uops(前端: ，每2.75c 一次)。执行单位:仍然在转换端口(p0/p6)上每2c出现瓶颈。 延迟:从位集到结果为7c，从位置到结果为8c。 ( cmov是2c延迟，对于p0/p1/p5/p6中的任何一个都是2微秒。)

Clang 有一些不同的技巧:代替 test/ cmovs，它使用算术右移将符号位广播到寄存器的所有位置，从而生成全1或全0的掩码。我喜欢它:在英特尔上，使用 and代替 cmov更有效。但是，它仍然具有数据依赖性，并且可以在分支的两侧进行工作(这通常是cmov的主要缺点)。更新:通过正确的源代码，gcc也将使用此方法。

clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int):
    mov     ecx, 63
    sub     ecx, esi      ; larger code size, but faster on CPUs without mov-elimination
    shl     rdi, cl       ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi      ; doesn't start a fresh dep chain before this, like gcc does
    sar     rdi, 63       ; broadcast the sign bit
    and     eax, edi      ; eax = 0 or its previous value
    ret

sar / and替换了 xor / test / cmov，并且 cmov是Intel CPU上的2 uop指令，因此非常好。 (对于三元运算符版本)。

当使用乘法源版本或“bitbroadcast”源版本时，Clang仍会执行 sar / and技巧而不是实际的 imul。因此，这些帮助gcc不会损害clang。 ( sar/and绝对比 shr/imul更好:在关键路径上的延迟减少了2c。) pow_of_two_sub版本确实伤害了clang(请参阅第一个“godbolt”链接:此答案中省略了它，以避免困惑的想法没有被提出)。

实际上，在没有reg，reg移动(零延迟和无执行端口，通过寄存器重命名处理)消除运动的CPU上， mov ecx, 63/ sub ecx, esi实际上更快。这包括Intel之前的IvyBridge，但不包括更新的Intel和AMD CPU。

Clang的 mov imm/ sub方法仅将 pos的延迟周期放到关键路径上(除了bitset-> result延迟之外)，而不是在 mov ecx, esi具有1c延迟的CPU上将 not ecx/ mov r,r延迟两个周期。

使用BMI2 (Haswell及更高版本)，最佳的ASM版本可以将 mov保存为 ecx。其他所有功能都一​​样，因为 shlx将其移位计数输入寄存器屏蔽为操作数大小，就像 shl一样。

x86移位指令具有疯狂的CISC语义，其中，如果移位计数为零，则标志不会受到影响。因此，可变计数移位指令对标志的旧值具有(潜在)依赖性。在Haswell上，“普通” x86 shl r, cl解码为3 oups，但是BMI2 shlx r, r, r只有1。因此，非常糟糕的是gcc仍然使用 sal而不是 -march=haswell发出 shlx(在某些其他情况下会使用)。

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
    not     esi           ; The low 6 bits hold 63-pos.  gcc's two-s complement trick
    xor     eax, eax      ; break false dependency on Intel.  maybe not needed when inlined.
    shlx    rdi, rdi, rsi ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi
    sar     rdi, 63       ; broadcast the sign bit: rdi=0 or -1
    and     eax, edi      ; eax = 0 or its previous value
    ret

英特尔Haswell性能分析:6个融合域uops( 前端:每1.5c 之一)。执行单位:2 p0/p6移位单位。 1 p1哎呀。 2个任意端口oups :(从总执行端口限制中每1.25c发送一个)。关键路径延迟: shlx(1)-> popcnt(3)-> and(1)= 5c位集->结果。 (或 pos-> result中的6c)。

请注意，在内联时，人工(或智能编译器)可以避免需要 xor eax, eax。仅因为 popcnt 's false dependency on the output register (on Intel)而存在，并且我们需要 eax的输出(调用者最近可能在较长的dep链上使用了该输出)。使用 -mtune=bdver2或其他东西，gcc不会将要用于 popcnt输出的寄存器清零。

进行内联时，我们可以使用至少必须早于 popcnt的源寄存器就已经准备就绪的输出寄存器，以避免出现此问题。当以后不需要源代码时，编译器将执行就地 popcnt rdi,rdi，但这不是这种情况。相反，我们可以选择另一个在源之前已经准备好的寄存器。 popcnt的输入取决于 63-pos，我们可以破坏它，因此 popcnt rsi,rdi的对rsi的依赖关系不会延迟它。或者，如果我们在寄存器中包含 63，则可以 popcnt rsi,rdi/ sarx rax, rsi, reg_63/ and eax, esi。否则，BMI2 3操作数转换指令也不会让我们在以后需要输入时费心。

如此轻巧，以至于循环开销和设置输入操作数/存储结果将成为主要因素。 (并且 63-pos可以使用编译时常量进行优化，也可以优化到变量计数来自何处。)

英特尔编译器很有趣，没有充分利用A [63]是符号位这一事实。 shl/ bt rdi, 63/ jc。它甚至以非常愚蠢的方式建立分支机构。它可以将eax设为零，然后根据 shl设置的符号标志跳过popcnt或不跳过。

最佳分支实现，从Godbolt上 -O3 -march=corei7的ICC13输出开始:

   // hand-tuned, not compiler output
        mov       ecx, esi    ; ICC uses neg/add/mov :/
        not       ecx
        xor       eax, eax    ; breaks the false dep, or is the return value in the taken-branch case
        shl       rdi, cl
        jns    .bit_not_set
        popcnt    rax, rdi
.bit_not_set:
        ret

这几乎是最佳选择: A[pos] == true案例有一个未采用的分支。但是，与无分支方法相比，它并没有节省太多。

如果 A[pos] == false情况更常见:跳过 ret指令，转到 popcnt/ ret。 (或内联之后:跳转到执行 popcnt的末尾的一个块并跳回)。