Dlaczego Garbage Collection tylko zamiata stosy?

28

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?

Mroczny Templariusz
źródło
21
„zamiatanie stosu” jest bezpieczniejsze niż „walenie w stos” ... :-)
Brian Knoblauch,

Odpowiedzi:

62

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

Jeff Grigg
źródło
7
+1 do stosu jest zawsze w pełni osiągalny, więc nie ma sensu go zamiatać
maniak zapadkowy
2
+1 dziękuję, wziął 4 posty, aby trafić właściwą odpowiedź. Nie wiem, dlaczego musiałeś powiedzieć, że wszystko na stosie jest „uważane” za używane, jest używane co najmniej tak samo silnie, jak używane są obiekty stosu - ale to naprawdę drobiazg bardzo dobra odpowiedź.
psr
@psr ma na myśli, że wszystko na stosie jest osiągalne i nie trzeba go zbierać, dopóki metoda nie powróci, ale (RAII) jest już jawnie zarządzany
maniak ratchet
@ratchetfreak - Wiem. I chodziło mi tylko o to, że słowo „rozważane” prawdopodobnie nie jest potrzebne, bez wyraźniejszego wyrażania się lepiej.
psr.
5
@psr: Nie zgadzam się. „ uważany za używany” jest bardziej poprawny zarówno dla stosu, jak i sterty, z bardzo ważnych powodów. To, czego chcesz, to odrzucić to, czego już nie użyjesz; robisz to, że odrzucasz to, co nieosiągalne . Być może masz dostępne dane, których nigdy nie będziesz potrzebować; gdy te dane rosną, masz przeciek pamięci (tak, są one możliwe nawet w językach GC, w przeciwieństwie do wielu osób). I można argumentować, że zdarzają się również wycieki stosu, najczęstszym przykładem są niepotrzebne ramki stosu w programach rekurencyjnych uruchamianych bez eliminacji wywołania ogona (np. W JVM).
Blaisorblade,
19

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

Po pierwsze, jakie 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.

Eric Lippert
źródło
13

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.

Czad
źródło
5
Ale sterta nie jest lokalizacją „danych instancji”. Mogą też znajdować się na stosie.
svick,
@svick Oczywiście zależy od języka. Java obsługuje tylko obiekty alokowane na stosie, a Vala dość wyraźnie rozróżnia między alokacją sterty (klasa) a alokacją stosu (struct).
puszysty
1
@fluffy: są to bardzo ograniczone języki, nie można zakładać, że tak jest w ogóle, ponieważ nie określono żadnego języka.
Matthieu M.,
@MatthieuM. To był mój punkt widzenia.
puszysty
@fluffy: dlaczego więc klasy są przydzielane na stercie, a struktury na stosie?
Dark Templar,
10

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.

Jason Baker
źródło
1
Nie tylko zostanie on ostatecznie „zwolniony”, ale zostanie zwolniony w odpowiednim czasie.
Boris Yankov,
3
  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.


źródło
„W Pythonie po prostu nie ma sekcji danych”. To nie jest ściśle prawdą. Żadne, Prawda i Fałsz są przydzielane w sekcji danych, jak rozumiem: stackoverflow.com/questions/7681786/how-is-hashnone-calculated
Jason Baker,
@JasonBaker: Ciekawe znalezisko! Nie ma to jednak żadnego efektu. Jest to szczegół implementacji i jest ograniczony do wbudowanych obiektów. Nie wspominając już o tym, że te obiekty nie powinny być nigdy zwolnione w czasie trwania programu, nie są i są również małe (chyba mniej niż 32 bajty każdy).
@delnan Jak zauważył Eric Lippert, w większości języków istnienie osobnych regionów pamięci dla stosu i sterty jest szczegółem implementacji. Możesz wdrożyć większość języków bez użycia stosu (choć wydajność może się pogorszyć) i nadal być zgodna ze specyfikacjami
Jules
2

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

Ryan Culpepper
źródło
Byłoby interesujące wiedzieć. Pierwsza myśl jest taka, że ​​niwelowanie przestrzeni jest najbardziej realistyczne. Przemierzanie drzewa wykluczonych obszarów może potrwać dłużej niż tylko skanowanie zer. Oczywiście każda próba zagęszczenia stosu jest pełna niebezpieczeństw! Sprawienie, by ta praca brzmiała jak proces zginania / podatności na błędy.
Brian Knoblauch,
@Brian, Właściwie, myśląc o tym trochę więcej, dla maszyny wirtualnej i tak potrzebujesz czegoś takiego, więc możesz określić, które szczeliny są referencjami, a nie liczbami całkowitymi, liczbami zmiennymi itp. Również na temat kompaktowania stosu, patrz „CONS powinien Nie CONS jego argumenty ”Henry Baker.
Ryan Culpepper
Określenie typów gniazd i sprawdzenie, czy są one odpowiednio używane, może i zwykle odbywa się statycznie, albo w czasie kompilacji (dla maszyn wirtualnych używających zaufanego kodu bajtowego), albo w czasie ładowania (gdzie kod bajtowy pochodzi z niezaufanego źródła, np. Java).
Jules
1

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 .

rurban
źródło
Wydaje się, że pytanie dotyczy raczej tego, które części pamięci są gromadzone, a nie konkretnych algorytmów. Ostatnie zdanie w szczególności sugeruje, że OP używa „zamiatania” jako ogólnego synonimu „odśmiecania”, a nie konkretnego mechanizmu do implementacji odśmiecania. Biorąc to pod uwagę, twoja odpowiedź brzmi: powiedz, że tylko najprostsze śmieciarze zbierają śmieci, a szybkie śmieciarze zamiast śmieci zbierają stos i pamięć statyczną, pozostawiając stertę do wzrostu i wzrostu, aż zabraknie pamięci.
8bittree,
Nie, pytanie było bardzo konkretne i sprytne. Odpowiedzi nie tak. Powolne zaznaczanie i zamiatanie GC mają dwie fazy: krok oznaczenia skanuje korzenie na stosie, a etap zamiatania skanuje stos. Szybkie kopiowanie GC ma tylko jedną fazę, skanowanie stosu. To takie proste. Ponieważ najwyraźniej nikt tutaj nie wie o właściwych śmieciarzach, na pytanie należy odpowiedzieć. Twoja interpretacja jest szalona.
rurban
0

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 .

dokładnie
źródło