Czy użycie tablicy skrótów w procesie odśmiecania rozwiązałoby problem zatrzymania światowego znaku i zamiatania?

13

W algorytmie zbierania śmieci mark-sweep-compact musisz zatrzymać świat podczas przenoszenia obiektów, ponieważ wykres odniesienia staje się niespójny i musisz zastąpić wartości wszystkich odniesień wskazujących na obiekt.

Ale co, gdybyś miał tablicę skrótów z identyfikatorem obiektu jako kluczem i wskaźnikiem jako wartością, a referencje wskazywałyby na wspomniany identyfikator zamiast adresu obiektu ... wtedy ustalanie referencji wymagałoby zmiany tylko jednej wartości, a pauza byłaby potrzebna tylko, gdyby obiekt próbuje zostać zapisany podczas kopiowania ...

Czy w mojej linii myślenia jest błąd?

mrpyo
źródło

Odpowiedzi:

19

Aktualizacja referencji nie jest jedyną rzeczą, która wymaga pauzy. Wszystkie standardowe algorytmy zgrupowane w obszarze „przeciągnij znacznik” zakładają, że cały wykres obiektu pozostaje niezmieniony podczas zaznaczania. Prawidłowa obsługa modyfikacji (tworzone nowe obiekty, zmieniane odniesienia) wymaga dość trudnych alternatywnych algorytmów, takich jak algorytm trójkolorowy. Terminem parasolowym jest „równoczesne zbieranie śmieci”.

Ale tak, aktualizacja referencji po zagęszczeniu również wymaga przerwy. I tak, użycie pośrednictwa (np. Poprzez trwały identyfikator obiektu i tablicę skrótów do rzeczywistych wskaźników) może znacznie zmniejszyć pauzę. Możliwe jest nawet, aby uczynić tę część bez blokady, jeśli ktoś sobie tego życzy. Nadal byłoby tak samo trudne, jak każda współbieżność pamięci współdzielonej niskiego poziomu, ale nie ma fundamentalnego powodu, aby to nie działało.

Jednak , by to mieć poważne wady. Oprócz zajmowania dodatkowej przestrzeni ( co najmniej dwa dodatkowe słowa dla wszystkich obiektów), każda dereferencja jest znacznie droższa. Nawet coś tak prostego, jak uzyskanie atrybutu, obejmuje teraz pełne wyszukiwanie tabeli skrótów. Oceniłbym, że osiągnięty wynik jest znacznie gorszy niż w przypadku przyrostowego śledzenia.


źródło
Dobrze, że mamy dużo pamięci dzisiaj więc możemy mieć powiedzmy 50 Mb i tabela hash może być prosty modulo więc tylko jedna instrukcja ...
mrpyo
3
@mrpyo pobieranie wielkości tabeli haszującej, działanie modulo, dereferencja z przesunięcia tabeli haszowej w celu uzyskania rzeczywistego wskaźnika obiektu, dereferencja do samego obiektu. Plus ewentualnie tasowanie rejestrów. Skończyło się na 4+ instrukcjach. Ten schemat ma również problemy z lokalizacją pamięci: teraz zarówno tablica skrótu, jak i same dane muszą zmieścić się w pamięci podręcznej.
amon
@mrpyo Potrzebujesz jednego wpisu (identyfikator obiektu -> aktualny adres) na obiekt, prawda? I niezależnie od tego, jak tania jest funkcja skrótu, będziesz mieć kolizje i będziesz musiał je rozwiązać. Także to, co powiedział amon.
@amon to tylko kwestia czasu, zanim procesory będą miały co najmniej 50 MB pamięci podręcznej :)
Móż
1
@ Ᶎσᶎ Do tego czasu możemy umieścić 50 MiB tranzystorów na chipie i nadal mieć wystarczająco niskie opóźnienie, aby działało ono jako pamięć podręczna L1 lub L2 (pamięci podręczne L3 mają już rozmiar do 15 MiB, ale zwykle poza chipem AFAIK i daleko gorsze opóźnienie niż L1 i L2), będziemy mieli odpowiednio ogromne ilości pamięci głównej (i danych do włożenia). Tabela nie może mieć ustalonego rozmiaru, musi rosnąć wraz ze stertą.
19

Wszystkie problemy w informatyce mogą być rozwiązane przez inny poziom pośredni… z wyjątkiem problemu zbyt wielu warstw pośrednich

Twoje podejście nie rozwiązuje od razu problemu zbierania śmieci, ale przesuwa go tylko o jeden poziom wyżej. I za jaką cenę! Teraz każdy dostęp do pamięci podlega kolejnej dereferencji wskaźnika. Nie możemy buforować lokalizacji wyniku, ponieważ mogła ona zostać w międzyczasie przeniesiona, zawsze musimy przejść przez identyfikator obiektu. W większości systemów ta pośrednia nie jest akceptowalna i zakłada się, że zatrzymanie świata ma niższy całkowity koszt czasu wykonywania.

Powiedziałem, że twoja propozycja tylko porusza problem, a nie rozwiązuje go. Problem dotyczy ponownego użycia identyfikatorów obiektów. Identyfikatory obiektów są teraz naszym odpowiednikiem wskaźników i istnieje tylko skończona liczba adresów. Można sobie wyobrazić (szczególnie w systemie 32-bitowym), że w czasie życia twojego programu powstanie więcej niż obiektów INT_MAX, np. W pętli

