Haskell 中的性能改进

Question

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

所以写了两个函数用莱布尼茨公式计算圆周率（不是计算圆周率，只是一个例子）：

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通过递归构造一个无限List。带有 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 解决方案快。理论上是否可以重写我的 Haskell 代码以实现与 C++ 类似的性能？

Answer 1

使用 foldl'（来自 Data.List）而不是 foldl（与延迟生成的列表相比，更喜欢该变体）
使用显式类型签名，否则你会得到 Integer。
使用优化（-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++ 的速度。然而，这种行为可能并不普遍，我们需要根据懒惰改变一些功能：

Type annotations	`foldl'`	`-O2`	Runtime [s]
yes	no	yes	0.063
yes	yes	yes	0.063
no	yes	yes	0.180
no	no	yes	0.190
yes	yes	no	0.825
no	yes	no	1.700
yes	no	no	2.477
no	no	no	3.599

Haskell 中的性能改进

Performance Improvements in Haskell

performance

haskell

lazy-evaluation