85

我不想优化任何东西，我发誓，我只是想出于好奇问这个问题。我知道在大多数硬件上都有一个移位的汇编命令（例如shl，shr），这是一个单一的命令。但是你移动多少位是否重要（纳秒或 CPU 机智）。换句话说，在任何 CPU 上，以下任一方法是否更快？

x << 1;

和

x << 10;

请不要因为这个问题恨我。:)

4

9 回答 9

86

可能取决于 CPU。

但是，所有现代 CPU（x86、ARM）都使用“桶形移位器”——一种专门设计用于在恒定时间内执行任意移位的硬件模块。

所以底线是......不。没有不同。

于 2010-11-20T17:58:01.703 回答
65

一些嵌入式处理器只有“移位”指令。在这样的处理器上，编译器会x << 3变成((x << 1) << 1) << 1.

我认为摩托罗拉 MC68HCxx 是具有此限制的较受欢迎的系列之一。幸运的是，这样的架构现在已经很少见了，现在大多数都包括一个具有可变移位大小的桶形移位器。

Intel 8051 有许多现代衍生产品，也不能移动任意数量的位。

于 2010-11-20T17:58:19.737 回答
29

这方面的案例很多。

  1. 许多高速 MPU 具有桶形移位器，类似于多路复用器的电子电路，可以在恒定时间内进行任何移位。

  2. 如果 MPU 只有 1 个位移x << 10通常会更慢，因为它主要通过 10 个位移或 2 个位移的字节复制来完成。

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

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

请注意，一些微控制器根本没有左移指令，add x,x而是使用。

于 2010-11-20T19:51:14.440 回答
9

在 ARM 上，这可以作为另一条指令的副作用来完成。所以潜在地，它们中的任何一个都没有延迟。

于 2010-11-20T18:33:05.510 回答
9

这是我最喜欢的 CPU，它x<<2需要两倍的时间x<<1:)

于 2010-11-22T17:02:22.647 回答
7

这取决于 CPU 和编译器。即使底层 CPU 使用桶形移位器进行任意位移，也只有在编译器利用该资源时才会发生这种情况。

请记住，在 C 和 C++ 中，移动超出数据位宽度的任何内容都是“未定义行为”。有符号数据的右移也是“实现定义的”。与其过分担心速度，不如担心您在不同的实现中得到相同的答案。

引用 ANSI C 第 3.3.7 节：

3.3.7 移位运算符

句法

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

约束

每个操作数都应具有整数类型。

语义

对每个操作数执行积分提升。结果的类型是提升的左操作数的类型。如果右操作数的值为负数或大于或等于提升的左操作数的位宽度，则行为未定义。

E1 << E2 的结果是 E1 左移 E2 位位置；空出的位用零填充。如果 E1 具有无符号类型，则结果的值是 E1 乘以数量，2 的 E2 次方，如果 E1 具有无符号长类型，则模 ULONG_MAX+1 减少，否则为 UINT_MAX+1。（常量 ULONG_MAX 和 UINT_MAX 在标题中定义。）

E1 >> E2 的结果是 E1 右移 E2 位位置。如果 E1 具有无符号类型或 E1 具有有符号类型和非负值，则结果的值是 E1 的商除以数量的整数部分，2 的幂 E2 。如果 E1 具有带符号类型和负值，则结果值是实现定义的。

所以：

x = y << z;

"<<": y × 2 z (如果发生溢出则未定义);

x = y >> z;

“>>”：为有符号实现定义（通常是算术移位的结果：y / 2 z）。

于 2010-11-20T23:15:03.177 回答
7

可以想象，在 8 位处理器上，x<<1实际上可能比16 位处理器慢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 的内容。这可以另外加快操作。

于 2010-12-07T11:23:18.590 回答
5

在某些代的 Intel CPU（P2 或 P3？不是 AMD，如果我没记错的话），位移操作非常慢。不过，位移 1 位应该总是很快，因为它只能使用加法。另一个需要考虑的问题是，恒定位数的位移是否比可变长度位移更快。即使操作码的速度相同，在 x86 上，移位的非常量右手操作数也必须占用 CL 寄存器，这对寄存器分配施加了额外的约束，并且也可能以这种方式减慢程序的速度。

于 2010-11-20T21:28:41.840 回答
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,1oradd eax,eax比 短一个字节shl eax,10，并且代码大小会直接（解码/前端瓶颈）或间接（L1I 代码缓存未命中）影响性能。

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

x在仍然需要原始值的情况下，需要复制+移位很常见。但大多数 x86 整数指令都在原地运行。add（目标是or 等​​指令的来源之一shl。）x86-64 System V 调用约定将 args 传递到寄存器中，第一个 arg inedi和返回值 in eax，因此返回的函数x<<10也会使编译器发出 copy+shift代码。

该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

在最新的 Intel 和 AMD CPU 上，具有 2 个组件的 LEA 具有 1 个周期延迟和 2 个每时钟吞吐量。（Sandybridge 系列和 Bulldozer/Ryzen）。在 Intel 上，对于lea eax, [rdi + rsi + 123]. （相关：为什么这个 C++ 代码比我用于测试 Collat​​z 猜想的手写程序集更快？详细介绍了这一点。）

无论如何，copy+shift by 10 需要单独的mov指令。在最近的许多 CPU 上，它可能是零延迟，但它仍然需要前端带宽和代码大小。（x86 的 MOV 真的可以“免费”吗？为什么我根本无法重现这个？）

还相关：如何在 x86 中仅使用 2 个连续的 leal 指令将寄存器乘以 37？.

编译器还可以自由地转换周围的代码，因此没有实际的转变，或者它与其他操作相结合。

例如if(x<<1) { }，可以使用 anand检查除高位之外的所有位。在 x86 上，您将使用test指令，例如test eax, 0x7fffffff/jz .false而不是shl eax,1 / jz. 这种优化适用于任何班次计数，它也适用于大量班次缓慢（如 Pentium 4）或不存在（某些微控制器）的机器。

许多 ISA 具有位操作指令，而不仅仅是移位。例如，PowerPC 有很多位域提取/插入指令。或者 ARM 将源操作数的移位作为任何其他指令的一部分。（所以移位/旋转指令只是 的一种特殊形式move，使用移位源。）

请记住，C 不是汇编语言。当您调整源代码以高效编译时，请始终查看优化的编译器输出。

于 2017-10-07T23:50:20.723 回答