为何C语言函数fib2的执行速度远快于fib与fib3？

编译环境 #

• 编译命令：gcc -O3 main.c -o main
• GCC版本：

gcc (GCC) 10.2.1 20200825 (Alibaba 10.2.1-3.6 2.32)
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE

程序输出 #

102334155   fib Time spent: 0.185822 seconds
1059467309  fib2 Time spent: 0.036215 seconds  // 为什么更快？
102334155   fib3 Time spent: 0.181988 seconds

测试代码 #

#include <stdio.h>
#include <time.h>

long long fib2(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        long long first = fib2(n - 1);
        long long second = fib2(n - 2);
        return first * first + second * second;
    }
}

int fib(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return fib(n - 1) + fib(n - 2);
    }
}

long long fib3(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        long long first = fib3(n - 1);
        long long second = fib3(n - 2);
        return first + second;
    }
}

void main()
{
    clock_t start1 = clock();
    printf("%d", fib(40));
    clock_t end1 = clock();
    double time_spent1 = (double)(end1 - start1) / CLOCKS_PER_SEC;
    printf("fib Time spent: %f seconds\n", time_spent1);
    printf("%d", fib2(40));
    clock_t end2 = clock();
    double time_spent2 = (double)(end2 - end1) / CLOCKS_PER_SEC;
    printf("fib2 Time spent: %f seconds\n", time_spent2);
    printf("%d", fib3(40));
    clock_t end3 = clock();
    double time_spent3 = (double)(end3 - end2) / CLOCKS_PER_SEC;
    printf("fib3 Time spent: %f seconds\n", time_spent3);
}

原因分析 #

这三个函数都是递归实现，但fib2的执行速度远超另外两个，关键在于GCC的-O3优化对fib2的递归结构做了更高效的处理，而fib和fib3的标准斐波那契递归逻辑没法享受到同样的优化，具体细节如下：

• 递归逻辑的结构差异
  fib和fib3是标准的斐波那契递归：f(n) = f(n-1) + f(n-2)。这种结构里，计算f(n)必须分别算出f(n-1)和f(n-2)，且两者之间没有直接推导关系，编译器没法用f(n-1)的结果推导f(n-2)，导致递归调用次数是指数级的（约为O(φ^n)，φ是黄金分割比），计算fib(40)时调用次数能达到上亿次。
  而fib2的逻辑是f(n) = f(n-1)^2 + f(n-2)^2，它计算的根本不是标准斐波那契数列（从输出结果也能看出fib2(40)的数值和另外两个不同）。重点是，编译器在-O3优化时，发现fib2(n-2)的调用结果可以通过fib2(n-1)的计算过程缓存下来，或者因为乘法操作的存在，编译器对这个递归结构做了深度内联和结果缓存，直接砍掉了大量重复的递归调用。

• 优化空间的差异
  fib返回int类型，fib3返回long long，但两者递归逻辑完全一致，所以优化效果接近。而fib2的计算涉及乘法操作，编译器处理乘法时会把递归调用的结果存在寄存器中，避免了反复创建销毁栈帧，大幅降低了函数调用的开销。

• 实际调用次数的差距
  标准斐波那契递归计算n=40需要上亿次调用，而fib2因为编译器的优化，实际调用次数可能接近线性级别，这直接导致了执行时间的巨大差距。

内容的提问来源于stack exchange，提问作者zmhuang