Почему в коробке векторы так медленно?

Я пытаюсь получить амортизацию 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? Есть ли что-то, что я могу сделать, чтобы улучшить скорость, если мне нужно сохранить значения, которые нельзя распаковать?

Ответы

Ответ 1

Я не уверен, почему это так сильно влияет на коробку Vector s, но вы тратите много времени на

V.freeze m3

Это создает копию m3 каждый раз. Таким образом, вы копируете 100 000 Vector увеличения длины. Тебе больше не нужны старые, поэтому они собираются с мусором. Сбор мусора в коробке Vector занимает гораздо больше времени, чем сборка unboxed 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>>

Итак, вы видите, что огромная разница связана с GC, althogh MUT (время, когда ваша программа выполняет фактическую работу) намного меньше для unboxed. Теперь, если мы заменим оскорбление freeze на unsafeFreeze, получим

$ 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 все еще намного выше, но, тем не менее, общий unboxed все еще быстрее, но на 0,66 с против 0,82, это ничего не драматично.