Windows – Euler问题的性能问题和Int64类型的递归

我正在学习 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或者两者之前都有bangs,而norm2和acc在声明arcLength’x y！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(Haskell平台二进制分发)下使用GHC 7.0.2.根据注释,在其他配置下进行编译时,不会出现此问题.这使我觉得Int64类型在Windows版本中被破坏.

Main.$warcLength' =
   (ww_s1my :: GHC.Prim.Int64#) (ww1_s1mC :: GHC.Prim.Int64#)
    (ww2_s1mG :: GHC.Prim.Int64#) (ww3_s1mK :: GHC.Prim.Int64#) ->
    case {__pkg_ccall ghc-prim hs_gtInt64 [...]
           ww_s1my ww1_s1mC GHC.Prim.realWorld#
[...]

pushl %eax
movl 76(%esp),%eax
pushl %eax
call _hs_gtInt64
addl $16,%esp