Warum sind gepackte Vektoren so langsam?

Question

Ich versuche, mich zu amortisieren O(n) zeitliche Verkettung von Vektoren. Es scheint zu funktionieren, aber wenn ich gepackte Werte (wie Vektoren) speichern muss, ist das Ergebnis immer noch sehr langsam.

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 diesem Beispiel, testVals ist eine Textdatei mit 100000 ganzen Zahlen, Boxed.hs ist der obige Code und Unboxed.hs ist dasselbe wie Boxed.hs außer bei der Einfuhr Data.Vector.Unboxed inmitten von 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

Meine Frage ist: Warum gibt es einen so drastischen Unterschied zwischen Unboxed und Boxed? Gibt es etwas, das ich tun kann, um die Geschwindigkeit zu verbessern, wenn ich Werte speichern muss, die nicht unboxed sein können?

Answer 1

Ich bin mir nicht sicher, warum es so dramatische Auswirkungen auf die Boxen hat Vector s, aber Sie vergeuden eine Los der Zeit in

V.freeze m3

Dadurch wird eine Kopie von m3 jedes Mal. Du kopierst also 100.000 Vector s mit zunehmender Länge. Die alten braucht man nicht mehr, also werden sie auf den Müll geworfen. Müllsammeln von verpackten Vector s dauert viel länger als das Sammeln von unverpackten Vector s, weil alle Zeiger verfolgt werden müssen, um zu sehen, ob die Zeiger auch gesammelt werden können. Ich bin allerdings ein wenig überrascht, wie viel das ausmacht.

Ein paar Statistiken:

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

Sie sehen also, dass der enorme Unterschied auf GC zurückzuführen ist, obwohl die MUT (die Zeit, in der Ihr Programm tatsächlich arbeitet) auch bei unboxed viel geringer ist.
Ersetzen wir nun die beanstandete freeze von unsafeFreeze erhalten wir

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

was einen weitaus geringeren Unterschied aufzeigt. In der Tat, hier die Boxen Vector benötigte weniger Mutatorzeit als unboxed. Die GC-Zeit ist immer noch viel höher, obwohl, so insgesamt unboxed immer noch schneller ist, aber bei 0,66s vs 0,82s, es ist nichts dramatisch.