在一个或更低的位置对设置位进行计数的有效方法是什么？

Question

给定std::bitset<64>位，设置任意位数和位位置x(0-63)

对位置X或更低的位进行计数或在X处的位未设置时返回0的最有效的方法是什么

注意：如果设置了该位，则返回值将始终至少为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;
}

注意：这不是一个如何计算32位整数中设置位数的dup吗？因为它询问的是0到X范围以外的所有位

Answer 1

这个C++让G++发出非常好的x86 ASM（godbolt编译器资源管理器）。我希望它在其他64位体系结构上也能高效地编译（如果std::bitset::count有一个HW popcount，否则它总是很慢的部分；例如，一定要使用g++-march=nehalem或更高的版本，或者如果您不想启用任何其他功能，如果您可以将代码限制为只在支持该x86指令的CPU上运行，则使用-mpopcnt):

#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 widthes创建一个具有专门化的模板函数。在这种情况下，将位集提取为适当宽度的unsigned类型，并移到寄存器的顶部，而不是位集的顶部。

您希望这也能为位集<32>生成理想的代码，但事实并非如此。GCC/CLANG仍然使用X86-64上64位寄存器。

对于较大的位集，移动整个内容将比仅仅在包含pos的单词下方弹出单词，并在该单词上使用这个更慢。（如果您可以假设SSSE3而不是popcntinsn硬件支持，或者对于32bit目标，这就是向量化popcount在x86上真正发挥作用的地方。AVX2 256bitpshufb是执行批量popcount的最快方法，但如果没有AVX2，我认为64bitpopcnt与128 bitpshufb实现相当接近。请参阅注释了解更多讨论。）

如果您有一个由64位元素组成的数组，并且希望分别计算每个元素中某个位置以下的位，那么您肯定应该使用SIMD。该算法的移位部分向量化，而不仅仅是popcnt部分。对全零寄存器使用psadbw对基于pshufb的popcnt后的64位块中的字节进行水平求和，该popcnt分别为每个字节中的位产生计数。SSE/AVX没有64位算术右移，但您可以使用不同的技术来混合每个元素的高位。

您希望编译器输出的asm指令将：

1. 从64bit值中删除不需要的位
2. 测试所需的最高位。
3. 点击它。
4. 返回0或popcount，具体取决于测试结果。（无分支或分支实现都有优点。如果分支是可预测的，则无分支实现的速度往往较慢。）

这还有一个有趣的副作用，就是将要测试的位作为寄存器的顶部位。测试符号位，而不是任何其他任意位，所需的指令略少。算术右移可以将符号位广播到寄存器的其余部分，从而实现比通常更高效的无分支代码。

做popcount是一个讨论得很多的问题，但实际上是这个难题中比较棘手的部分。在x86上，有非常有效的硬件支持，但只有在最近的-足够的硬件上。在Intel CPU上，popcnt指令仅在Nehalem和更新版本上可用。我忘了AMD是什么时候加入支持的。

因此，为了安全地使用它，您需要使用不使用popcnt的回退来执行CPU调度。或者，制作独立的二进制文件，这些二进制文件依赖于/不依赖于某些CPU特性。

该广播可以通过63的算术右移来完成，该右移在高位的副本中移动。

clang从原始版本生成了此代码。在Glenn关于4的不同实现的一些催促之后，我意识到，通过编写更像我想要的ASM的源代码，我可以将gcc引向Clang的最佳解决方案。明显的((int64_t)something)>>63来更直接地请求算术右移将不是严格可移植的，因为有符号右移是实现定义为算术或逻辑的。该标准没有提供任何可移植的算术右移运算符。（不过，这不是没有定义的行为。）不管怎样，幸运的是编译器足够聪明：只要给它足够的提示，gcc就会看到最好的方法。

这个源代码使用gcc和clang在x86-64和ARM64上编写了很好的代码。两者都只是在popcnt的输入上使用算术右移位（因此移位可以与popcnt并行运行）。它还可以在32bit x86上使用gcc进行很好的编译，因为掩蔽只发生在32bit变量上（在添加多个popcnt结果之后）。在32bit上（当位集大于寄存器时），函数的其余部分是糟糕的。

带有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

看看如何证明C语句-x、~x+1和~(x-1)得到相同的结果？有关GCC使用-x==~x+1二的补码标识的背景信息。（如果只想要结果的低部分，那么哪一个2的补码整数运算可以在不将输入中的高位清零的情况下使用呢？其中切线地提到shl屏蔽了移位计数，所以我们只需要ecx的低6位来保存63-pos。主要是因为我最近写了这篇文章，任何还在读这段话的人可能会觉得很有趣。）

内联时，这些指令中的一些将会消失。（例如，gcc首先会在ecx中生成计数。）

使用Glenn的乘法而不是三元运算符思想（由use_mul启用），gcc可以

    shr     rdi, 63
    imul    eax, edi

而不是xor/test/cmovs。

