logo标签列表

在ARM汇编中，最快的方法是计算寄存器中1的数量。

assemblyarmhammingweight
18
所以我之前在一家知名的GPU公司面试时遇到了一个有关位操作的问题。尽管我是计算机体系结构的博士生，但对汇编语言了解甚少（这很奇怪），正如这个故事所表明的那样，我搞砸了。问题很简单：
“编写一个快速的代码，用于计算32位寄存器中1的数量。”
现在我正在学习ARM汇编语言。因此，自然而然地，我重新思考了这个问题，并通过研究ISA提出了以下代码。
对于你们那些精通ARM的专家，这个代码正确吗？有更快的方法吗？作为一个初学者，我自然认为这还不完整。在ARM ISA中，“xx”中的AND指令似乎是多余的，但没有其他方法可以移动寄存器...
R1将包含最终的位数，而R2是我们要计算的位的寄存器。r6只是一个虚拟寄存器。注释用()括起来。
    MOV   R1, #0                (initialize R1 and R6 to zero)
    MOV   R6, #0        
xx: AND   R6, R6, R2, LSR #1    (Right shift by 1, right most bit is in carry flag)
    ADDCS R1, #1                (Add #1 to R1 if carry  flag is set)
    CMP R2, #0                  (update the status flags if R2 == 0 or not)
    BEQ xx                      (branch back to xx until R2==0)
1
什么是最快的也取决于您希望设置的位数。对于非常少的1，Kernighan的位计数器将获胜，因为它为每个设置的位运行一轮循环。 - Bo Persson
你的算法对于所有的1需要4*32+2个指令。Dave Seal的算法只需六个指令加上一次内存访问；除非内存非常慢，否则它可能对所有类型的输入都同样快。我怀疑很少有人会理解Dave Seal的解决方案。对我来说，“反向减”只是很奇怪。 - artless noise
8个回答
12

代码运行速度快不快取决于处理器。在Cortex-A8上肯定不会很快，但在Cortex-A9和更新的CPU上可能非常快。

然而，这是一个非常简短的解决方案。

期望输入在r0中，并将输出返回到r0中。

  vmov.32 d0[0], r0
  vcnt.8  d0, d0
  vmov.32 r0, d0[0]

  add r0, r0, r0, lsr #16
  add r0, r0, r0, lsr #8
  and r0, r0, #31
主要工作在于vcnt.8指令，它计算NEON寄存器中每个字节的位数，并将位数统计结果存储回D0的字节中。
没有vcnt.32形式，只有.8，因此需要将4个字节水平相加，这就是代码的其余部分所做的事情。
3
“vmov.32 r0, d0[0]” 在 NEON 和 Core 之间引起了非常大的同步延迟。 - user3124812
@user3124812：我的理解是这取决于CPU。我认为许多ARMv8的CPU在遇到数据依赖时有更少的坏停顿，或者如果它们具有乱序执行功能，可以绕过数据依赖（因此会有一些延迟但不会停顿）。据我所知，即使在32位模式下运行也适用。但是是的，我认为有一些CPU在这方面比较慢。与大多数循环相比，除非只有几个位被设置并且您正在遍历设置的位，否则它可能比大多数循环慢。我不知道它与Hacker's Delight中auslen回答中展示的无分支SWAR位操作的比较情况；可能会因CPU型号而异。 - Peter Cordes
7
由于该标记被标记为ARM，因此clz指令非常有用。该问题还描述为人口普查。gcc具有__builtin_popcount()。 ARM工具也是如此。有此链接（不要因您的解决方案而感到难过，有人制作了一个网页，内容几乎相同），以及Dave Seal的版本适用于非clz ARMs的六个指令。根据输入情况，clz更具优势，可以用于生成更快的算法。

除了auselen 的好的阅读建议，《黑客的乐趣》，这个位操作博客可能有所帮助，其中讨论了这些内容在图形上下文中。至少我发现它对理解Qt的混合代码非常有用。但是，它在编写人口普查例程方面也很有用。

使用carry add单元将问题分治会使问题变成O(ln n)。如果数据具有一连串的1或0，则clz更有用。

《黑客的快感》条目详细介绍了Dave Seal的ARM代码背景。

1
我认为__builtin_popcount是从查找表实现编译的，它应该足够好，但并没有专门为arm设计。 - auselen
@auselen：请检查您的ARM架构级别。clz仅在ARMv5及以上版本中可用。 - Igor Skochinsky
@IgorSkochinsky 我认为gcc或llvm没有提供clz的实现。__builtin_popcount()链接到__popcountsi2。 - auselen
好的，popcount 比 clz 做得更多，因此它需要一个辅助程序。对于支持的架构，__builtin_clz 或 __builtin_ctz 直接发出 clz。 - Igor Skochinsky
1
例如，在二进制图像/图片数据上进行人口统计可能会从clz中受益，特别是如果它具有大量的低频内容。我认为这个问题是在图形上下文中提出的。 - artless noise
显示剩余2条评论
7

