哪个更快:x << 1或x << 10?

我不想优化任何东西,我发誓,我只是想出于好奇而问这个问题。 我知道在大多数硬件上都有一个位移的汇编命令(例如shlshr ),这是一个单一的命令。 但是,这有什么重要的(纳秒级或CPU-tact-wise)你转移了多less位。 换句话说,在任何一个CPU上,以下哪一项更快?

 x << 1; 

 x << 10; 

请不要讨厌我这个问题。 🙂

可能取决于CPU。

然而,所有现代CPU(x86,ARM)都使用“桶式移位器” – 专门devise用于在任意时间执行任意移位的硬件模块。

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

一些embedded式处理器只有一个“移位”指令。 在这样的处理器上,编译器会把x << 3变成((x << 1) << 1) << 1

我认为摩托罗拉MC68HCxx是这个限制更受欢迎的家庭之一。 幸运的是,这样的体系结构现在非常罕见,现在大多数都包含一个可变移位大小的桶式移位器。

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

有很多这样的情况。

  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的有效位数,并优化进一步的操作来缩小宽度,比如用16×8乘以16×8乘(因为低位字节总是为零)。

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

在ARM上,这可以作为另一条指令的副作用来完成。 所以潜在的是,这两者都没有延迟。

这是我最喜欢的CPU ,其中x<<2长度是x<<1两倍

这取决于CPU和编译器。 即使底层CPU具有桶式移位器的任意位移,只有编译器利用该资源才会发生这种情况。

请记住,在C和C ++中,移动数据位宽以外的任何内容都是“未定义的行为”。 签名数据的右移也是“实现定义”。 不要太在意速度,关心你在不同的实现上得到同样的答案。

从ANSI C第3.3.7节引用:

3.3.7按位移位运算符

句法

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

约束

每个操作数应具有整数types。

语义

积分促销在每个操作数上执行。 结果的types是升级的左操作数的types。 如果右操作数的值为负值或大于或等于提升的左操作数的位宽,则行为是不确定的。

E1 << E2的结果是E1左移E2位的位置; 空位被零填充。 如果E1是无符号types,则结果的值是E1乘以数量,2增加到E2,如果E1的types是unsigned long,则模ULONG_MAX + 1,否则UINT_MAX + 1。 (常量ULONG_MAX和UINT_MAX在标题中定义。)

E1 >> E2的结果是E1右移E2位的位置。 如果E1具有无符号types,或者如果E1具有带符号types和非负值,则结果的值是E1除以数量的商的整数部分,2提高到E2。 如果E1有签名types和负值,则结果值是实现定义的。

所以:

 x = y << z; 

“<<”:y×2 z (如果发生溢出则不确定 );

 x = y >> z; 

“>>”: 实现 – 为有符号定义 (通常是算术移位的结果:y / 2 z )。

可以想象的是,在一个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的结果不依赖于字节1的内容。 这可以加速操作。

在几代英特尔处理器(P2或P3?不是AMD,但是如果我没有记错的话),移位操作是非常慢的。 1位Bitshift应该总是很快,因为它可以使用加法。 另一个需要考虑的问题是,移位数是否等于可变长度移位。 即使操作码速度相同,在x86上,bitshift的非常量右侧操作数也必须占用CL寄存器,这对寄存器分配施加了额外的限制,并且也可能会使程序减慢。

像往常一样,它取决于周围的代码上下文 :例如,你使用x<<1作为数组索引? 或者把它添加到其他东西? 在这两种情况下,小的移位计数(1或2)通常可以优化,甚至比编译器不得不刚刚移位更多。 更不用说整体吞吐量与延迟与前端瓶颈的权衡。 一个小碎片的性能不是一维的。

硬件移位指令不是编译器唯一的编译x<<1选项,但其他的答案大都是假设的。


x << 1对于无符号和2的补码有符号整数完全等价于x+x 。 编译人员在编译时总是知道他们的硬件是什么,所以他们可以利用这样的技巧。

在Intel Haswell上 ,每个时钟吞吐量add 4个,但即时计数的shl只有每时钟吞吐量2个。 (请参阅http://agner.org/optimize/获取指令表,以及x86标签wiki中的其他链接)。; SIMDvector移位是每个时钟1(Skylake中为2),但SIMDvector整数加起来是每个时钟2(Skylake中为3)。 等待时间是一样的,但是:1个周期。

还有一个shl特殊的shift-by-one编码,其中count在操作码中是隐含的。 8086没有立即转换,只有一对一和一对一的登记。 这主要与右移相关,因为除非要移动内存操作数,否则只需添加左移即可。 但是如果稍后需要该值,则最好首先加载到寄存器中。 但无论如何, shl eax,1add eax,eaxshl eax,10短一个字节,并且代码大小可以直接(解码/前端瓶颈)或间接(L1I代码caching未命中)影响性能。

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


在需要x的原始值的情况下,需要复制+移位是常见的。 但大多数x86整数指令在原地运行。 (目标是addshl等指令的来源之一)。x86-64 System V调用约定传递寄存器中的args, edi的第一个arg和eax返回值,所以返回x<<10的函数也使编译器发出copy + shift代码。

LEA指令允许您移位和添加 (移位计数为0到3,因为它使用寻址模式机器编码)。 它把结果放在一个单独的寄存器中。

gcc和clang都以同样的方式优化这些函数,就像你在Godbolt编译器的资源pipe理器中看到的那样 :

 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 

具有2个组件的LEA在最近的Intel和AMD CPU上具有1个周期的延迟和2个每时钟的吞吐量。 (桑迪布里奇家族和推土机/ Ryzen)。 在英特尔,每秒时钟吞吐量只有1次,而lea eax, [rdi + rsi + 123]延迟为3c。 (相关: 为什么这个C ++代码比我手写的用于testingCollat​​z猜想的程序集更快? )

无论如何,copy + shift 10需要一个单独的mov指令。 许多最近的CPU可能是零延迟,但仍然需要前端带宽和代码大小。 ( x86的MOV真的可以“免费”吗?为什么我不能重现这一点? )

还有相关: 如何在x86中使用两个连续的leal指令乘以一个寄存器? 。


编译器也可以自由地转换周围的代码,所以没有实际的转换,或者与其他操作相结合

例如, if(x<<1) { }可以使用an and来检查除高位以外的所有位。 在x86上,您将使用test指令,如test eax, 0x7fffffff / jz .false而不是shl eax,1 / jz 。 这种优化适用于任何移位计数,并且也适用于大计数移位较慢(如奔腾4)或不存在(某些微控制器)的机器。

许多ISA都有位操作指令,而不仅仅是移位。 例如PowerPC有很多位字段提取/插入指令。 或者ARM将源操作数转换为任何其他指令的一部分。 (所以移位/旋转指令只是一种特殊的move ,使用一个移位源。)

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

    Interesting Posts