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

23

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?

Jake
źródło
1
GC przemierza wszystkie struktury mniej więcej w ten sam sposób, ale tylko w bardzo abstrakcyjnym sensie (patrz odpowiedź). Sposób, w jaki konkretnie śledzą, jest o wiele bardziej wyrafinowany niż wskazują na to podstawowe prezentacje, które można znaleźć w podręcznikach. I nie używają rekurencji. Co więcej, z pamięcią wirtualną, złe implementacje pokazują się jako spowolnienie GC, rzadko jako przepełnienie pamięci.
babou
Martwisz się o miejsce potrzebne do śledzenia. Ale co z przestrzenią lub strukturami potrzebnymi do odróżnienia pamięci, która została prześledzona i wiadomo, że jest używana, od pamięci, którą potencjalnie można odzyskać. Może to mieć znaczny koszt pamięci, prawdopodobnie proporcjonalny do wielkości sterty.
babou
Uznałem, że byłoby to zrobione za pomocą bitvectora na obiekcie o rozmiarze większym niż około 16 bajtów, tak więc narzut byłby co najmniej 1000 razy mniejszy.
Jake
Istnieje wiele sposobów, aby to zrobić (patrz odpowiedź), a także można ich użyć do śledzenia, które następnie odpowiedzą na twoje pytanie (do śledzenia można użyć bitvectors lub bitmaps, a nie stosu lub kolejki, które sugerujesz). Nie możesz założyć, że wszystkie obiekty są duże, chyba że masz zamiar marnować miejsce na małe przedmioty, których może być wiele, i wtedy nie powinieneś martwić się o miejsce. Jeśli jesteś w pamięci wirtualnej, przestrzeń często stanowi znacznie mniejszy problem, a problemy są bardzo różne.
babou

Odpowiedzi:

13

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.

Gilles „SO- przestań być zły”
źródło
2
Technika opisana w ostatnim akapicie jest często nazywana „ odwróceniem wskaźnika ”.
Wandering Logic
@WanderingLogic Tak, odwrócenie wskaźnika to sposób, w jaki to nazwałem we własnej odpowiedzi. Wynika to z Deutsch, Schorr i Waite (1967). Jednak niepoprawne jest stwierdzenie, że działa w stałej pamięci: wymaga dodatkowych bitów dla każdej komórki z wskaźnikami , choć można to zmniejszyć za pomocą stosów bitów. Z tego samego powodu zaakceptowana odpowiedź, do której się odwołujesz, nie jest całkiem poprawna ani kompletna. plog2pp
babou
I zostały wykorzystane odwrotność wskaźnika w niestandardowym GC bez potrzeby te dodatkowe bity; sztuczka polegała na użyciu specjalnej reprezentacji obiektów w pamięci w pamięci. Mianowicie, obiekt „nagłówek” znajdował się pośrodku, z polami wskaźnika przed nagłówkiem i polami niebędącymi wskaźnikami po; ponadto wszystkie wskaźniki zostały wyrównane, a nagłówek zawierał pole z zawsze ustawionym najmniej znaczącym bitem. Tak więc, podczas cofania wskaźnika cofania, dotarcie do następnego wskaźnika i zauważenie, że skończyliśmy z obiektem, można było zrobić jednoznacznie bez dodatkowych bitów. Ten układ obsługuje także dziedziczenie OOP.
Thomas Pornin
@ThomasPornin Myślę, że informacje o bitach muszą gdzieś być. Pytanie brzmi gdzie? Czy możemy to omówić na czacie? Muszę teraz wyjść, ale chciałbym przejść do sedna. Czy jest dostępny opis w Internecie?
babou
1
@babou i Thomas, proszę
Gilles „SO- przestań być zły”
11

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.

UV

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:

  • VVV=UT

  • U

  • T

  • H

VUUT

UV

UcVUcUT

UUV=TVHVV

VUUT

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ć.

  • log2pp

  • 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.

  • VTTU

  • 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.

Babou
źródło
4

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.

DW
źródło
Po wywołaniu GC sterty są zwykle pełne. Inną kwestią jest to, że zdarza się, że stos i sterty rosną z obu końców tej samej przestrzeni pamięci ..
babou
4

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:

Przykład algorytmu Cheyneya

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.

Wędrująca logika
źródło
W rzeczywistości, jak wyjaśniono w mojej odpowiedzi, zarówno kolekcja Mark + Sweep, jak i Copy są tym samym algorytmem wykresu abstrakcyjnego. Kolekcja MS i Copy różnią się tylko sposobem, w jaki zestawy zaimplementowane przez algorytm abstrakcyjny są zaimplementowane, a obie rodziny są zawarte, z wieloma wariantami, w pewnej kombinacji technik implementacji zestawu, które opisuję w mojej odpowiedzi. Niektóre warianty GC mieszają MS i Copy w tym samym GC. Oddzielenie MS od kopiowania jest przez niektórych postrzegane jako wygodny sposób na uporządkowanie książek, ale jest to arbitralna i, jak sądzę, nieaktualna wizja.
babou
@babou: Jeśli używasz algorytmu kopiowania, w którym wszystko, co odwiedzasz, zostanie skopiowane (powoli, ale może być przydatne na małych platformach, na których zestaw roboczy nigdy nie jest aż tak duży), niektóre algorytmy mogą być nieco uproszczone, ponieważ można użyć pamięć poprzednio zajmowana przez relokowany obiekt jako notatnik. Można także uzyskać ograniczoną możliwość wykonywania przez inne wątki dostępu do obiektów tylko do odczytu podczas gromadzenia, pod warunkiem, że sprawdza się ważność obiektu przed każdym odczytem i po nim oraz podąża za wskaźnikiem przekazywania, jeśli obiekt został przeniesiony.
supercat
@ supercat Nie jestem pewien, co próbujesz powiedzieć, jaki jest twój zamiar. Niektóre z twoich stwierdzeń wydają się poprawne. Ale nie rozumiem, jak można używać z kosmosu przed zakończeniem cyklu GC (zawiera wskaźniki przekazywania). I do czego byłby scratchpad? Uprość algorytm jak? Jeśli chodzi o wiele wątków mutatora wykonanych podczas GC, jest to w dużej mierze kwestia ortogonalna, choć może mieć poważny wpływ na implementację. Nie będę próbował tego rozwiązać w komentarzach. Powinno to powodować mniej problemów z dostępem tylko do odczytu, ale diabeł tkwi w szczegółach.
babou