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

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计算百万分之斐波纳契数需要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(),而不是使用移动语义.

Answer 1

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

Answer 2

在这种情况下，将 GMP 版本与 simple int 版本进行比较是没有意义的。Fib(1000000) 是一个约 86KB 的数字，它比简单的int. 对于ints来说，在某些情况下复制基本上可以是自由操作，而对于GMP号码来说，则涉及到86KB缓冲区的复制。

（当然，请注意，副本不会总是 86KB。一开始，它是 ~0KB，但随着例程的进行，它会增长到 86KB。并且随着数字的增长，例程变得越来越慢，所以大部分时间都花在数字很大的时候）

假设实现质量良好BigInt，我们在每次迭代中都有以下操作计数：

• fib_dp_classic：1 个添加，2 个副本
• fib_dp_mod：1 添加

正如您所看到的，经典版本有 2 个额外的副本（注意，在高质量实现中，x=y+z不涉及副本）。并且复制的速度与添加的速度具有相同的数量级（我的意思是，添加可能比复制慢 2-3 倍）。因此，这解释了经典例程减速约 2.3 倍的原因。

请注意，如果BigInt是使用引用计数的实现，则x=y操作基本上可以是自由操作，因为它不需要副本，只需递增计数器（在这种情况下，经典例程将具有与模式一）。

最后注意：如果非复制swap操作可用，您可能可以加快经典版本的速度：

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;
    x.swap(y); // Note the 2 swaps here
    y.swap(z);
  }

  return y;
}

使用gmpxx，这个例程与mod版本同时运行，并且简单得多。

这是因为swap操作比副本便宜得多。Swap 只需要交换内部的指针BigInt，而副本则需要约 86KB 的内存副本。