Haskell 的性能改进

Question

我想提高编写真正高性能代码的 haskell 技能(来自 C/C++ 背景，这对我的 self 很重要 :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通过递归构造一个无限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

1. 使用 foldl'(来自 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++ 的速度。然而，这种行为通常可能不成立，我们需要根据惰性更改一些功能:

<表类="s-表"><头>类型注解折叠'-O2运行时间[s]<正文>是没有是0.063是是是0.063没有是是0.180没有没有是0.190是是没有0.825没有是没有1.700是没有没有2.477没有没有没有3.599