Dlaczego Garbage Collection tylko zamiata stosy?

Zasadniczo nauczyłem się do tej pory, że wyrzucanie elementów bezużytecznych usuwa na zawsze dowolną strukturę danych, która nie jest obecnie wskazywana. Ale to sprawdza tylko stos pod kątem takich warunków.

Dlaczego nie sprawdza również sekcji danych (globale, stałe itp.) Ani stosu? Co takiego jest w tej kupie, że jest to jedyna rzecz, którą chcemy, abyśmy byli śmieciami?

Garbage collector robi skanowanie stos - aby zobaczyć, jakie rzeczy w stercie są obecnie wykorzystywane (wskazywanego) przez rzeczy na stosie.

Śmieciarka nie ma sensu rozważać gromadzenia pamięci stosu, ponieważ stos nie jest zarządzany w ten sposób: wszystko na stosie jest uważane za „używane”. Pamięć używana przez stos jest automatycznie odzyskiwana po powrocie z wywołań metod. Zarządzanie pamięcią miejsca na stosie jest tak proste, tanie i łatwe, że nie chcesz angażować śmieci.

(Istnieją systemy, takie jak smalltalk, w których ramki stosu są pierwszorzędnymi obiektami przechowywanymi w stercie, a śmieci zbierane jak wszystkie inne obiekty. Ale to nie jest obecnie popularne podejście. Java JVM i CLR Microsoftu używają stosu sprzętu i ciągłej pamięci .)

Odwróć swoje pytanie. Prawdziwe motywujące pytanie brzmi: w jakich okolicznościach możemy uniknąć kosztów wywozu śmieci?

Po pierwsze, jakie są koszty wywozu śmieci? Istnieją dwa główne koszty. Najpierw musisz ustalić, co żyje ; co wymaga potencjalnie dużo pracy. Po drugie, musisz zagęścić dziury , które powstają, gdy uwolnisz coś, co zostało podzielone na dwie żywe rzeczy. Te dziury są marnotrawstwem. Ale ich kompaktowanie jest również drogie.

Jak możemy uniknąć tych kosztów?

Oczywiście, jeśli możesz znaleźć wzorzec użycia pamięci, w którym nigdy nie przydzielasz czegoś długowiecznego, a następnie przydzielasz coś krótkotrwałego, a następnie przydzielasz coś długowiecznego, możesz wyeliminować koszt dziur. Jeśli możesz zagwarantować, że w przypadku niektórych podzbiorów magazynu każdy kolejny przydział jest krótszy niż poprzedni w tym magazynie, nigdy nie będzie żadnych dziur w tym magazynie.

Ale jeśli rozwiązaliśmy problem dziury, to rozwiązaliśmy również problem usuwania śmieci . Czy masz coś w tym magazynie, który wciąż żyje? Tak. Czy wszystko zostało przydzielone, zanim trwało dłużej? Tak - to założenie eliminuje możliwość powstawania dziur. Dlatego wszystko, co musisz zrobić, to powiedzieć „czy ostatnia alokacja jest aktualna?” i wiesz, że wszystko żyje w tym magazynie.

Czy mamy zestaw przydziałów pamięci, w którym wiemy, że każdy kolejny przydział jest krótszy niż poprzedni? Tak! Ramki aktywacyjne metod są zawsze niszczone w odwrotnej kolejności niż zostały utworzone, ponieważ są one zawsze krótsze niż aktywacja, która je utworzyła.

Dlatego możemy przechowywać ramki aktywacyjne na stosie i wiedzieć, że nigdy nie trzeba ich zbierać. Jeśli na stosie jest jakaś ramka, cały zestaw ramek pod nią jest dłuższy, więc nie trzeba ich zbierać. I zostaną zniszczone w odwrotnej kolejności niż zostały stworzone. Koszt zbierania śmieci jest w ten sposób wyeliminowany dla ramek aktywacyjnych.

Właśnie dlatego mamy tymczasową pulę na stosie: ponieważ jest to prosty sposób na wdrożenie aktywacji metody bez ponoszenia kary za zarządzanie pamięcią.

(Oczywiście koszt wyrzucania śmieci do pamięci, o którym mowa w odnośnikach do ramek aktywacyjnych, nadal istnieje).

