यह कोड शीर्ष स्तर पर निर्दिष्ट दो (पारस्परिक रूप से रद्द) अनंत सूचियों की सामग्री का योग करता है:

{-# language BangPatterns #-}
module Main where

unending1 :: [Int]
unending1 = cycle [1]

unending2 :: [Int]
unending2 = cycle [negate 1]

main :: IO ()
main = do
    let summator :: Int -> [Int] -> [Int] -> Int
        summator !acc (i1 : rest1) (i2 : rest2) =
            if acc > 100
            then acc -- never happens
            else summator (acc+i1+i2) rest1 rest2
    print (summator 0 unending1 unending2)

मैं इस कोड को बिना किसी अनुकूलन और कम ढेर आकार के संकलित करता हूं, जैसे:

ghc -O0 -with-rtsopts="-M10m" Main.hs

मेरा अंतर्ज्ञान यह है कि यह कोड स्मृति रिसाव का कारण बनता है, क्योंकि सारांश कार्य दो सूचियों को "भौतिक" करने का प्रयास करेगा, और उन दोनों के प्रमुख शीर्ष-स्तर पर हैं, इसलिए उन्हें त्याग नहीं किया जाएगा।

हालांकि जब मैं प्रोग्राम निष्पादित करता हूं तो ऐसा लगता है कि यह बिना किसी समस्या के अनिश्चित काल तक चलता है।

मैं कहाँ गलत हूँ?


संपादित करें। -ddump-simpl का उपयोग करके उत्पन्न कोर का निरीक्षण करने पर, सूचियां शीर्ष स्तर पर बनी हुई प्रतीत होती हैं। उदाहरण के लिए:

Result size of Tidy Core = {terms: 77, types: 52, coercions: 0}

-- RHS size: {terms: 5, types: 3, coercions: 0}
unending1 :: [Int]
[GblId, Str=DmdType]
unending1 =
  cycle
    @ Int (GHC.Types.: @ Int (GHC.Types.I# 1#) (GHC.Types.[] @ Int))
3
danidiaz 12 नवम्बर 2016, 14:39

2 जवाब

सबसे बढ़िया उत्तर

जैसा कि ची ने उत्तर दिया, cycle की परिभाषा के कारण आपका कोड निरंतर स्थान पर चलता है।

हालांकि, यह ghc -O0 के साथ cycle xs = xs ++ cycle xs के साथ भी निरंतर स्थान पर चलता है, क्योंकि शीर्ष-स्तरीय थंक्स (निरंतर आवेदक फॉर्म, सीएएफ-एस) कचरा एकत्र किया जा सकता है। क्लोजर की सूचना तालिका में "स्थैतिक संदर्भ सारणी" होती है, जो स्थिर बंदों को सूचीबद्ध करती है जैसे कि

  • बंद करने का कोड उनका उल्लेख करता है
  • वे या तो शीर्ष-स्तरीय थंक हैं या उनका कोड ट्रांज़िटिव रूप से शीर्ष-स्तरीय थंक्स को संदर्भित करता है

दस्तावेज़ीकरण यहां। यदि जीसी रूट्स से शीर्ष-स्तरीय थंक्स तक नहीं पहुंचा जा सकता है (जिसमें थ्रेड-स्टेट ऑब्जेक्ट्स के ढेर शामिल हैं, तो हमारे मामले में main निष्पादन के तहत बंद होना), ढेर ऑब्जेक्ट्स जो वे इंगित करते हैं उन्हें छोड़ दिया जाता है।

4
András Kovács 12 नवम्बर 2016, 15:39

GHC.List से:

cycle                   :: [a] -> [a]
cycle []                = errorEmptyList "cycle"
cycle xs                = xs' where xs' = xs ++ xs'

ध्यान दें कि रिकर्सन में फ़ंक्शन कॉल शामिल नहीं है, लेकिन एक सूची मान xs' शामिल है।

जब पूरी तरह से मजबूर किया जाता है, तो इसे स्मृति में एक पिछड़े सूचक के साथ एक परिपत्र लिंक्ड-सूची के रूप में दर्शाया जाना चाहिए। तब केवल एक सीमित मात्रा में स्मृति की आवश्यकता होती है।

उदाहरण के लिए प्रयास करें अपना खुद का cycle परिभाषित करना:

cycle' xs = xs ++ cycle' xs

चूंकि जीएचसी स्वचालित संस्मरण नहीं करता है, इसलिए इसे स्मृति में एक असीमित सूची उत्पन्न करनी चाहिए।

दरअसल, जीएचसीआई (अडॉप्टिमाइज्ड) में भी, यह मेरी मशीन पर 70M से कम रहता है

> let list1 :: [Int] ; list1 = cycle [1,2,3]
> list1 !! (4*10^9)
2

जबकि यह फट जाता है (>1GB):

> let list2 :: [Int] ; list2 = cycle' [1,2,3]
> list2 !! (4*10^7)
2
3
chi 12 नवम्बर 2016, 15:39