Warum fegt die Garbage Collection nur den Haufen?

28

Grundsätzlich habe ich bisher erfahren, dass die Garbage Collection für immer alle Datenstrukturen löscht, auf die derzeit nicht verwiesen wird. Dies überprüft jedoch nur den Heap auf solche Bedingungen.

Warum überprüft es nicht auch den Datenbereich (Globals, Konstanten usw. usw.) oder den Stack? Was ist mit dem Haufen, dass es das einzige ist, was wir Müll sammeln wollen?

Dunkler Templer
quelle
21
"Sweep the Heap" ist sicherer als "Whack the Stack" ... :-)
Brian Knoblauch

Antworten:

62

Der Garbage Collector hat den Stapel scannen - um zu sehen , was die Dinge in der Halde sind zur Zeit (spitz zu) verwendet werden , auf dem Stapel von Dingen.

Es macht keinen Sinn, dass der Garbage Collector das Sammeln von Stapelspeicher in Betracht zieht, da der Stapel nicht auf diese Weise verwaltet wird: Alles auf dem Stapel wird als "in Verwendung" betrachtet. Der vom Stapel belegte Speicher wird automatisch zurückgefordert, wenn Sie von Methodenaufrufen zurückkehren. Die Speicherverwaltung des Stapelspeichers ist so einfach, kostengünstig und unkompliziert, dass Sie nicht möchten, dass die Garbage Collection beteiligt wird.

(Es gibt Systeme wie Smalltalk, bei denen Stack-Frames erstklassige Objekte sind, die im Heap gespeichert sind, und Garbage, der wie alle anderen Objekte gesammelt wird. Dies ist jedoch heutzutage nicht der gängige Ansatz. Javas JVM und Microsofts CLR verwenden den Hardware-Stack und den zusammenhängenden Speicher .)

Jeff Grigg
quelle
7
+1 Der Stapel ist immer voll erreichbar, daher macht es keinen Sinn, ihn zu fegen
Ratschenfreak
2
+1 Danke, habe 4 Beiträge geschrieben, um die richtige Antwort zu finden. Ich weiß nicht, warum Sie sagen mussten, dass alles auf dem Stapel als "in Gebrauch" betrachtet wird, es ist in Gebrauch, zumindest so stark, wie noch in Gebrauch befindliche Heap-Objekte in Gebrauch sind - aber das ist ein echter Trottel eine sehr gute antwort.
PSR
@psr er bedeutet, dass alles auf dem Stapel sehr gut erreichbar ist und nicht gesammelt werden muss, bis die Methode zurückkehrt, aber dass (RAII) bereits explizit verwaltet wird
Ratschenfreak
@ratchetfreak - ich weiß. Und ich meinte nur, dass das Wort "überlegt" wahrscheinlich nicht gebraucht wird, es ist in Ordnung, eine stärkere Aussage zu machen, ohne es.
PSR
5
@psr: Ich bin anderer Meinung. " Wird als in Verwendung betrachtet" ist aus sehr wichtigen Gründen sowohl für Stapel als auch für Haufen korrekter. Was Sie wollen, ist zu verwerfen, was nicht wieder verwendet wird; Was Sie tun, ist, dass Sie verwerfen, was nicht erreichbar ist . Möglicherweise haben Sie erreichbare Daten, die Sie nie brauchen werden. Wenn diese Daten größer werden, ist ein Speicherverlust aufgetreten (ja, sie sind sogar in GC-Sprachen möglich, anders als viele denken). Und man könnte argumentieren, dass auch Stack-Lecks auftreten. Das häufigste Beispiel sind nicht benötigte Stack-Frames in rekursiven Programmen, die ohne Tail-Call-Eliminierung ausgeführt werden (z. B. auf der JVM).
Blaisorblade
19

Drehen Sie Ihre Frage um. Die eigentliche motivierende Frage ist, unter welchen Umständen wir die Kosten für die Müllabfuhr vermeiden können.

