c++ - 为什么斐波那契数列的这些动态编程实现中的一个比另一个更快？

Question

我最近一直在研究各种 Fibonacci 算法并对其进行基准测试以供自己娱乐，并且或多或少偶然想到了经典 O(n) 时间和 O(1) 空间动态规划实现的替代实现。

考虑以下两个函数:

BigInt fib_dp_classic(int n) {
  if (n == 0) {
    return 0;
  }

  BigInt x = 0, y = 1, z;
  for (int i = 2; i <= n; ++i) {
    z = x + y;
    x = y;
    y = z;
  }

  return y;
}

和

BigInt fib_dp_mod(int n) {
  BigInt x = 0, y = 1, z = 1;
  for (int i = 0; i < n; ++i) {
    switch (i % 3) {
      case 0:
        y = x + z;
        break;
      case 1:
        z = x + y;
        break;
      case 2:
        x = y + z;
        break;
    }
  }

  switch (n % 3) {
    case 0:
      return x;
      break;
    case 1:
      return y;
      break;
    case 2:
      return z;
      break;
  }
}

在我的机器上，使用 fib_dp_classic 计算第 100 万斐波那契数需要 6.55 秒，使用 fib_dp_mod 需要 2.83 秒，即使打开 -O3 也不会改变太多。关于为什么 mod 版本更快，我真的没有什么好主意。是因为经典版的额外商店说明比第二版的mod贵吗？据我了解，编译器应该将所有三个变量放入两个版本的寄存器中，并且计算 mod 实际上相当昂贵；不是这样吗？

其实我只是把这两个都通过了compiler explorer一旦你打开优化，两者都只使用寄存器。当然，这只是使用整数，而不是我实际用于基准测试的基于 GMP 的双整数。是否有一些奇怪的 GMP 实现细节可能是这里的原因？

更新:我什至用 strace 来查看 malloc() 是否可能是罪魁祸首，而 fib_dp_classic 使用 130 个系统调用(对于 n=1000000)，而 fib_dp_mod 使用 133 个。所以仍然没有真正的线索......

更新 2:是的，缓冲区拷贝是罪魁祸首(正如 geza 指出的那样)，我很愚蠢没有意识到。以下是两个替代版本及其基准测试结果:

BigInt fib_dp_move(int n) {
  if (n == 0) {
    return 0;
  }

  BigInt x = 0, y = 1, z;
  for (int i = 2; i <= n; ++i) {
    z = std::move(x) + y;
    x = std::move(y);
    y = std::move(z);
  }

  return y;
}

运行时间为 2.84 秒，与 mod 版本差不多，因为它消除了不必要的拷贝。

BigInt fib_dp_swap(int n) {
  if (n == 0) {
    return 0;
  }

  BigInt x = 0, y = 1, z;
  for (int i = 2; i <= n; ++i) {
    z = x + y;
    swap(x, y);
    swap(y, z);
  }

  return y;
}

这个(来自 geza)也运行了 2.84 秒，所以同样与 mod 版本相当，因为它以基本相同的方式消除了拷贝，只是调用 swap() 而不是使用移动语义.

Answer 1

您的第一个函数对 BigInt 使用了一个加法和 3 个拷贝——所有这些都是非常耗时的操作。第二个函数使用一次加法和一次复制操作——这就是节省的来源，您使用 BigInt 节省了 2 次复制操作。