W jaki sposób śmieciarze unikają przepełnienia stosu?

Zastanawiałem się więc, jak działają śmieciarki, i pomyślałem o interesującym problemie. Przypuszczalnie śmieciarze muszą przemierzać wszystkie struktury w ten sam sposób. Nie znają pogody, przemierzają połączoną listę, zrównoważone drzewo czy cokolwiek innego. Nie mogą też zużywać zbyt dużo pamięci podczas wyszukiwania. Jednym z możliwych sposobów i jedynym sposobem, w jaki mogę przejść przez WSZYSTKIE struktury, może być przechodzenie przez nie rekurencyjnie tak jak w przypadku drzewa binarnego. To jednak spowodowałoby przepełnienie stosu na połączonej liście, a nawet po prostu źle zrównoważone drzewo binarne. Ale wszystkie języki, w których śmieci były używane, wydają się nie mieć problemu z takimi przypadkami.

W książce o smokach używa ona kolejki „Nie skanowane”. Zasadniczo zamiast przechodzenia przez strukturę rekurencyjnie, po prostu dodaje rzeczy, które muszą zostać oznaczone jako kolejka, a następnie dla każdej rzeczy nieoznaczonej na końcu jest usuwane. Ale czy ta kolejka nie byłaby bardzo duża?

Jak więc śmieciarki przechodzą przez dowolne struktury? W jaki sposób ta technika przejścia zapobiega przepełnieniu?

Zauważ, że nie jestem ekspertem od śmieci. Ta odpowiedź podaje tylko przykłady technik. Nie twierdzę, że jest to reprezentatywny przegląd technik zbierania śmieci.

Nie skanowana kolejka jest częstym wyborem. Kolejka może być duża - potencjalnie tak duża, jak najgłębsza struktura danych. Kolejka jest zwykle przechowywana jawnie, a nie na stosie wątku odśmiecania.

Po przeskanowaniu wszystkich elementów potomnych węzła oprócz jednego, węzeł można usunąć z nieskanowanej kolejki. Jest to w zasadzie optymalizacja ogona. Śmieciarze mogą zawierać heurystykę, aby spróbować skanować najgłębsze dziecko węzła jako ostatnie; na przykład metodą chromatografii gazowej Lispie powinien zeskanować carz consprzed cdr.

Jednym ze sposobów uniknięcia utrzymywania nie skanowanej kolejki jest modyfikacja wskaźników w miejscu, dzięki czemu dziecko tymczasowo wskazuje na element nadrzędny. Jest to technika przechodzenia drzewa o stałej pamięci, która jest używana w kontekstach innych niż śmieciarze. Minusem tej techniki jest to, że podczas gdy GC przemierza strukturę danych, struktura danych jest nieprawidłowa, więc GC musi zatrzymać świat. Nie jest to przełomem: wiele śmieciarek zawiera fazę, która zatrzymuje świat, oprócz faz, które nie pomijają śmieci.

W skrócie : śmieciarze nie używają rekurencji. Kontrolują tylko śledzenie, śledząc zasadniczo dwa zestawy (które mogą się łączyć). Kolejność śledzenia i przetwarzania komórek jest nieistotna, co daje znaczną swobodę implementacji do reprezentowania zbiorów. Dlatego istnieje wiele rozwiązań, które w rzeczywistości są bardzo tanie w użyciu pamięci. Jest to niezbędne, ponieważ GC jest wywoływana właśnie wtedy, gdy na stosie zabraknie pamięci. W przypadku dużych wirtualnych pamięci sytuacja wygląda nieco inaczej, ponieważ nowe strony można łatwo przydzielić, a wrogowi nie jest brak miejsca, ale brak lokalizacji danych .

Zakładam, że rozważasz śledzenie śmieciarek, a nie liczenie referencji, do których twoje pytanie nie wydaje się mieć zastosowania.

$U$$V$

Pierwszą rzeczą, na którą należy zwrócić uwagę, jest to, że wszystkie śledzące GC są oparte na tym samym abstrakcyjnym modelu, opartym na systematycznym badaniu ukierunkowanego wykresu komórek w pamięci dostępnej z programu, gdzie komórki pamięci są wierzchołkami, a wskaźniki są skierowanymi krawędziami. Wykorzystuje do tego następujące zestawy:

• $V$$V$$V=U\cup T$

• $U$

• $T$

• $H$

$V$$U$$U$$T$

$U$$V$

$U$$c$$V$$U$$c$$U$$T$

$U$$U$$V=T$$V$$H-V$$V$

$V$$U$$U$$T$

Pomijam też szczegóły na temat tego, co to jest komórka, czy są one w jednym rozmiarze, czy w wielu, w jaki sposób znajdujemy w nich wskaźniki, jak można je zagęścić, a także wiele innych problemów technicznych, które można znaleźć w książkach i ankietach na temat usuwania śmieci .

$U$

Różnice między znanymi implementacjami dotyczą sposobu, w jaki te zestawy są faktycznie reprezentowane. Zastosowano wiele technik:

• mapa bitowa: Część mapy pamięci jest zachowana dla mapy, która ma jeden bit dla każdej komórki pamięci, którą można znaleźć za pomocą adresu komórki. Bit jest włączony, gdy odpowiednia komórka znajduje się w zestawie zdefiniowanym przez mapę. Jeśli używane są tylko mapy bitowe, potrzebujesz tylko 2 bity na komórkę.

