Dlaczego bezpośrednio importowane funkcje w GHC różnią się tak bardzo z funkcji piszę z kodem źródłowym skopiowane z GHC Bibliotek

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: Ten filter jest kopiowany z biblioteki GHC „s, ale dlaczego zużywa coraz większej liczby pamięci w kontrast z bezpośrednio zaimportowanym filter, który zużywa stałą liczbę pamięci.

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

problem2: Ten filter jest kopiowany z biblioteki GHC „s, ale dlaczego zużywa coraz większej liczby pamięci jak bezpośrednio stosowanego elem, który również zużywa coraz większej liczby pamięci w przeciwieństwie bezpośrednio zaimportowany filter.

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

GHC wersja: 7.4.2 OS: Ubuntu 12.10 Zestawione z -O2 do optymalizacji

jak powyżej filter i elem 'definicje s oznaczać zarówno p = filter (==1000000000000) [0..] i s = 1000000000000 `elem` [0..]' s [0..] śmieci powinny być zbierane stopniowo. Ale zarówno p, jak i s zużywa coraz większą ilość pamięci. I r, który jest zdefiniowany za pomocą bezpośrednio importowanego filter, zużywa stałą liczbę pamięci.

Moje pytanie brzmi: dlaczego funkcje importowane bezpośrednio w GHC różnią się tak bardzo funkcjami, które piszę z kodem źródłowym skopiowanym z bibliotek GHC. Zastanawiałem się, czy coś jest nie tak z GHC?

Mam kolejne pytanie: Powyższy kod jest pobierany z projektu, który napisałem, a projekt napotyka również problem "pochłania coraz większą ilość pamięci, która powinna być zbiorem odpadów w teorii". Więc chcę wiedzieć, że istnieje sposób na znalezienie, która zmienna zajmuje tyle pamięci w GHC.

Dzięki za przeczytanie.

Answer 1

Przyczyną zużycia pamięci w ghci nie jest kod filter lub elem. (Mimo, że reguła przepisywania dla filter w GHC.List sprawia, że ​​trochę lepiej zwykle).

Spójrzmy (części) rdzeń ghc-7.4.2 produkowane -O2 (-ddump-simpl). Pierwszy dla r korzystając 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 jest 0 :: Integer i Has.p2 jest 1 :: Integer. Reguły przepisywania (dla filter i enumDeltaInteger) przekształcił go (z krótszymi nazwami)

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 

który prawdopodobnie może być nieco bardziej wydajne jeśli fun został inlined, ale chodzi o to, że lista będzie filter ed robi” T istnieje jako taki, został zlikwidowany.

Dla p Z drugiej strony, bez reguły (ów) przepisywanie otrzymujemy

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 

CAF najwyższego poziomu na liście [0 .. ] (Has.p1), a Has.filter stosowane do (== 1000000000000) i listy.

W ten sposób tworzy się rzeczywistą listę do przefiltrowania - dlatego jest nieco mniej wydajna.

Ale normalnie (uruchamianie skompilowanego pliku binarnego) nie stanowi problemu pod względem zużycia pamięci, ponieważ lista jest czyszczona podczas jej pobierania. Jednak z powodów, które są poza mną, ghci zachowuje listę [0 .. ] wokół przy ocenie p lub s (ale ma swoją własną kopię [0 .. ], więc nie jest to niechciane udostępnianie tutaj), jak można zebrać z profilu sterty -hT (oceniając . s, więc istnieje tylko jedno możliwe źródło komórek lista ghci wywołany z +RTS -M300M -hT -RTS, więc wkrótce po wykorzystaniu pamięci osiągnął 300M, ghci zakończony):

więc przyczyną zużycia pamięci w ghci jest kodowanie na liście, która ma być filtrowana. Jeśli użyjesz Has.filter z listą podaną w monicie, użycie pamięci będzie stałe zgodnie z oczekiwaniami.

Nie jestem pewien, czy ghci zachowujący listę [0 .. ] jest błędem lub zamierzonym zachowaniem.