Metody realizacji języków programowania/MRJP Wykład 9

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl)

Odśmiecanie z punktu widzenia programisty

Obiekty i referencje

Relacja między obiektami a zmiennymi w różnych językach programowania jest najczęściej dwojakiego rodzaju:

  1. Zmienna zawiera obiekt, jest z nim nierozerwalnie związana. Czas życia (istnienia) obiektu pokrywa się z czasem aktywności zakresu bądź obiektu, w którym zdefiniowana jest zmienna.
  2. Zmienna wskazuje na obiekt. Utworzenie obiektu i utworzenie zmiennej to osobne operacje. Wiele zmiennych może wskazywać na ten sam obiekt, a ta sama zmienna może w różnym czasie wskazywać na różne obiekty. Czas życia obiektów nie jest ściśle związany z czasem życia zmiennych, które na nie wskazują.

W tym samym języku mogą współistnieć oba paradygmaty, choć różne języki wspierają te paradygmaty w różnym stopniu. Pierwszy z nich, nazwijmy go paradygmatem wartości, jest najczęściej stosowany do małych obiektów o prostej strukturze, których typ jest dokładnie znany statycznie (w czasie kompilacji), np. przy liczbach i niewielkich rekordach.

Skopiowanie takiej wartości — wykonywane przy okazji przypisania zmiennej, przekazania argumentu funkcji albo zwrócenia wyniku funkcji — jest dla kompilatora łatwe i często sprowadza się do skopiowania kilku bajtów.

Zajmiemy się bliżej drugim paradygmatem, paradygmatem referencji. Wartościami zmiennych są tutaj referencje nazywane też wskaźnikami.

Gospodarka pamięcią

Skoro czas życia obiektu nie pokrywa się z czasem życia zmiennych wskazujących na ten obiekt, pojawia się pytanie, co wyznacza czas życia obiektu, w szczególności kiedy pamięć zajmowana przez obiekt zostanie zwolniona. Najczęściej spotykane są dwa rozwiązania:

Ręczna gospodarka pamięcią

Programista ma do dyspozycji operację zwalniającą wskazany obiekt, nazwaną np. delete albo free. Każdy obiekt z grupy obiektów niezwiązanych z konkretnymi zmiennymi należy zwolnić dokładnie raz, po zakończeniu jego użycia.

Jeśli taki obiekt nie zostanie zwolniony w ogóle, to będzie zajmował pamięć aż do zakończenia działania programu. Sytuacja, w której program ciągle tworzy obiekty, o których potem zapomina, nazywa się wyciekiem pamięci (memory leak) i najczęściej skutkuje niepotrzebnym zajęciem bardzo dużej ilości pamięci, spowolnieniem systemu i w końcu zabiciem aplikacji przez system operacyjny. Wyciek pamięci jest niegroźny tylko jeśli dotyczy z góry ograniczonej liczby obiektów.

Z drugiej strony zwolnienie obiektu zanim program skończył go używać (w tym wielokrotne zwolnienie) powoduje, że referencje, które wskazywały na ten obiekt, wskazują teraz na miejsce w pamięci, w którym jest już coś zupełnie innego. Są to tzw. wiszące referencje (dangling references). Operacje na tych referencjach mają chaotyczne skutki: od niewidocznych, przez awaryjne zakończenie programu przez system operacyjny, do przekłamania wyników i utraty danych użytkownika albo złośliwego zdalnego położenia usługi sieciowej (denial-of-service attack).

Odśmiecanie

Język programowania automatycznie zwalnia pamięć obiektów, do których program już nie ma szans się odwołać. Takie obiekty nazywają się śmieciami (garbage) albo martwymi obiektami (dead objects), w odróżnieniu od pozostałych, żywych obiektów (live objects).

Ponieważ w ogólności nie da się automatycznie stwierdzić, których obiektów program będzie w przyszłości używał, stosowane są różne przybliżenia tego warunku. Oczywiście każde przybliżenie może odbiegać od tego nieosiągalnego ideału tylko w jedną stronę: może nie wykryć, że jakiś obiekt już nie będzie potrzebny, ale nie może uznać żywego obiektu za martwy.

