performance - Haskell 性能 : Struggling with utilizing profiling results and basic tuning techniques (eliminating explicit recursion, 等)

Question

我从玩 Haskell 中休息了很长时间，现在我开始重新投入其中。我肯定还在学习这门语言。我已经意识到，在编写 Haskell 时总是让我紧张/不舒服的一件事是，我对如何制作既惯用的算法没有很强的把握和 性能。我意识到“过早的优化是万恶之源”，但同样缓慢的代码最终必须得到处理，而且我无法摆脱我对高级语言 super 慢的先入为主的观念。

所以，在这种情况下，我开始玩测试用例。我正在研究的其中一个方法是对经典的四阶 Runge-Kutta 方法进行简单、直接的实现，应用于相当简单的 IVP dy/dt = -y; y(0) = 1 ，这给 y = e^-t .我用 Haskell 和 C 编写了一个完全直接的实现(我稍后会发布)。 Haskell 版本非常简洁，当我看到它时，它在内部给了我温暖的模糊感，但 C 版本(实际上根本不难解析)快了两倍多。

我意识到比较 2 种不同语言的性能并不是 100% 公平的；直到我们都死了，C 很可能永远是性能之王，尤其是手工优化的 C 代码。我不想让我的 Haskell 实现和我的 C 实现一样快地运行。但是我很确定，如果我更清楚自己在做什么，那么我可以从这个特定的 Haskell 实现中获得更快的速度。

Haskell 版本是用 -02 编译的在 OS X 10.8.4 上的 GHC 7.6.3 下，C 版本是用 Clang 编译的，我没有给它任何标志。使用 time 跟踪时，Haskell 版本的平均时间约为 0.016 秒，C 版本大约 0.006 秒。

这些时间考虑了二进制文件的整个运行时间，包括输出到标准输出，这显然占了一些开销，但我确实通过重新编译 -prof -auto-all 对 GHC 二进制文件进行了一些分析。并运行 +RTS -p并使用 +RTS -s 查看 GC 统计信息.我并没有真正理解我所看到的所有内容，但似乎我的 GC 并没有失控，尽管可能会受到一点控制(5%，生产力在 ~93% 用户，~85 % total elapsed)并且大部分生产时间都花在了函数 iterateRK 上。 ，当我写它的时候我知道它会很慢，但对我来说如何清理它并不是很明显。我意识到我在使用 List 时可能会受到惩罚，无论是在常量 cons 中ing 和懒惰地将结果转储到标准输出。

我到底做错了什么？不幸的是，我没有意识到我可以使用哪些库函数或 Monadic 魔法来清理 iterateRK ?有哪些学习如何成为 GHC 分析摇滚明星的好资源？

RK.hs

rk4 :: (Double -> Double -> Double) -> Double -> Double -> Double -> Double
rk4 y' h t y = y + (h/6) * (k1 + 2*k2 + 2*k3 + k4)
  where k1 = y' t y
        k2 = y' (t + h/2) (y + ((h/2) * k1))
        k3 = y' (t + h/2) (y + ((h/2) * k2))
        k4 = y' (t + h) (y + (h * k3))

iterateRK y' h t0 y0 = y0:(iterateRK y' h t1 y1)
  where t1 = t0 + h
        y1 = rk4 y' h t0 y0

main = do
  let y' t y = -y
  let h = 1e-3
  let y0 = 1.0
  let t0 = 0
  let results = iterateRK y' h t0 y0
  (putStrLn . show) (take 1000 results)

RK.c

#include<stdio.h>

#define ITERATIONS 1000

double rk4(double f(double t, double x), double h, double tn, double yn)
{
  double k1, k2, k3, k4;

  k1 = f(tn, yn);
  k2 = f((tn + h/2), yn + (h/2 * k1));
  k3 = f((tn + h/2), yn + (h/2 * k2));
  k4 = f(tn + h, yn + h * k3);

  return yn + (h/6) * (k1 + 2*k2 + 2*k3 + k4);
}

double expDot(double t, double x)
{
  return -x;
}

