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

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,但运行速度一直较慢.

题

为什么会出现这种时差？不仅仅是,而且为什么我的加法/减法方法与我的预期相反？

Answer 1

为什么会出现这种时差？

使用优化编译时(在最近版本的gcc和clang下)没有时间差异.例如,gcc 8.1 for x86_64将两者编译为:

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

不仅仅是,而且为什么我的加法/减法方法与我的预期相反？

加法和减法可能比移动慢.但是,在大多数体系结构(例如x86 CPU)中,它基本相同(1个周期加上内存延迟); 所以这并不能解释它.

真正的问题很可能是数据之间的依赖关系.看到:

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

要计算第二行,您必须完成计算第一行的值.如果编译器按原样使用表达式(在下面就是这种情况-O0),那就是CPU将看到的内容.

但是,在你的第二个例子中:

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

您既可以同时计算新的a,也可以同时计算b,因为它们不相互依赖.而且,在现代处理器中,这些操作实际上可以并行计算.或者,换句话说,你不是通过让处理器等待先前的结果来"停止"处理器.这称为指令级并行.