在C++中，哪个更快？(2 * i + 1)还是(i << 1 | 1)?

Question

在C++中，哪个更快？(2 * i + 1)还是(i << 1 | 1)?

c++assemblyperformancebit-shift

8

我意识到答案可能是硬件特定的，但我想知道是否有一种更普遍的直觉我没有理解？

我问了这个问题（链接）并得到了答案，现在我想知道是否应该改变我的方法，通常使用"(i << 1|1)"而不是"(2*i + 1)"？

- M. Tibbits

4

我不确定，但它可能会转化为相同的机器指令...所以我建议选择更易读的那个。 - Jon Seigel

2

@Jon Seigel：而“可读性”意味着更清晰地表达代码的意图。你（楼主）是在乘以二再加一，还是在左移并设置最低位？ - jason

2

你正在尝试做编译器本应该做的工作。所以最好不要这样做。^^ - pinichi

我发现第一个版本阅读速度更快。第二个版本需要些思考才能明确你想要实现什么。因此，我总是会使用第一个版本，因为它最容易理解。 - Martin York

https://dev59.com/iHVC5IYBdhLWcg3wykaj - JohnMcG

8个回答

8

这只是一个关于“...它将使用LEA”所给答案的实验：
以下代码：

int main(int argc, char **argv)
{
#ifdef USE_SHIFTOR
return (argc << 1 | 1);
#else
return (2 * argc + 1);
#endif
}

使用gcc -fomit-frame-pointer -O8 -m{32|64}（对于32位或64位）编译将产生以下汇编代码：

x86，32位：

080483a0 <main>:
80483a0:    8b 44 24 04             mov    0x4(%esp),%eax
80483a4:    8d 44 00 01             lea    0x1(%eax,%eax,1),%eax
80483a8:    c3                      ret

x86，64位：

00000000004004c0 <main>:
4004c0: 8d 44 3f 01             lea    0x1(%rdi,%rdi,1),%eax
4004c4: c3                      retq

x86，64位，-DUSE_SHIFTOR:

080483a0 <main>:
80483a0:    8b 44 24 04             mov    0x4(%esp),%eax
80483a4:    01 c0                   add    %eax,%eax
80483a6:    83 c8 01                or     $0x1,%eax
80483a9:    c3                      ret

x86，32位，-DUSE_SHIFTOR:

00000000004004c0 <main>:
4004c0: 8d 04 3f                lea    (%rdi,%rdi,1),%eax
4004c3: 83 c8 01                or     $0x1,%eax
4004c6: c3                      retq

事实上，大多数情况下都会使用LEA。但是这两种情况的代码不同，原因有两个：

加法可能会溢出和回绕，而位运算如<<或|则不会。
(x + 1) == (x | 1)仅在!(x & 1)时成立，否则加法会进位到下一位。一般来说，加一只会在一半的情况下将最低位设置为1。

虽然我们（以及编译器）知道第二个必须适用，但第一个仍然是可能的。因此，编译器创建了不同的代码，因为“or版本”需要强制将位零设置为1。

- FrankH.

gcc（Ubuntu/Linaro 4.4.4-14ubuntu5）4.4.5 - FrankH.

1

很高兴看到有人确实将猜测和荒唐的假设付诸实践。但是你关于gcc为什么不优化移位版本的解释是错误的：你的第一点是无效的，对于每个x，x<<1都会以与x+x完全相同的方式进行包装。而且，一个足够新的编译器将把移位版本优化为完全相同的lea指令。 - Gunther Piez

@drhirsch: 我改正了；-) 你是对的，我已经测试过了，gcc 4.7.2在32位/64位上无论源代码的具体形式如何，都会生成相同的代码。 - FrankH.

5

任何一个稍有头脑的编译器都会将这些表达式视为等价的，并将它们编译成相同的可执行代码。

通常情况下，不必过于担心优化这些简单的算术表达式，因为编译器最擅长优化这种类型的表达式。（与许多其他情况不同，其中“聪明的编译器”可能会做正确的事情，但实际编译器却无法胜任。）

顺便说一句，在 PPC、Sparc 和 MIPS 上，这将变为相同的一对指令：移位后加上。在 ARM 上，它将缩减为单个融合移位加操作，而在 x86 上，它可能是一个单独的 LEA 操作。

- Crashworks

这个代码在x86上不能编译成单个LEA吗？ - Axel Gneiting

2

是的，在x86下，可能 LEA EAX，EAX + EAX + 1 是最快的方法。 - GJ.

4

使用-gcc命令行选项-S（未给出编译器标志）的输出：

.LCFI3:
        movl    8(%ebp), %eax
        addl    %eax, %eax
        orl     $1, %eax
        popl    %ebp
        ret

.LCFI1:
        movl    8(%ebp), %eax
        addl    %eax, %eax
        addl    $1, %eax
        popl    %ebp
        ret

我不确定哪一个是哪一个，但我认为这并不重要。

如果编译器没有进行任何优化，那么第二个可能会转换为更快的汇编指令。每个指令所需的时间完全取决于体系结构。大多数编译器将优化它们成为相同的汇编级指令。

- Jonathan Sternberg

实际上，你不能一般性地说第二个是最快的，因为有可能存在一种架构，其中加法的速度是移位的十倍（虽然不太可能，但我的观点是这取决于平台）。如果你限制自己在特定的平台上，那么这可能是正确的，但你应该在回答中明确说明。 - paxdiablo

1

记住这句谚语：没有 -O3 的基准测试就像比较 F1 赛车手在滑板上的速度一样。 - Kos

1

我刚刚使用FrankH的源代码和gcc-4.7.1进行了测试，生成的代码如下：

lea    0x1(%rdi,%rdi,1),%eax
retq

无论使用移位版本还是乘法版本。

- Gunther Piez

0

没有人在意，也不应该在意。
别再担心这个了，把你的代码写好，简单明了，然后完成它。

- Stephen Hazel

1

我们能不能少一些负面情绪，或者至少支持你的陈述，说“编译器将等效地处理这两种形式”？ - Seth Johnson

好的，好的，抱歉。如果你在意细节上的速度，也许你应该写手工汇编代码？不行吗？一般来说，在编写C++代码时，我追求正确性、简洁和完成。如果优化不是从简洁中得出的，那么你只是在恳求下一个可怜的家伙来接手这段代码并找到你然后开枪... - Stephen Hazel

0

i + i + 1 可能比其他两个更快，因为加法比乘法快，也可能比移位操作更快。

- Abyx

这个答案没有帮助，因为它是一个毫无根据的猜测，甚至没有任何分析或反汇编来支持它。它鼓励人们进行“微观优化”，而其他答案已经指出，这是错误的。 - Seth Johnson

-2

更快的是第一种形式（带有右移的那个），实际上，shr指令在最坏情况下需要4个时钟周期才能完成，而mul 10则在最好情况下。然而，最佳形式应由编译器决定，因为它可以完全了解其他（汇编）指令。

- BlackBear

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paxdiablo · Accepted Answer

由于ISO标准实际上并未强制执行性能要求，这将取决于实现、选择的编译器标志、目标CPU，并且很可能还会受到月相的影响。

这种优化（节省一些周期）在回报率方面几乎总是微不足道，而宏观级别的优化（如算法选择）则更具有意义。

首先追求代码的可读性。如果你的意图是移位和“或”，请使用移位版本。如果你的意图是进行乘法运算，使用“*”版本。只有在确定存在问题后才考虑性能。

任何一个像样的编译器都会比你更好地优化它 :-)