深入理解编译期计算斐波拉契数列

C++一个常见的“面试题”是使用template，模板元编程相关的特性计算斐波拉契数列。其实现是十分简单的：

#include <iostream>

template <unsigned int n>
struct Calculator
{
    static const unsigned int value = Calculator<n - 1>::value + Calculator<n - 2>::value;
};

template <>
struct Calculator<1>
{
    static const unsigned int value = 1;
};

template <>
struct Calculator<2>
{
    static const unsigned int value = 1;
};

template <unsigned int n>
const unsigned int fibonacci = Calculator<n>::value;

int main(void)
{
    std::cout << fibonacci<5> << std::endl;
}

核心是 C++ 特色的模板参数推导和匹配机制，实质带来了分支选择：编译器会优先匹配“更适合”的参数；所以我们特化了这个模板参数n取1和2的时候作为递归终点。

类似理念的应用是模板的偏特化：

#include <iostream>

template <typename T>
struct is_pointer
{
    static const bool value = false;
};

template <typename T>
struct is_pointer<T *>  // 偏特化！
{
    static const bool value = true;
};

template <>
struct is_pointer<decltype(nullptr)>
{
    static const bool value = true;
};

template <typename T>
const bool is_pointer_v = is_pointer<T>::value;

int main(void)
{
    std::cout << is_pointer_v<decltype(nullptr)> << std::endl;
    std::cout << is_pointer_v<decltype(2)> << std::endl;
    std::cout << is_pointer_v<decltype(&std::cout)> << std::endl;
}

&std::cout时C++匹配了更适合的模板参数T *，我们也因此得到value被设置为true。

当然“更合适”也只是一种合适的表述，实际上C++标准对推导机制是有严格定义的。

需要注意的是，软件工程的定律早已指出：复杂度不会消失，只会转移；在模板实例化时这种计算器实际上是把运行期的计算带来的复杂度平移到了编译期：在绝大多数时候这是值得的，因为实际上线的代码我们是使用渐进复杂度的思维审视——优化更关注增长（虽然用户体验可能带来一个新挑战：相当场景中常数时间的优化往往也值得重视）。

但是现代 C++ 的滥觞 C++11 为这种编译期计算提供了一个更好的选择：constexpr。

我们实际上是在等效地实现这样功能的代码：

