Warum in GHC direkt importierten Funktionen mit Funktionen so viel unterscheiden mich mit dem Quellcode von GHC Bibliotheken

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 kopiert schreiben: Diese filter aus GHC ‚s Bibliothek kopiert, aber warum verbraucht es eine wachsende Anzahl von Speicher in Kontrast zu der direkt importiert filter, die eine konstante Anzahl von Speicher verbraucht.

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

Problem2: Diese filter aus GHC ‚s Bibliothek kopiert, aber warum es verbraucht eine wachsende Anzahl von Speicher wie die direkt elem verwendet, die auch eine wachsende Anzahl von Speichern mit im Gegensatz verbraucht die direkt importiert filter.

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

GHC Version: 7.4.2 OS: Ubuntu 12.10 mit -O2 Zusammengestellt

Als die oben filter und elem 's Definitionen implizieren sowohl p = filter (==1000000000000) [0..] und s = 1000000000000 `elem` [0..]' s [0..] sollte Müll allmählich gesammelt werden, um zu optimieren. Aber sowohl als auch s verbrauchen eine wachsende Anzahl von Speicher. Und r, die mit der direkt importierten filter definiert ist, verbraucht eine konstante Anzahl von Arbeitsspeicher.

Meine Frage ist, warum sich direkt importierte Funktionen in GHC so sehr durch Funktionen unterscheiden, die ich mit dem aus GHC Libraries kopierten Quellcode schreibe. Ich habe mich gefragt, ob etwas mit GHC nicht stimmt.

Ich habe eine weitere Frage: Der obige Code ist abstrahiert von einem Projekt, das ich geschrieben habe, und das Projekt steht auch vor dem Problem "verbraucht eine wachsende Anzahl von Speicher, die in der Theorie Müll gesammelt werden sollte". Also möchte ich wissen, dass es eine Möglichkeit gibt herauszufinden, welche Variable in GHC so viel Speicher beansprucht.

Danke für Ihre Lektüre.

Answer 1

Die Ursache für den Speicherverbrauch in ghci ist nicht der Code filter oder elem. (Obwohl die Rewrite-Regel für filter in GHC.List es ein wenig besser macht in der Regel.)

Schauen wir uns an (Teil) der Kern ghc-7.4.2 hergestellt mit -O2 (-ddump-simpl). Zunächst für r, mit 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.p3 ist 0 :: Integer und Has.p2 ist 1 :: Integer. Die Rewrite-Regeln (für filter und enumDeltaInteger) verwandelten sie in (mit kürzeren Namen)

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 

das wahrscheinlich etwas effizienter sein könnte, wenn fun wurde inlined, aber der Punkt ist, dass die Liste filter ed doesn‘zu sein Wenn es als solches existiert, ist es weggewachsen.

Für p auf der anderen Seite, ohne die Rewrite-Regel (n), so erhalten wir

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 

ein Top-Level-CAF für die Liste [0 .. ] (Has.p1) und Has.filter-(== 1000000000000) und die Liste angewandt.

Also diese erstellt die eigentliche Liste zu filtern - also ist es etwas weniger effizient.

Aber normalerweise (Ausführen einer kompilierten Binärdatei), das ist kein Problem in Bezug auf Speicherverbrauch, da die Liste Müll gesammelt wird, wie es verbraucht wird. Aus Gründen, die über mich hinausgehen, hält Ghci die Liste [0 .. ] bei der Auswertung p oder s (aber das hat seine eigene Kopie von [0 .. ], so ist es nicht unerwünschtes Teilen hier), wie aus dem -hT Haufen Profil (Auswertung . s, so gibt es nur eine mögliche Quelle für die Liste Zellen GHCI mit +RTS -M300M -hT -RTS aufgerufen, so kurz nach der Speicherauslastung erreicht 300M, beendet GHCI):

die Ursache für den Speicherverbrauch in GHCI so ist die Hardcodierung der zu filternden Liste. Wenn Sie Has.filter mit einer Liste verwenden, die an der Eingabeaufforderung angegeben wird, ist die Speicherauslastung wie erwartet konstant.

Ich bin mir nicht sicher, ob ghci, das die Liste [0 .. ] beibehält, ein Fehler oder ein beabsichtigtes Verhalten ist.