Nun, zunächst einmal, was sind die Kosten für die Garbage Collection? Es gibt zwei Hauptkosten. Zunächst müssen Sie feststellen, was noch lebt . das erfordert möglicherweise viel arbeit. Zweitens müssen Sie die Löcher komprimieren , die entstehen, wenn Sie etwas freigeben, das zwischen zwei noch lebenden Dingen aufgeteilt wurde. Diese Löcher sind verschwenderisch. Sie zu verdichten ist aber auch teuer.

Wie können wir diese Kosten vermeiden?

Wenn Sie ein Speichernutzungsmuster finden, bei dem Sie niemals etwas Langlebiges zuweisen, dann etwas Kurzlebiges zuweisen und dann etwas Langlebiges zuweisen, können Sie die Kosten von Löchern eliminieren. Wenn Sie sicherstellen können, dass für eine Teilmenge Ihres Speichers jede nachfolgende Zuordnung kürzer als die vorherige Zuordnung in diesem Speicher ist, werden in diesem Speicher keine Lücken mehr vorhanden sein.

Aber wenn wir das Lochproblem gelöst haben, haben wir auch das Garbage Collection-Problem gelöst . Haben Sie etwas in diesem Speicher, das noch lebt? Ja. Wurde alles zugeteilt, bevor es länger lebte? Ja - diese Annahme ist, wie wir die Möglichkeit von Löchern beseitigt haben. Sie müssen also nur sagen: "Ist die letzte Zuweisung noch aktiv?" und Sie wissen, dass in diesem Speicher alles lebendig ist.

Haben wir eine Reihe von Speicherzuordnungen, bei denen wir wissen, dass jede nachfolgende Zuordnung von kurzer Dauer ist als die vorherige Zuordnung? Ja! Aktivierungsframes von Methoden werden immer in der entgegengesetzten Reihenfolge zerstört, in der sie erstellt wurden, da sie immer kürzer sind als die Aktivierung, die sie erstellt hat.

Daher können wir Aktivierungsrahmen auf dem Stapel speichern und wissen, dass sie niemals gesammelt werden müssen. Befindet sich ein Frame auf dem Stapel, ist der gesamte Satz von Frames darunter länger haltbar, sodass sie nicht gesammelt werden müssen. Und sie werden in der entgegengesetzten Reihenfolge zerstört, in der sie erschaffen wurden. Die Kosten für die Speicherbereinigung entfallen somit für Aktivierungsrahmen.

Deshalb haben wir in erster Linie den temporären Pool auf dem Stack: weil dies eine einfache Möglichkeit ist, die Methodenaktivierung zu implementieren, ohne dass ein Speicher-Management-Aufwand entsteht.

(Natürlich sind die Kosten für das Sammeln des Speichers , auf den in den Aktivierungsrahmen verwiesen wird, immer noch da.)

Stellen Sie sich nun ein Kontrollflusssystem vor, bei dem Aktivierungsrahmen nicht in einer vorhersehbaren Reihenfolge zerstört werden. Was passiert, wenn eine kurzlebige Aktivierung zu einer langlebigen Aktivierung führen kann? Wie Sie sich vorstellen können, können Sie in dieser Welt den Stapel nicht mehr verwenden, um die Notwendigkeit zu optimieren, Aktivierungen zu sammeln. Der Aktivierungssatz kann wieder Löcher enthalten.

C # 2.0 hat diese Funktion in Form von yield return. Eine Methode, die eine Rendite erzielt, wird zu einem späteren Zeitpunkt - wenn MoveNext das nächste Mal aufgerufen wird - wieder aktiviert. Wann dies geschieht, ist nicht vorhersehbar. Daher werden die Informationen, die sich normalerweise auf dem Stapel für den Aktivierungsrahmen des Iteratorblocks befinden, stattdessen auf dem Heap gespeichert, wo sie beim Sammeln des Enumerators als Müll gesammelt werden.

In ähnlicher Weise können Sie mit der Funktion "Async / Warten", die in den nächsten Versionen von C # und VB verfügbar ist, Methoden erstellen, deren Aktivierungen an genau definierten Punkten während der Aktion der Methode "nachgeben" und "wieder aufnehmen". Da die Aktivierungsframes nicht mehr auf vorhersehbare Weise erstellt und zerstört werden, müssen alle Informationen, die zuvor im Stapel gespeichert waren, im Heap gespeichert werden.

