8

我意识到答案可能是特定于硬件的，但我很好奇我是否缺少更一般的直觉？

我问了这个问题并给出了答案，现在我想知道我是否应该改变我的方法以使用“（i << 1 | 1）”而不是“（2 * i + 1）”？

4

8 回答 8

13

由于 ISO 标准实际上并没有强制要求性能要求，这将取决于实现、选择的编译器标志、目标 CPU 以及很可能的月相。

与算法选择等宏观层面的优化相比，这类优化（节省几个周期）在投资回报方面几乎总是微不足道。

首要目标是代码的可读性。如果您的意图是移位 和OR，请使用移位版本。如果您的意图是成倍增加，请使用该*版本。一旦确定存在问题，只需担心性能。

任何体面的编译器都会比你优化得更好:-)

于 2010-12-07T04:50:20.797 回答
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 位）编译成以下汇编代码：

  1. x86，32位：
    080483a0 <主>:
80483a0: 8b 44 24 04 移动 0x4(%esp),%eax
80483a4: 8d 44 00 01 lea 0x1(%eax,%eax,1),%eax
80483a8：c3 雷特
  2. x86、64位：
    00000000004004c0 <主>：
4004c0: 8d 44 3f 01 lea 0x1(%rdi,%rdi,1),%eax
4004c4：c3 retq
  3. x86，64位，-DUSE_SHIFTOR：
    080483a0 <主>:
80483a0: 8b 44 24 04 移动 0x4(%esp),%eax
80483a4: 01 c0 添加 %eax,%eax
80483a6: 83 c8 01 或 $0x1,%eax
80483a9: c3 雷特
  4. x86, 32 位, -DUSE_SHIFTOR:
    00000000004004c0 <主>：
4004c0: 8d 04 3f lea (%rdi,%rdi,1),%eax
4004c3: 83 c8 01 或 $0x1,%eax
4004c6：c3 retq

事实上，大多数情况下确实会使用LEA. 然而，这两种情况的代码并不相同。有两个原因：

  1. 加法可以溢出和回绕，而位操作喜欢<<或|不能
  2. (x + 1) == (x | 1)!(x & 1)只有当加法延续到下一位时才为真。一般来说，加一只会导致在一半的情况下设置最低位。

虽然我们（和编译器，可能）知道第二个必然适用，但第一个仍然是可能的。因此，编译器会创建不同的代码，因为“or-version”需要将位 0 ​​强制为 1。

于 2010-12-07T16:14:15.823 回答
5

除了最脑残的编译器之外的任何编译器都会将这些表达式视为等效的并将它们编译为相同的可执行代码。

通常情况下，优化这些简单的算术表达式并不值得过多担心，因为这是编译器最擅长优化的事情。（与“智能编译器”可以做正确事情的许多其他情况不同，但实际的编译器却失败了。）

顺便说一句，这将适用于 PPC、Sparc 和 MIPS 上的同一对指令：移位后加。在 ARM 上，它会简化为一条融合的移位加法指令，而在 x86 上，它可能是一个单一的LEA操作。

于 2010-12-07T04:48:27.197 回答
4

带有 -S 选项的 gcc 输出（没有给出编译器标志）：

.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

我不确定哪个是哪个，但我不相信这很重要。

如果编译器根本不进行优化，那么第二个可能会转化为更快的汇编指令。每条指令需要多长时间完全取决于架构。大多数编译器会将它们优化为相同的汇编级指令。

于 2010-12-07T04:54:12.610 回答
1

我刚刚使用FrankH的源代码用gcc-4.7.1测试了这个，生成的代码是

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

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

于 2012-08-19T10:27:04.270 回答
0

没人在乎。他们也不应该。
不必为此担心，让您的代码正确、简单并完成。

于 2010-12-07T06:02:09.537 回答
0

i + i + 1可能比其他两个快，因为加法比乘法快，而且比移位快。

于 2010-12-07T11:18:29.857 回答
-2

更快的是第一种形式（右移的形式），实际上 shr 指令在最坏的情况下需要 4 个时钟周期才能完成，而 mul 在最好的情况下需要 10 个时钟周期。但是，最好的形式应该由编译器决定，因为它可以完整地查看其他（汇编）指令。

于 2010-12-07T14:11:19.283 回答