हास्केल

Question

में गूढ़ स्मृति व्यवहार मैं हास्केल सूचियों और सरणी के प्रदर्शन की तुलना करने और एक अजीब व्यवहार में चलाने की कोशिश कर रहा हूं। मैंने देखा कि यदि मैं एक सरणी बनाता हूं और फिर इसे प्रिंट करता हूं तो यह 'x' मेमोरी मेमोरी लेता है, लेकिन अगर मैं 'elems' फ़ंक्शन का उपयोग करके सरणी को एक सूची में परिवर्तित करता हूं और फिर प्रिंट करता हूं तो यह 'x' से कम स्मृति लेता है। क्या 'elems' फ़ंक्शन सरणी से एक नई सूची बनाने वाला नहीं है? क्या उस समारोह से अधिक जगह नहीं लेनी चाहिए जो सूची नहीं बनाती? मैं -O2 और -fspec-constr को झंडे अनुकूलित करने का उपयोग कर रहा हूं। मैं कार्यों को प्रोफाइल करने के लिए -p ध्वज का भी उपयोग कर रहा हूं।

इस मध्यवर्ती सूची के बिना कोड है,

fun n = runST $ do 
     final_soln <- newArray_ ((1,1), (n, (10^n))) :: ST s ((STUArray s) (Int,Int) Int) 
     U.unsafeFreeze final_soln 

main = do 
    [n] <- getArgs 
    {-# SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt" $ show $ fun (read n)) 

इस मध्यवर्ती की सूची के साथ कोड है,

fun :: Int -> UArray (Int,Int) Int 
fun n = runST $ do 
     final_soln <- newArray_ ((1,1), (n, (10^n))) :: ST s ((STUArray s) (Int,Int) Int) 
     U.unsafeFreeze final_soln 

main = do 
    [n] <- getArgs 
    {-# SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt" $ show $ elems $ fun (read n)) 

अग्रिम धन्यवाद

Answer 1

में lazyness की कमी नहीं है पहला संस्करण, और यह आपकी गलती नहीं है। ,

पहले कोड की रूपरेखा उत्पादन होता है, जबकि

का परिणाम है: पैरामीटर 6 के साथ एक रन की रूपरेखा निर्गम (+RTS -hd) की तुलना पहले संकेत देता है दूसरा कोड सरणी स्वयं (ARR_WORDS) दोनों में एक ही स्थान लेता है। आप यह भी देखते हैं कि पहला कोड Int कन्स्ट्रक्टर (Int# नाम होने वाला) की एक बड़ी सूची (: कन्स्ट्रक्टर द्वारा मान्यता प्राप्त) उत्पन्न करता है।

अब यह मुद्रित के रूप में अंतिम स्ट्रिंग नहीं हो सकता है, क्योंकि यह Char एस होगा (कन्स्ट्रक्टर C# के साथ)। यह सरणी में तत्वों की सूची भी नहीं हो सकता है, क्योंकि सरणी में शून्य होते हैं और कचरा कलेक्टर के पास छोटे Int एस (श्रेणी [-16,16]) का कैश होता है जो इसे आवंटित करने के बजाय उपयोग करेगा (या वास्तव में प्रतिलिपि बनाने के बजाय) एक नया कन्स्ट्रक्टर।

यह भी ध्यान रखें कि : रचनाकारों के लिए लगभग 24 एमबी और I# रचनाकारों के लिए 16 एमबी लगता है। यह जानकर कि पूर्व को 3 शब्दों और बाद वाले 2 शब्दों की आवश्यकता होती है, और मेरी मशीन पर एक शब्द 8 बाइट लंबा है, हम पाते हैं कि सूची 100000 = 10^6 तत्व लंबी है। तो एक बहुत अच्छा उम्मीदवार दूसरे सूचकांक पैरामीटर की सीमा है।

तो यह सरणी कहां है? हमें show करने के लिए अपने कॉल का पता लगाने करते हैं:

showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS 
showsIArray p a = 
    showParen (p > 9) $ 
    showString "array " . 
    shows (bounds a) . 
    showChar ' ' . 
    shows (assocs a) 

(Data.Array.Base से कोड)। जाहिर है, अपराधी assocs कॉल में होना चाहिए, इसलिए यहाँ उस के लिए स्रोत है:

assocs :: (IArray a e, Ix i) => a i e -> [(i, e)] 
assocs arr = case bounds arr of 
    (l,u) -> [(i, arr ! i) | i <- range (l,u)] 

जब से हम देख रहे हैं सूचकांक की सूची के लिए, range कॉल पर्याप्त संदिग्ध लग रहा है।

instance (Ix a, Ix b) => Ix (a, b) where 
    range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ] 

और अब हम दोषी पाया है: ऐसी स्थिति में हमने GHC.Arr के स्रोत (जो दुर्भाग्य में गड़बड़ हेडॉक) पर गौर करने के लिए है यहाँ, range (l2,u2) सूची [1..1000000] और करने का मूल्यांकन करेंगे हर कदम के लिए साझा सूचकांक के पहले घटक में।

अब मुझे लगता है कि आप दूसरे कोड में elems के बजाय assocs डालकर और अंतरिक्ष रिसाव की अपेक्षा करने में उत्सुक होंगे। लेकिन आप इसे नहीं देख पाएंगे। इसका कारण यह है कि show रेखांकित नहीं है, लेकिन assocs स्वयं को रेखांकित किया जाता है, और फिर range समेत अन्य कार्यों का एक समूह भी प्रभावी ढंग से साझा करने से परहेज करता है। आप देख सकते हैं कि (कुछ) GHC को -ddump-rule-firings पास करके:

$ ghc --make -O2 -fspec-constr -ddump-rule-firings -fforce-recomp code2.hs -prof -fprof-auto 
[1 of 1] Compiling Main    (code2.hs, code2.o) 
Rule fired: SPEC GHC.Arr.$fIx(,) 
Rule fired: unpack 
Rule fired: Class op fail 
Rule fired: unpack 
Rule fired: Class op show 
Rule fired: Class op newArray_ 
Rule fired: unsafeFreeze/STUArray 
Rule fired: Class op >>= 
Rule fired: Class op >>= 
Rule fired: Class op showList 
Rule fired: Class op rangeSize 
Rule fired: Class op rangeSize 
Rule fired: Class op bounds 
Rule fired: Class op bounds 
Rule fired: Class op numElements 
Rule fired: Class op index 
Rule fired: Class op unsafeAt 
Rule fired: Class op range 
Rule fired: fold/build 
Rule fired: SPEC GHC.Real.^ 
Rule fired: unpack-list 
Rule fired: foldr/app 
Rule fired: unpack-append 
Rule fired: foldr/app 
Rule fired: unpack-append 
Rule fired: ># 
Rule fired: ># 
Rule fired: x# <=# x# 
Rule fired: x# -# x# 
Rule fired: 0# *# x# 
Rule fired: 0# +# x# 
Linking code2 ...