比特运算技巧的最佳参考资料是：

Bit Twiddling Hacks 页面说：

The best method for counting bits in a 32-bit
integer v is the following:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

那么我建议您使用gcc和objdump(或这个很好的在线gcc工具)来查看这个高级代码段在arm指令中的样子。

00000000 <popcount>:
 0: 1043        asrs    r3, r0, #1
 2: f003 3355   and.w   r3, r3, #1431655765 ; 0x55555555
 6: 1ac0        subs    r0, r0, r3
 8: 1083        asrs    r3, r0, #2
 a: f000 3033   and.w   r0, r0, #858993459  ; 0x33333333
 e: f003 3333   and.w   r3, r3, #858993459  ; 0x33333333
12: 18c0        adds    r0, r0, r3
14: eb00 1010   add.w   r0, r0, r0, lsr #4
18: f000 300f   and.w   r0, r0, #252645135  ; 0xf0f0f0f
1c: eb00 2000   add.w   r0, r0, r0, lsl #8
20: eb00 4000   add.w   r0, r0, r0, lsl #16
24: 1600        asrs    r0, r0, #24
26: 4770        bx  lr

所以看起来这个指令可以给你12个结果，大约可以转化为相同数量的周期。将整数扭曲与由libgcc使用的查找表方法进行比较，考虑到额外的内存访问，查找表应该更慢。
00000028 <__popcountSI2>:
28: b410        push    {r4}
2a: 2200        movs    r2, #0
2c: 4c06        ldr r4, [pc, #24]   ; (48 <__popcountSI2+0x20>)
2e: 4613        mov r3, r2
30: fa40 f103   asr.w   r1, r0, r3
34: 3308        adds    r3, #8
36: 2b20        cmp r3, #32
38: b2c9        uxtb    r1, r1
3a: 5c61        ldrb    r1, [r4, r1]
3c: 440a        add r2, r1
3e: d1f7        bne.n   30 <__popcountSI2+0x8>
40: 4610        mov r0, r2
42: bc10        pop {r4}
44: 4770        bx  lr
46: bf00        nop
48: 00000000    andeq   r0, r0, r0
<.. snipped ..>
如何将一个32位的常量放入一个32位指令中？ - phuclv
@LưuVĩnhPhúc 说什么？ - auselen
像这样：and.w r0，r0，＃252645135 ; 0xf0f0f0f 常量的大小为32位。 - phuclv
@LưuVĩnhPhúc 嗯，那是编译器的输出，所以我认为这是非常可能的。如果常量的熵值很低，那么就可以将其放入指令中。应该有一种有效的方法来将0x80000000加载到寄存器中，否则它将成为一个较差的ISA。 - auselen
1
and.w指令不是普通的AND，从操作码条件字段中的f前缀可以看出。在这种情况下，它被赋予一个单字节的立即数0x0f，它应用于寄存器输入的所有4个字节，有效地为0x0f0f0f0f。 - davenpcj
@phuclv 请查看 ARM 中的 Operand2。灵活的第二操作数支持0xXYXYXYXY形式的复杂打包，例如，其中X和Y是指令中编码的4位半字节。还支持常量值的可变移位。 - Thomas O
5

您可以使用预计算的查找表，将迭代次数减少到2或4次。

您也可以使用对数方法。

更多信息请参见此维基百科文章。

1
看起来汉明重量是一个相当著名的问题。谢谢！ - dean
3
+1 给汉明重量文章。特别是对于 ARM，它提到 Neon SIMD 指令提供了 vcnt，http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489c/CIHCFDBJ.html 来执行这个操作。对于 SIMD 类型的指令集，还有使用洗牌指令作为表查找的方法来加速它（每个 SSE2 寄存器都可以通过 pshufb 作为 16 字节查找表使用，或者在 ARM Neon 的情况下，使用 vtbl）。请参见 https://dev59.com/THA65IYBdhLWcg3wrQl4 - FrankH.
2
    LDR r0, = 0x000000FF;
    MOV r1, #0;
    MOV r3, #0; this will always be zero
    MOV r2,r0;
rep MOVS r2, r2, LSR #1;
    ADC r1,r1, r3;  this adds r1 with zero plus the carry bit
    CMP r2, #0;
    BNE rep

这样做可以解决问题，r3只是一个虚拟寄存器，其值为0以确保ADC正常工作。

每次移动1位并不快速。 - Peter Cordes
1
@Avsharian：这里的“CMP”是多余的（你看出来了吗？）。同样的，r3: #0就足够“使ADC正常工作”了（至于最初的“LDR”，我只是在想……）。如果你在写汇编，请至少在StackOverflow上注意一下 :) - avs333
1

long count_bits_long (long);

    vmov.32 d0[0], r0       // R0 --> SIMD

    vcnt.8  d0, d0          // count bits in bytes
    vpaddl.u8 d0, d0        // add adjacent pairs of bytes and put into 16b words
    vpaddl.u16 d0, d0       // add adjacent pairs of 16b words and put into 32b word

    vmov.32 r0, d0[0]       // SIMD --> R0

    mov pc, lr              // return
这是@Nils的答案，但使用NEON水平求和而不是标量。这在哪些CPU上更快？ - Peter Cordes
0
在AArch64中，CSSC扩展引入了一种标量形式的popcount指令。
 cnt  w0, w0

我不认为这在32位模式下可用，所以这个答案有点离题，只有需要复制到NEON寄存器然后再复制回来的vcnt。这可能会在CPU上阻塞流水线，如果它们没有紧密耦合，那么在某些情况下使用标量位操作可能会更快，或者甚至使用循环，如果你预计通常只有几个位被设置。（我认为AArch64 CPU在整数和向量寄存器之间移动数据时不会阻塞，或者不会太严重，但是没有CSSC也一样；请参见编译器输出。）
GCC13增加了对CSSC的支持，您需要手动启用它，使用-march=armv8-a+cssc。即使使用-march=armv9.3-a，GCC或clang也无法在C++20中使用(Godbolt)的std::popcount（即__builtin_popcount()）而不带+cssc部分。-mcpu=cortex-x3和-mcpu=cortex-a710也不能启用它，所以我认为它们没有这个功能。
0
如果您没有popcnt指令，通常可以使用vperm/pshufb/vtbl指令来查找使用洗牌指令在表中查找位数。大致上的伪代码如下：
ucharN someVector = …;
ucharN lowNibbles = someVector & 0xf;
ucharN highNibbles = someVector >> 4;

static const ucharN popcntTable = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4…}; // vector[i] = popcnt(i)
return vtblq_u8(lowNibbles, popcntTable) + 
       vtblq_u8(highNibbles, popcntTable);

