Czy Haskell potrzebuje śmieciarki?


118

Jestem ciekaw, dlaczego implementacje Haskell używają GC.

Nie przychodzi mi do głowy przypadek, w którym GC byłaby konieczna w czystym języku. Czy jest to tylko optymalizacja w celu ograniczenia kopiowania, czy rzeczywiście jest to konieczne?

Szukam na przykład kodu, który przeciekałby, gdyby nie było GC.


14
Możesz uznać tę serię za pouczającą; opisuje, w jaki sposób śmieci są generowane (i następnie zbierane): blog.ezyang.com/2011/04/the-haskell-heap
Tom Crockett

5
wszędzie są odniesienia w czystych językach! po prostu niemodyfikowalne odniesienia.
Tom Crockett

1
@pelotom Odwołania do niezmiennych danych czy niezmiennych odwołań?
Pubby

3
Obie. Fakt, że dane, do których się odwołujemy, są niezmienne, wynika z faktu, że wszystkie odniesienia są niezmienne, aż do końca.
Tom Crockett

4
Z pewnością zainteresuje Cię problem zatrzymania , ponieważ zastosowanie tego rozumowania do alokacji pamięci pomaga zrozumieć, dlaczego zwolnienia alokacji nie można przewidzieć statycznie w przypadku ogólnym . Jednakże istnieją pewne programy, dla których dealokacji można przewidzieć, tak jak są one pewne programy, które mogą być znane do wypowiedzenia bez faktycznego ich uruchamianiu.
Paul R

Odpowiedzi:


218

Jak inni już zauważyli, Haskell wymaga automatycznego , dynamicznego zarządzania pamięcią: automatyczne zarządzanie pamięcią jest konieczne, ponieważ ręczne zarządzanie pamięcią jest niebezpieczne; dynamiczne zarządzanie pamięcią jest konieczne, ponieważ w przypadku niektórych programów czas życia obiektu można określić tylko w czasie wykonywania.

Weźmy na przykład pod uwagę następujący program:

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

W tym programie lista [1..1000]musi być przechowywana w pamięci, dopóki użytkownik nie wpisze „wyczyść”; więc czas życia tego musi być określany dynamicznie, i dlatego konieczne jest dynamiczne zarządzanie pamięcią.

W tym sensie automatyczna alokacja dynamicznej pamięci jest niezbędna, co w praktyce oznacza: tak , Haskell wymaga modułu odśmiecania pamięci, ponieważ czyszczenie pamięci jest automatycznym menedżerem pamięci dynamicznej o najwyższej wydajności.

Jednak...

Chociaż garbage collector jest konieczny, możemy spróbować znaleźć kilka specjalnych przypadków, w których kompilator może użyć tańszego schematu zarządzania pamięcią niż czyszczenie pamięci. Na przykład podane

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

możemy mieć nadzieję, że kompilator wykryje, że x2można bezpiecznie cofnąć przydział przy zwrocie f(zamiast czekać, aż moduł odśmiecania pamięci zwolni przydziałx2 ). Zasadniczo prosimy, aby kompilator przeprowadził analizę ucieczki, aby przekonwertować alokacje na stertę zebraną bez pamięci na alokacje na stosie, jeśli to możliwe.

Nie jest to zbyt nierozsądne, aby poprosić o: kompilator jhc haskell robi to, chociaż GHC tego nie robi. Simon Marlow mówi, że generowany przez GHC garbage collector sprawia, że ​​analiza ucieczki jest w większości niepotrzebna.

jhc w rzeczywistości wykorzystuje wyrafinowaną formę analizy ucieczki znaną jako wnioskowanie o regionie . Rozważać

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

W tym przypadku uproszczona analiza ucieczki zakończyłaby się wnioskiem, że x2ucieka z f(ponieważ jest zwracana w krotce), a zatem x2musi zostać przydzielona na stercie zebranym z pamięci. Z drugiej strony wnioskowanie o regionie jest w stanie wykryć, że x2można to cofnąć, kiedyg zwrotu; chodzi tutaj o to, x2aby alokować w gregionie, a nie w fregionie.

