2011-11-02 32 views
15

Vektörlerin zaman uyumlulaştırılması için O (n) amortize edilmeye çalışıyorum. Çalışıyor gibi görünüyor, ancak kutulu değerleri (vektörler gibi) saklamak gerekirse, sonuç hala çok yavaş. Bu örnekte Kutulu vektörler neden bu kadar yavaş?

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 tamsayılar olan bir metin dosyasıdır, Boxed.hs Yukarıdaki kod olup Unboxed.hs Data.Vector ait Data.Vector.Unboxed instaid ithal hariç Boxed.hs aynıdır.

> 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 

Soruma Soru: Neden Kutusuz ve Kutulu arasında büyük bir fark var? Kutusuz durumda olmayan değerleri saklamak gerekirse hızını artırmak için yapabileceğim bir şey var mı?

+0

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

cevap

15

Ben kutulu Vector s üzerinde böyle dramatik bir etkiye sahip olmasının emin değilim ama m3 her zaman bir kopyasını oluşturur

V.freeze m3 

bir zaman sürü harcıyorsun. Yani 100.000 Vector s uzunluğunu arttırıyorsunuz. Artık eskilere ihtiyacın yok, o yüzden çöp topladılar. Kutulu Vector numaralı çöplerin toplanması, kutulu olmayan Vector s koleksiyonundan daha uzun sürebilir, çünkü tüm işaretçilerin pointeelerin de toplanıp toplanmayacağını görmek için takip edilmesi gerekir. Yine de, ne kadar fark yarattığına biraz şaşırdım.

Birkaç istatistik:

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

Yani muazzam bir fark da kutusuz için çok düşüktür MUT (programınızın gerçek çalışır zamanı) althogh GC nedeniyle olduğunu görüyoruz. Biz unsafeFreeze tarafından kusurlu freeze değiştirirseniz
Şimdi, biz çok küçük bir fark ortaya

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

olsun. Aslında, burada kutulu Vector kutudan daha az mutajör süresine ihtiyaç duyuyordu. Yine de, GC zamanı hala çok daha yüksektir, bu yüzden genel kutulanmamış hala daha hızlıdır, ancak 0.66'larda ve 0.82'lerde bu dramatik değildir.

+0

Şaşırtıcı yanıt ile ilgili. Çok teşekkür ederim! – HaskellElephant

+0

Üzgünüm, kodu biraz temizlemem gerekiyordu. toV <- V.freeze m3 'şimdi v.freeze m3' olmalıdır ... – HaskellElephant

+0

Uyarlandı, teşekkürler. –

İlgili konular