Standarowym przybliżeniem kryterium żywotności, do którego można odnosić różne algorytmy odśmiecania, jest uznanie za żywe najmniejszego zbioru obiektów, z których każdy spełnia co najmniej jeden z warunków:

  • Jest wskazywany przez zmienną globalną albo aktywną zmienną lokalną.
  • Jest wskazywany przez pole jakiegoś żywego obiektu.

Odśmiecenie obiektu z reguły nie jest obserwowalne przez program, skutkuje tylko zwolnieniem pamięci. Odśmiecanie stwarza iluzję, że pamięci jest nieograniczona ilość, pod warunkiem, że w każdej chwili liczba żywych obiektów jest ograniczona.

Konsekwencje odśmiecania

Starsze języki częściej stosowały ręczną gospodarkę pamięcią, np. Fortran, Pascal, C i C++. Większość nowych języków stosuje odśmiecanie. Ale nie tylko nowe; odśmiecanie zostało wymyślone w 1959 roku dla potrzeb Lispa.

Przy ręcznej gospodarce pamięcią paradygmat wartości jest istotnie łatwiejszy w użyciu dla programisty niż paradygmat referencji, bo zwalnia programistę z obowiązku ustalenia, kiedy należy zwolnić dany obiekt. Dlatego w C++ paradygmat wartości jest bardzo rozwinięty. Wartościami zawartymi w zmiennych mogą być nawet bardzo złożone obiekty ze wskazywanymi przez wskaźniki podobiektami, którym programista określa sposób kopiowania (konstruktor kopiujący, operator przypisania) i zwalniania (destruktor). Zautomatyzowane jest generowanie implementacji tych operacji wykonujących analogiczną operację pole po polu.

W C++ paradygmat wartości jest stosowany również dla obiektów ze zmieniających się stanem, których nie można kopiować. Powszechne jest przekazywanie funkcjom referencji na zmienne lokalne.

W nowoczesnym C++ odwołania do dynamicznie zaalokowanych obiektów coraz częściej odbywają się przez pomocnicze obiekty zajmujące się zarządzaniem czasem ich życia, tzw. sprytne wskaźniki (smart pointers). Automatyczne wykonanie destruktura w momencie zakończenia czasu życia zmiennej jest wykorzystywane do skojarzenia ze sobą akcji „zajmującej” i „zwalniającej” zasób, które są wykonywane odpowiednio przed i po jakimś fragmencie kodu, niezależnie od sposobu opuszczenia tego fragmentu (RAII — Resource Acquisition Is Initialization).

Z kolei odśmiecanie pozwala na swobodniejsze stosowanie paradygmatu referencji. Stosowanie referencji na niezmienialne obiekty (immutable objects) jest równoważne stosowaniu wartości z paradygmatu wartości, o ile one nie mają samodzielnie adresowalnej struktury wewnętrznej. Programiście jest zwykle wszystko jedno, czy operacja zapisana przez coś podobnego do x := 5 w danym języku sprowadza się do skopiowania liczby 5, czy skopiowania referencji na któryś obiekt reprezentujący liczbę 5. Dlatego odśmiecane języki często stosują paradygmat referencji jako podstawowy albo wręcz jedyny.

W odśmiecanych językach jest silniejsza tendencja do programowania w stylu funkcyjnym, przez tworzenie nowych obiektów i podmianę na nie referencji zamiast przez zmiany starych obiektów w miejscu. Również charakterystyczna dla programowania funkcyjnego możliwość tworzenia lokalnych funkcji i zwracania ich na zewnątrz (upward closures) w zasadzie wymaga odśmiecania, żeby te lokalne funkcje mogły używać lokalnych zmiennych funkcji, w której są zawarte, również po zakończeniu tej zewnętrznej funkcji.

Większość algorytmów odśmiecania nie zapewnia zwolnienia obiektu natychmiast po zniknięciu ostatniej żywej referencji do niego. Obiekt jest faktycznie zwalniany w jakimś późniejszym czasie, zależnym od intensywności alokacji innych obiektów przez program. Odśmiecanie służy przede wszystkim do automatyzacji zwalniania pamięci. Poleganie na wykonywaniu przez odśmiecacz innych czynności związanych z kończeniem życia obiektu niż zwolnienie pamięci jest ryzykowne. Jest jednaj technicznie możliwe, jeśli możemy sobie pozwolić na wykonanie tych czynności w późniejszym, bliżej nieokreślonym momencie.

