为什么使用第三个变量比加法技巧更快？

Question

计算斐波那契数列时，常用的方法是将一对数(a, b)多次映射到(b, a + b)。这通常可以通过定义第三个变量 c 并进行交换来完成。但是，我意识到您可以执行以下操作，避免使用第三个整数变量：

b = a + b;  // b2 = a1 + b1
a = b - a;  // a2 = b2 - a1 = b1, Ta-da!

我预计这会比使用第三个变量更快，因为在我看来，这种新方法应该只需要考虑两个内存位置。

所以我写了下面的C程序比较进程。这些模拟斐波那契数的计算，但请放心，我知道由于大小限制，它们不会计算出正确的值。

（注意：我现在意识到没必要把n改成long int，但我会保持原样，因为我最初就是这样编译的）

文件：PlusMinus.c

// Using the 'b=a+b;a=b-a;' method.
#include <stdio.h>

int main() {
    long int n = 1000000; // Number of iterations.
    long int a,b;

    a = 0; b = 1;
    while (n--) {
        b = a + b;
        a = b - a;
    }

    printf("%lu\n", a);
}

文件：ThirdVar.c

// Using the third-variable method.
#include <stdio.h>

int main() {
    long int n = 1000000; // Number of iterations.
    long int a,b,c;

    a = 0; b = 1;
    while (n--) {
        c = a;
        a = b;
        b = b + c;
    }

    printf("%lu\n", a);
}

当我运行两者使用 GCC（未启用优化）时，我注意到速度上存在一致的差异：

$ time ./PlusMinus
14197223477820724411

real    0m0.014s
user    0m0.009s
sys     0m0.002s

$ time ./ThirdVar
14197223477820724411

real    0m0.012s
user    0m0.008s
sys     0m0.002s

当我运行两个 GCC 和 -O3 时，汇编输出是相等的。（我怀疑我在之前的编辑中说一个人的表现优于另一个人时有确认偏差。）

检查每个程序集，我发现 PlusMinus.s 实际上比 ThirdVar.s 少了一条指令，但运行始终较慢。

问题

为什么会出现这个时差？不仅完全没有，而且为什么我的 addition/subtraction 方法比我的预期更慢？

Answer 1

Why does this time difference occur?

优化编译时没有时间差（在最新版本的gcc和clang下）。例如，x86_64 的 gcc 8.1 编译为：

Live at Godbolt

.LC0:
        .string "%lu\n"
main:
        sub     rsp, 8
        mov     eax, 1000000
        mov     esi, 1
        mov     edx, 0
        jmp     .L2
.L3:
        mov     rsi, rcx
.L2:
        lea     rcx, [rdx+rsi]
        mov     rdx, rsi
        sub     rax, 1
        jne     .L3
        mov     edi, OFFSET FLAT:.LC0
        mov     eax, 0
        call    printf
        mov     eax, 0
        add     rsp, 8
        ret

Not only at all, but also why is my addition/subtraction method slower contrary to my expectations?

加减可能比移动慢。然而，在大多数架构中（例如 x86 CPU），它基本上是相同的（1 个周期加上内存延迟）；所以这并不能解释它。

真正的问题很可能是数据之间的依赖关系。参见：

b = a + b;
a = b - a;

要计算第二行，您必须计算完第一行的值。如果编译器按原样使用表达式（在 -O0 下就是这种情况），那就是 CPU 会看到的。

然而，在您的第二个示例中：

c = a;
a = b;
b = b + c;

您可以同时计算新的 a 和 b，因为它们不相互依赖。而且，在现代处理器中，这些操作实际上可以并行计算。或者，换句话说，您不是 "stopping" 处理器，而是让它等待先前的结果。这叫做Instruction-level parallelism.

为什么使用第三个变量比加法技巧更快？

Why is using a third variable faster than an addition trick?

c

optimization

fibonacci

文件：PlusMinus.c

文件：ThirdVar.c

问题