W jaki sposób śmieciarz zapobiega skanowaniu całej pamięci przy każdym zbieraniu?

16

Niektóre śmieciarki (przynajmniej Mono i .NET) mają obszar pamięci krótkotrwałej, który często skanują, oraz obszar pamięci pomocniczej, który skanują rzadziej. Mono nazywa to żłobkiem.

Aby dowiedzieć się, które obiekty można usunąć, skanują wszystkie obiekty, zaczynając od korzeni, stosu i rejestrów, i usuwają wszystkie obiekty, do których nie ma już odniesienia.

Moje pytanie brzmi: w jaki sposób zapobiegają skanowaniu wszystkich używanych pamięci na każdym zbiorze? Zasadniczo jedynym sposobem, aby dowiedzieć się, które obiekty nie są już używane, jest zeskanowanie wszystkich obiektów i wszystkich ich odniesień. Zapobiegnie to jednak zamianie pamięci przez system operacyjny, mimo że nie jest ona używana przez aplikację i wydaje się, że trzeba wykonać ogrom pracy, także w przypadku „Nursery Collection”. Nie wydaje się, żeby dużo wygrywali, korzystając z pokoju dziecinnego.

Czy coś mi brakuje, czy śmieciarz faktycznie skanuje każdy obiekt i każde odwołanie za każdym razem, gdy wykonuje kolekcję?

Pieter van Ginkel
źródło
1
ładny przegląd znajduje się w artykule The Art of Garbage Collection Tuning napisanym przez Angelikę Langer. Formalnie chodzi o to, jak się to robi w Javie, ale przedstawione koncepcje są dość agnostyczne z języka
gnat

Odpowiedzi:

14

Podstawowe obserwacje, które pozwalają pokoleniowemu śmieciu na śmieci, aby uniknąć konieczności skanowania wszystkich obiektów starszej generacji, to:

  1. Po kolekcji wszystkie obiekty, które nadal istnieją, będą miały pewną minimalną generację (np. W .net, po kolekcji Gen0 wszystkie obiekty są Gen1 lub Gen2; po kolekcji Gen1 lub Gen2 wszystkie obiekty są Gen2).
  2. Obiekt lub jego część, który nie został napisany od czasu kolekcji, która promowała wszystko do generacji N lub wyższej, nie może zawierać żadnych odniesień do obiektów niższych generacji.
  3. Jeśli obiekt osiągnął określone pokolenie, nie musi być identyfikowany jako osiągalny, aby zapewnić jego zachowanie podczas gromadzenia niższych pokoleń.

W wielu frameworkach GC śmieciarz może oflagować obiekty lub ich części w taki sposób, że pierwsza próba zapisu do nich wywoła specjalny kod, aby zarejestrować fakt, że zostały one zmodyfikowane. Obiekt lub jego część, który został zmodyfikowany, niezależnie od jego generacji, należy przeskanować w następnej kolekcji, ponieważ może zawierać odniesienia do nowszych obiektów. Z drugiej strony bardzo często zdarza się, że wiele starszych obiektów nie jest modyfikowanych między kolekcjami. Fakt, że skany niższej generacji mogą ignorować takie obiekty, może pozwolić, aby takie skany zakończyły się znacznie szybciej niż w innym przypadku.

Zauważ, przy okazji, że nawet jeśli nie można wykryć, kiedy obiekty są modyfikowane i trzeba będzie skanować wszystko na każdym przejściu GC, generowanie odśmiecania może nadal poprawić wydajność etapu zamiatania kompaktora zbierającego. W niektórych środowiskach osadzonych (szczególnie w tych, w których istnieje niewielka lub żadna różnica prędkości między sekwencyjnym i losowym dostępem do pamięci), przenoszenie bloków pamięci jest stosunkowo drogie w porównaniu do oznaczania odnośników. W konsekwencji, nawet jeśli nie można przyspieszyć fazy „oznaczenia” za pomocą kolektora pokoleniowego, warto przyspieszyć fazę „zamiatania”.

