为什么Fibonacci序列的这些动态编程实现之一比另一个更快？

我最近为了自己的娱乐而研究和测试各种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 

在我的机器上,使用fib_dp_classic计算百万分之斐波纳契数需要6.55秒,使用fib_dp_mod计算百万分之2.83秒,甚至打开-O3也不会改变太多.关于为什么mod版本更快,我真的没有任何好主意.是因为经典版本中的额外商店说明比第二版中的mod贵吗？我的理解是编译器应该将所有三个变量放在两个版本的寄存器中,并且计算mod实际上相当昂贵; 情况并非如此吗？

实际上,我只是通过编译器资源管理器将这两者都放在一起,并且一旦你开启优化,它们都只使用寄存器.当然,这只是使用整数,而不是我实际用于基准测试的基于GMP的重点.是否有一些奇怪的GMP实施细节可能是这里的原因？

更新:我甚至试图看看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;
}


这(从格扎)也运行在2.84秒,如此反复约等同于MOD版,因为它消除了在复制方式基本相同,只是打电话swap(),而不是使用移动语义.


1> lenik..：
你的第一个函数使用了一个加法和3个副本BigInt- 所有这些都是非常耗时的操作.第二个功能使用一个加法和一个复制操作 - 这是节省的来源,你保存2个复制操作BigInt.