Kiedy śmieciarz zagęszcza obiekty na stercie, czy zmienia referencje na stosie?

18

To wydaje się proste pytanie, ale po wielu lekturach na ten temat wciąż nie znalazłem ostatecznej odpowiedzi (być może dlatego, że jest tak proste).

Moje pytanie brzmi: kiedy śmieciarz zagęszcza obiekty na stercie, w jaki sposób aktualizowane są odniesienia do tych obiektów na stosie? Mogę wymyślić dwa możliwe rozwiązania:

  1. Przejdź przez stos (i odniesienia w stercie) i zaktualizuj odniesienie, aby wskazywało nową lokalizację obiektu. Analogicznie do przeprowadzki byłoby to jak wysłanie listu do każdego, kto ma twój adres i poproszenie go o zaktualizowanie książki adresowej o nowy adres.
  2. Podaj tabelę wyszukiwania. To tak, jakby zostawić adres do przekazania w lokalnym urzędzie pocztowym.

Czy śmieciarze używają głównie jednej z tych dwóch metod? Jakaś inna metoda? Obie?

garbage-collection todorojo
źródło
Zobacz stackoverflow.com/questions/3799203/... i en.wikipedia.org/wiki/…
Gort the Robot
@StevenBurnap popraw mnie, jeśli się mylę, ale wierzę, że wątek, do którego linkujesz, nie zawierał ostatecznych odpowiedzi. Wydawało się, że zastanawiają się również nad tym właśnie pytaniem. Mogę źle odczytać. Jeśli udzielą odpowiedzi na pytanie, jeśli nie miałbyś nic przeciwko, myślę, że pomocne byłoby podsumowanie tutaj odpowiedzi dla przyszłych użytkowników SE (i mnie!)
todorojo
Termin, o którym mówisz, to „ruchomy śmieciarz”. Szczerze mówiąc, nie wiem, jak często są używane.
Gort the Robot

Odpowiedzi:

9

Nie mam specjalistycznej wiedzy na ten temat, ale rozumiem, że pierwsza metoda jest ogólnie stosowana.

Garbage collector i tak musi przeanalizować stos, aby dowiedzieć się, jakie rzeczy na stosie są określane ze stosu. Gdy zdecyduje się coś przenieść, musi skorygować odniesienia do niego, i nie ma powodu, aby rozróżniać stertę i stos w tym momencie.

Podejście oparte na tabeli przeglądowej może zasadniczo działać. Jednak to spowodowałoby, że wszystkie dostępy do wskaźnika muszą wykonać 2 kroki. Miałoby to ogromny wpływ na wydajność w normalnych czasach pracy. Szczególnie w przypadku użycia wielu małych obiektów. (Jest to przypadek, w którym najnowocześniejsze programy GC zwykle wyprzedzają liczenie referencji).

btilly
źródło
3
Dodałbym, że myślę, że GC prawdopodobnie nie próbuje przenosić rzeczy na stos, chyba że jest to konieczne. W dzisiejszym świecie wieloprocesorowym musi to być koszmar synchronizacji, gdy muszą zaktualizować wszystkie odwołania do czegoś na stercie, gdy uruchomiony jest program, który korzysta z tych odniesień. Tabela odnośników uprościłaby to, ale myślę, że to raczej wyjątek niż norma, więc większość GC prawdopodobnie musi zablokować niektóre referencje, przenieść pamięć, a następnie zaktualizować referencje. +1 ciekawe pytanie, +1 dobra odpowiedź.
GlenPeterson
3
@GlenPeterson Wiele GC faktycznie nie przenosi rzeczy na stos i nie ma z tym problemem. Jednak kompaktowanie GC z definicji przenosi obiekty na żywo do pamięci defragmentacji.
btilly,
@GlenPeterson to dobra obserwacja, że ​​przenoszenie rzeczy na stercie jest ogromnym bólem synchronizacji, jest to często pomijane, chociaż zagęszczanie GC ma z tego powodu ogromny wpływ falowy na uruchomiony proces. Jest to jedyny największy powód, dla którego mówi się ludziom, aby robili wszystko, co w ich mocy, aby obiekty były jak najkrótsze, aby uniknąć aktualizacji dużych hałd powodujących, że zagęszczanie utrzymuje długi mutex. Nieznajomość sposobu, w jaki zachowują się te rzeczy, może doprowadzić do tak zwanego trybu GC Freakout Mode.
Jimmy Hoffa
2
Zarówno oryginalny system Macintosh, jak i Palm OS do zarządzania pamięcią korzystały z tabeli przeglądowej. Wskaźniki w tabeli były nazywane uchwytami. Przenoszący GC musi znać miejsce absolutnie pozytywnie każdego odniesienia do każdego poruszającego się obiektu; korzystanie z jednego stołu do takich celów znacznie upraszcza sprawę.
supercat