Perché i vettori in scatola sono così lenti?

Question

Sto cercando di ottenere ammortizzato O (n) concatenazione di tempo di vettori. Sembra funzionare, ma se ho bisogno di memorizzare valori in box (come i vettori) il risultato è ancora molto lento.

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 

In questo esempio, testVals è un file di testo con numeri interi 100000, Boxed.hs è il codice di cui sopra e Unboxed.hs è uguale a Boxed.hs tranne che per l'importazione Data.Vector.Unboxed instaid di 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 

La mia domanda è: perché c'è una differenza così drastica tra Unboxed e Boxed? C'è qualcosa che posso fare per migliorare la velocità se ho bisogno di memorizzare valori che non possono essere unbox?

Answer 1

io non sono sicuro perché ha un impatto così drammatico sulla scatola Vector s, ma stai sprecando un sacco di tempo in

V.freeze m3 

che crea una copia di m3 ogni volta. Quindi stai copiando 100.000 Vector s di lunghezza crescente. Non hai più bisogno dei vecchi, quindi sono raccolti dai rifiuti. La raccolta dei dati inutili di boxing Vector s richiede molto più tempo della raccolta di unboxed Vector s perché tutti i puntatori devono essere seguiti per vedere se è possibile raccogliere anche le punte. Sono un po 'sorpreso da quanta differenza faccia, però.

alcune statistiche:

$ 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>> 

Così si vede che l'enorme differenza è dovuta al GC, althogh MUT (il tempo il vostro programma non lavoro effettivo) è di gran lunga inferiore per unboxed, anche.
Ora, se si sostituisce l'incriminata freeze da unsafeFreeze, otteniamo

$ 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>> 

che espone una differenza di gran lunga inferiore. In effetti, qui il box Vector aveva bisogno di meno tempo del mutatore rispetto a unbox. Il tempo di GC è ancora molto più alto, tuttavia, quindi nel complesso unboxed è ancora più veloce, ma a 0.66s contro 0.82s, non è niente di drammatico.