logo标签列表

x<<1和x<<10哪个更快？

c++cperformancecpulow-level
86

我绝对不想优化任何东西，我只是出于好奇想问这个问题。我知道在大多数硬件上都有一个位移的汇编指令（例如 shl, shr），这是一个单独的指令。但是，无论你移动多少位，它是否会影响性能（以纳秒或 CPU 指令为单位）？换句话说，在任何 CPU 上，以下哪种方法更快？

x << 1;

并且

x << 10;

请不要因为这个问题而讨厌我。 :)

1
作为附注：我最近意识到左移和右移不一定消耗相同的CPU时间。在我的情况下，右移比左移慢得多。起初我很惊讶，但我认为答案是左移意味着逻辑移位，而右移可能意味着算术移位: https://dev59.com/Q3VC5IYBdhLWcg3w7V73 - Christian Ammer
9个回答
86

可能与CPU有关。

然而，所有现代的CPU（x86，ARM）都使用“移位器”--一种专门设计用于在恒定时间内执行任意移位操作的硬件模块。

因此，最终结论是...没有区别。

12
这非常取决于处理器。在某些处理器上，这是恒定时间的。在其他处理器上，每次移位可能需要一个周期（我曾经使用过将约60,000个位置移位作为一种软件测量处理器时钟速度的方法）。对于其他处理器，可能只有单比特移位的指令，此时多比特移位将委托给一个库例程，该例程会循环迭代执行。 - quickly_now
5
那确实是衡量时钟速度的糟糕方法。没有处理器会愚蠢到真正执行60000个移位操作；这将被转换为“60000模寄存器大小”。例如，一个32位的处理器只会使用移位计数的最低的5个有效位。 - casablanca
4
Inmos Transputer拥有一个移位运算符，该运算符将位移量作为32位操作数。如果需要的话，您可以进行40亿次移位，每次仅需1个时钟周期。尽管其他处理器可能会认为这种做法太傻了，但这个处理器却不然。但需要用汇编语言编写这部分代码。编译器进行了合理的修改/优化（只需将结果设置为0，不执行任何操作）。 - quickly_now
5
Pentium 4可悲地失去了移位器，这导致它的每个时钟周期指令数表现不佳。我认为Core Blah架构重新引入了它。 - Russell Borogove
1
@RussellBorogove：在P4上，shl的性能仍然与计数无关，只是比较慢（4个周期延迟，或者在Prescott上为1c：http://agner.org/optimize/）。但是聪明的编译器会使用“add x，x”进行左移位1（在Prescott之前的双泵ALU上具有0.5c延迟）。右移位1没有这样的快捷方式。 - Peter Cordes
显示剩余2条评论
65

一些嵌入式处理器只有“移位1位”的指令。在这种处理器上，编译器会将x << 3转换为((x << 1) << 1) << 1。

我认为Motorola MC68HCxx是具有这种限制的更受欢迎的系列之一。幸运的是，这样的体系结构现在相当罕见，大多数现在包括一个可变移位大小的旋转移位器。

英特尔8051也不能移动任意数量的位，它有许多现代派生版本。

12
仍然常见于嵌入式微控制器。 - Ben Jackson
4
"Rare"在这里的意思是什么？根据统计数据，销售的8位微控制器数量大于所有其他类型的微处理器的数量。 - Vovanium
1
微控制器的字长与其是否具有移位寄存器无关，我提到的MC68HCxx系列也有16位处理器，它们每次只能移动一个位位置。 - Ben Voigt
大多数8位MCU没有移位器这一事实是正确的，尽管有些不是如此，也有没有移位器的非8位MCU存在。对于没有移位器的机器，位宽被用作可靠的近似值。此外，MCU的CPU核心通常不会设置型号选择，但芯片上的外设会进行设置。在同样的价格下，8位MCU通常被选用于更丰富的外设。 - Vovanium
我怀疑移位寄存器的存在往往与寄存器宽度相关，因为在32位处理器上没有移位寄存器的代价比在8位处理器上更严重。 - supercat
显示剩余3条评论
30

这个问题有很多情况需要考虑。

  1. 许多高速MPU具有位移寄存器，它们是类似于复用器的电子电路，可以在恒定时间内执行任何位移操作。

  2. 如果MPU只有1位移位，x << 10通常会更慢，因为大多数情况下需要进行10次位移或使用2次位移进行字节复制。

  3. 但已知一种常见情况，其中x << 10甚至比x << 1更快。如果x是16位，则只有其较低的6位是关键（所有其他位都将被移出），因此MPU仅需加载较低的字节，从而对8位内存进行单个访问周期，而x << 10需要两个访问周期。如果访问周期比移位（和清除低字节）慢，则x << 10将更快。这可能适用于具有快速内置程序ROM且访问缓慢外部数据RAM的微控制器。

  4. 作为第3种情况的补充，编译器可能关心x << 10中有效位的数量，并将进一步优化操作以进行更低宽度的运算，例如将16x16乘法替换为16x8乘法（因为低字节始终为零）。

