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

问：

我最初写了这种（蛮力和低效）计算素数的方法，目的是确保在 Haskell 中使用“if-then-else”与保护在速度上没有区别（而且没有区别！但后来我决定写一个 C 程序来比较，我得到了以下内容（Haskell 慢了 25% 多一点）：

（请注意，我从以下帖子中得到了使用 rem 而不是 mod 的想法，以及编译器调用中的 O3 选项：关于在斐波那契微基准测试中与 C 相比提高 Haskell 的性能)

Haskell：论坛.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：

3 分 31.372 秒/2 分 45.076 秒 = 211.37 秒/165 秒 = Haskell 慢 28.1%

最大测试数量 ： 800,000：

14 分 3.266 秒/11 分 6.024 秒 = 843.27 秒/666.02 秒 = Haskell 慢 26.6%

[编辑：艾伦的代码]

这是我之前写的代码，它没有递归，我已经在 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）：

递归：11分6.024秒

无递归：11分5.328秒

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