• MOV r,r:1融合域uop,0延迟,无执行单元
• 异或-归零：1个融合域uop，无执行单元
• 非:P0/P1/P5/P6的1个uop，1C延迟，每0.25C吞吐量1个
• shl（又名sal)，计数在cl:P0/P6:2C延迟为3个UOP，每2C吞吐量为1个。（Agner Fog的数据表明IvyBridge对此只使用了2个UOP，这很奇怪。）
• POPCNT:1个uop用于p1，3C延迟，每1C吞吐量1个
• SHR r,IMM:1 uop用于P0/P6,1C潜伏期。每0.5C吞吐量为1个。
• IMUL r,r:1UOP用于p1,3C延迟。
• 不计算ret

总数：

• 9个融合域uop，可以在2.25个周期内发出（理论上，uop缓存行效应通常会使前端稍有瓶颈）。
• P0/P6的4个UOP（移位）。P1的2 UOP。1任意ALU端口UOP。可以每2c执行一个（使移位端口饱和），因此前端是最大的瓶颈。

cmov（三元算子）版本：11个融合域UOP（前端：每2.75C一个）。执行单元：移位端口(P0/P6)仍然处于瓶颈状态，为每2c一个。延迟：从位集到结果的延迟为7c，从pos到结果的延迟为8c。(CMOV为2C延迟，对于P0/P1/P5/P6中的任一项为2 UOP。）

Clang有一些不同的诀窍：它不是test/cmovs，而是通过使用算术右移将符号位广播到寄存器的所有位置来生成全1或全0的掩码。我喜欢它：使用和而不是cmov在Intel上效率更高。但是，它仍然具有数据依赖性，并且为分支的两边都做工作（这是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/和替换了xor/test/cmov，cmov是Intel CPU上的2-UOP指令，所以这真的很好。（对于三元运算符版本）。

当使用multiply源版本或“bitbroadcast”源版本时，Clang仍然执行sar/和技巧，而不是实际的imul。所以这些帮助gcc而不伤害Clang。(SAR/和肯定比SHR/IMUL好：关键路径上的延迟少2C。）pow_of_two_sub版本确实会造成碰撞（请参见第一个godbolt链接：为了避免出现杂乱的想法，本文省略了这个链接）。

MOV ecx,63/子ecx,ESI实际上在没有MOV消除的CPU上更快，用于reg,reg移动（零延迟和无执行端口，通过寄存器重命名处理）。这包括Intel之前的IvyBridge，但不包括最近的Intel和AMD CPU。

Clang的mov imm/sub方法只将pos的一个延迟周期放入关键路径（超出位集->结果延迟周期），而不是将mov ecx、ESI/not ecx的两个延迟周期放入CPU上，其中mov r,r具有1C延迟。

使用BMI2(Haswell和更高版本），最佳ASM版本可以将MOV保存到ECX。其他的工作原理都是一样的，因为shlx像shl一样，将其移位计数输入寄存器屏蔽到操作数大小。

x86 shift指令具有疯狂的CISC语义，如果shift计数为零，则标志不受影响。所以变量计数移位指令对标志的旧值有（潜在的）依赖关系。“normal”x86SHL r,CL在Haswell上解码为3个UOP，但BMI2SHLX r,r,r仅为1个。所以很糟糕的是，gcc仍然使用-march=haswell发出sal，而不是使用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

Intel Haswell的性能分析：6个融合域UOP（前端：每1.5C一个）。执行单位：2个P0/P6班UOP。1个p1 UOP。2任意端口UOP：（总执行端口限制中每1.25C有一个）。关键路径延迟:shlx(1)->popcnt(3)->和(1)=5C位集->结果。（或来自位置->结果的6c)。

请注意，内联时，人工（或智能编译器）可以避免使用异或eax,eax。它之所以存在，是因为popcnt对输出寄存器的错误依赖（在Intel上），并且我们需要eax中的输出（调用方最近可能在长dep链中使用了它）。使用-mtune=bdver2或其他方法时，gcc不会将用于popcnt输出的寄存器归零。

内联时，我们可以使用至少在popcnt的源reg之前就已经准备好的输出寄存器来避免这个问题。当以后不需要源代码时，编译器将执行就地的POPCNT rdi，rdi，但这里不是这样。相反，我们可以选择在源之前已经准备好的另一个寄存器。popcnt的输入依赖于63-pos,我们可以对其进行重击,因此popcntRSI、RDI对rsi的依赖不能延迟它。或者，如果我们在寄存器中有63，我们可以POPCNT rsi,RDI/SARX rax,rsi,REG_63/和eax,ESI。或者BMI2的3操作数移位指令也可以让我们在以后需要输入的情况下不重击输入。

这是如此轻量级，循环开销和设置输入操作数/存储结果将是主要因素。（63-pos可以使用编译时常量进行优化，也可以在变量计数的任何地方进行优化。）

有趣的是，英特尔编译器搬起石头砸自己的脚，并没有利用A[63]是符号位的事实。SHL/BT rdi，63/JC。它甚至以一种非常愚蠢的方式设置分支。它可以使eax归零，然后根据shl设置的符号标志跳过popcnt或不跳过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并跳回的末尾块）。