क्यों GHC में सीधे आयात कार्यों कार्यों मैं GHC पुस्तकालय से नकल स्रोत कोड के साथ लिखने के साथ इतना कुछ अलग

Question

module Has (r,p,s) where 

import Prelude ((==),Bool(..),otherwise,(||),Eq) 
import qualified Data.List as L 

filter :: (a -> Bool) -> [a] -> [a] 
filter _pred [] = [] 
filter pred (x:xs) 
    | pred x   = x : filter pred xs 
    | otherwise  = filter pred xs 

problem1: यह filterGHC के पुस्तकालय से कॉपी किया जाता है, लेकिन क्यों यह में स्मृति की बढ़ती संख्या की खपत के साथ विपरीत सीधे आयातित filter, जो स्मृति की निरंतर संख्या का उपभोग करता है।

elem :: (Eq a) => a -> [a] -> Bool 
elem _ []  = False 
elem x (y:ys) = x==y || elem x ys 

problem2: यह filterGHC के पुस्तकालय से कॉपी किया जाता है, लेकिन क्यों यह स्मृति की तरह सीधे elem इस्तेमाल किया की बढ़ती संख्या, जो भी स्मृति की बढ़ती संख्या के विपरीत के साथ की खपत की खपत सीधे आयातित filter।

r = L.filter (==1000000000000) [0..] 
p = filter (==1000000000000) [0..] 
s = 1000000000000 `elem` [0..] 

GHC संस्करण: 7.4.2 ओएस: उबंटू 12.10 -O2 साथ संकलित

अनुकूलन करने के लिए ऊपर filter के रूप में और elem की परिभाषाओं दोनों p = filter (==1000000000000) [0..] दिखाते हैं और s = 1000000000000 `elem` [0..] के [0..] कचरा धीरे-धीरे एकत्र किया जाना चाहिए। लेकिन p और s दोनों मेमोरी की बढ़ती संख्या का उपभोग करते हैं। और r जिसे सीधे आयातित filter के साथ परिभाषित किया गया है, स्मृति की निरंतर संख्या का उपभोग करता है।

मेरा सवाल यह है कि जीएचसी में सीधे आयातित कार्यों को जीएचसी पुस्तकालयों से कॉपी किए गए स्रोत कोड के साथ लिखने वाले कार्यों के साथ इतना अलग है। मुझे आश्चर्य हुआ कि जीएचसी के साथ कुछ गड़बड़ है?

मेरे पास एक और सवाल है: उपर्युक्त कोड एक प्रोजेक्ट से निकला हुआ है, और परियोजना को "स्मृति में बढ़ती कचरा होने की समस्या" का सामना करना पड़ता है। तो मैं जानना चाहता हूं कि यह पता लगाने का कोई तरीका है कि जीएचसी में कौन सी चरम इतनी मेमोरी लेती है।

आपके पढ़ने के लिए धन्यवाद।

Answer 1

ghci में स्मृति खपत का कारण filter या elem का कोड नहीं है। (हालांकि GHC.List में filter के लिए पुनर्लेखन नियम बनाता है थोड़ा बेहतर आमतौर पर।)

के (का हिस्सा) कोर GHC-7.4.2 -O2 (-ddump-simpl) के साथ उत्पादन पर नजर डालते हैं। r के लिए सबसे पहले, GHC.List.filter का उपयोग कर:

Has.r1 
    :: GHC.Integer.Type.Integer 
    -> [GHC.Integer.Type.Integer] -> [GHC.Integer.Type.Integer] 
[GblId, 
Arity=2, 
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True, 
     ConLike=True, Cheap=True, Expandable=True, 
     Guidance=IF_ARGS [0 0] 60 30}] 
Has.r1 = 
    \ (x_awu :: GHC.Integer.Type.Integer) 
    (r2_awv :: [GHC.Integer.Type.Integer]) -> 
    case GHC.Integer.Type.eqInteger x_awu Has.p5 of _ { 
     GHC.Types.False -> r2_awv; 
     GHC.Types.True -> 
     GHC.Types.: @ GHC.Integer.Type.Integer x_awu r2_awv 
    } 

Has.r :: [GHC.Integer.Type.Integer] 
[GblId, 
Str=DmdType, 
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False, 
     ConLike=False, Cheap=False, Expandable=False, 
     Guidance=IF_ARGS [] 40 0}] 
Has.r = 
    GHC.Enum.enumDeltaIntegerFB 
    @ [GHC.Integer.Type.Integer] Has.r1 Has.p3 Has.p2 

Has.p30 :: Integer है, और Has.p21 :: Integer है। पुनर्लेखन नियम (filter और enumDeltaInteger के लिए) (छोटा नाम के साथ)

r = go fun 0 1 
    where 
    go foo x d = x `seq` (x `foo` (go foo (x+d) d)) 

fun n list 
    | n == 1000000000000 = n : list 
    | otherwise   = list 

जो शायद थोड़ा और अधिक कुशल हो सकता है अगर fun inlined गया था में बदल गया है, लेकिन मुद्दा यह है कि सूची हो रहा है filter एड नहीं करता ' इस तरह अस्तित्व में नहीं है, यह दूर हो गया था।

p दूसरी ओर के लिए, पुनर्लेखन नियम (रों) के बिना, हम सूची [0 .. ] (Has.p1) के लिए

Has.p1 :: [GHC.Integer.Type.Integer] 
[GblId, 
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False, 
     ConLike=False, Cheap=False, Expandable=False, 
     Guidance=IF_ARGS [] 30 0}] 
Has.p1 = GHC.Enum.enumDeltaInteger Has.p3 Has.p2 

Has.p :: [GHC.Integer.Type.Integer] 
[GblId, 
Str=DmdType, 
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False, 
     ConLike=False, Cheap=False, Expandable=False, 
     Guidance=IF_ARGS [] 30 0}] 
Has.p = Has.filter @ GHC.Integer.Type.Integer Has.p4 Has.p1 

एक शीर्ष स्तर सीएएफ मिलता है, और Has.filter(== 1000000000000) और सूची के लिए आवेदन किया।

तो यह फ़िल्टर करने के लिए वास्तविक सूची बनाता है - इस प्रकार यह कुछ हद तक कम कुशल है।

लेकिन आम तौर पर (एक संकलित बाइनरी चला रहा है), यह स्मृति खपत के मामले में कोई समस्या नहीं है, क्योंकि सूची उपभोग के रूप में एकत्रित कचरा है। हालांकि, मेरे बाहर होने वाले कारणों के लिए, ghci [0 .. ] को p या s का मूल्यांकन करते समय सूची में रखता है (लेकिन इसकी अपनी प्रति [0 .. ] है, इसलिए यह अवांछित साझाकरण नहीं है), जैसा कि -hT ढेर प्रोफ़ाइल से मूल्यांकन किया जा सकता है (मूल्यांकन । s, इसलिए केवल एक संभावित स्रोत स्मृति के उपयोग पर पहुंच गया 300 मिलियन के बाद सूची कोशिकाओं GHCi +RTS -M300M -hT -RTS के साथ आमंत्रण के लिए वहाँ है, तो शीघ्र ही, GHCi समाप्त):

तो GHCi में स्मृति की खपत का कारण है सूची के हार्डकोडिंग फ़िल्टर करने के लिए। यदि आप प्रॉम्प्ट पर आपूर्ति की गई सूची के साथ Has.filter का उपयोग करते हैं, तो स्मृति उपयोग अपेक्षा के अनुरूप स्थिर होता है।

मुझे यकीन नहीं है कि ghci सूची [0 .. ] एक बग या इच्छित व्यवहार है या नहीं।