int main()
{
  double t0, y0, tn, yn, h, results[ITERATIONS];
  int i;

  h = 1e-3;
  y0 = 1.0;
  t0 = 0.0;
  yn = y0;

  for(i = 0; i < ITERATIONS; i++)
  {
    results[i] = yn;

    yn = rk4(expDot, h, tn, yn);
    tn += h;
  }

  for(i = 0; i < ITERATIONS; i++)
  {
    printf("%.10lf", results[i]);
    if(i != ITERATIONS - 1)
      printf(", ");
    else
      printf("\n");
  }

  return 0;
}

Answer 1

使用更大的程序会导致堆栈溢出:

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

这可能是由于过于懒惰造成的。
查看按类型分割的堆配置文件，您会得到以下信息:



(注意:我按照 leftaroundabout 指出的那样修改了你的程序)

这看起来不太好。你的算法不应该需要线性空间。您持有的 Double 值似乎比要求的时间长。使严格解决问题:

{-# LANGUAGE BangPatterns #-}

iterateRK :: (Double -> Double -> Double) -> Double -> Double -> Double -> [Double]
iterateRK y' !h !t0 !y0 = y0:(iterateRK y' h t1 y1)
  where t1 = t0 + h
        y1 = rk4 y' h t0 y0

通过此修改，新的堆配置文件如下所示:



这看起来好多了，内存使用量要低得多。 -sstderr` 也证实了我们在修改后的垃圾收集器中只花费了总时间的 2.5%:

%GC     time       2.5%  (2.9% elapsed)

现在，haskell 版本仍然比 C 版本慢 40% 左右(使用用户时间):

$ time ./tesths; time ./testc     
2.47e-321
./tesths  0,73s user 0,01s system 86% cpu 0,853 total
2.470328e-321
./testc  0,51s user 0,01s system 95% cpu 0,549 total

增加迭代次数并在 C 中使用堆分配数组存储结果再次降低了差异:

time ./tesths; time ./testc
2.47e-321
./tesths  18,25s user 0,04s system 96% cpu 19,025 total
2.470328e-321
./testc  16,98s user 0,14s system 98% cpu 17,458 total

这仅相差约 9%。

但我们仍然可以做得更好。使用 stream-fusion包，我们可以完全消除列表，同时仍然保持解耦。这是包含该优化的完整代码:

{-# LANGUAGE BangPatterns #-}
import qualified Data.List.Stream as S

rk4 :: (Double -> Double -> Double) -> Double -> Double -> Double -> Double
rk4 y' !h !t !y = y + (h/6) * (k1 + 2*k2 + 2*k3 + k4)
  where k1 = y' t y
        k2 = y' (t + h/2) (y + ((h/2) * k1))
        k3 = y' (t + h/2) (y + ((h/2) * k2))
        k4 = y' (t + h) (y + (h * k3))

iterateRK :: (Double -> Double -> Double) -> Double -> Double -> Double -> [Double]
iterateRK y' h = curry $ S.unfoldr $ \(!t0, !y0) -> Just (y0, (t0 + h, rk4 y' h t0 y0))

main :: IO ()
main = do
  let y' t y = -y
  let h = 1e-3
  let y0 = 1.0
  let t0 = 0
  let results = iterateRK y' h t0 y0
  print $ S.head $ (S.drop (pred 10000000) results)

我提出了:

$ ghc -O2 ./test.hs -o tesths -fllvm

以下是时间安排:

$ time ./tesths; time ./testc                    
2.47e-321
./tesths  15,85s user 0,02s system 97% cpu 16,200 total
2.470328e-321
./testc  16,97s user 0,18s system 97% cpu 17,538 total

现在我们甚至比 C 快一点，因为我们不做分配。为了对 C 程序进行类似的转换，我们必须将两个循环合二为一并松散漂亮的抽象。即便如此，它也只有haskell一样快:

$ time ./tesths; time ./testc
2.47e-321
./tesths  15,86s user 0,01s system 98% cpu 16,141 total
2.470328e-321
./testc  15,88s user 0,02s system 98% cpu 16,175 total