बॉक्स किए गए वैक्टर इतने धीमे क्यों हैं?

Question

मैं अमृत ओ (एन) वैक्टरों का समय समामेलन करने की कोशिश कर रहा हूं। ऐसा लगता है कि काम कर रहा है लेकिन अगर मुझे बॉक्स किए गए मूल्यों (जैसे वेक्टर) स्टोर करने की ज़रूरत है तो परिणाम अभी भी बहुत धीमा है।

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.hsData.Vector की Data.Vector.Unboxed instaid आयात करने के अलावा Boxed.hs के समान है।

> 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 

मेरा प्रश्न है: क्यों वहाँ अनबॉक्स्ड और बॉक्सिंग के बीच इस तरह के एक कठोर अंतर है? क्या मुझे गति में सुधार करने के लिए कुछ कर सकता है यदि मुझे उन मूल्यों को स्टोर करने की आवश्यकता है जिन्हें अनबॉक्स नहीं किया जा सकता है?

Answer 1

मुझे यकीन है कि क्यों यह बॉक्सिंग Vector रों पर इस तरह के एक नाटकीय प्रभाव पड़ता है नहीं कर रहा हूँ, लेकिन आप

V.freeze m3 

कि m3 हर बार एक कॉपी बन में समय की एक बहुत बर्बाद कर रहे हैं। तो आप बढ़ती लंबाई के 100,000 Vector एस की प्रतिलिपि बना रहे हैं। आपको अब पुराने लोगों की आवश्यकता नहीं है, इसलिए वे कचरे से एकत्र हुए हैं। बॉक्स किए गए Vector एस का कचरा संग्रह अनबॉक्स किए गए 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>> 

तो आप देखते हैं कि भारी अंतर जीसी की वजह से है, MUT (समय अपने कार्यक्रम वास्तविक काम करता है) Althogh अनबॉक्स्ड के लिए काफी कम है, भी है।
अब, अगर हम unsafeFreeze द्वारा हमलावर freeze की जगह है, हम

$ 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 को अनबॉक्स किए गए कम म्यूटेटर समय की आवश्यकता है। जीसी समय अभी भी बहुत अधिक है, हालांकि, कुल मिलाकर अनबॉक्स अभी भी तेज है, लेकिन 0.66 बनाम 0.82s पर, यह नाटकीय नहीं है।