欧拉问题的性能问题和Int64types的recursion

目前我正在学习使用欧拉问题项目的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版本中被打破。

Solutions Collecting From Web of "欧拉问题的性能问题和Int64types的recursion"

嗯,我安装了一个新的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