在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，发现处理3000000个数字需要大约0.22秒，处理30000000个数字需要大约2.69秒。

与博客作者在Lush中得到的0.02秒和0.18秒的结果相比，这要差得多，这让我相信可以用更好的方法来解决这个问题。

注意：上述代码需要 TimeIt 包才能运行。cabal install timeit命令将为您获取此包。

- Fredrik

---

小心你所测量的内容。目前，你正在测量向量的分配和求和。 - Heinrich Apfelmus

不要使用ghci进行性能测试，而是使用ghc --make -O2。 - Sjoerd Visscher

如果你想学习如何使用vector包，可以查看这个优秀的教程：http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector_Tutorial - applicative

Answer 1

首先，要认识到 GHCi 是一个解释器，它并不是为了速度而设计的。为了获得更有用的结果，您应该启用编译优化来编译代码。这可能会产生巨大的差异。

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

我修改了您的代码以使用 criterion，并删除了打印语句，这样我们就不会计时 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进行编译，在一台运行较慢的netbook上得到以下结果：

$ 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的代码生成器。显然非常适合数值代码。

- hammar

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

- applicative

Answer 3

尝试使用非装箱向量，虽然我不确定在这种情况下是否会有明显的差异。请注意，比较略微不公平，因为vector包应该完全优化向量（此优化称为流融合）。

- ertes

Answer 4

如果你使用的向量足够大，那么未装箱的向量可能变得不实用。对于我来说，如果向量大小> 50000000，则纯（惰性）列表更快：

import System.TimeIt

sumit :: IO ()
sumit = print . sum $ replicate 50000000 10

main :: IO ()
main = timeIt sumit

我得到了这些时间：

Unboxed Vectors
CPU time:   1.00s

List:
CPU time:   0.70s

编辑: 我已经使用Criterion重复了基准测试，并使sumit成为纯函数。以下是代码和结果:

代码:

import Criterion.Main

sumit :: Int -> Int
sumit m = sum $ replicate m 10

main :: IO ()
main = defaultMain [bench "sumit" $ nf sumit 50000000]

结果：

warming up
estimating clock resolution...
mean is 7.248078 us (80001 iterations)
found 24509 outliers among 79999 samples (30.6%)
  6044 (7.6%) low severe
  18465 (23.1%) high severe
estimating cost of a clock call...
mean is 68.15917 ns (65 iterations)
found 7 outliers among 65 samples (10.8%)
  3 (4.6%) high mild
  4 (6.2%) high severe

benchmarking sumit
collecting 100 samples, 1 iterations each, in estimated 46.07401 s
mean: 451.0233 ms, lb 450.6641 ms, ub 451.5295 ms, ci 0.950
std dev: 2.172022 ms, lb 1.674497 ms, ub 2.841110 ms, ci 0.950

看起来print很重要，这是可以预料的！

- lbolla

---

你是用优化编译吗？对于你的版本，即使是100倍于此的数字，我得到的比例仍然是4:60。 - applicative

是的，我使用 ghc --make -O2 进行了编译。 - lbolla