haskell - 为什么盒装向量这么慢？

Question

我正在尝试获得向量的摊销 O(n) 时间串联。它似乎正在工作，但如果我需要存储装箱值(例如向量)，结果仍然很慢。

import qualified Data.Vector as V
import qualified Data.Vector.Generic.Mutable as GM
import Data.Vector(Vector)
import Control.Monad.State.Strict
import Control.Monad.ST

data App = S !(Vector Int) !Int deriving (Show)

main = do
  x <- liftM (map read . words) getContents
  print $ execState (mapM_ (add . V.singleton) x) (S V.empty 0)

add :: Vector Int -> State App ()
add v1 = do
    S v2 n <- get
    let v3 = vectorGrowAdd v1 v2 n
    put (S v3 (n + V.length v1))

vectorGrowAdd v1 v2 n = runST $ do
  m1 <- V.unsafeThaw v1
  m2 <- V.unsafeThaw v2
  m3 <- if GM.length m2 > (GM.length m1 + n)
         then do
           return m2
         else do
           GM.unsafeGrow m2 (GM.length m1 + 2*(GM.length m2))
  let copyTo = GM.unsafeSlice n (GM.length m1) m3 
  GM.unsafeCopy copyTo m1
  V.freeze m3

在本例中， testVals是一个包含 100000 个整数的文本文件， Boxed.hs是上面的代码和 Unboxed.hs与 Boxed.hs 相同进口除外 Data.Vector.Unboxed代替 Data.Vector .

> ghc -v
Glasgow Haskell Compiler, Version 7.0.3
> ghc --make -O2 Boxed.hs
> time (cat testVals | ./Boxed.hs)
  ...
  real      1m39.855s
  user      1m39.282s 
  sys       0m0.252s
> ghc --make -O2 Unboxed.hs
> time (cat testVals | ./Unboxed.hs)
...
real        0m4.372s
user        0m4.268s
sys         0m0.088s

我的问题是:为什么 Unboxed 和 Boxed 之间存在如此巨大的差异？如果我需要存储无法拆箱的值，我可以做些什么来提高速度？

Answer 1

我不知道为什么它对盒装 Vector 有如此巨大的影响s，但你在上面浪费了很多时间

V.freeze m3

这将创建 m3 的副本每一次。所以你复制了 100,000 Vector s 的长度增加。你不再需要旧的了，所以它们被垃圾收集了。盒装垃圾收集 Vector s 比收集未装箱的 Vector 花费的时间要长得多s 因为必须遵循所有指针才能查看是否也可以收集指针。不过，我对它产生的差异感到有些惊讶。

一些统计数据:

$ cat ./testVals | ./OldBoxed +RTS -t > Bxd.txt
<<ghc: 72590744976 bytes, 79999 GCs, 5696847/15655472 avg/max bytes residency (16 samples),
802M in use, 0.00 INIT (0.00 elapsed), 36.97 MUT (37.01 elapsed), 52.60 GC (52.67 elapsed) :ghc>>
$ cat ./testVals | ./OldUnboxed +RTS -t > UBxd.txt
<<ghc: 72518297568 bytes, 78256 GCs, 1013955/2294848 avg/max bytes residency (63 samples),
81M in use, 0.00 INIT (0.00 elapsed), 9.14 MUT (9.16 elapsed), 0.60 GC (0.60 elapsed) :ghc>>

因此，您会看到巨大的差异是由于 GC 造成的，但未装箱的 althogh MUT(程序执行实际工作的时间)也远低于此值。
现在，如果我们替换有问题的 freeze通过 unsafeFreeze ，我们得到

$ cat ./testVals | ./Boxed +RTS -t > Bxd.txt
<<ghc: 1149880088 bytes, 2214 GCs, 5236803/17102432 avg/max bytes residency (11 samples),
39M in use, 0.00 INIT (0.00 elapsed), 0.53 MUT (0.53 elapsed), 0.29 GC (0.29 elapsed) :ghc>>
$ cat ./testVals | ./Unboxed +RTS -t > UBxd.txt
<<ghc: 1152277200 bytes, 2229 GCs, 767477/2267200 avg/max bytes residency (31 samples),
7M in use, 0.00 INIT (0.00 elapsed), 0.61 MUT (0.62 elapsed), 0.04 GC (0.04 elapsed) :ghc>>

这暴露了一个小得多的差异。事实上，这里的盒装 Vector所需的更改器(mutator)时间比未装箱时少。不过，GC 时间仍然要高得多，因此整体拆箱仍然更快，但在 0.66 秒与 0.82 秒之间，这并没有什么戏剧性的。