Poza Haskellem

Chociaż wnioskowanie o regionie jest pomocne w niektórych przypadkach, jak omówiono powyżej, wydaje się, że trudno jest go skutecznie pogodzić z leniwą oceną (patrz komentarze Edwarda Kmetta i Simona Peytona Jonesa ). Weźmy na przykład pod uwagę

f :: Integer -> Integer
f n = product [1..n]

Można by pokusić się o przydzielenie listy [1..n] na stosie i zwolnienie jej po fzwróceniu, ale byłoby to katastrofalne: zmieniłoby się fz używania pamięci O (1) (w ramach czyszczenia pamięci) na pamięć O (n).

W latach 90. i na początku 2000 r. Przeprowadzono obszerne prace nad wnioskiem o regiony dla ścisłego języka funkcjonalnego ML. Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg napisali dość czytelną retrospektywę na temat ich pracy nad wnioskiem o regiony, z których większość zintegrowali z kompilatorem MLKit . Eksperymentowali z zarządzaniem pamięcią opartym wyłącznie na regionach (tj. Bez modułu wyrzucania elementów bezużytecznych), a także z zarządzaniem pamięcią opartą na regionach / gromadzeniu elementów bezużytecznych i stwierdzili, że ich programy testowe działają „od 10 razy szybciej do 4 razy wolniej” niż czyste zebrane wersje.


2
Czy Haskell wymaga udostępniania? Jeśli nie, w pierwszym przykładzie możesz przekazać kopię listy (odpowiednio Nothing) do rekurencyjnego wywołania loopi cofnąć przydział starego - bez nieznanego czasu życia. Oczywiście nikt nie chce nie współużytkującej implementacji Haskell, ponieważ jest strasznie powolny w przypadku dużych struktur danych.
nimi

3
Bardzo podoba mi się ta odpowiedź, chociaż moje jedyne zamieszanie dotyczy pierwszego przykładu. Oczywiście, jeśli użytkownik nigdy nie wpisał „wyczyść”, mógłby użyć nieskończonej pamięci (bez GC), ale nie jest to dokładnie przeciek, ponieważ pamięć jest nadal śledzona.
Pubby

3
C ++ 11 ma wspaniałą implementację inteligentnych wskaźników. Zasadniczo wykorzystuje liczenie referencji. Wydaje mi się, że Haskell mógłby porzucić zbieranie śmieci na rzecz czegoś podobnego i dlatego stał się deterministyczny.
intrepidis

3
@ChrisNash - nie działa. Inteligentne wskaźniki wykorzystują liczenie referencyjne pod maską. Zliczanie referencji nie radzi sobie ze strukturami danych z cyklami. Haskell może generować struktury danych z cyklami.
Stephen C

3
Nie jestem pewien, czy zgadzam się z częścią tej odpowiedzi dotyczącą dynamicznej alokacji pamięci. Tylko dlatego, że program nie wie, kiedy użytkownik przestanie tymczasowo zapętlać, nie powinno nadawać mu dynamiki. Zależy to od tego, czy kompilator wie, czy coś wyjdzie poza kontekst. W przypadku Haskella, gdzie jest to formalnie określone przez samą gramatykę języka, kontekst życia jest znany. Jednak pamięć może nadal być dynamiczna, ponieważ wyrażenia listy i typ są generowane dynamicznie w języku.
Timothy Swan

27

Weźmy trywialny przykład. Biorąc to pod uwagę

f (x, y)

musisz (x, y)gdzieś przydzielić parę, zanim zadzwonisz f. Kiedy można zwolnić tę parę? Nie masz pojęcia. Nie można go cofnąć, gdy fzwraca, ponieważ fmogłaby umieścić parę w strukturze danych (np. f p = [p]), Więc czas życia pary może być dłuższy niż powrót z f. Powiedzmy, że para została umieszczona na liście, czy ktokolwiek rozdzieli listę, może cofnąć przydział tej pary? Nie, ponieważ para może być współdzielona (np let p = (x, y) in (f p, p).). Dlatego naprawdę trudno jest stwierdzić, kiedy para może zostać zwolniona.