int fibonacci(int n)
{
    if (n == 1 or n == 2)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

过去真正的瓶颈在于，编译器不知道这里应当挪到编译期解决，所以我们只能使用template强制编译器计算。我们审视编译器，真正强大之处是它维护着类型信息，编译过程的实质是完成构造性证明，优化的边界便是编译器拥有信息的边界；那么更自然的解决方法则是给编译器提供信息，让编译器完成编译期计算，这就是constexpr。

它建议编译器在编译期完成计算：

#include <iostream>

// 使用 constexpr 函数，可以在编译期进行计算！
constexpr int fibonacci(int n)
{
    // C++14 之后，constexpr 函数内可以写很多东西，像普通函数一样！
    if (n == 1 or n == 2)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(int argc, char *argv[])
{
    // 因为 fibonacci(10) 是一个常量表达式，
    // 编译器会直接在编译期把它算出来！
    std::cout << fibonacci(10) << std::endl; // 编译后这里直接就是 std::cout << 55 << std::endl;

    // 甚至可以用它来定义数组大小
    int arr[fibonacci(6)] = {}; // 定义一个大小为 8 的数组
    std::cout << "Array size: " << sizeof(arr) / sizeof(int) << std::endl;
}

不过问题也出在这个“建议”；正如 C++ 模板有递归深度限制一样，constexpr对于深度过深的编译期运算，或者是编译器能力不足以推导出这里是常量，会选择还是放到运行期解决。要消除这种“建议”，使用consteval关键字即可：它们都是向编译器提供信息来优化代码。

由于我的 Gemini 实在吵得严重，这里专门讲一下计算斐波拉契本身的问题。在前面使用模板元编程的例子中，每一个Calculator<n> 都是一个单独的类型，所以维护类型信息的编译器会对它们进行储存，因而不会出现重复计算子结构的情况，算法复杂度并非 $O(2^n)$ 而是 $O(n)$，因为我们实际上只需要计算从 1 到 n 的所有情况一次，而通常的 RAM 模型随机访问是常数时间。而在后面的 constexpr 的方法中，现代主流编译器实现的角度看，它们在优化等级较高下处理一个常量求值的上下文时，它们实际上会进行记忆化来避免重复劳动。所以，在实践中，constexpr int fib(10); 这样的递归调用，其编译耗时也更接近线性复杂度 O(n)，而不是指数级。

当然，C++17 之后constexpr也有类似“运算符重载的功能”——if constexpr，在编译期完成判断，直接把分支代码优化掉：

#include <iostream>
#include <type_traits>

template<typename T>
void print_info(T value) 
{
    if constexpr (std::is_pointer_v<T>) 
    {
        // 如果 T 不是指针，下面这整块代码，包括花括号，
        // 都会被编译器直接剪掉，仿佛从未存在过。
        // 所以即使 T 是 int，*value 这种语法错误也不会引发编译失败！
        std::cout << "It's a pointer to: " << *value << std::endl;
    } 
    else 
    {
        // 反之，如果 T 是指针，这块代码就会被剪掉。
        std::cout << "It's a value: " << value << std::endl;
    }
}

总的来说，就是体现 C++ 的编译期计算倾向。

当然，如果坚持可读性极差的模板元编程做计算器，或者就是单纯想尝试一些奇技淫巧，constexpr 也还是有用武之地的，制造编译期对象，这是对功能和可读性的一个极大优化：

#include <iostream>

struct Point 
{
    double x, y;

    // 施展魔法第一步：一个 constexpr 构造函数！
    // C++11 要求构造函数体必须为空，只能有初始化列表。
    // C++14 之后放宽了限制，函数体内可以有更复杂的逻辑。
    constexpr Point(double x_val, double y_val) : x(x_val), y(y_val) {}

    // 施展魔法第二步：你希望在编译期调用的成员函数，也必须是 constexpr！
    constexpr double length_sq() const 
    {
        return x * x + y * y;
    }
    
    // 施展魔法第三步（隐式）：它的析构函数必须是平凡的 (trivial)
    // 默认的析构函数就是平凡的，所以我们不用特地写出来。
    // ~Point() = default;
};

int main() 
{
    // 见证奇迹！我们在编译期创建了一个 Point 对象！
    constexpr Point p1(3.0, 4.0);
    constexpr Point p2(5.0, 12.0);

    // 在编译期调用它的成员函数，计算另一个常量
    constexpr double len_sq = p1.length_sq(); // 编译器直接算出 25.0

    // 用这个编译期计算的结果来定义一个数组
    int my_array[static_cast<int>(len_sq)]; // 创建一个大小为 25 的数组！
    std::cout << "Array size: " << std::size(my_array) << std::endl;

    // 甚至可以在编译期对这些对象进行运算
    constexpr Point p3(p1.x + p2.x, p1.y + p2.y); // p3 是 (8.0, 16.0)
    
    std::cout << "p3.x = " << p3.x << std::endl; // 这行代码在编译后，可能直接变成了 std::cout << "p3.x = " << 8.0 << std::endl;
}

总的来说，我想指出：编译器优化的进步历史像是开源节流，一方面是优化算法的进步，另外一方面则是向它提供更多的信息推移语义约束的边界。如果在 modern C++ 的视角下审视模板元编程，还是应当回到template抽象一类过程的实质做 policy-driven 的本义，用模板实现编译期计算斐波拉契数列更多是 C++11 之前一种无可奈何的举措，模板递归实例化也是模板天书的源泉。