请注意，有些微控制器根本没有左移指令，它们使用add x,x代替。

我不明白，为什么x << 10比x << 8更快，因为在x << 8中，您需要从16位的低字节进行加载，而不是加载和两个移位。我不理解。 - none
3
我没有说x<<10比x<<8更快。 - Vovanium
9

这是我最喜欢的CPU，点击链接查看。在这个CPU中，x<<2所需时间是x<<1的两倍 :)

很不幸的是，它没有像8051、PIC或AVR那样的nibble swap指令，因此无法使用优化技巧。 - phuclv
9

在ARM上，这可以作为另一条指令的副作用而完成。因此，在任何一种情况下都没有潜在的延迟。

1
指令执行的周期数相同吗？在某些体系结构中，相同的指令将根据操作数转换为几个不同的操作码，并且需要花费1到5个周期。 - Nick T
@Nick 一条ARM指令通常需要1到2个周期。不确定在新的架构中是否有所改变。 - onemasse
2
@Nick T：他在谈论 ARM，它具有移位不是专用指令，而是许多数据处理指令的“特性”。例如 ADD R0，R1，R2 ASL #3 将使 R1 和 R2 左移 3 位。 - Vovanium
7

可以想象，在8位处理器上，对于16位值，x<<1实际上比x<<10慢得多。

例如，x<<1的合理翻译可能是：

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

相比之下，x<<10 更为简单:

byte1 = (byte2 << 2)
byte2 = 0

请注意，x<<1的移位次数比x<<10更多，甚至更远。此外，x<<10的结果不取决于byte1的内容。这可以进一步加速操作。
7
这取决于CPU和编译器。即使底层CPU具有带有桶移位器的任意位移，只有编译器利用该资源才会发生这种情况。
请记住，在C和C ++中，将任何数据移动到超出其比特宽度范围之外是“未定义行为”。有符号数据的右移也是“实现定义”的。与其过分关注速度，不如关注在不同实现上获得相同的答案。
引用ANSI C第3.3.7节：

3.3.7 Bitwise shift operators

Syntax

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

Constraints

Each of the operands shall have integral type.

Semantics

The integral promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width in bits of the promoted left operand, the behavior is undefined.

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity, 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. (The constants ULONG_MAX and UINT_MAX are defined in the header .)

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 divided by the quantity, 2 raised to the power E2 . If E1 has a signed type and a negative value, the resulting value is implementation-defined.

所以：
x = y << z;

"< < ": 如果没有溢出，y × 2^z，否则为“未定义”。
x = y >> z;

">>：对于有符号数，其实现方式是未定义的（通常是算术右移的结果：y / 2z）。"
我认为 1u << 100 不是未定义行为。它只是0。 - Armen Tsirunyan
@Armen Tsirunyan：位移 1u << 100 作为位移操作可能会导致溢出；而作为算术移位则为0。在 ANSI C 中，<< 是位移操作。http://en.wikipedia.org/wiki/Arithmetic_shift - the wolf
2
@Armen Tsirunyan：请参阅 ANSI 第 3.3.7 节--如果右操作数的值为负数或大于等于提升后的左操作数位数宽度，则行为未定义。因此，除非存在 101+ 位类型，否则您的示例在任何 ANSI C 系统上都是 UB。 - the wolf
@carrot-pot：好的，你说服我了 :) - Armen Tsirunyan
相关：如果编译器知道目标架构的移位指令掩码计数（如x86），则x << (y & 31)仍然可以编译为单个移位指令而无需AND指令。（最好不要硬编码掩码；从CHAR_BIT * sizeof(x) - 1或其他地方获取。）这对于编写旋转惯用语很有用，它可以编译为单个指令，而不管输入如何都不会出现C UB。（https://dev59.com/J3RA5IYBdhLWcg3w8SiJ）。 - Peter Cordes
5

在一些Intel CPU的世代中（P2或P3？不过好像不包括AMD），位移操作非常慢。但是将数字左移1位应该总是很快，因为它只需使用加法。另一个需要考虑的问题是，按恒定数量的位移是否比按变长位移更快。即使操作码的速度相同，在x86上，位移的非恒定右操作数必须占用CL寄存器，这对寄存器分配施加了额外的限制，并可能以此方式减慢程序的运行速度。

1
那是奔腾4。基于PPro的CPU（如P2和P3）具有快速移位功能。是的，在x86上，变量计数移位比它们本应该的更慢，除非您可以使用BMI2 shlx / shrx / sarx（Haswell及更高版本和Ryzen）。CISC语义（如果count = 0，则标志未修改）在这里对x86造成了伤害。在Sandybridge系列上，“shl r32，cl”需要3个微操作（尽管英特尔声称如果不使用标志结果，则可以取消其中一个微操作）。AMD具有单微操作“shl r32，cl”（但对于扩展精度而言，双移位较慢，“shld r32，r32，cl”）。 - Peter Cordes
1
移位操作（即使是变量计数）在P6系列处理器上只需要一个uop，但读取shl r32, cl的标志结果或使用除1以外的立即数会阻塞前端，直到移位操作完成！（https://dev59.com/y1oV5IYBdhLWcg3wPctv）。编译器知道这一点，并使用单独的`test`指令而不是使用移位操作的标志结果。（但在CPU不受影响的情况下，这会浪费指令，参见https://dev59.com/Huk6XIcBkEYKwwoYAfK1#40355466） - Peter Cordes
3