while (true) {
    Object garbage = new Object();
}

Jeśli tylko zwiększymy identyfikator obiektu dla każdego obiektu, w pewnym momencie skończą nam się identyfikatory. Dlatego musimy dowiedzieć się, które identyfikatory są nadal w użyciu, a które są bezpłatne, aby można je było odzyskać. Brzmi znajomo? Wróciliśmy teraz do punktu wyjścia.

amon
źródło
Można przypuszczalnie użyć identyfikatorów, które są „wystarczająco duże”, powiedzmy 256-bitowych bignów? Nie twierdzę, że ten pomysł jest ogólnie dobry, ale prawie na pewno można obejść się przy ponownym użyciu IDS.
Rzeczywistość
@ Rzeczywistość realistycznie tak - z tego, co widzimy, można obejść problem ponownego użycia identyfikatora. Ale to tylko kolejny argument „640K powinien wystarczyć dla każdego” i tak naprawdę nie rozwiązuje problemu. Bardziej katastrofalnym aspektem jest to, że rozmiar wszystkich obiektów (i tabeli skrótów) musiałby wzrosnąć, aby pomieścić te ponadwymiarowe pseudo-wskaźniki, i że podczas dostępu do skrótu musimy porównać tę bigint z innymi identyfikatorami, które prawdopodobnie będą blokować wiele rejestrów , i weź wiele instrukcji do wykonania (przy 64-bitowym: 8 × obciążeniu, 4 × porównaniu, 3 × i co stanowi wzrost o 5 × w porównaniu z natywnymi intami).
amon
Tak, po pewnym czasie zabraknie Ci identyfikatorów i będziesz musiał zmienić je wszystkie, co wymagałoby przerwy. Ale być może byłoby to rzadkie wydarzenie ...
mrpyo,
@amon Bardzo się zgadzam, wszystkie bardzo dobre punkty, zdecydowanie lepiej jest mieć naprawdę zrównoważony system, zgadzam się. To będzie nieznośnie powolne, cokolwiek byś nie zrobił, to i tak jest interesujące tylko w teorii. Jednak osobiście nie jestem wielkim fanem śmieciarek: P
Vality
@amon: na świecie jest więcej kodu niż tylko ten, który popełniłby błąd, gdybyś owinął 64-bitowy identyfikator (584 lata nanosekund) i prawdopodobnie możesz zorganizować przydzielenie pamięci na 1ns, szczególnie jeśli nie odłamujesz globalnego licznika który wyrzuca identyfikatory!). Ale oczywiście, jeśli nie musisz na tym polegać, nie musisz.
Steve Jessop,
12

W twoim myśleniu nie ma błędu, właśnie opisałeś coś bardzo zbliżonego do tego, jak działał oryginalny moduł śmieciowy Java

Oryginalna maszyna wirtualna Java [6] i niektóre maszyny wirtualne Smalltalk używają wskaźników pośrednich, zwanych uchwytami w [6], w odniesieniu do obiektów. Uchwyty umożliwiają łatwe przenoszenie obiektów podczas wyrzucania elementów bezużytecznych, ponieważ przy uchwytach do każdego obiektu jest tylko jeden bezpośredni wskaźnik: ten w jego uchwycie. Wszystkie inne odniesienia do obiektu pośrednio przez uchwyt. W takich systemach pamięci opartych na uchwytach, podczas gdy adresy obiektów zmieniają się w czasie życia obiektów, a zatem nie można ich używać do mieszania, adresy uchwytów pozostają stałe.

Wydajne przestrzennie i czasowo mieszanie obiektów zbieranych śmieci

W bieżącej implementacji wirtualnej maszyny Java firmy Sun odwołanie do instancji klasy jest wskaźnikiem do uchwytu, który sam jest parą wskaźników: jeden do tabeli zawierającej metody obiektu i wskaźnik do obiektu klasy reprezentującego typ obiektu, a drugi do pamięci przydzielonej ze sterty Java dla danych obiektu.

Specyfikacja wirtualnej maszyny Java (1997)

Tak więc działa, zostało wypróbowane, a jego nieefektywność doprowadziła do opracowania systemów znakowania i zamiatania pokoleń.

Pete Kirkham
źródło
Prawdopodobnie te uchwyty nie były kluczami w tablicy mieszającej (jak w pytaniu)? Nie ma potrzeby, wystarczy struktura zawierająca wskaźnik. Następnie wszystkie uchwyty mają taki sam rozmiar, aby można je było przydzielić z przydziału sterty. Który ze swej natury nie wymaga wewnętrznego zagęszczania, ponieważ nie ulega fragmentacji. Możesz opłakiwać niemożność przeniesienia dużych bloków używanych przez ten alokator. Które można rozwiązać przez inny poziom pośredni ;-)
Steve Jessop
@ SteveJessop tak, nie było hashtable w implementacji gc, chociaż wartość uchwytu była również wartością zwracaną przezObject.getHashCode()
Pete Kirkham