supercat
źródło
przenoszenie bloków pamięci jest kosztowne w każdym systemie, więc poprawa wymiaru jest korzystna nawet dla twojego czterordzeniowego systemu CPU.
gbjbaanb
@gbjbaanb: W wielu przypadkach koszt skanowania wszystkiego w celu znalezienia obiektów na żywo byłby znaczny i budziłby zastrzeżenia, nawet gdyby przenoszenie obiektów było całkowicie bezpłatne. W związku z tym należy w miarę możliwości unikać skanowania starych obiektów. Z drugiej strony powstrzymywanie się od kompaktowania starszych obiektów jest prostą optymalizacją, którą można osiągnąć nawet w prostych ramach. BTW, jeśli projektujemy platformę GC dla małego systemu osadzonego, pomocna może być deklaratywna obsługa niezmiennych obiektów. Śledzenie, czy zmienny obiekt się zmienił, jest trudne, ale dobrze byłoby ...
supercat
... po prostu załóżmy, że obiekty zmienne muszą być skanowane przy każdym przejściu GC, ale obiekty niezmienne nie. Nawet jeśli jedynym sposobem skonstruowania niezmiennego obiektu było zbudowanie „prototypu” w przestrzeni mutowalnej, a następnie skopiowanie go, pojedyncza dodatkowa operacja kopiowania mogłaby uniknąć konieczności skanowania obiektu w przyszłych operacjach GC.
supercat
Nawiasem mówiąc, wydajność wyrzucania elementów bezużytecznych w implementacjach BASIC pochodzących z Microsoftu w latach 80-tych dla 6502 mikroprocesorów (i być może także innych) mogłaby zostać znacznie zwiększona w niektórych przypadkach, gdyby program, który generował wiele ciągów, które nigdy się nie zmieniły, skopiował „następny wskaźnik alokacji ciągu znaków do wskaźnika „góra przestrzeni znaków”. Taka zmiana uniemożliwiłaby śmieciarzowi sprawdzanie któregokolwiek ze starych ciągów, aby sprawdzić, czy nadal są potrzebne. Commodore 64 nie był zbyt zaawansowany technologicznie, ale taka „generacyjna” GC pomogłaby nawet tam.
supercat
7

GC, o których mówisz, to generatory śmieci. Zostały zaprojektowane tak, aby jak najlepiej wykorzystać obserwację zwaną „śmiertelnością niemowląt” lub „hipotezą pokoleniową”, co oznacza, że ​​większość obiektów bardzo szybko staje się nieosiągalna. Rzeczywiście skanują, zaczynając od korzeni, ale ignorują wszystkie stare obiekty . Dlatego nie muszą skanować większości obiektów w pamięci, skanują tylko młode obiekty (kosztem niewykrycia nieosiągalnych starych obiektów, przynajmniej nie w tym momencie).

„Ale to źle”, słyszę, jak krzyczysz, „stare przedmioty mogą odnosić się do młodych przedmiotów”. Masz rację i istnieje kilka rozwiązań tego problemu, które polegają na szybkim i wydajnym zdobywaniu wiedzy, które stare obiekty należy sprawdzić, a które można bezpiecznie zignorować. Sprowadzają się one raczej do rejestrowania obiektów lub małych (większych niż obiekty, ale znacznie mniejszych niż cała kupa) zakresów pamięci, które zawierają wskaźniki dla młodszych pokoleń. Inni opisali je o wiele lepiej niż ja, więc dam ci tylko kilka słów kluczowych: znakowanie kart, zapamiętane zestawy, pisanie barier. Istnieją również inne techniki (w tym hybrydy), ale obejmują one powszechnie znane mi podejścia.


źródło
3

Aby dowiedzieć się, jakie obiekty przedszkolne są nadal aktywne, kolektor musi tylko zeskanować zestaw główny i wszystkie stare obiekty, które zostały zmutowane od ostatniej kolekcji , ponieważ stary obiekt, który nie został niedawno zmutowany, nie może wskazywać na młody obiekt . Istnieją różne algorytmy utrzymywania tej informacji na różnych poziomach dokładności (od dokładnego zestawu zmutowanych pól do zestawu stron, na których mogła wystąpić mutacja), ale ogólnie wszystkie one zawierają pewną barierę zapisu : kod, który działa przy każdym odwołaniu -typedowa mutacja polowa, która aktualizuje księgowość GC.

Ryan Culpepper
źródło
1

Najstarsza i najprostsza generacja śmieciarek faktycznie skanowała całą pamięć i musiała przerwać wszystkie inne procesy. Później algorytmy poprawiły to na różne sposoby - dzięki czemu kopiowanie / skanowanie jest przyrostowe lub działa równolegle. Większość współczesnych śmieciarek segreguje obiekty na pokolenia i ostrożnie zarządza wskaźnikami międzypokoleniowymi, dzięki czemu nowsze generacje można zbierać bez przeszkadzania starszym.

Kluczową kwestią jest to, że śmieciarze ściśle współpracują z kompilatorem i resztą środowiska wykonawczego, aby zachować iluzję, że obserwuje całą pamięć.

