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

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?

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.

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.

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