To samo dotyczy prawie wszystkich przydziałów w Haskell. To powiedziawszy, możliwe jest przeprowadzenie analizy (analiza regionu), która daje górną granicę czasu życia. Działa to dość dobrze w językach ścisłych, ale mniej w językach leniwych (języki leniwe mają tendencję do przeprowadzania o wiele więcej mutacji niż języki ścisłe w implementacji).

Więc chciałbym odwrócić pytanie. Jak myślisz, dlaczego Haskell nie potrzebuje GC. Jak sugerowałbyś alokację pamięci?


18

Twoja intuicja, że ​​ma to coś wspólnego z czystością, ma w sobie trochę prawdy.

Haskell jest uważany za czysty częściowo dlatego, że efekty uboczne funkcji są uwzględniane w sygnaturze typu. Więc jeśli funkcja ma efekt uboczny drukowania czegoś, musi istnieć plikIO gdzieś w jej typie zwracanym.

Ale jest funkcja, która jest używana niejawnie wszędzie w Haskell i której sygnatura typu nie wyjaśnia, co jest w pewnym sensie efektem ubocznym. Mianowicie funkcja, która kopiuje niektóre dane i zwraca dwie wersje. Pod maską może to działać dosłownie, powielając dane w pamięci lub „wirtualnie”, zwiększając dług, który musi zostać spłacony później.

Możliwe jest projektowanie języków z jeszcze bardziej restrykcyjnymi systemami czcionek (czysto „liniowymi”), które nie pozwalają na funkcję kopiowania. Z punktu widzenia programisty w takim języku Haskell wygląda na trochę nieczystego.

W rzeczywistości Clean , krewny Haskella, ma typy liniowe (ściślej: unikalne), co może dać wyobrażenie o tym, jak by to było, gdybyśmy zabronili kopiowania. Ale Clean nadal umożliwia kopiowanie dla „nieunikalnych” typów.

Jest wiele badań w tej dziedzinie i jeśli wystarczająco dobrze wygooglujesz, znajdziesz przykłady czystego kodu liniowego, który nie wymaga czyszczenia pamięci. Znajdziesz wszystkie rodzaje systemów typów, które mogą sygnalizować kompilatorowi, jakiej pamięci można użyć, umożliwiając kompilatorowi wyeliminowanie części GC.

W pewnym sensie algorytmy kwantowe są również czysto liniowe. Każda operacja jest odwracalna, więc żadne dane nie mogą być tworzone ani kopiowane ani niszczone. (Są również liniowe w zwykłym matematycznym sensie).

Interesujące jest również porównanie z Forth (lub innymi językami opartymi na stosie), które mają wyraźne operacje DUP, które wyjaśniają, kiedy zachodzi duplikacja.

Innym (bardziej abstrakcyjnym) sposobem myślenia o tym jest zauważenie, że Haskell jest zbudowany z prostego rachunku lambda, który jest oparty na teorii zamkniętych kategorii kartezjańskich i że takie kategorie są wyposażone w funkcję diagonalną diag :: X -> (X, X). Język oparty na innej kategorii kategorii może nie mieć czegoś takiego.

Ale ogólnie programowanie czysto liniowe jest zbyt trudne, aby było użyteczne, więc decydujemy się na GC.


3
Odkąd napisałem tę odpowiedź, popularność języka programowania Rust znacznie wzrosła. Warto więc wspomnieć, że Rust używa liniowego systemu kontroli dostępu do pamięci i warto się temu przyjrzeć, jeśli chcesz zobaczyć pomysły, o których wspomniałem, zastosowane w praktyce.
sigfpe

14

Standardowe techniki implementacji zastosowane w Haskell w rzeczywistości wymagają GC bardziej niż większość innych języków, ponieważ nigdy nie mutują poprzednich wartości, zamiast tego tworzą nowe, zmodyfikowane wartości na podstawie poprzednich. Ponieważ oznacza to, że program stale alokuje i wykorzystuje więcej pamięci, w miarę upływu czasu duża liczba wartości zostanie odrzucona.

