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

Question

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

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

现在慢多了； 15:38 每帧分钟。图像的设置与以前相同，算法也相同。唯一改变的是我使用 mpf_class 作为需要精确的小数（即只是复数）。为了比较性能，我使用了与双精度相同的精度：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 和编译器最优化的领域之一； CPU 有多个执行单元，它们设法并行执行多个浮点运算，通常由编译器提供帮助，编译器会尝试自动向量化循环（尽管这并不特别适用于您的情况，因为您的最内层循环强烈依赖于上一次迭代）。

另一方面，在诸如 GMP 之类的多个动态精度库中，每个操作都需要大量工作 - 有多个 b运行ches 需要检查，甚至只是检查两个 ope运行ds 具有 same/right 的精度，并且实现的计算算法是通用的并且针对 "higher precision" 端量身定制，这意味着它们没有针对您当前的用例进行特别优化（将它们与相同的使用精度为 double);此外，GMP 值可以并且确实在创建时分配内存，这是另一个代价高昂的操作。

我对你的程序稍作修改，使其在要使用的类型上参数化（使用 #define），减少采样正方形的边（从 3200 到 800，以加快测试速度）并添加 iterate 的 return 值的累加器以在最后打印它，既检查各种版本之间的一切是否以相同的方式工作，并确保优化器不会完全放弃循环。

我机器上的 double 版本大约需要 0.16 秒，并且运行进入分析器，在火焰图中显示出完全平坦的轮廓；一切都发生在 iterate.

GMP 版本正如预期的那样需要 45 秒（300 倍；您谈到了 60 倍的减速，但您是在与未优化的基本情况进行比较）并且更加多样化：

和以前一样，iterate 几乎占用了整个时间（因此就优化而言，我们可以完全忽略 linear_map）。所有这些 "towers" 都是对 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 值（最终只是寄存器 space 或更糟的是堆栈 space 不同，它们都是免费的并由编译器静态处理），mpt_class 对象不是每次都可以自由地重新创建，正如上面的分析器跟踪中内存分配函数的突出所暗示的那样；我并不完全了解 GMP C++ 包装器的内部工作原理，但我怀疑它享有类似于 std::vector 的优化 - 在分配时，已经分配的值将能够在分配时回收其 space而不是再次分配。

因此，我们甚至可以将 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%。

火焰图与之前的类似，但看起来更紧凑 - 我们已经去掉了一些 "interstitial" 时间浪费，只留下计算的核心部分。最重要的是，查看热门热点，我们确实可以看到乘法和减法交换了位置，malloc/free失去了几个位置。

我认为从纯黑盒的角度来看，这不能再优化了。如果这些是要做的计算，我担心没有简单的方法可以使用 GMP 的 mpf_class 更快地执行它们。此时你应该：

放弃 GMP 并使用其他一些库，对于固定大小的情况具有更好的性能；我怀疑这里有一些收获——即使只是避免完全分配和内联计算也是一个巨大的胜利；
开始应用一些 algorithmic optimizations；无论您最终决定使用何种数据类型，这些都将显着缩短运行时间。

备注

可以在 https://bitbucket.org/mitalia/mandelbrot_gmp_test/
所有测试均使用 g++ 7.3 完成，优化级别为 -O3，64 位 Linux 运行ning 在我的 i7-6700
使用 linux-tools 4.15 中的 perf record 和调用堆栈捕获进行分析； KDAB Hotspot 1.1.0

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

Should I expect GMP's mpf_class to be much slower than the primitive data type double?

c++

performance

gmp