Rozważmy teraz system kontroli przepływu, w którym ramki aktywacyjne nie są niszczone w przewidywalnej kolejności. Co się stanie, jeśli aktywacja krótkotrwała może spowodować aktywację długoterminową? Jak możesz sobie wyobrazić, na tym świecie nie możesz już używać stosu do optymalizacji potrzeby zbierania aktywacji. Zestaw aktywacji może ponownie zawierać dziury.

C # 2.0 ma tę funkcję w postaci yield return. Metoda, która zwraca zysk, zostanie ponownie aktywowana w późniejszym czasie - przy następnym wywołaniu MoveNext - a kiedy tak się stanie, nie jest przewidywalna. W związku z tym informacje, które normalnie byłyby na stosie dla ramki aktywacyjnej bloku iteratora, są zamiast tego przechowywane na stercie, gdzie są gromadzone śmieci po zebraniu modułu wyliczającego.

Podobnie funkcja „asynchronizuj / czekaj” pojawiająca się w następnych wersjach C # i VB pozwoli ci tworzyć metody, których aktywacje „dają” i „wznawiają” w ściśle określonych punktach podczas działania metody. Ponieważ ramki aktywacyjne nie są już tworzone i niszczone w przewidywalny sposób, wszystkie informacje, które były przechowywane na stosie, będą musiały być przechowywane na stosie.

To tylko przypadek historii, że przez kilka dziesięcioleci zdecydowaliśmy, że języki z ramkami aktywacyjnymi, które są tworzone i niszczone w ściśle uporządkowany sposób, są modne. Ponieważ współczesne języki w coraz większym stopniu nie mają tej właściwości, należy spodziewać się, że coraz więcej języków będzie potwierdzało kontynuację na stosie śmieci, a nie stosie.

Najbardziej oczywistą odpowiedzią, a może nie najpełniejszą, jest to, że stertą jest lokalizacja danych instancji. Przez dane instancji rozumiemy dane reprezentujące instancje klas, czyli obiekty, które są tworzone w czasie wykonywania. Dane te są z natury dynamiczne, a liczba tych obiektów, a tym samym ilość zajmowanej przez nie pamięci, jest znana tylko w czasie wykonywania. MUSI być pewien problem z odzyskaniem tej pamięci, ponieważ długo działające programy zużywałyby całą pamięć z czasem.

Pamięć zużywana przez definicje klas, stałe i inne statyczne struktury danych z natury rzeczy raczej nie zwiększy się bez kontroli. Ponieważ w pamięci występuje tylko jedna definicja klasy na nieznaną liczbę wystąpień tej klasy, ma sens, że ten typ struktury nie stanowi zagrożenia dla użycia pamięci.

Warto wziąć pod uwagę powód, dla którego mamy śmieci, ponieważ czasami trudno jest określić, kiedy należy cofnąć przydział pamięci. Naprawdę masz tylko ten problem ze stertą. Dane przydzielone na stosie zostaną ostatecznie zwolnione, więc tak naprawdę nie ma potrzeby usuwania śmieci. Zakłada się, że rzeczy w sekcji danych są przydzielane na cały okres istnienia programu.

1. Ich wielkość jest przewidywalna (stała, z wyjątkiem stosu, a stos jest zwykle ograniczony do kilku MB) i zwykle bardzo mały (co najmniej w porównaniu do setek MB, które mogą przydzielić duże aplikacje).

2. Dynamicznie przydzielane obiekty mają zazwyczaj krótki przedział czasowy, w którym są osiągalne. Po tym nie będzie już możliwości, aby można było do nich odwoływać. Porównajmy to z wpisami w sekcji danych, zmiennymi globalnymi i takimi: Często jest fragment kodu, który odwołuje się do nich bezpośrednio (pomyśl const char *foo() { return "foo"; }). Normalnie kod się nie zmienia, więc odwołanie pozostanie, a kolejne odwołanie zostanie utworzone za każdym razem, gdy funkcja zostanie wywołana (co może być w dowolnym momencie, o ile komputer wie - chyba że rozwiążesz problem zatrzymania, to znaczy ). Tak więc i tak nie można uwolnić większości pamięci, ponieważ zawsze będzie ona dostępna.