ddyer
źródło
Nie jestem pewien, jakie metody wyrzucania elementów bezużytecznych były używane w minikomputerach i komputerach mainframe przed końcem lat siedemdziesiątych, ale moduł zbierający elementy bezużyteczne Microsoft BASIC, przynajmniej na maszynach 6502, ustawiłby wskaźnik „następnego ciągu” na szczycie pamięci, a następnie wyszukiwał wszystkie odwołania do ciągu znaków, aby znaleźć najwyższy adres poniżej „wskaźnika następnego ciągu”. Ten ciąg znaków zostanie skopiowany tuż pod „wskaźnikiem następnego ciągu”, a ten wskaźnik zostanie zaparkowany tuż pod nim. Algorytm następnie się powtórzy. Możliwe było, że kod połączy wskaźniki w celu zapewnienia ...
supercat,
... coś w rodzaju kolekcji pokoleniowej. Czasami zastanawiałem się, jak trudno byłoby załatać BASIC, aby zaimplementować kolekcję „generacyjną”, po prostu utrzymując adresy z góry każdej generacji i dodając kilka operacji zamiany wskaźnika przed i po każdym cyklu GC. Wydajność GC nadal byłaby dość zła, ale w wielu przypadkach może być ogolona z dziesiątek sekund do dziesiątych sekund.
supercat,
-2

Zasadniczo ... GC używa „segmentów” do oddzielenia tego, co jest używane, a co nie. Gdy sprawi, że będzie sprawdzane, usuwa rzeczy, które nie są używane, i przenosi wszystko inne do drugiej generacji (która jest sprawdzana rzadziej niż pierwsza generacja), a następnie przenosi rzeczy, które są nadal używane w drugiej den do trzeciej generacji.

Tak więc, rzeczy w trzeciej generacji są zwykle obiektami, które z jakiegoś powodu są zablokowane, a GC nie sprawdza tam zbyt często.

aserwin
źródło
1
Ale skąd ma wiedzieć, które obiekty są w użyciu?
Pieter van Ginkel
Śledzi, które obiekty są osiągalne z dostępnego kodu. Gdy obiekt nie jest już osiągalny z żadnego kodu, który może zostać wykonany (powiedzmy kod dla metody, która została zwrócona), GC wie, że można go bezpiecznie pobrać
JohnL
Obaj opisują, jak GC są poprawne, a nie jak wydajne. Sądząc po pytaniu, OP doskonale o tym wie.
@delnan tak Odpowiadałem na pytanie, skąd wie, które obiekty są w użyciu, co było w komentarzu Pietera.
JohnL
-5

Algorytmem zwykle stosowanym w tym GC jest Naiwna ocena i przegląd

powinieneś również zdawać sobie sprawę z faktu, że nie jest to zarządzane przez sam C #, ale przez tak zwane CLR .

użytkownik827992
źródło
To właśnie czułem, czytając o zbieraczu śmieci Mono. Jednak nie rozumiem, dlaczego, jeśli skanują cały zestaw roboczy, który kiedykolwiek zbiera, mają kolekcjoner pokoleniowy, dzięki któremu kolekcja GEN-0 jest bardzo szybka. Jak to może być w ogóle szybkie z działającym zestawem powiedzmy 2 GB?
Pieter van Ginkel
Cóż, prawdziwym GC dla mono jest Sgen, powinieneś przeczytać ten mono-project.com/Generational_GC lub kilka artykułów online schani.wordpress.com/tag/mono infoq.com/news/2011/01/SGen , chodzi o to, że te nowe technologie, takie jak CLR i CLI, mają naprawdę modułową budowę, język staje się po prostu sposobem wyrażenia czegoś dla CLR, a nie sposobem na tworzenie kodu binarnego. Twoje pytanie dotyczy szczegółów implementacji, a nie algorytmów, ponieważ algorytm wciąż nie ma implementacji, powinieneś po prostu przeczytać dokumenty techniczne i artykuły z Mono, nikogo innego.
user827992,
Jestem zmieszany. Strategia stosowana przez śmieciarza nie jest algorytmem?
Pieter van Ginkel
2
-1 Przestań mylić OP. To, że GC jest częścią CLR i nie jest specyficzne dla języka, w ogóle nie ma znaczenia. GC jest głównie charakteryzuje sposób ustanawia się stosu i określa osiągalność, a drugi jest cały o algorytm (ów) stosowanych do tego. Chociaż może istnieć wiele implementacji algorytmu i nie powinieneś zajmować się szczegółami implementacji, sam algorytm określa liczbę skanowanych obiektów. Generacyjna GC to po prostu algorytm + układ sterty, który próbuje wykorzystać „hipotezę generacyjną” (że większość obiektów umiera młodo). To nie są naiwne.
4
Algorytm! = Implementacja rzeczywiście, ale implementacja może odejść tak daleko, zanim stanie się implementacją innego algorytmu. Opis algorytmu w świecie GC jest bardzo konkretny i obejmuje takie rzeczy, jak nie skanowanie całej sterty w kolekcji szkółek oraz sposób wyszukiwania i przechowywania wskaźników międzypokoleniowych. Prawdą jest, że algorytm nie mówi, jak długo zajmie określony krok algorytmu, ale nie ma to żadnego związku z tym pytaniem.