Dlatego do określenia czynności do wykonania w momencie wejścia i wyjścia z zakresu odśmiecane języki oferują inne mechanizmy językowe niż RAII, np. unwind-protect i makra w stylu with-open-file w Lispie i using w C#.

Zatem różnice w stylu programowania między odśmiecanymi a nieodśmiecanymi językami nie sprowadzają się do jawnego stosowania bądź pomijania delete. Odśmiecanie wpływa na organizację obiektów, na projektowanie interfejsów, na stopień współdzielenia tudzież kopiowania obiektów przez różne fragmenty programu.

Implementacja odśmiecania

Zliczanie odwołań (reference counting)

Technika zliczania odwołań polega na powiązaniu z każdym obiektem licznika przechowującego aktualną liczbę referencji na ten obiekt. Wraz z utworzeniem nowej referencji, np. kiedy obiekt jest przekazywany jako argument jakiejś funkcji, licznik jest zwiększany o 1. Usunięcie referencji na ten obiekt, np. przypisanie zmiennej, która wcześniej wskazywała na ten obiekt, innej wartości, wymaga zmniejszenia licznika. Za każdym razem, kiedy zmniejszany licznik zejdzie do 0, odpowiedni obiekt jest zwalniany, zmniejszając przy tym liczniki obiektów, do których się odwoływał.

Zauważmy, że ten mechanizm powoduje osłabienie kryterium żywotności obiektów względem standardowego: obiekt jest uznawany za żywy, kiedy jest wskazywany przez pole jakiegokolwiek obiektu, niekoniecznie żywego. Innymi słowy, zbiór obiektów, które wskazują na siebie nawzajem, a przestaną być osiągalne z reszty programu, powoduje wyciek pamięci. Dlatego część ludzi w ogóle nie uznaje zliczania odwołań za technikę odśmiecania: algorytm nie spełnia podstawowego założenia ostatecznego zwalniania wszystkich nieosiągalnych obiektów.

Do wad trzeba zaliczyć wysoki koszt manipulacji licznikami odwołań, często większy niż narzut innych algorytmów odśmiecania. Co prawda pojedyncza operacja na liczniku jest tania, ale takich operacji jest bardzo dużo, a zwolnienie złożonej struktury danych wymaga obejścia całego grafu obiektów.

Mimo to, zliczanie odwołań jest używane w wielu projektach. Wynika to prawdopodobnie między innymi z tego, że jest łatwe do zintegrowania z językiem programowania nie wspierającym odśmiecania, zwłaszcza takim jak C++, gdzie manipulacje licznikiem odwołań przy okazji przekazywania referencji mogą być automatyzowane za pomocą konstruktorów kopiujących, operatorów przypisania i destruktorów.

Zliczanie odwołań umożliwia zwolnienie obiektu natychmiast, kiedy tylko zniknie ostatnie odwołanie do niego. Dzięki temu względnie bezpiecznie jest uwzględnić w zwalnianiu obiektu również inne czynności kończące jego życie, nie tylko zwolnienie pamięci. Co więcej, momenty i długości przerw w wykonywaniu programu w celu zwolnienia obiektów są przewidywalne.

Możliwe są wariacje podstawowego mechanizmu zliczania odwołań, np. połączenie go z okresowo wykonywanymi innymi algorytmami odśmiecania w celu usunięcia cyklicznych śmieci (tak robi podstawowa implementacja Pythona).

Mark & sweep

Algorytm mark & sweep wymaga zarezerwowania jednego dodatkowego bitu w każdym obiekcie. Przynajmniej koncepcyjnie, bo ta informacja nie musi mieć fizycznej formy bitu, wystarczy jakaś realizacja podziału obiektów na dwa podzbiory z możliwością przenoszenia obiektu między zbiorami.