3. W wielu językach, które są śmieciami, wszystko , co należy do uruchomionego programu, jest alokowane na stos. W Pythonie po prostu nie ma sekcji danych i wartości przypisywanych do stosu (istnieją odwołania do zmiennych lokalnych i stos wywołań, ale nie ma też wartości w tym samym sensie, co intw C). Każdy obiekt jest na stercie.

Jak powiedziało wielu innych respondentów, stos jest częścią zestawu głównego, więc jest skanowany w poszukiwaniu referencji, ale nie „zbierany” per se.

Chcę tylko odpowiedzieć na niektóre komentarze sugerujące, że śmieci na stosie nie mają znaczenia; tak, ponieważ może spowodować, że więcej śmieci na stercie zostanie uznane za osiągalne. Sumienni autorzy maszyn wirtualnych i kompilatorów albo null out, albo w inny sposób wykluczają martwe części stosu ze skanowania. IIRC, niektóre maszyny wirtualne mają tabele mapujące zakresy komputerów na bitmapy stosu szczelin stosu, a inne po prostu niwelują szczeliny. Nie wiem, jaka technika jest obecnie preferowana.

Jednym terminem używanym do opisania tego szczególnego rozważania jest „ bezpieczne dla przestrzeni kosmicznej” .

Pozwolę sobie wskazać kilka fundamentalnych nieporozumień, które myliłeś się i wielu innych:

„Dlaczego Garbage Collection tylko zamiata stosy?” Odwrotnie. Tylko najprostsi, najbardziej konserwatywni i najwolniejsi śmieciarze zamiatają stertę. Dlatego są tacy powolni.

Szybkie śmieciarze tylko zamiatają stos (i opcjonalnie niektóre inne katalogi główne, takie jak niektóre globale dla wskaźników FFI i rejestry dla wskaźników aktywnych) i kopiują tylko wskaźniki osiągalne przez obiekty stosu. Reszta jest wyrzucana (tj. Ignorowana), w ogóle nie skanując stosu.

Ponieważ stos jest około 1000 razy większy niż stos (stosy), taki GC do skanowania stosów jest zwykle znacznie szybszy. ~ 15ms vs 250ms na stosach normalnej wielkości. Ponieważ kopiuje (przenosi) obiekty z jednej przestrzeni do drugiej, najczęściej nazywany jest kolektorem do kopiowania półprzestrzeni, potrzebuje 2x pamięci i dlatego w większości nie nadaje się do użytku na bardzo małych urządzeniach lubi telefony z małą ilością pamięci. Kompaktuje, więc jest bardzo przyjazny dla pamięci podręcznej, w przeciwieństwie do prostych skanerów znaczników i zamiatania stosów.

Ponieważ poruszają się wskaźniki, FFI, tożsamość i referencje są trudne. Tożsamość zazwyczaj rozwiązuje się za pomocą losowych identyfikatorów, referencji za pośrednictwem wskaźników przekazywania. FFI jest trudne, ponieważ obce obiekty nie mogą powstrzymywać wskaźników do starej przestrzeni. Wskaźniki FFI są zwykle przechowywane na osobnej arenie hałdy, np. Z wolnym kolorem statycznym i znacznikiem. Lub banalny malloc z rachunkowością. Zauważ, że malloc ma ogromne koszty ogólne i rachunki jeszcze więcej.

Mark & ​​sweep jest trywialny w implementacji, ale nie powinien być używany w prawdziwych programach, a zwłaszcza nie powinien być nauczany jako standardowy kolektor. Najsłynniejszy z takich szybkich skanerów kopiujących stosy nazywany jest kolekcjonerem dwóch palców Cheney .

Co jest przydzielane na stosie? Zmienne lokalne i adresy zwrotne (w C). Gdy funkcja zwraca, jej zmienne lokalne są odrzucane. Zamiatanie stosu nie jest konieczne, a nawet szkodliwe.

Wiele języków dynamicznych, a także Java lub C # są zaimplementowane w systemowym języku programowania, często w C. Można powiedzieć, że Java jest implementowana z funkcjami C i używa lokalnych zmiennych C, a zatem moduł śmieciowy Javy nie musi zamiatać stosu.

Istnieje ciekawy wyjątek: moduł zbierający śmieci w programie Chicken Scheme wymiata stos (w pewien sposób), ponieważ jego implementacja używa stosu jako przestrzeni do śmieci pierwszej generacji: patrz Wikipedia Scheme Chicken .