Dlatego programy GHC mają zwykle tak wysokie całkowite wartości alokacji (od gigabajtów do terabajtów): stale alokują pamięć i tylko dzięki wydajnemu GC odzyskują ją przed wyczerpaniem.


2
„nigdy nie zmieniają poprzednich wartości”: możesz sprawdzić haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011/Takano , chodzi o eksperymentalne rozszerzenie GHC, które ponownie wykorzystuje pamięć.
gfour

11

Jeśli język (dowolny język) umożliwia dynamiczne przydzielanie obiektów, istnieją trzy praktyczne sposoby radzenia sobie z zarządzaniem pamięcią:

  1. Język pozwala tylko na przydzielenie pamięci na stosie lub podczas uruchamiania. Jednak te ograniczenia poważnie ograniczają rodzaje obliczeń, które może wykonywać program. (W praktyce. Teoretycznie można emulować dynamiczne struktury danych w (powiedzmy) Fortranie, przedstawiając je w dużej tablicy. Jest to STRASZNE ... i nie dotyczy tej dyskusji.)

  2. Język może zapewnić wyraźne free lub disposemechanizm. Ale to zależy od programisty, aby zrobić to dobrze. Każdy błąd w zarządzaniu pamięcią może spowodować wyciek pamięci ... lub gorzej.

  3. Język (a ściślej implementacja języka) może zapewnić automatyczny menedżer pamięci dla dynamicznie przydzielanej pamięci; czyli jakaś forma garbage collectora.

Jedyną inną opcją jest to, aby nigdy nie odzyskiwać pamięci przydzielonej dynamicznie. Nie jest to praktyczne rozwiązanie, z wyjątkiem małych programów wykonujących małe obliczenia.

Stosując to do Haskell, język nie ma ograniczenia 1. i nie ma ręcznej operacji zwalniania przydziału zgodnie z 2. Dlatego, aby być użytecznym do rzeczy nietrywialnych, implementacja Haskella musi zawierać moduł odśmiecania pamięci .

Nie przychodzi mi do głowy przypadek, w którym GC byłaby konieczna w czystym języku.

Przypuszczalnie masz na myśli czysty język funkcjonalny.

Odpowiedź jest taka, że ​​GC jest wymagany pod maską, aby odzyskać obiekty sterty, które język MUSI utworzyć. Na przykład.

  • Czysta funkcja musi tworzyć obiekty sterty, ponieważ w niektórych przypadkach musi je zwrócić. Oznacza to, że nie można ich przydzielić na stosie.

  • Fakt, że mogą istnieć cykle (wynikające let recna przykład z a ) oznacza, że ​​podejście zliczania referencji nie będzie działać dla obiektów sterty.

  • Są też zamknięcia funkcji ... których również nie można zaalokować na stosie, ponieważ mają czas życia, który jest (zazwyczaj) niezależny od ramki stosu, w której zostały utworzone.

Szukam na przykład kodu, który przeciekałby, gdyby nie było GC.

Prawie każdy przykład obejmujący zamknięcia lub struktury danych w kształcie wykresu przeciekłby w takich warunkach.


2
Jak myślisz, dlaczego Twoja lista opcji jest wyczerpująca? ARC w celu C, wnioskowanie o regionie w MLKit i DDC, wyrzucanie elementów bezużytecznych w czasie kompilacji w Mercury - wszystkie nie pasują do tej listy.
Dee Mon,

@DeeMon - wszystkie pasują do jednej z tych kategorii. Jeśli uważasz, że tak nie jest, to dlatego, że zbyt ciasno rysujesz granice kategorii. Kiedy mówię „jakaś forma zbierania śmieci”, mam na myśli dowolny mechanizm w którym pamięć jest odzyskiwana automatycznie.
Stephen C,

1
C ++ 11 używa inteligentnych wskaźników. Zasadniczo wykorzystuje liczenie referencji. Jest deterministyczna i automatyczna. Bardzo chciałbym zobaczyć implementację Haskell używającą tej metody.
intrepidis