根据向量架构，您需要调整表的大小和表的值以适应洗牌指令的特殊性，例如AVX2在寄存器中间的屏障，或者arm32s的8字节洗牌单元。可能我还交换了vtbl的参数顺序。希望你明白我的意思。
有没有带有NEON vtbl但没有vcnt的ARM CPU？（https://developer.arm.com/documentation/dui0489/i/neon-and-vfp-programming/vcnt）。从那里，您需要对每个字节的结果进行水平求和，无论您是从`vcnt`还是`vtbl`获取它们。 - Peter Cordes
你需要查看每个指令是在哪个处理器架构中引入的。这对于SSE和AltiVec来说确实是一个问题。通常会使用成对的加法来对大于8位元素的向量进行水平求和。作为一道面试题，我敢打赌他们不仅仅希望得到“只需使用vcnt”作为答案，但提及它也无妨。 - Ian Ollmann
是的，不同的架构师在他们的SIMD指令集的第一个版本中包含了不同的特性。x86直到Nehalem（在Core 2的SSSE3之后）的SSE4.2才有了popcnt指令，而且只支持标量操作。SIMD popcnt指令要等到十多年后的Ice Lake才出现，具体是通过AVX-512VPOPCNT和AVX-512BITALG实现的。但据我所知（例如来自2008年的ARMv7 ISA手册），ARM直到ARMv7才引入了NEON指令集，一次性引入了所有的NEON（即Advanced SIMD）指令，并将NEON作为可选扩展全部引入到ARMv7中。 - Peter Cordes
好的，所以在最初的ARMv7 NEON之后发生了一些演变。但是ARMv7 NEON包括vcnt，而之前的ARM SIMD扩展中没有包括vtbl或等效的字节重排，据我所知。而且据我所知，后来的CPU不可能省略vcnt但不省略vtbl。（至少不能通过ARMv7引入的CPUID机制进行广告宣传，据我所知。当然，自定义核心可以省略任何你想要的内容，并且编写代码时只需避免使用特定指令。）此外，在某些低端ARM核心上，vtbl的速度较慢，并且NEON到整数的转换在某些核心上也很慢，导致流水线停顿以进行同步。 - Peter Cordes
我本来是想早点链接为什么Clang在AArch32上不使用vcnt来实现__builtin_popcountll？的。Nate在被接受的答案中的评论提到了使用vpaddl序列对每个字节的计数进行hsum，因为与AArch64不同，我们没有一个可以在超过一对以上的元素上执行单指令hsum的功能。但无论如何，有趣的是，一个通常表现良好的编译器选择不使用整数-> NEON-> 整数的往返方式来进行单个标量popcount。这可能是某些CPU的合理调优决策，而不是一个错失的优化机会。（但对于其他CPU可能是错失的优化机会） - Peter Cordes
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接