Es ist nur ein Zufall der Geschichte, dass wir für einige Jahrzehnte entschieden haben, dass Sprachen mit Aktivierungsrahmen, die streng geordnet erstellt und zerstört werden, in Mode sind. Da modernen Sprachen diese Eigenschaft zunehmend fehlt, erwarten Sie immer mehr Sprachen, die Fortsetzungen auf dem mit Müll gesammelten Haufen statt auf dem Stapel wiedergeben.

Eric Lippert
quelle
13

Die naheliegendste und vielleicht nicht die vollständigste Antwort ist, dass der Heap die Position der Instanzdaten ist. Mit Instanzdaten sind die Daten gemeint, die die Instanzen von Klassen oder Objekten darstellen, die zur Laufzeit erstellt werden. Diese Daten sind von Natur aus dynamisch und die Anzahl dieser Objekte und damit der Speicherbedarf ist erst zur Laufzeit bekannt. Die Wiederherstellung dieses Speichers muss schmerzhaft sein, oder lang laufende Programme würden im Laufe der Zeit den gesamten Speicher belegen.

Es ist unwahrscheinlich, dass der von Klassendefinitionen, Konstanten und anderen statischen Datenstrukturen belegte Speicher ungeprüft zunimmt. Da es nur eine Klassendefinition im Speicher für eine unbekannte Anzahl von Laufzeitinstanzen dieser Klasse gibt, ist es sinnvoll, dass dieser Strukturtyp keine Bedrohung für die Speichernutzung darstellt.

Tschad
quelle
5
Der Heap ist jedoch nicht der Speicherort von "Instanzdaten". Sie können auch auf dem Stapel sein.
Svick
@svick Kommt natürlich auf die Sprache an. Java unterstützt nur Heap-allokierte Objekte, und Vala unterscheidet ganz explizit zwischen Heap-allokierten (Klasse) und Stack-allokierten (Struktur) Objekten.
flauschiger
1
@fluffy: das sind sehr eingeschränkte sprachen, man kann nicht davon ausgehen, dass dies generell gilt, da keine sprache präzisiert wurde.
Matthieu M.
@MatthieuM. Das war irgendwie mein Punkt.
flauschiger
@fluffy: Warum werden also Klassen im Heap zugewiesen, während Strukturen im Stack zugewiesen werden?
Dunkle Templer
10

Es lohnt sich, den Grund für die Garbage Collection zu berücksichtigen: Manchmal ist es schwierig zu wissen, wann Speicher freigegeben werden muss. Sie haben wirklich nur dieses Problem mit dem Haufen. Auf dem Stapel zugewiesene Daten werden schließlich freigegeben, sodass dort keine Speicherbereinigung erforderlich ist. Es wird allgemein davon ausgegangen, dass Dinge im Datenbereich für die Laufzeit des Programms zugewiesen werden.

Jason Baker
quelle
1
Es wird nicht nur "irgendwann" freigegeben, sondern es wird zum richtigen Zeitpunkt freigegeben.
Boris Yankov
3
  1. Die Größe dieser ist vorhersehbar (konstant mit Ausnahme des Stapels, und der Stapel ist normalerweise auf einige MB beschränkt) und normalerweise sehr klein (zumindest im Vergleich zu den Hunderten von MB, die große Anwendungen zuweisen können).

  2. Dynamisch zugewiesene Objekte haben normalerweise einen kleinen Zeitrahmen, in dem sie erreichbar sind. Danach können sie nie wieder referenziert werden. Vergleichen Sie dies mit Einträgen im Datenbereich, globalen Variablen und dergleichen: Häufig gibt es einen Code, der direkt auf sie verweist (think const char *foo() { return "foo"; }). Normalerweise ändert sich der Code nicht, sodass die Referenz erhalten bleibt und jedes Mal, wenn die Funktion aufgerufen wird, eine neue Referenz erstellt wird (dies kann nach Kenntnis des Computers jederzeit der Fall sein - es sei denn, Sie lösen das Problem des Anhaltens ). So konnte man sowieso den größten Teil des Speichers nicht freigeben, da er immer erreichbar wäre.

  3. In vielen müllsammelnden Sprachen wird alles , was zu dem ausgeführten Programm gehört, auf Heap reserviert. In Python gibt es einfach keinen Datenabschnitt und keine vom Stapel zugewiesenen Werte (es gibt die Referenzen, die lokale Variablen enthalten, und es gibt den Aufrufstapel, aber es gibt keinen Wert im gleichen Sinne wie intin C). Jedes Objekt ist auf dem Haufen.


