なぜ箱入りベクトルが遅いのですか？

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はData.VectorのData.Vector.Unboxed instaidをインポート以外Boxed.hsと同じであるとのテキストファイルです。

> 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の上のような劇的な影響を与えている理由はわからないんだけど、あなたはm3たびのコピーを作成します

V.freeze m3 

時間の多くを無駄にしています。したがって、あなたは100,000の長さが増加するVectorをコピーしています。古いものはもう必要ないので、ガベージコレクションされます。ボックス化されたVectorのガーベッジコレクションは、ボックス化されていない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>> 

だから、あなたは大きな違いがあまりにも、アンボクシングのためにはるかに低いMUT（あなたのプログラムは、実際の作業を行う時間）althogh、GCによるものであることを参照してください。私たちはunsafeFreezeで問題freezeを交換する場合
今、私たちは、はるかに小さい違いを公開

$ 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秒ではそれほど劇的ではありません。