比较Haskell和C的速度来计算质数

Question

我最初编写了这个(强力和低效)计算素数的方法,目的是确保在Haskell中使用"if-then-else"与守卫之间的速度没有差别(并且没有区别!).但后来我决定编写一个C程序进行比较,我得到了以下内容(Haskell慢了25%):

(注意我从以下帖子中获得了使用rem而不是mod以及编译器调用中的O3选项的想法:在Fibonacci微基准测试中改进Has​​kell的性能与C相比)

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解释了为什么会发生这种情况并提供解决方案.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%

[编辑:艾伦代码]

这是我之前写过的代码,它没有递归,我在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'是严格foldl从Data.List避免的thunk正在建立).

Answer 2

写下算法的另一种方法是

main = print $ length [()|x<-[2..200000], and [rem x d>0|d<-[x-1,x-2..2]]]

不幸的是，它运行得较慢。作为all ((>0).rem x) [x-1,x-2..2]测试，它运行速度仍然较慢。但也许您仍然会在您的设置上测试它。

用带有爆炸模式的显式循环替换代码没有任何区别：

{-# OPTIONS_GHC -XBangPatterns #-}
r4::Int->Int
r4 n = go 0 2 where
  go !c i | i>n = c
          | True = go (if not(divisible i) then (c+1) else c) (i+1)

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