Haskell三角微基准

Question

考虑这个简单的"基准":

n :: Int
n = 1000
main = do
    print $ length [(a,b,c) | a<-[1..n],b<-[1..n],c<-[1..n],a^2+b^2==c^2]

和适当的C版本:

#include <stdio.h>

int main(void)
{
    int a,b,c, N=1000;
    int cnt = 0;

    for (a=1;a<=N;a++)
        for (b=1;b<=N;b++)
            for (c=1;c<=N;c++)
                if (a*a+b*b==c*c) cnt++;
    printf("%d\n", cnt);
}

汇编:

• Haskell版本编译为:ghc -O2 triangle.hs(ghc 7.4.1)
• C版编译为:gcc -O2 -o triangle-c triangle.c(gcc 4.6.3)

运行时间:

• Haskell:4.308s真实
• C:1.145s真实

即使对于如此简单且可以很好地优化的程序,Haskell的速度几乎要慢4倍,这是不是很好？Haskell在哪里浪费时间？

Answer 1

Haskell版本浪费时间分配盒装整数和元组.

您可以通过例如使用标志运行haskell程序来验证这一点+RTS -s.对我来说输出的统计数据包括:

  80,371,600 bytes allocated in the heap

由于编译器可以使用未装箱的整数并跳过分配元组,因此C版本的直接编码更快:

n :: Int
n = 1000
main = do
  print $ f n

f :: Int -> Int
f max = go 0 1 1 1
  where go cnt a b c
          | a > max = cnt
          | b > max = go cnt (a+1) 1 1
          | c > max = go cnt a (b+1) 1
          | a^2+b^2==c^2 = go (cnt+1) a b (c+1)
          | otherwise = go cnt a b (c+1)

看到:

  51,728 bytes allocated in the heap

此版本的运行时间1.920s与1.212sC版本相比.