Okresowo, np. kiedy od ostatniego odśmiecania zaalokowano już odpowiednio dużo pamięci, wykonywane jest odśmiecanie, które składa się z dwóch faz. Odśmiecanie wykorzystuje tymczasowy zbiór bieżących obiektów G.

Faza I: mark.

  1. Na początku wszystkie obiekty mają ten bit ustawiony na „nieodwiedzony”.
  2. Do zbioru G na początku należą obiekty wskazywane przez „korzenie” odśmiecania (roots), czyli przez zmienne globalne i lokalne. Ustawiamy bity tych obiektów na „odwiedzony”.
  3. Dopóki zbiór G jest niepusty:
    1. Wyjmujemy jakiś obiekt z G
    2. Dodajemy do G wszystkie nieodwiedzone obiekty wskazywane przez ten obiekt, ustawiając ich bity na „odwiedzony”.

Faza II: sweep.

  1. Zwalniamy wszystkie nieodwiedzone obiekty, a pozostałym ustawiamy bit z powrotem na „nieodwiedzony”. Zamiast fizycznego odwracania bitu w każdym żywym obiekcie można zamienić znaczenie bitów rolami.

Możliwe są różne realizacje zbioru G i w związku z tym różne strategie wyboru obiektu z niego:

  • Jako stos adresów obiektów, w formie jawnej struktury danych, np. tablicy. W efekcie graf obiektów jest przeglądany w głąb.
  • Jako stos rekurencyjnych wywołań funkcji "mark". To jest ryzykowne podejście, kiedy głębokość grafu obiektów może być większa niż maksymalna głębokość zagnieżdżonych wywołań funkcji.
  • Jako kolejka. W efekcie graf obiektów jest przeglądany wszerz.

Wadą podstawowej formy tego algorytmu jest konieczność okresowego wstrzymania programu na czas przejrzenia całej pamięci i odwiedzenia każdego obiektu.

Mark & compact

Zamiast zwalniać pojedyncze obiekty jak w algorytmie mark & sweep, pozostawiając żywe obiekty między zwolnionymi miejscami, można przenieść żywe obiekty do spójnego obszaru pamięci, „zsuwając” je na miejsca po zwolnionych obiektach. Dzięki temu alokacja nowych obiektów pobiera pamięć ze spójnego obszaru wolnej pamięci, co jest bardzo szybkie. Poza tym zgrupowanie używanych obiektów w spójnym kawałku pamięci ułatwia procesorowi efektywne cache’owanie pamięci.

Oczywiście zmiana fizycznego położenia obiektu wymaga uaktualnienia reprezentacji wszystkich wskaźników na niego, a wskaźniki są ze swojej natury „jednokierunkowe”: nie można szybko zlokalizować wszystkich wskaźników na dany obiekt. Faza „sweep” składa się więc z kilku przejść, np. najpierw ustalamy nowy adres każdego obiektu, potem uaktualniamy wskaźniki, wreszcie ostatecznie przesuwamy obiekty.

Odśmiecanie kopiujące (copying GC)

Kopiować obiekty pod nowe adresy można od razu w trakcie przechodzenia grafu obiektów. Po przeniesieniu obiektu pod nowy adres pod starym adresem można zostawić odsyłacz do nowego adresu. Zwykły obiekt jest zawsze odróżnialny od takiego pozostawionego odsyłacza.

Odśmiecanie używa tymczasowo zbioru G bieżących obiektów i odbywa się następująco:

  1. Alokujemy nowy obszar pamięci, do którego zostaną przeniesione żywe obiekty. Na początku zbiór G jest pusty.
  1. Odwiedzamy korzenie odśmiecania. Odwiedzenie wskaźnika polega na sprawdzeniu, czy pod danym adresem znajduje się odsyłacz. Jeśli tak, to tylko uaktualniamy wskaźnik na adres podany w odsyłaczu. Jeśli nie, to przenosimy obiekt pod pierwszy wolny adres w nowym obszarze pamięci, pozostawiamy odsyłacz, uaktualniamy wskaźnik i dodajemy przeniesiony obiekt do zbioru G.
  2. Dopóki zbiór G jest niepusty:
    1. Wyjmujemy jakiś obiekt z G.
    2. Odwiedzamy wskaźniki zawarte w tym obiekcie.
  3. Zwalniamy stary obszar pamięci, który zawiera teraz same śmieci. Nowy obszar pamięci staje się bieżącą stertą.