一如既往，这取决于周围的代码上下文：例如，您将x<<1用作数组索引吗？还是将其添加到其他内容中？在任何情况下，小的移位计数（1或2）通常可以比编译器最终必须进行的仅仅移位更加优化。更不用说整个吞吐量与延迟与前端瓶颈之间的权衡了。一个微小片段的性能不是单一维度的。

硬件移位指令不是编译器编译x<<1的唯一选择，但其他答案大多都假定了这一点。

x << 1等价于x+x对于无符号整数和2进制补码有符号整数。编译器在编译时总是知道他们要针对哪种硬件，因此可以利用这样的技巧。

在Intel Haswell上，add每个时钟周期有4个吞吐量，但带有立即计数的shl每个时钟周期只有2个吞吐量。（请参见http://agner.org/optimize/以获取指令表和标签wiki中的其他链接）。SIMD矢量移位为每个时钟周期1个（Skylake为2个），但SIMD矢量整数加法为每个时钟周期2个（Skylake为3个）。然而延迟时间相同：1个周期。

还有一种特殊的shl编码方式，其中计数在操作码中是隐含的。8086没有立即计数移位，只有按一和按cl寄存器移位。这对于右移最为相关，因为左移可以通过加法实现，除非你正在移动一个内存操作数。但是，如果需要该值，最好先加载到寄存器中。总之，shl eax,1或add eax,eax比shl eax,10少一个字节，并且代码大小直接（解码/前端瓶颈）或间接（L1I代码缓存未命中）影响性能。

更一般地说，在x86上，小的移位计数有时可以优化为缩放索引的寻址模式。现在大多数其他常用的体系结构都是RISC结构，没有缩放索引寻址模式，但x86是一个足够常见的架构，值得一提。（例如，如果您正在索引一个4字节元素的数组，则可以通过将比例因子增加1来增加空间int arr[]; arr[x<<1]）。

在需要保留变量 x 原始值的情况下，需要进行复制和移位操作。但是大多数 x86 整数指令都是就地操作（目标寄存器是类似于add或shl这样的指令的源之一）。x86-64 System V 调用约定使用寄存器传递参数，第一个参数在 edi 中，返回值在 eax 中，因此返回 x<<10 的函数也会使编译器生成复制和移位代码。

LEA 指令允许您进行移位和加法计算

，其移位数量为 0 到 3（因为它使用寻址模式机器编码）。该指令将结果放入单独的寄存器中。

GCC和Clang都以同样的方式对这些函数进行优化，如您在Godbolt编译器探索器中所见：

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

LEA指令在现代英特尔和AMD CPU上具有1个时钟周期延迟和2个每时钟周期的吞吐量，且具有2个组件。在英特尔上，对于lea eax，[rdi + rsi + 123]，每时钟周期吞吐量为1，延迟为3个时钟周期。(相关: 为什么这段C++代码比我手写的汇编测试Collatz猜想更快?详细介绍了这一点。)
无论如何，复制+移位10需要单独的mov指令。在许多现代CPU上它可能是零延迟，但它仍然需要前端带宽和代码大小。( x86的MOV指令真的可以“免费”吗？为什么我根本无法重现这个结果?)
此外相关: 如何在x86中仅使用2个连续的leal指令将寄存器乘以37？。
编译器也可以自由地转换周围的代码，所以实际上并没有移位操作，或者将其与其他操作组合在一起。例如，if(x<<1) { } 可以使用and检查除高位之外的所有位。在x86上，您将使用test指令，如test eax, 0x7fffffff / jz .false而不是shl eax,1 / jz。这种优化适用于任何移位次数，并且在大位移速度缓慢（如Pentium 4）或不存在（某些微控制器）的机器上也适用。许多ISA具有超出移位之外的位操作指令。例如，PowerPC具有许多位字段提取/插入指令。或者ARM将源操作数移位作为任何其他指令的一部分。（因此，移位/旋转指令只是move的特殊形式，使用了移位的源）。请记住，C不是汇编语言。当您调整源代码以有效地编译时，请始终查看优化的编译器输出。
更正：P4在大移位计数方面并不慢，它只是在移位方面比较慢，具有4个时钟周期的延迟，但对于立即或隐式-1移位仍然是单uop。没有性能依赖于计数。此外，Prescott将其改进为32位寄存器的立即移位具有1个时钟周期的延迟，但64位移位具有7个时钟周期的延迟 :/ - Peter Cordes
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接