¿Por qué los vectores en caja son tan lentos?

Question

Estoy tratando de obtener amortizado O (n) tiempo de concatenación de vectores. Parece que funciona, pero si necesito almacenar valores encuadrados (como vectores), el resultado es muy 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 

En este ejemplo, testVals es un archivo de texto con números enteros 100000, Boxed.hs es el código de arriba y Unboxed.hs es lo mismo que Boxed.hs excepto para importar Data.Vector.Unboxed instaid de 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 

Mi pregunta es: ¿Por qué hay una diferencia tan drástica entre Unboxed y Boxed? ¿Hay algo que pueda hacer para mejorar la velocidad si necesito almacenar valores que no se pueden desempaquetar?

Answer 1

no estoy seguro de por qué tiene un impacto tan dramático en la caja Vector s, pero usted está perdiendo una gran cantidad de tiempo en

V.freeze m3 

que crea una copia de m3 cada vez. Entonces está copiando 100,000 Vector s de mayor longitud. Ya no necesitas los viejos, por lo que están recogidos de basura. La recolección de basura de Vector en caja tarda mucho más que la colección de Vector s no empaquetados porque se deben seguir todos los indicadores para ver si también se pueden recopilar los puntos. Sin embargo, estoy un poco sorprendido por la cantidad de diferencia que hace.

Algunas estadísticas:

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

por lo que ver que la enorme diferencia se debe a GC, althogh MUT (el tiempo que su programa hace el trabajo real) es mucho menor para los sacó de la caja, también.
Ahora, si sustituimos el infractor freeze por unsafeFreeze, obtenemos

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

que expone una diferencia mucho menor. De hecho, aquí el recuadro Vector necesitó menos tiempo de mutador que unboxed. Sin embargo, el tiempo de GC todavía es mucho más alto, por lo que el desempaquetado global aún es más rápido, pero en 0.66s frente a 0.82s, no es nada dramático.