Możliwe są różne warianty. Przetwarzanie zbioru G może się przeplatać z odwiedzaniem poszczególnych korzeni. Zbiór G może zawierać wskaźniki zawarte w obiektach, a nie same obiekty, dzięki czemu znalezienie pól obiektu dla potrzeb skopiowania oraz dla potrzeb zapamiętania tych pól do późniejszego odwiedzenia może się odbyć równocześnie.

Na różne sposoby można również zrealizować znajdowanie pól mogących zawierać wskaźniki (pola, które na pewno nie zawierają wskaźników, trzeba tylko skopiować wraz z całą zawartością obiektu, ale oczywiście nie trzeba ich odwiedzać). Na przykład każdy obiekt może zaczynać się od nagłówka opisującego liczbę i położenie pól albo od wskaźnika na statycznie zaalokowany deskryptor. Zamiast interpretowanego przez odśmiecacz opisu pól, nagłówek może też zawierać adres kodu, który wykonuje zależne od typu obiektu czynności kopiowania i odwiedzania pól.

Reprezentacja zbioru G i strategia wyboru przetwarzania obiektów czy wskaźników z G wpływa na kolejność ułożenia obiektów w pamięci. Kolejność stosowa i tym samym przeglądanie grafu obiektów w głąb powoduje ułożenie wskazujących na siebie obiektów blisko siebie, co ułatwia pracę sprzętowym mechanizmom cache’ującym.

Istnieje ciekawy sposób reprezentacji zbioru G, jeśli godzimy się na przeglądanie obiektów wszerz. Mianowicie obiekty te zajmują zawsze spójny obszar pamięci w nowej stercie. Wystarczy więc pamiętać dwa wskaźniki: na pierwszy nieprzetworzony jeszcze obiekt w nowej stercie i na początek wolnego miejsca. W miarę przetwarzania kolejnych obiektów pierwszy wskaźnik przesuwa się naprzód, a odnajdowanie wskazywanych przez nie nowych obiektów do przejrzenia powoduje przesuwanie się drugiego wskaźnika. Kiedy oba wskaźniki się spotkają, odśmiecanie można zakończyć. Jest to algorytm Cheneya.

Zauważmy, że odśmiecacz kopiujący nie odwiedza śmieci indywidualnie. Odwiedzane i kopiowane są tylko żywe obiekty, a następnie cały obszar sterty zawierający śmieci jest zwalniany jednym ruchem. Taka charakterystyka pracy sprawdza się, kiedy większość obiektów ma krótki czas życia i umiera przed następnym odśmiecaniem.

Koszt odśmiecania kopiującego nie ma oczywistego porównania z odśmiecaniem w stylu mark & sweep albo ze zliczaniem odwołań. Na niekorzyść przemawia fizycznie kopiowanie obiektów z miejsca w miejsce, ale z drugiej strony unikamy zwalniania indywidualnych obiektów. Koszt jest uzależniony od średniej ilości żywych obiektów i od czasu ich życia, a nie od tempa alokacji.

Odśmiecanie pokoleniowe (generational GC)

Odśmiecanie kopiujące opiera się na okresowym przechodzeniu całego grafu obiektów. Można zredukować częstość odwiedzania każdego obiektu wykorzystując statystyczną obserwację: wiele obiektów jest tworzonych tylko na chwilę i żyje krótko; natomiast jeśli dany obiekt przeżył już wiele cykli odśmiecania, to jest duża szansa, że przeżyje i następny. Zatem opłaca się koncentrować na odśmiecaniu młodych obiektów, bo tam prawdopodobnie łatwo odzyskamy dużo pamięci. Stare obiekty odkładamy na bok i odwiedzamy je rzadko.

