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

Why is one of these dynamic programming implementations of the Fibonacci sequence faster than the other?

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

考虑以下两个函数:

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 实施细节可能是这里的原因?

更新:我什至都跟踪查看 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() 而不是使用 move语义。

您的第一个函数使用一个加法和 3 个副本 BigInt -- 所有这些都是非常耗时的操作。第二个函数使用一次加法和一次复制操作——这就是节省的来源,您使用 BigInt.

节省了 2 次复制操作

这是经典中数据依赖的情况,每次迭代需要两个周期,因为

z = x + y;
x = y; // depends on y from previous loop.
y = z; // depends on z

在 mod 的情况下,每次迭代仅依赖于前一次迭代,因此它可以在每个循环中执行一次。

此外,%3 并不是真正的 modulo 3,而是一些使它成为简单操作的编译器魔法。事实上,你可以通过编写

来适当地优化它
  for (int i = 0; i < n; i+=3) {
      y = x + z;
      z = x + y;
      x = y + z;
    }
  }

额外计算的成本将节省在额外的控制逻辑中。

在这种情况下,没有必要将 GMP 版本与简单的 int 版本进行比较。 Fib(1000000) 是一个 ~86KB 的数字,它比简单的 int 很多 。对于ints,一个副本在一定情况下基本可以自由操作,而对于GMP号,则涉及到一个86KB buffer的副本。

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

假设质量 BigInt 实施,我们在每次迭代中都有这些操作计数:

  • fib_dp_classic:1个添加,2个拷贝
  • fib_dp_mod: 1 加

如您所见,经典版本多了 2 个副本(请注意,在质量实现中,x=y+z 不涉及副本)。并且副本的速度与添加的速度具有相同的数量级(我的意思是,添加可能比副本慢 2 到 3 倍)。所以这解释了经典例程的 ~2.3 倍减速。

请注意,如果 BigInt 将是一个使用引用计数的实现,那么 x=y 操作基本上可以是一个自由操作,因为它不需要副本,只需递增一个计数器(在这种情况下,经典例程的速度与 mod 相同)。

最后说明:估计可以加速经典版,如果非复制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 内存副本。