目前我正在学习使用欧拉问题项目的Haskell作为我的操场。 我很惊讶我的Haskell程序竟然与其他语言编写的类似程序相比有多慢。 我想知道是否有什么东西，或者如果这是使用Haskell时期望的性能惩罚。
以下程序受到331问题的启发，但在发布之前我已经更改了，所以我不会为其他人破坏任何东西。 它计算在2 ^ 30 x 2 ^ 30网格上绘制的离散圆弧的弧长。 这是一个简单的尾部recursion实现，我确保跟踪弧长的累加variables的更新是严格的。 不过花了差不多一分半钟就完成了（用ghc编译-O标志）。
import Data.Int arcLength :: Int64->Int64 arcLength n = arcLength' 0 (n-1) 0 0 where arcLength' xy 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代码做了som修改，并做了一些性能testing。 首先我把n改成2 ^ 29以避免溢出。 然后，我尝试了6个不同的版本：使用Int64或Int以及在norm2或两者之间使用bangs，并在声明arcLength' xy !norm2 !acc norm2和arcLength' xy !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。 根据评论，在其他configuration下编译时不会出现这个问题。 这使我认为Int64types在Windows版本中被打破。
嗯，我安装了一个新的Haskell平台7.0.3，并大致获得您的程序（ -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调用。 显然这很慢 。
GHC.IntWord64的源代码似乎验证：在一个32位版本（如目前平台附带的版本）中，您将只能通过FFI接口进行仿真。
嗯，这很有趣。 所以我只编译了你的两个程序，并试用了它们：
％java -version java版本“1.6.0_18” OpenJDK运行环境（IcedTea6 1.8.7）（6b18-1.8.7-2〜squeeze1） OpenJDK 64位服务器虚拟机（构建14.0-b16，混合模式） ％javac ArcLength.java ％java ArcLength 843298604 6630
所以Java解决方案大约需要6.6秒 。 接下来是ghc进行一些优化：
％ghc --version 格拉斯哥Glasgow Haskell编译系统，版本6.12.1 ％ghc --make -O arc.hs ％时间./arc 843298604 ./arc 12.68s用户0.04s系统99％cpu 12.718 total
ghc -O只有13秒
尝试进一步优化：
％ghc --make -O3 ％time ./arc [13:16] 843298604 ./arc 5.75s用户0.00s系统99％cpu 5.754总
随着进一步的优化标志，haskell解决方案花了6秒钟
知道你使用的是什么版本的编译器会很有趣。
在你的问题中有一些有趣的事情。
你应该主要使用-O2 。 它会做得更好（在这种情况下，确定和消除在-O版本中仍然存在的懒惰）。
其次，你的Haskell和Java不太一样（不同的测试和分支）。 和其他人一样，在我的Linux机器上运行你的代码会导致大约6s的运行时间。 看起来很好。
确保它与Java相同
一个想法：让我们做一个Java的字面转录，具有相同的控制流程，操作和类型。
import Data.Bits import Data.Int loop :: Int -> Int loop n = go 0 (n-1) 0 0 where go :: Int -> Int -> Int -> Int -> Int go xy acc norm2 | x <= y = case () of { _ | norm2 < 0 -> go (x+1) y acc (norm2 + 2*x + 1) | norm2 > 2 * (n-1) -> go (x-1) (y-1) acc (norm2 + 2 - 2 * (x+y)) | otherwise -> go (x+1) y (acc+1) (norm2 + 2*x + 1) } | otherwise = acc main = print $ loop (1 `shiftL` 30)
偷看核心
我们将使用ghc-core快速浏览一下Core，它会显示一个非盒式的非常好的循环：
main_$s$wgo :: Int# -> Int# -> Int# -> Int# -> Int# main_$s$wgo = \ (sc_sQa :: Int#) (sc1_sQb :: Int#) (sc2_sQc :: Int#) (sc3_sQd :: Int#) -> case <=# sc3_sQd sc2_sQc of _ { False -> sc1_sQb; True -> case <# sc_sQa 0 of _ { False -> case ># sc_sQa 2147483646 of _ { False -> main_$s$wgo (+# (+# sc_sQa (*# 2 sc3_sQd)) 1) (+# sc1_sQb 1) sc2_sQc (+# sc3_sQd 1); True -> main_$s$wgo (-# (+# sc_sQa 2) (*# 2 (+# sc3_sQd sc2_sQc))) sc1_sQb (-# sc2_sQc 1) (-# sc3_sQd 1) }; True -> main_$s$wgo (+# (+# sc_sQa (*# 2 sc3_sQd)) 1) sc1_sQb sc2_sQc (+# sc3_sQd 1)
也就是说，全部拆箱到寄存器中。 那个循环看起来很棒！
并执行得很好（Linux / x86-64 / GHC 7.03）：
./A 5.95s user 0.01s system 99% cpu 5.980 total
检查模块
我们也得到合理的组装，作为一个很好的循环：
Main_mainzuzdszdwgo_info: cmpq %rdi, %r8 jg .L8 .L3: testq %r14, %r14 movq %r14, %rdx js .L4 cmpq $2147483646, %r14 jle .L9 .L5: leaq (%rdi,%r8), %r10 addq $2, %rdx leaq -1(%rdi), %rdi addq %r10, %r10 movq %rdx, %r14 leaq -1(%r8), %r8 subq %r10, %r14 jmp Main_mainzuzdszdwgo_info .L9: leaq 1(%r14,%r8,2), %r14 addq $1, %rsi leaq 1(%r8), %r8 jmp Main_mainzuzdszdwgo_info .L8: movq %rsi, %rbx jmp *0(%rbp) .L4: leaq 1(%r14,%r8,2), %r14 leaq 1(%r8), %r8 jmp Main_mainzuzdszdwgo_info
使用-fvia-C后端。
所以这看起来很好！
正如上面的评论中所提到的，我的怀疑与在32位Windows上为64位整数生成糟糕代码的libgmp版本有关。 首先尝试升级到GHC 7.0.3，然后尝试其他一些代码生成器后端，如果仍然存在Int64问题，请向GHC trac提交错误报告。
从广义上来说，确实是在64位的32位仿真中进行这些C调用的代价，我们可以用Integer来代替Int64 ，而Integer是在每台机器上用C调用GMP来实现的，实际上，运行时间从3s到好一分钟。
课程：尽可能使用硬件64位。
性能相关代码的正常优化标志是-O2 。 你用的是-O ，做得很少。 -O3比-O2更多（甚至更多），它甚至包括实验性的“优化”，通常使程序变得更慢。
使用-O2我可以获得与Java相媲美的性能：
tommd@Mavlo:Test$ uname -r -m 2.6.37 x86_64 tommd@Mavlo:Test$ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.0.3 tommd@Mavlo:Test$ ghc -O2 so.hs [1 of 1] Compiling Main ( so.hs, so.o ) Linking so ... tommd@Mavlo:Test$ time ./so 843298604 real 0m4.948s user 0m4.896s sys 0m0.000s
而Java大约快1秒（20％）：
tommd@Mavlo:Test$ time java ArcLength 843298604 3880 real 0m3.961s user 0m3.936s sys 0m0.024s
但是关于GHC有趣的是它有许多不同的后端。 默认情况下，它使用我们在上面计时的本机代码生成器（NCG）。 还有一个LLVM后端，往往会更好…但不是在这里：
tommd@Mavlo:Test$ ghc -O2 so.hs -fllvm -fforce-recomp [1 of 1] Compiling Main ( so.hs, so.o ) Linking so ... tommd@Mavlo:Test$ time ./so 843298604 real 0m5.973s user 0m5.968s sys 0m0.000s
但是，正如FUZxxl在评论中提到的那样，当您添加一些严格注释时，LLVM会更好：
$ ghc -O2 -fllvm -fforce-recomp so.hs [1 of 1] Compiling Main ( so.hs, so.o ) Linking so ... tommd@Mavlo:Test$ time ./so 843298604 real 0m4.099s user 0m4.088s sys 0m0.000s
还有一个使用C作为中间语言的旧式“via-c”生成器。 它在这种情况下表现很好：
tommd@Mavlo:Test$ ghc -O2 so.hs -fvia-c -fforce-recomp [1 of 1] Compiling Main ( so.hs, so.o ) on the commandline: Warning: The -fvia-c flag will be removed in a future GHC release Linking so ... ttommd@Mavlo:Test$ ti tommd@Mavlo:Test$ time ./so 843298604 real 0m3.982s user 0m3.972s sys 0m0.000s
希望NCG能够改进，以便在这种情况下匹配via-c，然后再删除这个后端。
dberg ，我觉得所有这些都让这个不幸的-O标志起了个坏头。 只是为了强调别人提出的一点，对于普通的编译和测试，像我一样，粘贴到你的.bashrc或其他：
alias ggg="ghc --make -O2" alias gggg="echo 'Glorious Glasgow for Great Good!' && ghc --make -O2 --fforce-recomp"
我已经玩了一些代码，这个版本似乎运行速度比我的笔记本电脑上的Java版本（3.55s和4.63s）：
{-# LANGUAGE BangPatterns #-} arcLength :: Int->Int arcLength n = arcLength' 0 (n-1) 0 0 where arcLength' :: Int -> Int -> Int -> Int -> Int arcLength' !x !y !norm2 !acc | x > y = acc | norm2 > 2*(n-1) = arcLength' (x - 1) (y - 1) (norm2 - 2*(x + y) + 2) acc | norm2 < 0 = arcLength' (succ x) y (norm2 + x*2 + 1) acc | otherwise = arcLength' (succ x) y (norm2 + 2*x + 1) (acc + 1) main = print $ arcLength (2^30)
：
$ ghc -O2 tmp1.hs -fforce-recomp [1 of 1] Compiling Main ( tmp1.hs, tmp1.o ) Linking tmp1 ... $ time ./tmp1 843298604 real 0m3.553s user 0m3.539s sys 0m0.006s