各种代码的常数 benchmark

测试环境：duck.ac

运行时间以 ms 为单位，保留两位小数。

若运行时长差异较大，则跑 $10$ 次取平均处理，并标注（*）。

EP.1 函数递归

用于测试的写法：

1. 普通函数递归（代码中的 plain_dfs）
2. lambda 递归（传入 auto self，代码中的 lambda_rec1）
3. lambda 递归（传入 auto &&self，代码中的 lambda_rec2）
4. std::function 递归（代码中的 func_rec）

测试方式：

跑 $n:=41$ 的暴力斐波那契。

代码如下：

#include <functional>
#include <iostream>

namespace {
volatile int n;
inline void func_rec() {
  std::function<int(int)> dfs = [&](int x) {
    if (x <= 2)
      return 1;
    return dfs(x - 1) + dfs(x - 2);
  };
  std::cout << dfs(n) << '\n';
}
inline void lambda_rec1() {
  auto dfs = [](auto dfs, int x) -> int {
    if (x <= 2)
      return 1;
    return dfs(dfs, x - 1) + dfs(dfs, x - 2);
  };
  std::cout << dfs(dfs, n) << '\n';
}
inline void lambda_rec2() {
  auto dfs = [](auto &&dfs, int x) -> int {
    if (x <= 2)
      return 1;
    return dfs(dfs, x - 1) + dfs(dfs, x - 2);
  };
  std::cout << dfs(dfs, n) << '\n';
}
int plain_dfs(int x) {
  if (x <= 2)
    return 1;
  return plain_dfs(x - 1) + plain_dfs(x - 2);
}
inline void Main() {
  n = 41;

  std::cout << plain_dfs(n) << '\n'; // (1)
  // lambda_rec1(); // (2)
  // lambda_rec2(); // (3)
  // func_rec(); // (4)
}
} // namespace

signed main() { return Main(), 0; }

测试结果：

1. 275.82 ms
2. 241.31 ms
3. 286.23 ms（*）
4. 637.27 ms

可以看到，std::function 巨慢无比，请慎用。

EP.2 gcd

用于测试的写法：

1. std::__gcd
2. std::gcd
3. platelet 集训队论文中的写法
4. 朴素手写递归 (euclid)

测试代码：

#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

namespace {
using uint = unsigned int;
std::mt19937 rnd(12345);
std::vector<std::pair<int, int>> todo(5e6);
inline void init() {
  for (auto &[u, v] : todo)
    u = rnd() & 0x7fffffff, v = rnd() & 0x7fffffff;
}

inline void plain_enumerate() { // 对照组
  volatile int chksum = 0;
  for (auto &[u, v] : todo)
    chksum ^= u ^ v;
  std::cout << chksum << '\n';
}

inline void std_gcd1() {
  volatile int chksum = 0;
  for (auto &[u, v] : todo)
    chksum ^= std::__gcd(u, v);
  std::cout << chksum << '\n';
}

inline void std_gcd2() {
  volatile int chksum = 0;
  for (auto &[u, v] : todo)
    chksum ^= std::gcd(u, v);
  std::cout << chksum << '\n';
}

namespace fast_gcd_impl {
inline int fast_gcd(int a, int b) {
  if (__builtin_expect(a == 0, 0))
    return b;
  if (__builtin_expect(b == 0, 0))
    return a;
  int az = __builtin_ctz(a);
  int bz = __builtin_ctz(b);
  int shift = std::min(az, bz);
  b >>= bz;

  while (a != 0) {
    a >>= az;
    int diff = b - a;
    az = __builtin_ctz(diff);
    b = std::min(a, b);
    a = std::abs(diff);
  }

  return b << shift;
}
} // namespace fast_gcd_impl
inline void stein_gcd_optimized() {
  volatile int chksum = 0;
  for (auto &[u, v] : todo)
    chksum ^= fast_gcd_impl::fast_gcd(u, v);
  std::cout << chksum << '\n';
}

namespace slow_gcd_impl {
inline int slow_gcd(int x, int y) { return !y ? x : slow_gcd(y, x % y); }
} // namespace slow_gcd_impl
void plain_gcd() {
  volatile int chksum = 0;
  for (auto &[u, v] : todo)
    chksum ^= slow_gcd_impl::slow_gcd(u, v);
  std::cout << chksum << '\n';
}

inline void Main() {
  init();
  std::cout << 1. * clock() / CLOCKS_PER_SEC << '\n';
  plain_enumerate(); // (0)
  // std_gcd1(); // (1)
  // std_gcd2(); // (2)
  // stein_gcd_optimized(); // (3)
  // plain_gcd(); // (4)
}
} // namespace

signed main() { return Main(), 0; }

测试结果：

比较复杂。

在基本上所有的测试中，stein_gcd_optimized (3) 表现都最为优秀。

由于编译器会自动优化尾递归，plain_gcd (4) 和 std_gcd1 (1) 的速度大致相近。

但是 std_gcd1 (1) 和 std_gcd2 (2) 哪个快呢？在不同的机子上得出了不同的结果。

考场的编译器是 gcc 9.3.0，其 std::gcd 是 euclid 实现的，故与 std::__gcd 效率相近。

新版编译器的 std::gcd 改用了 stein 实现，理论效率高于 euclid；但是实际测试结果却不尽如人意。

本地（Homebrew GCC 14.2.0, Intel(R) Core(TM) i5-5350U CPU @ 1.80GHz, 编译选项 -std=c++17 -Ofast）上，std_gcd2 (2) 用时（0.65s）大约是 std_gcd1 (1)（0.86s）的 $75.6\%$；但是 quick-bench 测出来 则是 std_gcd1 更快。

如果继续开大数据范围，std_gcd2 (2) 在 quick-bench 上展现出了 微弱的性能优势，但是远远不如本地机子上的优势显著，原因未知。

在另一台电脑上测了也是 std_gcd2 (2) 更快，测试细节先咕了。

特别地，斐波那契数列上 std_gcd2 (2) 完爆 std_gcd1 (1)。

结论：如果确实追求性能请选用 (3)；否则看自己喜好吧。