我目前正在使用项目欧拉问题学习Haskell编程。与其他语言编写的类似程序相比,我的Haskell程序速度非常慢,这让我感到惊讶。我想知道是否预见到了什么问题,或者这是使用Haskell时需要预期的性能损失。
以下程序受问题331启发,但我在发布之前进行了更改,以免为其他人提供任何线索。它计算在2^30 x 2^30网格上绘制的离散圆的弧长。这是一个简单的尾递归实现,并且我确保跟踪弧长的累加变量的更新是严格的。然而,即使使用ghc的-O标志编译,它也需要将近一分半钟才能完成。
import Data.Int
arcLength :: Int64->Int64
arcLength n = arcLength' 0 (n-1) 0 0 where
arcLength' x y norm2 acc
| x > y = acc
| norm2 < 0 = arcLength' (x + 1) y (norm2 + 2*x +1) acc
| norm2 > 2*(n-1) = arcLength' (x - 1) (y-1) (norm2 - 2*(x + y) + 2) acc
| otherwise = arcLength' (x + 1) y (norm2 + 2*x + 1) $! (acc + 1)
main = print $ arcLength (2^30)
这是Java的一个对应实现。它需要大约4.5秒完成。
public class ArcLength {
public static void main(String args[]) {
long n = 1 << 30;
long x = 0;
long y = n-1;
long acc = 0;
long norm2 = 0;
long time = System.currentTimeMillis();
while(x <= y) {
if (norm2 < 0) {
norm2 += 2*x + 1;
x++;
} else if (norm2 > 2*(n-1)) {
norm2 += 2 - 2*(x+y);
x--;
y--;
} else {
norm2 += 2*x + 1;
x++;
acc++;
}
}
time = System.currentTimeMillis() - time;
System.err.println(acc);
System.err.println(time);
}
编辑:在评论讨论后,我对Haskell代码进行了一些修改并进行了一些性能测试。首先,我将n更改为2 ^ 29以避免溢出。然后我尝试了6个不同版本:使用Int64或Int,在norm2或both之前加上bangs以及在声明arcLength' x y!norm2!acc
中使用norm2和acc。所有版本都编译了。
ghc -O3 -prof -rtsopts -fforce-recomp -XBangPatterns arctest.hs
以下是结果:
(Int !norm2 !acc)
total time = 3.00 secs (150 ticks @ 20 ms)
total alloc = 2,892 bytes (excludes profiling overheads)
(Int norm2 !acc)
total time = 3.56 secs (178 ticks @ 20 ms)
total alloc = 2,892 bytes (excludes profiling overheads)
(Int norm2 acc)
total time = 3.56 secs (178 ticks @ 20 ms)
total alloc = 2,892 bytes (excludes profiling overheads)
(Int64 norm2 acc)
arctest.exe: out of memory
(Int64 norm2 !acc)
total time = 48.46 secs (2423 ticks @ 20 ms)
total alloc = 26,246,173,228 bytes (excludes profiling overheads)
(Int64 !norm2 !acc)
total time = 31.46 secs (1573 ticks @ 20 ms)
total alloc = 3,032 bytes (excludes profiling overheads)
我正在使用64位Windows 7操作系统下的GHC 7.0.2(Haskell平台二进制发行版)。根据评论,当在其他配置下编译时,问题不会出现。这让我认为,在Windows版本中,Int64类型存在问题。
arcLength' x y !norm2 !acc
?因为当第一个分支被执行时,norm2
和acc
并不总是需要严格传递。顺便说一下,在我的机器上只需要6秒钟。 - fuz-O2
是 GHC 优化的典型标志。如果我没记错,-O
的优化效果不太明显。 - Thomas M. DuBuissonInt64
类型来自)在32位Windows上相关的错误。您可以升级libgmp
,将GHC升级到7.0.3或在64位Windows上进行测试吗? - Don Stewart