Haskell与C++中的简单π(x)

Question

我正在学习Haskell.我的兴趣是将它用于个人计算机实验.现在,我正试图看看Haskell有多快.许多人声称与C(++)相同,如果这是真的,我会非常高兴(我应该注意到我将使用Haskell,无论它是否快,但快速仍然是一件好事).

我的测试程序用一个非常简单的算法实现π(x):Primes数字为结果加1.素数在1和√x之间没有整数除数.这不是算法之争,这纯粹是为了编译器性能.

Haskell似乎在我的计算机上慢了大约6倍,这很好(仍然比纯Python快100倍),但这可能只是因为我是一个Haskell新手.

现在,我的问题是:如何在不改变算法的情况下优化Haskell实现？Haskell真的与C的性能平价吗？

这是我的Haskell代码:

import System.Environment

-- a simple integer square root
isqrt :: Int -> Int
isqrt = floor . sqrt . fromIntegral

-- primality test        
prime :: Int -> Bool
prime x = null [x | q <- [3, 5..isqrt x], rem x q == 0]

main = do
  n <- fmap (read . head) getArgs
  print $ length $ filter prime (2:[3, 5..n])

这是我的C++代码:

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

bool isPrime(int);

int main(int argc, char* argv[]) {
    int primes = 10000, count = 0;
    if (argc > 1) {
        primes = atoi(argv[1]);
    }
    if (isPrime(2)) {
        count++;
    }
    for (int i = 3; i <= primes; i+=2) {
        if (isPrime(i)){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

bool isPrime(int x){
    for (int i = 2; i <= floor(sqrt(x)); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Answer 1

您的Haskell版本正在构建一个惰性列表,prime仅用于测试它是否为null.这似乎确实是瓶颈.以下版本的运行速度与我机器上的C++版本一样快:

prime :: Int -> Bool
prime x = go 3
  where
    go q | q <= isqrt x = if rem x q == 0 then False else go (q+2)
    go _  = True

使用-O2编译时为3.31s,对于C++编译为3.18s,gcc为4.8,对于n = 5000000为-O3.

当然,"猜测"程序缓慢优化它并不是一个很好的方法.幸运的是,Haskell拥有良好的分析工具.

编译和运行

$ ghc --make primes.hs -O2 -prof -auto-all -fforce-recomp && ./primes 5000000 +RTS -p

给

# primes.prof
  Thu Feb 20 00:49 2014 Time and Allocation Profiling Report  (Final)

     primes +RTS -p -RTS 5000000

  total time  =        5.71 secs   (5710 ticks @ 1000 us, 1 processor)
  total alloc = 259,580,976 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

prime.go    Main     96.4    0.0
main        Main      2.0   84.6
isqrt       Main      0.9   15.4

                                                      individual     inherited
COST CENTRE MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                     45           0    0.0    0.0   100.0  100.0
 main       Main                     91           0    2.0   84.6   100.0  100.0
  prime     Main                     92     2500000    0.7    0.0    98.0   15.4
   prime.go Main                     93   326103491   96.4    0.0    97.3   15.4
    isqrt   Main                     95           0    0.9   15.4     0.9   15.4

--- >8 ---

这清楚地表明这prime是事情变得热的地方.有关分析的更多信息,我将向您介绍真实世界Haskell,第25章.

要真正了解正在发生的事情,您可以查看(其中一个)GHC的中间语言Core,它将向您展示优化后代码的外观.一些好的信息在Haskell维基.除非必要,否则我不建议这样做,但很高兴知道存在这种可能性.

至于你的其他问题:

1)如何在不改变算法的情况下优化Haskell实现？

配置文件,并尝试编写内部循环,以便它们不进行任何内存分配,并且可以由编译器严格控制.这样做可以采取一些实践和经验.

2)Haskell真的与C的性能平价吗？

那要看.GHC非常棒,通常可以很好地优化您的程序.如果您知道自己在做什么,通常可以接近优化C的性能(100% - C的速度的200%).也就是说,这些优化对于眼睛来说并不总是容易或漂亮,而高级Haskell可能会变慢.但是不要忘记在使用Haskell时你获得了惊人的表现力和高水平的抽象.除了大多数性能关键的应用程序之外,它通常都足够快,即便如此,通过一些性能分析和性能优化,您通常可以非常接近C.