比较 Haskell 和 C 计算素数的速度

Question

我最初写这个(蛮力和低效的)计算素数的方法是为了确保在 Haskell 中使用“if-then-else”与守卫之间在速度上没有差异(而且没有差异! ).但后来我决定写一个 C 程序来比较，我得到了以下结果(Haskell 慢了 25% 以上):

(请注意，我从以下帖子中得到了使用 rem 而不是 mod 以及编译器调用中的 O3 选项的想法:On improving Haskell's performance compared to C in fibonacci micro-benchmark)

Haskell : Forum.hs

divisibleRec :: Int -> Int -> Bool
divisibleRec i j 
  | j == 1         = False 
  | i `rem` j == 0 = True 
  | otherwise      = divisibleRec i (j-1)

divisible::Int -> Bool
divisible i = divisibleRec i (i-1)

r = [ x | x <- [2..200000], divisible x == False]

main :: IO()
main = print(length(r))

C: main.cpp

#include <stdio.h>

bool divisibleRec(int i, int j){
  if(j==1){ return false; }
  else if(i%j==0){ return true; }
  else{ return divisibleRec(i,j-1); }
}

bool divisible(int i){ return divisibleRec(i, i-1); }

int main(void){
  int i, count =0;
  for(i=2; i<200000; ++i){
    if(divisible(i)==false){
      count = count+1;
    }
  }
  printf("number of primes = %d\n",count);
  return 0;
}

我得到的结果如下:

编译时间

time (ghc -O3 -o runProg Forum.hs)
real    0m0.355s
user    0m0.252s
sys 0m0.040s

time (gcc -O3 -o runProg main.cpp)
real    0m0.070s
user    0m0.036s
sys 0m0.008s

以及以下运行时间:

Ubuntu 32 位上的运行时间

Haskell
17984
real    0m54.498s
user    0m51.363s
sys 0m0.140s


C++
number of primes = 17984
real    0m41.739s
user    0m39.642s
sys 0m0.080s

Haskell 的运行时间给我留下了深刻的印象。但是我的问题是:我可以做任何事情来加速 haskell 程序吗:

1. 改变底层算法(很明显，通过改变算法可以获得巨大的加速；但我只是想了解我可以在语言/编译器方面做些什么来提高性能)
2. 调用 llvm 编译器(因为我没有安装它)

[编辑:内存使用情况]

在 Alan 的评论之后，我注意到 C 程序使用恒定数量的内存，而 Haskell 程序的内存大小缓慢增长。起初我认为这与递归有关，但 gspr 在下面解释了为什么会发生这种情况并提供了解决方案。 Will Ness 提供了另一种解决方案(类似于 gspr 的解决方案)，它还可以确保内存保持静态。

[编辑:更大运行的总结]

测试的最大数量:200,000:

(54.498s/41.739s) = Haskell 慢 30.5%

测试的最大数量:400,000:

3m31.372s/2m45.076s = 211.37s/165s = Haskell 慢 28.1%

测试的最大数量:800,000:

14m3.266s/11m6.024s = 843.27s/666.02s = Haskell 慢 26.6%

[编辑:Alan 的代码]

这是我之前编写的没有递归的代码，我在 200,000 上测试过:

#include <stdio.h>

bool divisibleRec(int i, int j){
  while(j>0){
    if(j==1){ return false; }
    else if(i%j==0){ return true; }
    else{ j -= 1;}
  }
}


bool divisible(int i){ return divisibleRec(i, i-1); }

int main(void){
  int i, count =0;
  for(i=2; i<8000000; ++i){
    if(divisible(i)==false){
      count = count+1;
    }
  }
  printf("number of primes = %d\n",count);
  return 0;
}

使用递归和不使用递归的 C 代码的结果如下(对于 800,000):

递归:11m6.024s

没有递归:11m5.328s

请注意，无论最大数量如何，可执行文件似乎都占用 60kb(如系统监视器中所示)，因此我怀疑编译器正在检测此递归。

Answer 1

这并不是真正回答您的问题，而是您在评论中提出的关于当数字 200000 增长时内存使用量增加的问题。

当这个数字增长时，列表 r 也会增长。您的代码在最后需要所有的 r 来计算它的长度。另一方面，C 代码只是递增一个计数器。如果你想持续使用内存，你也必须在 Haskell 中做类似的事情。代码仍然非常 Haskelly，一般来说，这是一个明智的提议:你真的不需要 divisible 为 False 的数字列表，你只需要知道有多少。

你可以试试

main :: IO ()
main = print $ foldl' (\s x -> if divisible x then s else s+1) 0 [2..200000]

(foldl' 是来自 Data.List 的更严格的 foldl，它避免了 thunk 的建立)。