在CPU上多次添加`a = a * 2 + b`指令？

Question

经典的Multiply-Accumulate操作是a = a + b*c。但我现在想知道是否存在允许在1个时钟周期内对整数执行以下操作的指令：（a和b是无符号的64位整数：unsigned long long int）

a = a*2-1
a = a*2+b

目前，我使用：

a *= 2
--a

对于第一个和

a *= 2
a += b

对于第二个。我认为每个都被转换为ASM中的2条指令。但有没有办法使用1 ASM指令（以及在Intel CPU上使用哪个指令集扩展）？

（我搜索那个因为我这次操作数十亿次）

Answer 1

1. 对于Intel CPU，请参阅LEA指令。它可以在一个指令中完成两个任务（不确定循环）。 （例如，LEA EAX, [EAX*2+EBX]）。请注意，这并非真正意味着乘法加法，因此它有趣的名称（加载有效地址）。
2. 在C和C ++中，你不应该打扰。编译器会做它认为最好的事情，你可能只是阻碍它的努力。我会留在古老的a = a*2-1。

PS：如果你认为某些内容被翻译为两个指令，那么没有什么比查看程序集更容易了。然后你就会知道。

Answer 2

有许多架构可以在单个指令中执行此类操作。例如a*2 + b编译成

• lea eax, [rsi+rdi*2]在x86-64
• 关于ARM的add r0, r1, r0, lsl #1
• ARM64上的add w0, w1, w0, lsl 1
• lda16 r0, r1[r0]在xcore上

编译器将适当地优化表达式。没有理由做a *= 2; a += b这样的事情，在许多情况下会降低可读性

你可以在Compiler Explorer上看到这个演示

但是，如果你只是因为你做了数十亿次这样的操作，那么这实际上是一个XY problem，因为更改C版本不是正确的方法，减少指令数量并不是减少运行时的方式。您不会按指令计数来衡量绩效

现代CPU是标量和微编码的，因此单个复杂指令可能比可以并行执行的多个简单指令慢。编译器显然知道这一点，并在编译时考虑延迟。真正的解决方案是使用多线程和SIMD

例如，Clang在AVX-512的主循环中发出以下指令

vpaddd  zmm0, zmm0, zmm0                            ; a *= 2
vpaddd  zmm1, zmm1, zmm1
vpaddd  zmm2, zmm2, zmm2
vpaddd  zmm3, zmm3, zmm3
vpaddd  zmm0, zmm0, zmmword ptr [rsi + 4*rdx]       ; a += b
vpaddd  zmm1, zmm1, zmmword ptr [rsi + 4*rdx + 64]
vpaddd  zmm2, zmm2, zmmword ptr [rsi + 4*rdx + 128]
vpaddd  zmm3, zmm3, zmmword ptr [rsi + 4*rdx + 192]

它涉及循环展开和自动矢量化。每条指令一次可以处理16个32位整数。当然，如果你使用64位int，那么它一次只能“工作”8。此外，每个相同的指令可以独立于其他指令完成，因此如果CPU有足够的执行端口，它可以并行添加64个ints。现在这就是我们所说的快速

GCC在循环展开时通常不太积极，并使用vpslld，然后使用vpaddd。但这仍然比标量版本更快。在带有霓虹灯的ARM上你可以看到使用shl v0.4s, v0.4s, 1; add v0.4s, v0.4s, v1.4s。这是Compiler Explorer demo link

结合多线程，比你的“优化”快得多