quelle
Msgstr "In Python gibt es einfach keinen Datenabschnitt". Dies ist streng genommen nicht wahr. Keine, Richtig
Jason Baker
@JasonBaker: Interessante Entdeckung! Es hat jedoch keine Wirkung. Es ist ein Implementierungsdetail und auf eingebaute Objekte beschränkt. Das heißt nicht, dass diese Objekte ohnehin nie im Laufe des Programms freigegeben werden sollen, und auch winzig sind (jeweils weniger als 32 Byte, würde ich vermuten).
@delnan Wie Eric Lippert gerne betont, ist für die meisten Sprachen die Existenz separater Speicherbereiche für den Stack und den Heap ein Implementierungsdetail. Sie können die meisten Sprachen implementieren, ohne einen Stack zu verwenden (obwohl die Leistung darunter leiden kann) und dennoch die Spezifikationen
Jules
2

Wie eine Reihe anderer Responder bereits sagte, ist der Stack Teil des Root-Sets, so dass er nach Referenzen durchsucht, aber nicht per se "gesammelt" wird.

Ich möchte nur auf einige der Kommentare antworten, die implizieren, dass Müll auf dem Stapel keine Rolle spielt. Dies ist der Fall, da dadurch möglicherweise mehr Müll auf dem Haufen als erreichbar eingestuft wird. Gewissenhafte VM- und Compiler-Writer können tote Teile des Stapels entweder vom Scannen ausschließen oder auf andere Weise ausschließen. IIRC, einige VMs haben Tabellen, die PC-Bereiche zu Bitmaps mit Stack-Slot-Liveness zuordnen, andere löschen die Slots einfach aus. Ich weiß nicht, welche Technik derzeit bevorzugt wird.

Ein Begriff, der verwendet wird, um diese besondere Überlegung zu beschreiben, ist Raumsicherheit .

Ryan Culpepper
quelle
Wäre interessant zu wissen. Der erste Gedanke ist, dass das Ausgleichen von Leerzeichen am realistischsten ist. Das Durchsuchen eines Baums ausgeschlossener Bereiche kann durchaus länger dauern als nur das Durchsuchen von Nullen. Offensichtlich ist jeder Versuch, den Stapel zu verdichten, mit Gefahren behaftet! Das klingt nach einem nervenaufreibenden / fehleranfälligen Prozess.
Brian Knoblauch
@Brian, Wenn Sie etwas mehr darüber nachdenken, benötigen Sie für eine typisierte VM sowieso so etwas, damit Sie bestimmen können, welche Slots im Gegensatz zu Ganzzahlen, Gleitkommazahlen usw. Referenzen sind. Informationen zum Komprimieren des Stapels finden Sie unter "CONS Should Keine Nachteile "von Henry Baker.
Ryan Culpepper
Das Ermitteln der Steckplatztypen und das Überprüfen ihrer ordnungsgemäßen Verwendung kann und wird in der Regel statisch ausgeführt, entweder zur Kompilierungszeit (für VMs, die vertrauenswürdigen Bytecode verwenden) oder zum Zeitpunkt des Ladens (wenn der Bytecode aus einer nicht vertrauenswürdigen Quelle stammt, z. B. Java).
Jules
1

Lassen Sie mich auf einige grundlegende Missverständnisse hinweisen, die Sie und viele andere falsch verstanden haben:

"Warum fegt Garbage Collection nur den Haufen?" Es ist umgekehrt. Nur die einfachsten, konservativsten und langsamsten Müllsammler fegen den Haufen. Deshalb sind sie so langsam.

