盒装载体为什么这么慢？

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是上面的代码,除了导入instaid 之外Unboxed.hs是相同的.Boxed.hsData.Vector.UnboxedData.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,但你却浪费了很多时间

V.freeze m3

这会创建m3每次的副本.所以你要复制100,000 Vector秒的长度.你不再需要旧的了,所以它们是垃圾收集的.盒装Vectors的垃圾收集比未装箱的垃圾收集时间长得多,Vector因为必须遵循所有指针以查看是否也可以收集指针.不过,我对它有多大的不同感到有些惊讶.

一些统计数据:

$ 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比无盒装的需要更少的增变时间.不过GC的时间仍然要高得多,所以整体未装箱仍然会更快,但是0.66秒对0.82秒,这并不是什么大事.