c++ - 我是否应该期望GMP的mpf_class比原始数据类型double慢得多？

Question

我正在编写一个C++程序来生成Mandelbrot集缩放。我所有的复数最初都是两个double(一个是实数部分，一个是复数部分)。这工作得很快。对于我生成的图像类型，每帧15秒。

由于缩放效果，我想为更放大的帧提高精度，因为这些帧在min_x和max_x之间具有如此小的差异。我希望GMP可以帮助我解决这个问题。

现在，它要慢得多。每帧15:38分钟。图像的设置与以前相同，算法也相同。唯一发生变化的是我使用mpf_class表示需要精确的小数(即仅是复数)。为了比较性能，我使用与double相同的精度:mpf_set_default_prec(64);
GMP是否会更改mpf_class的精度以满足表达式的需求？换句话说，如果我有两个64位mpf_class对象，并使用它们进行计算并将结果存储在另一个mpf_class中，精度是否会提高？我认为，随着时间的推移，这会破坏性能，但是我不确定这是导致我的问题的原因。

我的问题:这种性能下降仅仅是GMP和其他任意精度库的本质吗？您会提出什么建议？

编辑1
我(即一直都是)使用-O3标志进行优化。我还进行了一项测试，以验证GMP不会自动提高mpf_class对象的精度。因此，仍然存在关于性能急剧下降的原因的问题。

编辑2
作为说明示例，我将以下代码编译为g++ main.cpp -lgmp -lgmpxx，如下所示，一次，然后将每个double替换为mpf_class一次。使用double，它运行了12.75秒，而使用mpf_class，它运行了24:54分钟。当它们具有相同的精度时，为什么会这样？

#include <gmpxx.h>

double linear_map(double d, double a1, double b1, double a2, double b2) {
  double a = (d-a1)/(b1-a1);
  return (a*(b2-a2)) + (a2);
}

int iterate(double x0, double y0) {
  double x, y;
  x = 0;
  y = 0;
  int i;
  for (i = 0; i < 1000 && x*x + y*y <= 65536; i++) {
    double xtemp = x*x - y*y + x0;
    y = 2*x*y + y0;
    x = xtemp;
  }
  return i;
}

int main() {
  mpf_set_default_prec(64);
  for (int j = 0; j < 3200; j++) {
    for (int i = 0; i < 3200; i++) {
      double x = linear_map(i, 0, 3200, -2, 1);
      double y = linear_map(j, 0, 3200, -1.5, 1.5);
      iterate(x, y);
    }
  }
  return 0;
}

Answer 1

如评论中所述，完全可以从GMP之类的库中获得这种减慢效果。

内置double乘法是当今CPU和编译器最优化的 Realm 之一。 CPU具有多个执行单元，这些单元通常在编译器的帮助下设法并行执行多个浮点运算，这些编译器会尝试对循环进行自动向量化(尽管这不适用于您的情况，因为最内层的循环强烈依赖于之前的迭代)。

另一方面，在多个动态精度库(例如GMP)中，每个操作都需要大量工作-即使要检查两个操作数是否具有相同/正确的精度，也要检查多个分支，并且所实现的计算算法是通用的并针对“更高的精度”端进行了定制，这意味着它们并未针对当前用例进行特别优化(以与double相同的精度使用它们)；同样，GMP值可以在创建时确实分配内存，这是另一项昂贵的操作。