Odśmiecanie pokoleniowe polega na segregacji obiektów względem ich wieku, najczęściej mierzonego liczbą przeżytych cykli odśmiecania, i odśmiecaniu młodszych obiektów częściej. Dany cykl odśmiecania dotyczy obiektów wybranego pokolenia oraz wszystkich młodszych. Obiekty, które przeżyją, są przenoszone do starszych pokoleń od razu albo po przekroczeniu pewnej wartości licznika wieku obiektu. Wybór pokolenia do odśmiecenia jest jakąś funkcją wielkości poszczególnych pokoleń i ew. dotychczasowej statystycznej charakterystyki czasu życia obiektów danego programu.

W najprostszej wersji pokolenia są tylko dwa: młode obiekty, które nie przeżyły jeszcze żadnego odśmiecania, i pozostałe, stare obiekty. Są też dwa rodzaje cyklu odśmiecania: mniejsze, polegające na przejrzeniu wyłącznie młodych obiektów, oraz większe, które dotyczy wszystkich obiektów.

Z punktu widzenia odśmiecania danego pokolenia wskaźniki na należące do niego obiekty, ale zawarte w starszych obiektach, są korzeniami odśmiecania, od których trzeba zacząć przechodzenie grafu obiektów. Co więcej, jeśli skopiowanie żywego obiektu łączy się ze zmianą jego fizycznego adresu, to odśmiecacz musi znaleźć wszystkie wskaźniki na dany obiekt, żeby uaktualnić ich reprezentację. Żeby podział sterty na pokolenia się opłacał, trzeba umieć znaleźć takie wskaźniki taniej niż przez przejrzenie wszystkich starszych obiektów.

Wskaźnik ze starszego obiektu na młodszy może powstać tylko przez przypisanie pola wcześniej istniejącego obiektu. Odśmiecacz musi przechwycić każde przypisanie, które skutkuje albo może skutkować powstaniem takiego wskaźnika, i zarejestrować położenie przypisanego wskaźnika albo adres obiektu, do którego należy to pole, albo adres strony pamięci, do której należy to pole. Podczas odśmiecania zarejestrowane w ten sposób wskaźniki są dodatkowymi korzeniami. Takie przechwycenie zapisu nazywa się barierą zapisu (write barrier). Może ona być zrealizowana czysto programowo (przez wyemitowanie odpowiednich instrukcji wraz z instrukcjami przypisania, które mogą tworzyć wskaźniki ze starszego pokolenia na młodsze) albo z wykorzystaniem udostępnionych przez system operacyjny sprzętowych mechanizmów wygenerowania przerwania, kiedy odpowiednio oznaczona strona pamięci jest zapisywana.

Nie każdy zapis do pola obiektu musi podlegać barierze: jeśli statycznie wiadomo, że obiekt zawierający dane pole nie jest starszy niż obiekt wskazywany przez to pole, to zapis sprowadza się do prostego przypisania adresu. Taka statyczna gwarancja występuje na przykład w trakcie inicjalizacji dopiero co stworzonego obiektu wartościami istniejącymi przed jego utworzeniem.

Zmienne lokalne i globalne też mogą podlegać barierze zapisu albo mogą być przeglądane w całości przy każdym odśmiecaniu. Programowa bariera zapisu w przypadku zmiennych lokalnych byłaby dość kosztowna, bo zapis takich zmiennych jest częsty. Można jednak uniknąć przeglądania całego stosu przy każdym odśmiecaniu, jeśli zmiany zmiennych lokalnych dotyczą tylko najwyższej ramki stosu i jeśli można wykryć, jak głęboko od ostatniego odśmiecania danego pokolenia stos został najdalej zwinięty — wtedy wystarczy przejrzeć tylko ramki stosu między tą najdalszą a bieżącym wierzchołkiem.

Stopień prawdziwości wspomnianej na początku statystycznej obserwacji dotyczącej zróżnicowania wieku obiektów zależy od stylu programowania i od języka. Odśmiecanie pokoleniowe jest szczególnie opłacalne przy programowaniu funkcyjnym, które po pierwsze prowadzi do intensywnej alokacji nowych obiektów zamiast stopniowych zmian obiektów istniejących wcześniej, a po drugie ogranicza powstawanie wskaźników ze starszych obiektów do młodszych, które muszą być skutkiem imperatywnego przypisania. Ale również nowoczesne implementacje języków obiektowych często stosują odśmiecanie pokoleniowe.

