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

  • Z时代
  • 2024-01-10
  • 分类：问答

给定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()methof bitset将为您popcount提供所有位，但bitset不支持范围

注意：这不是 如何计算32位整数中的设置位数的重复？因为这会询问所有位，而不是0到X的范围

回答：

此C 使g 发出非常好的x86

ASM（godbolt编译器浏览器）。我希望它也可以在其他64位体系结构上有效地进行编译（如果有HW

popcount std::bitset::count可供使用，否则总是很慢的部分；例如，请确保使用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位构建，请比较其他替代方案。

。为了获得奇特大小的位集的最佳性能，请针对size <= register

width目标计算机专门设计一个模板功能。在这种情况下，将位集提取为unsigned适当宽度的类型，然后移至寄存器的顶部而不是位集的顶部。

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

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

。该算法的移位部分进行矢量化，而不仅仅是popcnt部分。使用psadbw针对全零寄存器水平之和后字节中的64位的块pshufb，在每个字节分别产生计数的位基POPCNT。SSE

/ AVX没有64位算术右移，但是您可以使用另一种技术来混合每个元素的高位。

我是怎么想到的：

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

  1. 从64位值中删除不需要的位

  2. 测试所需的最高位。

  3. 流行吧。

  4. 返回0或popcount，具体取决于测试结果。（无分支或分支实现都具有优势。如果分支是可预测的，则无分支实现往往会变慢。）

做 的明显方法是生成一个mask（(1<<(pos+1))

-1）及其它&。一种更有效的方法是左移63-pos，将要打包的位保留在寄存器的顶部。

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

进行 是一个

为讨论的问题，但实际上是难题的棘手部分。在x86上，它具有非常高效的硬件支持，但仅在最近使用的硬件上才如此。在Intel

CPU上，该popcnt指令仅在Nehalem及更高版本上可用。我忘了AMD增加支持的时间。

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

没有popcnt说明的popcount 可以通过几种方法来完成。人们使用SSSE3

pshufb来实现4位LUT。当在整个阵列上使用时，这是最有效的，而不是一次使用单个64b。标量bithack可能是最好的选择，并且不需要SSSE3（因此可以与具有64位但不包含pshufb的古老AMD

CPU兼容）。

比特广播：

(A[63]? ~0ULL :

0)要求编译器将高位广播到所有其他位位置，以便将其用作与（或）不将popcount结果置零的AND掩码。请注意，即使对于较大的位集大小，它仍然仅掩盖了popcntbitset

的输出，而不是位集本身，所以~0ULL很好，我使用ULL来确保不再要求编译器仅将位广播到寄存器的低32b（与UL在Windows，例如）。

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

clang从原始版本生成了此代码。在Glenn对

不同实现提出了一些建议之后，我意识到我可以通过编写更像我想要的ASM的源代码来使gcc转向clang的最佳解决方案。`((int64_t)something)

63`更直接地要求算术右移的明显做法不是严格可移植的，因为带符号的右移是在实现上定义为算术或逻辑的。该标准未提供任何可移植的算术右移运算符。（尽管这不是未定义的行为。）无论如何，幸运的是，编译器足够聪明：一旦给了足够的提示，gcc就会找到最佳方法。

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

与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掩盖了移位计数，因此我们只需要保持低6位ecx即可）63 -pos。主要是因为我最近写了这篇文章而将其链接起来，任何仍在阅读本段的人可能会觉得有趣。

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

想法（由启用USE_mul），gcc可以

    shr     rdi, 63
    imul    eax, edi

最后而不是xor/ test/ cmovs。

Haswell性能[分析，使用来自Agner

Fog](http://agner.org/optimize/)（乘数版本）的微拱数据：

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

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

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

  • shl（aka sal）的计算方式cl：p0 / p6为3 uops：2c延迟，每2c吞吐量1。（奇怪的是，Agner Fog的数据表明IvyBridge仅需2 oups。）

  • popcnt：p1 1 uop，3c延迟，每1c吞吐量1

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

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

  • 不算 ret

总计：

  • 9个融合域uops，可以 （理论上； uop缓存行效应通常会稍微影响前端的瓶颈）。

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

延迟：从准备好位集到结果为：shl（2）-> popcnt（3）-> imul（3）的关键路径。共

。还是从pos准备好的9c 开始，因为这not会增加1c的延迟。

的

内容替换shr与sar（相同PERF），和imul与and（1C延迟，而不是图3C中，任何端口上运行）。因此，唯一的性能变化是

。吞吐量仍然是前端的瓶颈。

and能够在任何端口上运行都没有什么不同，除非您将其与端口1上出现瓶颈的代码混合在一起（而不是在紧密循环中查看仅运行 此 代码的吞吐量）。

：11个融合域 （前端： ）。执行单元：仍然在转换端口（p0 /

p6）上每2c出现瓶颈。 ：从位集到结果为7c，从位置到结果为8c。（cmov是2c延迟，对于p0 / p1 / p5 /

p6中的任何一个都是2微秒。）

有一些不同的技巧：代替test/

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

铛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 / andreplaces 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。

铛的mov imm/ sub方法看跌期权延迟只有一个循环pos到关键路径（超出bitset->结果等待时间），而不是两个用于mov ecx,

esi/ not ecx上的CPU，其中mov r,r具有1c中的等待时间。

（Haswell和更高版本），最佳的ASM版本可以将

mov为ecx。其他所有操作都一样，因为将shlx其移位计数输入寄存器屏蔽为操作数大小，就像一样shl。

x86移位指令具有疯狂的CISC语义，其中，如果移位计数为零，则标志不会受到影响。因此，可变计数移位指令对标志的旧值具有（潜在）依赖性。“正常的” x86

shl r, cl解码上的Haswell 3个微指令，但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个融合域 （ ）。执行单位：2 p0 / p6移位单位。1 p1

2个任意端口oups ：（从总执行端口限制中每1.25c发送一个）。关键路径延迟：shlx（1）-> popcnt（3）-> and（1）=

5c bitset->结果。（或pos-> result中的6c ）。

请注意，在内联时，人工（或智能编译器）可以避免使用xor eax,

eax。仅在这里是因为popcnt对输出寄存器的错误依赖（在Intel上），并且我们需要其中的输出eax（调用者最近可能在较长的dep链中使用了该输出）。使用-mtune=bdver2gcc或其他方法，不会将要用于popcnt输出的寄存器清零。

进行内联时，我们可以使用至少必须早于popcnt‘source reg’ 已经准备就绪的输出寄存器，以避免出现此问题。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设为零，然后根据设置的符号标志跳过popcnt shl。

，从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并跳回末尾的块）。

以上是 什么是计数一个位置或更低位置的设置位的有效方法？ 的全部内容， 来源链接： utcz.com/qa/400477.html

回到顶部