Haskell 中的性能改进

Question

我想提高我编写真正高性能代码的 Haskell 技能（来自 C/C++ 背景，这对我的自我很重要：D）。

所以我写了两个函数来通过莱布尼茨公式计算 Pi（它不是关于计算 pi，它只是一个例子）：

calcPiStep k = (if even k then 4.0 else -4.0) / (2.0*fromIntegral k + 1.0)
calcPiN n = foldl (\p x -> p + calcPiStep x) 0.0 [0..n]
calcPiInf = toinf [0..] 0
    where
        toinf = \(x:xs) l -> do 
            let curr = l + calcPiStep x
            curr:toinf xs curr

calcPiInf 通过递归构造一个无限列表。带有 foldl 的 calcPiN 和带有 n 次迭代的 lambda。

我发现 calcPiInf 比 calcPiN 快，并且不会因为数字太大而导致堆栈溢出。 第一个问题：这仅仅是因为懒惰的评估吗？

其次我写了一个相应的C++程序：

using namespace std;
double calcPi(int n){
    double pi = 0;
    for(size_t i = 0; i < n; i++){
        pi += 4.0*(i%2 == 0?1:-1)/(2.0*i + 1.0);
    }
    return pi;
}
int main(){
    std::cout.precision(10);
    cout << calcPi(5000000) << endl;
}

这是远远快于我的哈斯克尔解决方案。理论上是否可以重写我的 Haskell 代码以获得与 C++ 类似的性能？

Answer 1

1. 使用foldl'(from Data.List) 而不是foldl(并且与懒惰生成的列表相比更喜欢该变体)
2. 使用显式类型签名，否则最终会使用Integer.
3. 使用优化 ( -O2)

以下代码在我的系统上需要大约 3.599 秒（GHC 8.0.2，无优化）

calcPiStep k = (if even k then 4.0 else -4.0) / (2.0*fromIntegral k + 1.0)
calcPiN n = foldl (\p x -> p + calcPiStep x) 0.0 [0..n]

main = print $ calcPiN 5000000

使用foldl'而不是foldl产生约 1.7 秒（仅原始时间的约 40%）。

import Data.List
calcPiStep k = (if even k then 4.0 else -4.0) / (2.0*fromIntegral k + 1.0)
calcPiN n = foldl' (\p x -> p + calcPiStep x) 0.0 [0..n]

main = print $ calcPiN 5000000

使用类型签名产生约 0.8 秒，或另外 50% 的减少。如果我们现在添加优化，我们最终会得到0.066s，它仍然是 C++ 变体的两倍（在我的机器上使用-O3,gcc 为0.033s ），但几乎是这样。

请注意，我们也可以-O2立即使用以低于一秒，但是在-O2经常添加之前（但不一定！）的任何改进也会导致之后的改进。

这里的所有时间都取决于是否使用了类型签名foldl'或优化标志。请注意，类型签名 与-O2已经使我们接近 C++ 的速度。然而，这种行为可能并不普遍，我们需要根据懒惰改变一些函数：

类型注释	foldl'	-O2	运行时 [s]
是的	不	是的	0.063
是的	是的	是的	0.063
不	是的	是的	0.180
不	不	是的	0.190
是的	是的	不	0.825
不	是的	不	1.700
是的	不	不	2.477
不	不	不	3.599