在Haskell中做有效的数字

Question

我被这篇名为" 只有快速语言很有趣 "的帖子所启发,以便在Haskell中查看他建议的问题(从向量中总结几百万个数字)并与他的结果进行比较.

我是一名Haskell新手,所以我真的不知道如何正确计时或如何有效地做到这一点,我对此问题的第一次尝试如下.请注意,我不是在向量中使用随机数,因为我不确定如何以一种好的方式做.我也打印东西,以确保完整的评估.

import System.TimeIt

import Data.Vector as V

vector :: IO (Vector Int)
vector = do
  let vec = V.replicate 3000000 10
  print $ V.length vec
  return vec

sumit :: IO ()
sumit = do
  vec <- vector
  print $ V.sum vec

time = timeIt sumit

在GHCI中加载并运行time告诉我,运行300万个数字需要大约0.22秒,而3000万个数字需要2.69秒.

与博客作者在郁郁葱葱中的0.02s和0.18s的结果相比,情况要糟糕得多,这使我相信这可以以更好的方式完成.

注意:上面的代码需要运行包TimeIt.cabal install timeit会得到它.

Answer 1

首先,要意识到GHCi是一个解释器,并不是设计得非常快.要获得更有用的结果,您应该在启用优化的情况下编译代码.这可以产生巨大的差异.

此外,对于任何严格的Haskell代码基准测试,我建议使用标准.它使用各种统计技术来确保您获得可靠的测量结果.

我修改了你的代码以使用标准并删除了print语句,这样我们就不会对I/O进行计时.

import Criterion.Main
import Data.Vector as V

vector :: IO (Vector Int)
vector = do
  let vec = V.replicate 3000000 10
  return vec

sumit :: IO Int
sumit = do
  vec <- vector
  return $ V.sum vec

main = defaultMain [bench "sumit" $ whnfIO sumit]

编译这个-O2,我得到一个非常慢的上网本的结果:

$ ghc --make -O2 Sum.hs
$ ./Sum 
warming up
estimating clock resolution...
mean is 56.55146 us (10001 iterations)
found 1136 outliers among 9999 samples (11.4%)
  235 (2.4%) high mild
  901 (9.0%) high severe
estimating cost of a clock call...
mean is 2.493841 us (38 iterations)
found 4 outliers among 38 samples (10.5%)
  2 (5.3%) high mild
  2 (5.3%) high severe

benchmarking sumit
collecting 100 samples, 8 iterations each, in estimated 6.180620 s
mean: 9.329556 ms, lb 9.222860 ms, ub 9.473564 ms, ci 0.950
std dev: 628.0294 us, lb 439.1394 us, ub 1.045119 ms, ci 0.950

所以我得到的平均值只有9毫秒,标准差小于1毫秒.对于更大的测试用例,我的时间约为100毫秒.

使用时使优化是特别重要的vector包,因为它使大量使用的流融合,而在这种情况下,能够完全消除的数据结构,把你的程序到一个高效,紧密的循环.

使用-fllvm选项试验新的基于LLVM的代码生成器也是值得的.它显然非常适合数字代码.

Answer 2

您的原始文件,未编译,然后编译而不进行优化,然后使用简单的优化标志进行编译:

$ runhaskell boxed.hs  
3000000
30000000
CPU time:   0.35s

$ ghc --make boxed.hs -o unoptimized 
$ ./unoptimized
3000000
30000000
CPU time:   0.34s



$ ghc --make -O2 boxed.hs 
$ ./boxed
3000000
30000000
CPU time:   0.09s

您的文件import qualified Data.Vector.Unboxed as V而不是import qualified Data.Vector as V(Int是一个无法打开的类型) - 首先没有优化,然后使用:

$ ghc --make unboxed.hs -o unoptimized
$ ./unoptimized
3000000
30000000
CPU time:   0.27s


$ ghc --make -O2 unboxed.hs 
$ ./unboxed
3000000
30000000
CPU time:   0.04s

所以,编译,优化......以及在可能的情况下使用 Data.Vector.Unboxed