2
@ChrisNash - 1) To nie zadziała. Odwołanie do odzyskiwania bazy zliczeń powoduje wycieki danych, jeśli występują cykle ... chyba że możesz polegać na kodzie aplikacji, aby przerwać cykle. 2) Powszechnie wiadomo (osobom, które badają te rzeczy), że zliczanie odniesień działa słabo w porównaniu z nowoczesnym (prawdziwym) odśmiecaczem.
Stephen C

@DeeMon - poza tym, zobacz odpowiedź Reinerpa na temat tego, dlaczego wnioskowanie o regionie nie byłoby praktyczne w przypadku Haskella.
Stephen C

8

Odśmiecacz nigdy nie jest potrzebny, pod warunkiem, że masz wystarczającą ilość pamięci. Jednak w rzeczywistości nie mamy nieskończonej pamięci, więc potrzebujemy jakiejś metody, aby odzyskać pamięć, która nie jest już potrzebna. W nieczystych językach, takich jak C, możesz wyraźnie stwierdzić, że masz już trochę pamięci, aby ją zwolnić - ale jest to operacja mutacji (pamięć, którą właśnie uwolniłeś, nie jest już bezpieczna do czytania), więc nie możesz użyć tego podejścia w czysty język. Więc albo w jakiś sposób statycznie przeanalizuj, gdzie możesz zwolnić pamięć (prawdopodobnie niemożliwe w ogólnym przypadku), wyciek z pamięci jak sito (działa świetnie, dopóki się nie skończy), albo użyj GC.


To wyjaśnia, dlaczego generalnie GC jest niepotrzebne, ale jestem bardziej zainteresowany w szczególności Haskellem.
Pubby

10
Jeśli GC jest teoretycznie niepotrzebne w ogóle, to po prostu wynika z tego, że teoretycznie jest również niepotrzebne dla Haskella.
ehird

@ehird Chciałem powiedzieć , że to konieczne , myślę, że mój moduł sprawdzania pisowni odwrócił znaczenie.
Pubby

1
Ehird komentarz nadal obowiązuje :-)
Paul R

2

GC to „must have” w czystych językach FP. Czemu? Operacje przydzielone i bezpłatne są nieczyste! Drugim powodem jest to, że niezmienne, rekurencyjne struktury danych potrzebują GC do istnienia, ponieważ łączenie wsteczne tworzy zawiłe i niemożliwe do utrzymania struktury dla ludzkiego umysłu. Oczywiście backlinkowanie jest błogosławieństwem, ponieważ kopiowanie struktur, które z niego korzystają, jest bardzo tanie.

W każdym razie, jeśli mi nie wierzysz, po prostu spróbuj zaimplementować język FP, a zobaczysz, że mam rację.

EDYCJA: zapomniałem. Lenistwo jest PIEKŁEM bez GC. Nie wierzysz mi? Po prostu spróbuj bez GC, na przykład w C ++. Zobaczysz ... rzeczy


1

Haskell nie jest surowym językiem programowania, ale większość implementacji używa wywołania według potrzeby (lenistwa) do implementacji braku ścisłości. W wywołaniu według potrzeby oceniasz rzeczy tylko wtedy, gdy zostaną osiągnięte w czasie działania przy użyciu mechanizmu „thunks” (wyrażeń, które czekają na ocenę, a następnie nadpisują się, pozostając widocznymi, aby ich wartość mogła zostać ponownie użyta w razie potrzeby).

Tak więc, jeśli leniwie zaimplementujesz swój język za pomocą thunks, odłożyłeś wszelkie rozumowania dotyczące czasu życia obiektów do ostatniej chwili, czyli czasu wykonania. Ponieważ teraz nie wiesz nic o wcieleniach, jedyne, co możesz rozsądnie zrobić, to zbieranie śmieci ...


1
W niektórych przypadkach analiza statyczna może wstawić do tych elementów kod, który zwalnia niektóre dane po ocenie tego elementu. Dealokacja nastąpi w czasie wykonywania, ale nie jest to GC. Jest to podobne do pomysłu liczenia odwołań inteligentnych wskaźników w C ++. Rozumowanie o okresach istnienia obiektów ma miejsce w czasie wykonywania, ale nie jest używany żaden GC.
Dee Mon,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.