Czym różni się odśmiecanie śmieci w czystych językach?

26

W czystym języku, takim jak Haskell, wszystkie dane są niezmienne i nie można w żaden sposób zmieniać istniejących struktur danych. Ponadto wiele algorytmów niezmiennych danych i wzorców programowania funkcjonalnego generuje duże ilości śmieci z natury ( mapna przykład łańcuchy tworzenia list pośrednich).

Jakie strategie i techniki stosują śmieciarze w obliczu czystości, których inaczej by nie zrobili? Co działa bardzo dobrze w GC języka nieczystego, który nie działa w czystym kontekście? Jakie inne nowe problemy stwarzają czyste języki dla GC?

Jacek
źródło

Odpowiedzi:

13

Obecna implementacja ghc wykorzystuje strategię, która działa tylko dlatego, że język jest funkcjonalny, a dane są niezmienne: ponieważ żadna zmienna nie może być nigdy zmieniona, aby odnosić się do czegokolwiek nowszego, obiekty przechowują tylko odniesienia do starszych obiektów, więc uruchamia generacyjny moduł czyszczenia pamięci ; ponieważ obiekt, do którego odnosi się wyższa generacja, nie może zostać usunięty, dopóki ta generacja nie będzie GCd, z niecierpliwością promuje obiekty do wyższych generacji; a ponieważ nic nie zmieni odniesień, podczas gdy GC je zamiata, może działać równolegle.

Oto artykuł ze szczegółami .

Davislor
źródło
4
Szybka promocja opiera się na lenistwie - aktualizacja złotówki w starym pokoleniu może stworzyć wskaźnik dla nowego pokolenia, ale złomki są tylko mutowane tylko raz, więc wystarczy z niecierpliwością promować młodego obiektu. Inne referencje od starych do młodych (np. Z tablic zmiennych) są śledzone przy użyciu „zapamiętanych zestawów”, które są również używane w przypadku niepowodzenia szybkiej promocji.
Jon Purdy,
1

W czystym języku, takim jak Haskell, wszystkie dane są niezmienne i nie można w żaden sposób zmieniać istniejących struktur danych

W rzeczywistości nie jest to ogólnie prawdą. Czyste języki używają nie ścisłej (leniwej) oceny, więc ocena potencjalnie wszystkich podwyrażeń jest odraczana. Nieocenione wyrażenia są na ogół przypisywane do sterty jako „thunk”. W razie potrzeby wyrażenie jest oceniane, a kolec jest mutowany w wynikową wartość.

Jakie strategie i techniki stosują śmieciarze w obliczu czystości, których inaczej by nie zrobili?

Jedyne, co mogę wymyślić, to czarne dziury . Nie przypominam sobie, aby widziałem coś nowego po stronie GC w pracach naukowych Haskell.

Co działa bardzo dobrze w GC języka nieczystego, który nie działa w czystym kontekście?

Bariera zapisu GC. Zanieczyszczone języki mają tendencję do pisania wskaźników na stosie o wiele częściej, więc ich bariery zapisu są bardziej zoptymalizowane.

Inne algorytmy GC, takie jak region znacznika, są znacznie bardziej opłacalne w kontekście nieczystych języków, ponieważ mogą mieć znacznie niższe wskaźniki alokacji niż języki czyste.

Jakie inne nowe problemy stwarzają czyste języki dla GC?

Czyste języki są bardzo rzadkie, więc jest o wiele mniej danych o tym, jak czyste programy wykorzystują pamięć, dlatego zaczynasz w gorszej sytuacji, gdy próbujesz napisać GC dla czystego języka.

Jon Harrop
źródło
„W razie potrzeby wyrażenie jest oceniane, a kolec jest mutowany w wynikową wartość”. Jest to wewnętrzny szczegół implementacji w odniesieniu do użytkownika Haskell. Nie można obserwować mutacji, więc nie jest to mutacja z punktu widzenia użytkownika.
Jack
Dodatkowo jest całkowicie możliwe, aby czysty język był ścisły - patrz Idris na przykład.
Jack