我采用了您的程序并对其进行了少许修改，以使其对要使用的类型具有参数性(使用#define)，将采样方的边减少(从3200减少到800，以使测试更快)，并添加了返回值的累加器iterate将其打印在最后，既可以检查各个版本之间的所有工作是否都以相同的方式进行，又可以确保优化程序不会完全放弃循环。

我的机器上的double版本大约需要0.16秒，然后撞到探查器中，在火焰图中显示出完全平坦的探查图；一切都发生在iterate中。



相反，GMP版本需要45秒(300倍；您谈到的速度降低了60倍，但您正在与未优化的基本情况进行比较)，并且变化更大:



和以前一样，iterate一直占用大量时间(因此就优化而言，我们可以完全忽略linear_map)。所有这些“塔”都是对GMP代码的调用； __gmp_expr<...>的东西不是特别相关-它们只是模板样板，可以在没有太多临时变量的情况下评估复杂的表达式，并且可以完全内联。大部分时间都花在那些塔的顶部，在那里进行实际的计算。

实际上，最终大部分时间都花在了GMP原语和内存分配上:



鉴于我们无法接触GMP内部，我们唯一能做的就是更加谨慎地使用它，因为每次GMP操作的确很昂贵。

确实，请务必记住，尽管编译器可以避免多次为double值计算相同的表达式，但对于GMP值却不能做到相同，因为它们都有副作用(内存分配，外部函数调用)，并且也有副作用无论如何，要对其进行检查很复杂。在您的内部循环中，我们有:

  double x, y;
  x = 0;
  y = 0;
  int i;
    for (i = 0; i < 1000 && x*x + y*y <= 65536; i++) {
      T xtemp = x*x - y*y + x0;

( T是我正在使用的通用类型，定义为 double或 mpf_class)

在此，每次迭代都要计算两次 x*x和 y*y。我们可以将其优化为:

T x = 0, y = 0, xsq, ysq;
for(i = 0; i < 1000; i++) {
  xsq = x*x;
  ysq = y*y;
  if(xsq+ysq > 65536) break;
  T xtemp = xsq - ysq + y0;

通过此修改重新运行GMP版本，我们的时间减少到38秒，提高了18％。

注意，我们将 xsq和 ysq置于循环之外，以避免在每次迭代时重新创建它们。这是因为，与 double值(最终只是寄存器空间，或者更糟的是堆栈空间，它们都是空闲的，并且由编译器静态处理)不同， mpt_class对象并非每次都可以自由地重新创建在上面的探查器跟踪中突出显示了内存分配功能；我并不完全了解GMP C++包装器的内部工作原理，但我怀疑它喜欢类似于 std::vector的优化-赋值时，已分配的值将能够在分配时回收其空间，而无需再次分配。

因此，我们甚至可以将 xtemp定义提升到循环之外

int iterate(T x0, T y0) {
  T x = 0, y = 0, xsq , ysq, xtemp;
  int i;
  for (i = 0; i < 1000; i++) {
    xsq = x*x;
    ysq = y*y;
    if(xsq+ysq > 65536) break;
    xtemp = xsq - ysq + y0;
    y = 2*x*y + y0;
    x = xtemp;
  }
  return i;
}

这将运行时间缩短至33秒，比原始时间少27％。



火焰图类似于以前的火焰图，但看起来更紧凑-我们消除了一些“插页式”浪费的时间，仅保留了计算的核心。最重要的是，查看最热门的热点，我们确实可以看到乘法在减法之间转换了位置，并且 malloc / free失去了几个位置。



从纯黑匣子的 Angular 来看，我认为这无法进一步优化。如果要进行这些计算，恐怕没有简单的方法可以使用GMP的 mpf_class更快地执行它们。此时，您应该:

删除GMP并使用其他一些库，在固定大小的情况下具有更好的性能；我怀疑这里会有收获-即使只是避免完全分配并内联计算也是一个大胜利；

开始应用一些algorithmic optimizations；无论您最终决定使用哪种数据类型，这些都将大大缩短运行时间。

注释

完整代码(在各种迭代中)可以在https://bitbucket.org/mitalia/mandelbrot_gmp_test/上找到

在我的i7-6700上运行的64位Linux上，使用优化级别为-O3的g++ 7.3完成的所有测试
使用linux-tools 4.15中的perf record执行

分析，并带有调用堆栈捕获功能； KDAB Hotspot 1.1.0

生成的图形和表格