3

我在玩 Haskell 的过程中休息了一段时间，现在我开始重新投入使用。我肯定还在学习这门语言。我意识到，在编写 Haskell 时总是让我感到紧张/不舒服的一件事是，我对如何制作既惯用又高效的算法没有深入的了解。我意识到“过早的优化是万恶之源”，但同样缓慢的代码最终将不得不被处理，而且我无法摆脱我对高级语言超级慢的先入为主的观念。

因此，本着这种精神，我开始使用测试用例。我正在研究的其中一个是经典的 4 阶龙格-库塔方法的简单、直接的实现，应用于相当简单的 IVP dy/dt = -y; y(0) = 1，它给出了y = e^-t. 我用 Haskell 和 C 编写了一个完全直接的实现（稍后我会发布）。Haskell 版本非常简洁，当我看到它时，它的内部给了我温暖的模糊感，但是 C 版本（实际上解析起来并不可怕）快了一倍多。

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

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

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

我到底做错了什么？我悲惨地不知道我可以用来清理哪些库函数或 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;
}
4

3 回答 3

14

使用增加大小的程序会导致堆栈溢出：

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

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

按类型划分的 Heao 个人资料

（注意：我修改了你的程序作为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% 的差异。

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

{-# 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
于 2013-09-02T18:51:27.640 回答
5

我认为为了进行公平比较，您应该排除程序初始化以及打印输出（或单独测量）。默认情况下，Haskell 使用Strings 列表，它是 s 的列表，Char这使得输出非常慢。此外，Haskell 有一个复杂的运行时，它的初始化会对这么短的任务产生很大的偏差。您可以为此使用标准库：

import Criterion.Main

-- ...

benchmarkIRK n =
    let y' t y = -y
        h      = 1e-3
        y0     = 1.0
        t0     = 0
    in take n (iterateRK y' h t0 y0)

benchmarkIRKPrint = writeFile "/dev/null" . show . benchmarkIRK

main = defaultMain
        [ bench "rk"      $ nf benchmarkIRK 1000
        , bench "rkPrint" $ nfIO (benchmarkIRKPrint 1000)
        ]

我的测量表明，实际计算大约需要27 us，计算和打印大约需要350 us，运行整个程序（没有标准）大约需要30 ms。所以实际的计算只需要整个时间的 1/1000，打印出来的时间只是 1/100。

您还应该类似地测​​量您的 C 程序，不包括任何启动时间并区分计算和打印消耗的时间部分。

于 2013-09-02T18:18:04.210 回答
1

您的程序的时间与语言的性能几乎没有关系，而一切都与终端 IO 相关。从你的 Haskell 程序中删除每个步骤的打印（顺便说一句，putStrLn . show ≡≡ print），你会得到

$ time RK-hs
1.0

real 0m0.004s
user 0m0.000s
sys 0m0.000s

......不过，这并不重要 - 1000 步太少了。和

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

你得到

$ 时间 RK-hs +RTS -K100M
0.36787944117145965

实际 0m0.653s
用户 0m0.572s
系统 0m0.076s

而C中的等价物有

$ time RK-c
分段错误（核心转储）

哦，太好了... ...但正如您所见，我还必须增加 Haskell 程序的堆栈大小。省略将结果存储在堆栈分配的数组中，我们有

$ time RK-c
0.3678794412

真实 0m0.152s
用户 0m0.148s
sys 0m0.000s

所以这确实比 Haskell 版本更快，尤其是现在。

当甚至 C 存在存储大量中间结果的内存问题时（如果你把它放在堆栈上），这在 Haskell 中更糟：每个列表节点必须单独在堆上分配，而在 Haskell 的垃圾中分配要快得多——收集堆比C的堆，它仍然慢。

于 2013-09-02T18:06:17.677 回答