यह हास्केल प्रोग्राम इतनी मेमोरी आवंटित क्यों कर रहा है?

Question

मन निम्नलिखित हास्केल कार्यक्रम:

-- (^) allocs memory so we define it using the native (**) 
pow :: Int -> Int -> Int 
pow x y = floor $ fromIntegral x ** fromIntegral y 

-- tail recursive, div and mod are native, I believe, so, no alloc 
isPalindrome :: Int -> Bool 
isPalindrome x = go (pow 10 (floor $ logBase 10 $ fromIntegral x)) x 
    where go m x = x <= 0 || div x m == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10) 

-- go is tail recursive too... no obvious allocation here 
wanderer :: Int -> Int 
wanderer n = go 0 (pow 10 n - 1) (pow 10 n - 1) where 
    go p x y | p > 0 && div p x >= pow 10 n = p     
    go p x y | p > 0 && y < div p x || y < x = go p (x-1) (pow 10 n - 1) 
    go p x y | isPalindrome (x*y)   = go (x*y) x (y-1) 
    go p x y         = go p x (y-1)  

main = print . wanderer $ 8 

यह रूपरेखा, हम पाते हैं:

Fri May 8 03:36 2015 Time and Allocation Profiling Report (Final) 

     aff +RTS -p -RTS 

    total time =  7.34 secs (7344 ticks @ 1000 us, 1 processor) 
    total alloc = 6,487,919,472 bytes (excludes profiling overheads) 

COST CENTRE  MODULE %time %alloc 

isPalindrome Main  41.9 18.5 
isPalindrome.go Main  22.6 1.4 
wanderer.go  Main  20.0 67.8 
pow    Main  15.5 12.3 


                   individual  inherited 
COST CENTRE   MODULE     no.  entries %time %alloc %time %alloc 

MAIN     MAIN      47   0 0.0 0.0 100.0 100.0 
main     Main      95   0 0.0 0.0  0.0 0.0 
CAF:main1   Main      92   0 0.0 0.0  0.0 0.0 
    main    Main      94   1 0.0 0.0  0.0 0.0 
CAF:main2   Main      91   0 0.0 0.0 100.0 100.0 
    main    Main      96   0 0.0 0.0 100.0 100.0 
    wanderer   Main      98   1 0.0 0.0 100.0 100.0 
    pow    Main     101   1 0.0 0.0  0.0 0.0 
    wanderer.go  Main      99 49995002 20.0 67.8 100.0 100.0 
    isPalindrome  Main     102 49985002 41.9 18.5 80.0 32.2 
     pow    Main     104 49985002 15.5 12.3 15.5 12.3 
     isPalindrome.go Main     103 52207117 22.6 1.4 22.6 1.4 
    pow    Main     100   1 0.0 0.0  0.0 0.0 
    pow    Main      97   2 0.0 0.0  0.0 0.0 
CAF     GHC.Conc.Signal   85   0 0.0 0.0  0.0 0.0 
CAF     GHC.IO.Encoding   78   0 0.0 0.0  0.0 0.0 
CAF     GHC.IO.Encoding.Iconv 76   0 0.0 0.0  0.0 0.0 
CAF     GHC.IO.Handle.FD   69   0 0.0 0.0  0.0 0.0 
CAF     GHC.Event.Thread   55   0 0.0 0.0  0.0 0.0 

जहां तक ​​मुझे पता है कर रहा हूँ, ऐसा लगता है जैसे मेरी सभी कार्यों पुनरावर्ती पूंछ कर रहे हैं और उन प्रस्तावना कार्य हैं एएसएम संचालन। फिर भी यह सरल कार्यक्रम स्मृति के 7 जीबी आवंटित करता है। सभी आवंटन कहां से आ रहे हैं?

Answer 1

आवंटन isPalindrome में go से आ रही है:

go m x = x <= 0 || div x m == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10) 

हम दाहिने हाथ की ओर एक || है। || के शॉर्ट-सर्किट अर्थशास्त्र आलसी मूल्यांकन के माध्यम से महसूस किया जाता है। जीएचसी देखता है कि m तर्क अप्रयुक्त है अगर x <= 0True का मूल्यांकन करता है, इसलिए यह m को अनबॉक्स नहीं करता है, जिससे यह असम्पीडित रहता है। बेशक, इस मामले में हम m को अनबॉक्सिंग से बेहतर कर रहे हैं, तो चलिए इसे करते हैं।

{-# LANGUAGE BangPatterns #-} 
go !m x = ... 

अब ghc -O2 और +RTS -s साथ:

 52,016 bytes allocated in the heap 
     3,408 bytes copied during GC 
     44,312 bytes maximum residency (1 sample(s)) 
     17,128 bytes maximum slop 
      1 MB total memory in use (0 MB lost due to fragmentation) 

Answer 2

GHC कभी कभी कहा गया है "आवंटन से मूल्यांकन"। और अधिक महत्वपूर्ण बात यह है कि स्मृति को बनाए रखा गया है या नहीं। बस कोड को नजरअंदाज कर, मुझे कोई स्पष्ट स्थान रिसाव दिखाई नहीं दे रहा है।

क्या आपने runtime stats पर देखा है? इसके लिए आपको प्रोफाइलिंग लाइब्रेरी की भी आवश्यकता नहीं है। जीसी बाइट्स की प्रतिलिपि बनाई गई है, और अधिकतम निवास ... यहां से अधिकतर मैं तुलनात्मक रूप से बहुत छोटा होने का अनुमान लगाता हूं।

पहली-आदेश चिंताओं से परे, इनमें से अधिकतर आवंटन संभवतः बंद हो जाते हैं। क्या आप सख्तता विश्लेषक चलाने के लिए ghc -O संकलित कर रहे हैं? यहां तक ​​कि यदि आप हैं, तो मुझे यकीन नहीं है कि सख्तता विश्लेषक के लिए पहले go फ़ंक्शन या x और y तर्कों के दूसरे go में तर्क के लिए बंद आवंटन को समाप्त करने में सक्षम होगा। मेरा अनुमान है कि बैंग पैटर्न यहां आपके आवंटन को बहुत कम कर देंगे।

पूंछ रिकर्सन के व्यावहारिक परिणाम सख्त भाषा की तुलना में हास्केल में बहुत अलग हैं; इसलिए यदि आप सख्त भाषा में पूंछ कॉल से परिचित हैं, तो आपके अंतर्ज्ञान संभवतः बंद हैं।