爲什麼盒裝矢量這麼慢？

我正在嘗試獲得攤銷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 instaid的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之間有這麼大的差別？如果我需要存儲無法拆箱的值，有什麼方法可以提高速度？

來源

2011-11-02 HaskellElephant

相關http://stackoverflow.com/q/7913934/283240 – HaskellElephant

我不知道爲什麼它有盒裝Vector一個如此巨大的影響，但要以

V.freeze m3

，創建了每次m3副本浪費時間很多。所以你正在拷貝100,000 Vector s的長度。你不再需要舊的，所以它們被垃圾收集。盒裝Vector的垃圾收集比收集未裝箱的Vectors要長得多，因爲必須遵循所有指示器以查看是否可以收集鱈魚。不過，我對它有多大的差異感到有點驚訝。

一些統計數據：

$ 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（你的程序做實際工作的時間）要低得多的未裝箱了。現在
，如果我們通過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比unboxed需要更少的突變體時間。雖然GC的時間仍然高得多，但整體拆箱仍然更快，但是在0.66s和0.82s之間，這並沒有什麼太大的戲劇性。

來源

2011-11-02 11:05:56

令人驚歎的答案。非常感謝！ – HaskellElephant

對不起，我只是清理了一下代碼。 'toV < - V.freeze m3'現在應該是'v.freeze m3' ... – HaskellElephant

改編，謝謝。 –

爲什麼盒裝矢量這麼慢？

回答

相關問題