Odśmiecanie przyrostowe (incremental GC)

Konieczność zatrzymania programu, żeby odśmiecić całą stertę, jest wadą wielu algorytmów odśmiecania. Moment takiej pauzy jest trudny do przewidzenia; może wypaść przy okazji dowolnej alokacji pamięci i tym samym może przeszkodzić programowi, którego reakcja na jakieś zdarzenie jest akurat pilna. Można próbować zmniejszać dokuczliwość pauz przez automatyczne odśmiecanie, kiedy wydaje się, że czas jest bardziej odpowiedni, np. kiedy program właśnie czeka na zdarzenie zewnętrzne i procesor nie ma nic do roboty. Z kolei odśmiecanie pokoleniowe powoduje, że większość pauz jest krótka — co jakiś czas jednak musi wciąż odśmiecić całość. Bardziej atrakcyjne jest wyeliminowanie w ogóle konieczności odśmiecania całej sterty naraz.

Odśmiecanie przyrostowe polega na przeplataniu odśmiecania z normalnym wykonaniem programu. Z punktu widzenia odśmiecacza, który stara się obejść graf obiektów i wnioskować o ich osiągalności z korzeni, główny program przeszkadza zmieniając co chwilę połączenia między obiektami i sam zbiór korzeni.

W ustaleniu niezmienników, które muszą być zachowane, żeby odśmiecacz mógł pracować na zmieniającym się wciąż grafie obiektów, pomaga koncepcyjne przyporządkowanie każdemu obiektowi „koloru”. Obiekty, które zostały uznane za żywe i których wszystkie pola zostały już odwiedzone, nazwijmy „czarnymi”. Żywe obiekty, których pola jeszcze nie zostały odwiedzone, nazwijmy „szarymi”. Pozostałe, nieodwiedzone obiekty są „białe”.

Odśmiecacz mark & sweep zaczyna cykl odśmiecania od sytuacji, w której wszystkie obiekty są białe, tylko korzenie są szare. Praca polega na przemalowywaniu białych obiektów wskazywanych przez szare obiekty na szaro i na przemalowywaniu białych obiektów, których wszystkie pola zostały już odwiedzone, na czarno. Innymi słowy, szare obiekty są cienką granicą między czarnymi a białymi obiektami, która przesuwa się naprzód w miarę kolorowania kolejnych białych obiektów na czarno. Kiedy nie pozostał już żaden szary obiekt, można zwolnić obiekty, które po przejściu tej fali pozostały białe, a pozostałe przemalować z powrotem na biało przed następnym cyklem.

Przy odśmiecaniu kopiującym stara kopia sterty zawiera białe obiekty, a nowa — szare i czarne. Szare obiekty to te z nowej kopii sterty, których pola należy jeszcze obejrzeć.

Podstawowy niezmiennik brzmi: żaden czarny obiekt nie wskazuje bezpośrednio na biały obiekt. Jeśli odśmiecanie przeplata się z głównym programem, to program musi być wyposażony w bariery zapisu, które zapewniają zachowanie tego niezmiennika przez odpowiednie przemalowanie obiektów, które pogwałciłyby niezmiennik. Oprócz tego główny program musi dbać o to, żeby odśmiecacz mógł znaleźć wszystkie szare obiekty. Istnieje wiele strategii kolorowania nowo alokowanych obiektów i przywracania niezmiennika po przypisaniu.

Trzeba jeszcze zapewnić, żeby odśmiecanie odbywało się w odpowiednim tempie. Z jednej strony odśmiecacz musi nadążyć ze znajdowaniem i zwalnianiem śmieci, żeby ograniczona ilość faktycznie żywych obiektów używanych przez program implikowała ograniczone zużycie pamięci. Z drugiej strony zbyt intensywne, wielokrotne przeglądanie obiektów, których sytuacja nie miała szans ulegać tak szybkim zmianom, marnuje czas procesora.

Niskopoziomowe aspekty implementacji odśmiecania

Odśmiecanie dokładne / konserwatywne (precise / conservative GC)

TODO

Cheney on the MTA

TODO

Obiekty specjalne

Finalizacja

TODO

Słabe referencje

TODO