• alternatywnie możesz mieć miejsce na specjalny bit znacznika (lub 2) w każdej komórce, aby go oznaczyć.

• $\log_2 p$$p$

• możesz przetestować orzeczenie dotyczące zawartości komórki i jej wskaźników.

• możesz przenieść komórkę do wolnej części pamięci przeznaczonej dla wszystkich komórek należących do reprezentowanego zestawu.

• $V$$T$$T$$U$

• możesz połączyć te techniki, nawet dla jednego zestawu.

Jak już powiedziano, wszystkie powyższe zostały wykorzystane przez jakiś zaimplementowany moduł wyrzucania elementów bezużytecznych, co może wydawać się dziwne. Wszystko zależy od różnych ograniczeń wdrożenia. I mogą być dość tanie w użyciu pamięci, być może pomocne w przetwarzaniu zasad zamówień, które mogą być dowolnie wybrane do tego celu, ponieważ nie mają znaczenia dla wyniku końcowego.

To, co może wydawać się najdziwniejsze, przenoszenie komórek w nowym obszarze, jest w rzeczywistości bardzo powszechne: nazywa się to zbieraniem kopii. Najczęściej jest używany z pamięcią wirtualną.

Oczywiście nie ma rekurencji, a stos algorytmu mutatora nie musi być używany.

Inną ważną kwestią jest to, że wiele nowoczesnych GC jest implementowanych dla dużych wirtualnych pamięci . Pozyskanie miejsca do wdrożenia i dodatkowej listy lub stosu nie stanowi problemu, ponieważ nowe strony można łatwo przypisać. Jednak w dużych wirtualnych wspomnieniach wrogiem nie jest brak miejsca, ale brak lokalizacji . Następnie struktura reprezentująca zestawy i ich użycie muszą być ukierunkowane na zachowanie lokalizacji struktury danych i wykonywania GC. Problemem nie jest przestrzeń, ale czas. Niewłaściwe implementacje częściej wykazują niedopuszczalne spowolnienie niż przepełnienie pamięci.

Nie podałem odniesień do wielu konkretnych algorytmów wynikających z różnych kombinacji tych technik, ponieważ wydaje się to wystarczająco długie.

Standardowym sposobem uniknięcia przepełnienia stosu jest użycie jawnego stosu (przechowywanego jako struktura danych w stercie). To działa również w tych celach. Śmieciarze często mają listę roboczą przedmiotów, które należy zbadać / przejść, co spełnia tę rolę. Na przykład twoja kolejka „Nie skanowane” jest przykładem dokładnie tego rodzaju wzorca. Kolejka może potencjalnie stać się duża, ale nie powoduje przepełnienia stosu, ponieważ nie jest przechowywana w segmencie stosu. W każdym razie nigdy nie będzie większa niż liczba żywych obiektów w stercie.

W „klasycznych” opisach usuwania śmieci (np. Mark Wilson, „ Uniprocessor Garbage Collection Techniques ”, Int'l Workshop on Memory Management , 1992, ( alternatywny link ) lub w opisie Modern Compiler Implementation Andrew Appela (Cambridge University Press, 1998)), kolektory są klasyfikowane jako „Mark and Sweep” lub „Copying”.

Kolekcjonerzy Mark i Sweep unikają potrzeby dodatkowego miejsca, używając odwrócenia wskaźnika, jak opisano w odpowiedzi @ Gilles. Appel mówi, że Knuth przypisuje algorytm odwrócenia wskaźnika Peterowi Deutschowi, Herbertowi Schorrowi i WM Waite'owi.

Kopiowanie śmieciarek używa tak zwanego algorytmu Cheyneya do wykonywania przejścia w kolejce bez potrzeby dodatkowego miejsca. Algorytm ten został wprowadzony w CJ Cheyney, „A Nonrecursive List Compacting Algorytm”, Comm. ACM , 13 (11): 677–678, 1970.

W kopiującym śmietniku masz fragment pamięci, który próbujesz zebrać, zwany spacją , oraz fragment pamięci, którego używasz dla kopii zwanych spacją . To-space jest zorganizowane jako kolejka ze scanwskaźnikiem wskazującym na najstarszy skopiowany, ale nieskanowany rekord i freewskaźnikiem wskazującym następną wolną pozycję w przestrzeni. Zdjęcie tego z artykułu Wilsona to:

Podczas skanowania każdego elementu w przestrzeni kosmicznej kopiujesz jego elementy potomne z przestrzeni kosmicznej do freewskaźnika w przestrzeni kosmicznej, a następnie zmieniasz wskaźnik na dziecko z przestrzeni kosmicznej na nową kopię dziecka w przestrzeni kosmicznej. Istnieje dodatkowa sztuczka, której należy użyć, gdy struktury danych nie są drzewami (gdy dziecko może mieć więcej niż jednego rodzica). W takim przypadku, gdy kopiujesz dziecko z kosmosu na kosmos, musisz zastąpić starą wersję dziecka wskaźnikiem przekierowania do nowej kopii dziecka. Następnie, jeśli kiedykolwiek zeskanujesz inny wskaźnik do starej wersji dziecka, zdasz sobie sprawę, że został on już skopiowany i nie kopiuj ponownie.