Schnelle Garbage Collectors durchsuchen nur den Stack (und optional einige andere Roots, z. B. einige Globals für FFI-Zeiger und die Register für Live-Zeiger) und kopieren nur die Zeiger, auf die die Stack-Objekte zugreifen können. Der Rest wird weggeworfen (dh ignoriert), ohne den Haufen zu durchsuchen.

Da der Heap ungefähr 1000x größer ist als die Stapel, ist ein solcher Stapel-Scan-GC in der Regel viel schneller. ~ 15 ms vs 250 ms auf normal großen Haufen. Da es sich um das Kopieren (Verschieben) von Objekten von einem Raum in einen anderen handelt, wird es meistens als Semi-Space-Kopiersammler bezeichnet. Es benötigt 2x Speicher und ist daher auf sehr kleinen Geräten meist nicht verwendbar. Es wird komprimiert und ist daher im Gegensatz zu einfachen Mark & ​​Sweep-Heap-Scannern sehr cachefreundlich.

FFI, Identität und Referenzen sind schwierig, da sie Zeiger bewegen. Identität wird normalerweise mit zufälligen IDs gelöst, Verweise über Weiterleitungszeiger. FFI ist schwierig, da Fremdkörper keine Zeiger auf das alte Feld zurückhalten können. FFI-Zeiger werden normalerweise in einer separaten Heap-Arena aufbewahrt, z. B. mit einem statischen Slow-Mark & ​​Sweep-Kollektor. Oder triviales Malloc mit Nachzählung. Beachten Sie, dass Malloc einen enormen Overhead hat und noch mehr zählt.

Mark & ​​Sweep ist trivial zu implementieren, sollte aber nicht in echten Programmen verwendet werden und insbesondere nicht als Standardkollektor unterrichtet werden. Der bekannteste dieser schnellen Stapel-Scan-Kopiersammler heißt Cheney-Zweifingersammler .

Rurban
quelle
Die Frage scheint eher danach zu gehen, welche Teile des Speichers mit Speicherbereinigung erstellt werden, als nach bestimmten Algorithmen für die Speicherbereinigung. Der letzte Satz impliziert insbesondere, dass das OP "Sweep" als generisches Synonym für "Garbage Collect" verwendet und nicht als spezifischer Mechanismus zur Implementierung der Garbage Collection. In Anbetracht dessen lautet Ihre Antwort, dass nur die einfachsten Garbage Collectors den Heap sammeln und schnelle Garbage Collectors stattdessen den Stack und den statischen Speicher sammeln, sodass der Heap wachsen und wachsen kann, bis ihm der Speicher ausgeht.
8bittree
Nein, die Frage war sehr spezifisch und klug. Die Antworten nicht so. Langsame Markierungs- und Sweep-GCs haben zwei Phasen: den Markierungsschritt zum Scannen der Wurzeln auf dem Stapel und die Sweep-Phase zum Scannen des Heaps. Schnelle Kopier-GCs haben nur eine Phase: Sie scannen den Stapel. So einfach ist das. Da hier anscheinend niemand etwas über richtige Müllsammler weiß, muss die Frage beantwortet werden. Ihre Interpretation ist verrückt.
Rurban
0

Was ist auf dem Stapel zugeordnet? Lokale Variablen und Rücksprungadressen (in C). Wenn eine Funktion zurückgegeben wird, werden ihre lokalen Variablen verworfen. Es ist nicht notwendig, auch nicht schädlich, den Stapel zu kehren.

Viele dynamische Sprachen und auch Java oder C # sind in einer Systemprogrammiersprache implementiert, häufig in C. Man könnte sagen, Java ist mit C-Funktionen implementiert und verwendet lokale C-Variablen. Daher muss der Garbage Collector von Java den Stack nicht durchsuchen.

Es gibt eine interessante Ausnahme: Der Garbage Collector von Chicken Scheme durchsucht den Stack (in gewisser Weise), da bei seiner Implementierung der Stack als Speicherbereich für die Garbage Collection der ersten Generation verwendet wird: siehe Chicken Scheme Design Wikipedia .

einfach
quelle