windows - 欧拉问题和 Int64 类型递归的性能问题

Question

我目前正在使用欧拉问题项目作为我的 Playground 来学习 Haskell。与类似的 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 种不同的版本:在声明 arcLength' x y !norm2 !acc 中，使用 Int64 或 Int 以及在 norm2 或两者之前使用 bangs 以及 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 版本中被破坏了。

Answer 1

嗯，我用 7.0.3 安装了一个新的 Haskell 平台，并为您的程序大致获得以下核心(-ddump-simpl):

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#
[...]

所以 GHC 已经意识到它可以解包你的整数，这很好。但是这个 hs_getInt64 调用看起来很像 C 调用。查看汇编器输出 (-ddump-asm)，我们看到如下内容:

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

所以这看起来非常像 Int64 上的每个操作都在后端变成了一个成熟的 C 调用。这显然慢。

source code GHC.IntWord64 似乎证实了这一点:在 32 位版本中(如当前随平台提供的版本)，您将只能通过 FFI 接口(interface)进行仿真。