Wie vermeiden Mülleimer einen Stapelüberlauf?

23

Also habe ich darüber nachgedacht, wie Müllsammler funktionieren, und mir ein interessantes Problem überlegt. Vermutlich müssen Müllsammler alle Bauwerke gleich durchqueren. Sie können nicht wissen, ob sie eine verknüpfte Liste oder einen ausgeglichenen Baum oder was auch immer durchqueren. Sie können auch nicht zu viel Speicher bei ihrer Suche verbrauchen. Ein möglicher Weg und der einzige Weg, wie ich denken kann, ALLE Strukturen zu durchlaufen, könnte darin bestehen, sie alle rekursiv zu durchlaufen, wie Sie es bei einem binären Baum tun würden. Dies würde jedoch einen Stapelüberlauf auf einer verknüpften Liste oder sogar nur einen schlecht ausbalancierten Binärbaum ergeben. Aber all die Sprachen, die ich jemals benutzt habe, scheinen kein Problem damit zu haben, mit solchen Fällen umzugehen.

Im Drachenbuch wird eine Art "Unscanned" -Warteschlange verwendet. Anstatt die Struktur rekursiv zu durchlaufen, werden nur Dinge hinzugefügt, die zu einer Warteschlange markiert werden müssen, und dann wird sie für jedes am Ende nicht markierte Objekt gelöscht. Aber würde diese Warteschlange nicht sehr groß werden?

Wie durchqueren Müllsammler also beliebige Strukturen? Wie vermeidet diese Traversiertechnik einen Überlauf?

Jake
quelle
1
GC durchquert alle Strukturen mehr oder weniger auf die gleiche Weise, jedoch nur in einem sehr abstrakten Sinne (siehe Antwort). Die Art und Weise, wie sie die Dinge konkret verfolgen, ist weitaus raffinierter als in den elementaren Präsentationen, die Sie in Lehrbüchern finden. Und sie verwenden keine Rekursion. Darüber hinaus zeigen sich schlechte Implementierungen mit virtuellem Speicher als GC-Verlangsamung, selten als Speicherüberlauf.
Babou
Sie sorgen sich um den Platz, der für die Verfolgung benötigt wird. Aber was ist mit dem Speicherplatz oder den Strukturen, die zur Unterscheidung von Speicher, der verfolgt wurde und der bekanntermaßen verwendet wird, von Speicher, der möglicherweise zurückgefordert werden kann, erforderlich sind? Dies kann erhebliche Speicherkosten verursachen, die möglicherweise proportional zur Größe des Heapspeichers sind.
Babou
Ich nahm an, dass dies mit einem Bitvektor bei einer Objektgröße von mehr als 16 Bytes geschehen würde, sodass der Overhead mindestens 1000-mal geringer wäre.
Jake
Es gibt viele Möglichkeiten, dies zu tun (siehe Antwort), und sie können auch zum Verfolgen verwendet werden, wodurch Ihre Frage beantwortet wird (Bitvektoren oder Bitmaps können zum Verfolgen anstelle des von Ihnen vorgeschlagenen Stacks oder der von Ihnen vorgeschlagenen Warteschlange verwendet werden). Sie können nicht davon ausgehen, dass alle Objekte groß sind, es sei denn, Sie möchten Platz für kleine Objekte verschwenden, von denen es viele geben kann. Dann sollten Sie sich keine Sorgen um den Platz machen. Wenn Sie sich im virtuellen Speicher befinden, ist der Speicherplatz oft weniger ein Problem und die Probleme sind sehr unterschiedlich.
Babou

Antworten:

13

Beachten Sie, dass ich kein Garbage Collection-Experte bin. Diese Antwort gibt nur Beispiele für Techniken. Ich behaupte nicht, dass es sich um einen repräsentativen Überblick über Müllsammeltechniken handelt.

Eine nicht gescannte Warteschlange ist eine häufige Wahl. Die Warteschlange kann groß werden - möglicherweise so groß wie die tiefste Datenstruktur. Die Warteschlange wird normalerweise explizit gespeichert und nicht auf dem Stapel des Garbage Collection-Threads.

Sobald alle bis auf eines der untergeordneten Elemente eines Knotens gescannt wurden, kann der Knoten aus der nicht gescannten Warteschlange entfernt werden. Dies ist im Grunde eine Tail-Call-Optimierung. Garbage Collectors können Heuristiken enthalten, um zu versuchen, das tiefste untergeordnete Element eines Knotens zuletzt zu scannen. Zum Beispiel sollte ein GC für Lisp das carvon a consvor dem scannen cdr.

Eine Möglichkeit, eine nicht gescannte Warteschlange nicht beizubehalten, besteht darin, die Zeiger so zu ändern, dass das untergeordnete Element vorübergehend auf das übergeordnete Element verweist. Hierbei handelt es sich um eine Konstantenspeicherbaum-Durchquerungstechnik, die in anderen Kontexten als Garbage Collectors verwendet wird. Der Nachteil dieser Technik ist, dass die Datenstruktur ungültig ist, während der GC eine Datenstruktur durchläuft, sodass der GC die Welt stoppen muss. Dies ist kein Deal Breaker: Viele Müllsammler haben eine Phase, die die Welt stoppt, zusätzlich zu Phasen, in denen kein Müll entgeht, sondern der Müll als Folge verloren geht.

Gilles 'SO - hör auf böse zu sein'
quelle
2
Die im letzten Absatz beschriebene Technik wird häufig als " Zeigerumkehr " bezeichnet.
Wandering Logic
@WanderingLogic Ja, Zeigerumkehr ist , wie ich es in meiner eigenen Antwort genannt. Es ist Deutsch, Schorr und Waite (1967) zu verdanken. Es ist jedoch falsch, dass es in einem konstanten Speicher arbeitet: Für jede Zelle mit Zeigern sind zusätzliche Bits erforderlich , obwohl dies durch Verwendung von reduziert werden kann. Die akzeptierte Antwort, auf die Sie verweisen, ist aus demselben Grund auch nicht ganz richtig oder vollständig. plog2pp
Babou
Ich habe die Zeigerumkehr in einem benutzerdefinierten GC verwendet, ohne diese zusätzlichen Bits zu benötigen. Der Trick bestand darin, eine spezielle speicherinterne Darstellung von Objekten im Speicher zu verwenden. Das Objekt "Header" befand sich nämlich in der Mitte mit Zeigerfeldern vor dem Header und Nicht-Zeigerfeldern danach. Außerdem wurden alle Zeiger ausgerichtet, und der Header enthielt ein Feld, in dem immer das niedrigstwertige Bit gesetzt war. Während der Zeigerumkehr-Rückverfolgung konnte somit das Erreichen des nächsten Zeigers und das Feststellen, dass wir mit einem Objekt fertig waren, eindeutig ohne die zusätzlichen Bits durchgeführt werden. Dieses Layout unterstützt auch die OOP-Vererbung.
Thomas Pornin
@ThomasPornin Ich denke, die Bit-Informationen müssen irgendwo sein. Die Frage ist wo? Können wir das im Chat diskutieren? Ich muss jetzt gehen, aber ich möchte dem auf den Grund gehen. Oder gibt es eine Beschreibung, die im Web erreichbar ist?
Babou
1
@babou und Thomas bitte
Gilles '
11

Auf den Punkt gebracht : Garbage Collectors verwenden keine Rekursion. Sie steuern lediglich die Verfolgung, indem sie im Wesentlichen zwei Sätze (die kombiniert werden können) verfolgen. Die Reihenfolge der Ablaufverfolgung und der Zellverarbeitung ist irrelevant, was eine erhebliche Freiheit bei der Implementierung zur Darstellung der Mengen bietet. Daher gibt es viele Lösungen, die in der Speichernutzung tatsächlich sehr billig sind. Dies ist wichtig, da der GC genau dann aufgerufen wird, wenn der Heap nicht mehr genügend Arbeitsspeicher hat. Die Dinge sind ein bisschen anders mit großen virtuellen Erinnerungen, als neue Seiten können einfach zugeordnet werden, und die ennemy ist der Mangel nicht von Raum, sondern von Daten fehlt Lokalität .

Ich gehe davon aus, dass Sie überlegen , Müllsammler aufzuspüren, nicht die Referenzzählung, für die Ihre Frage anscheinend nicht zutrifft.

Die Frage konzentriert sich auf die Speicherkosten der Verfolgung , um einen Satz zu verfolgen: den Satz (für nicht verfolgt) von zugänglichen Speicherzellen, die noch Zeiger enthalten, die noch nicht verfolgt wurden. Dies ist nur die Hälfte des Speicherproblems bei der Garbage Collection. Der GC muss auch einen anderen Satz verfolgen: den Satz V (für besucht) aller Zellen, die als zugänglich befunden wurden, um am Ende des Prozesses alle anderen Zellen zurückzugewinnen. Das eine und nicht das andere zu diskutieren ist nur bedingt sinnvoll, da sie ähnliche Kosten verursachen, ähnliche Lösungen verwenden und sogar kombiniert werden können.UV

Das erste, was zu beachten ist, ist, dass alle Trace-GCs demselben abstrakten Modell folgen, das auf einer systematischen Untersuchung des gerichteten Diagramms von Zellen im Speicher basiert, auf die vom Programm aus zugegriffen werden kann, wobei Speicherzellen Scheitelpunkte und Zeiger die gerichteten Kanten sind. Es verwendet dazu die folgenden Mengen:

  • Die Menge (Visited) der Zellen, auf die der Mutator bereits zugreifen kann , dh das Programm oder der Algorithmus, für den die GC durchgeführt wird. Die Menge V ist in zwei disjunkte Teilmengen unterteilt: V = U T ;VVV=UT

  • die Menge (nicht verfolgt) der besuchten Zellen mit Zeigern, denen noch nicht gefolgt wurde;U

  • Die Menge (verfolgt) der besuchten Zellen, deren Zeiger verfolgt wurden.T

  • H

VUUT

UV

UcVUcUT

UUV=TVHVV

VUUT

Ich überspringe auch Details darüber, was eine Zelle ist, ob sie in einer Größe oder in vielen Größen vorliegt, wie wir darin Hinweise finden, wie sie komprimiert werden können und eine Vielzahl anderer technischer Probleme, die Sie in Büchern und Umfragen zur Müllabfuhr finden können .

U

Wo bekannte Implementierungen sich unterscheiden, liegt die Art und Weise, in der diese Mengen tatsächlich dargestellt werden. Viele Techniken wurden tatsächlich verwendet:

  • Bitmap: Für eine Map, die ein Bit für jede Speicherzelle enthält, wird ein Teil des Speicherplatzes beibehalten, der über die Adresse der Zelle ermittelt werden kann. Das Bit ist eingeschaltet, wenn sich die entsprechende Zelle in der Menge befindet, die durch die Karte definiert ist. Wenn nur Bitmaps verwendet werden, benötigen Sie nur 2 Bits pro Zelle.

  • Alternativ können Sie in jeder Zelle Platz für ein spezielles Tag-Bit (oder 2) haben, um es zu markieren.

  • Log2pp

  • Sie können ein Prädikat für den Inhalt der Zelle und ihre Zeiger testen.

  • Sie können die Zelle in einen freien Teil des Speichers verschieben, der für alle Zellen bestimmt ist, die zu dem dargestellten Satz gehören.

  • VTTU

  • Sie können diese Techniken sogar für einen einzigen Satz kombinieren.

Wie gesagt, alle oben genannten wurden von einigen implementierten Garbage Collector verwendet, so seltsam einige scheinen mögen. Es hängt alles von den verschiedenen Einschränkungen der Implementierung ab. Und sie können in Bezug auf die Speichernutzung ziemlich billig sein, möglicherweise unterstützt durch die Verarbeitung von Auftragsrichtlinien , die für diesen Zweck frei gewählt werden können, da sie für das Endergebnis keine Rolle spielen.

Was als das seltsamste erscheinen mag, Zellen in ein neues Gebiet zu transferieren, ist tatsächlich sehr verbreitet: Man nennt es Kopiensammlung. Es wird hauptsächlich mit virtuellem Speicher verwendet.

Natürlich gibt es keine Rekursion und der Mutator-Algorithmus-Stack muss nicht verwendet werden.

Ein weiterer wichtiger Punkt ist, dass viele moderne GCs für große virtuelle Speicher implementiert sind . Dann ist es kein Problem, Speicherplatz für die Implementierung und zusätzliche Listen oder Stapel bereitzustellen, da neue Seiten leicht zugewiesen werden können. In großen virtuellen Erinnerungen ist der Feind jedoch nicht der Mangel an Raum, sondern der Mangel an Lokalität . Dann muss die Struktur, die die Mengen darstellt, und ihre Verwendung darauf ausgerichtet sein, die Lokalität der Datenstruktur und der GC-Ausführung zu bewahren . Das Problem ist nicht Raum, sondern Zeit. Bei unzureichenden Implementierungen ist mit größerer Wahrscheinlichkeit eine inakzeptable Verlangsamung zu verzeichnen als bei einem Speicherüberlauf.

Ich habe nicht auf die vielen spezifischen Algorithmen hingewiesen, die sich aus verschiedenen Kombinationen dieser Techniken ergeben, da dies lang genug zu sein scheint.

babou
quelle
4

Die Standardmethode zum Vermeiden eines Stapelüberlaufs ist die Verwendung eines expliziten Stapels (der als Datenstruktur im Heap gespeichert wird). Das funktioniert auch für diese Zwecke. Müllsammler haben oft einen Arbeitsvorrat von Gegenständen, die untersucht / durchlaufen werden müssen, was dieser Rolle dient. Zum Beispiel ist Ihre "Nicht gescannte" Warteschlange ein Beispiel für genau diese Art von Muster. Die Warteschlange kann möglicherweise groß werden, verursacht jedoch keinen Stapelüberlauf, da sie nicht im Stapelsegment gespeichert ist. In jedem Fall wird es nie größer als die Anzahl der lebenden Objekte im Heap.

DW
quelle
Wenn der GC aufgerufen wird, ist der Heap normalerweise voll. Ein weiterer Punkt ist, dass es passiert, dass der Stapel und der Haufen von beiden Enden des gleichen Speicherplatzes wachsen ..
babou
4

In "klassischen" Beschreibungen der Speicherbereinigung (z. B. Mark Wilson, " Uniprocessor Garbage Collection Techniques ", International Workshop on Memory Management , 1992, ( alternativer Link ) oder in der Beschreibung in Andrew Appels Modern Compiler Implementation (Cambridge University Press) 1998)) werden Sammler entweder als "Mark and Sweep" oder "Copying" klassifiziert.

Mark- und Sweep-Kollektoren benötigen keinen zusätzlichen Platz, indem sie die Zeigerumkehrung verwenden, wie in der Antwort von @ Gilles beschrieben. Appel sagt, dass Knuth den Zeiger-Umkehr-Algorithmus Peter Deutsch sowie Herbert Schorr und WM Waite zuschreibt.

Beim Kopieren von Garbage Collectors wird der so genannte Cheyney-Algorithmus verwendet , um einen Queue-Traversal durchzuführen, ohne zusätzlichen Speicherplatz zu benötigen. Dieser Algorithmus wurde in CJ Cheyney, "A Nonrecursive List Compacting Algorithm", Comm. ACM , 13 (11): 677 & ndash; 678, 1970.

In einem kopierenden Garbage Collector verfügen Sie über einen Teil des Speichers, den Sie sammeln möchten, der als From -Space bezeichnet wird , und einen Teil des Speichers, den Sie für die Kopien verwenden, die als To-Space bezeichnet werden . Der scanTo -Space ist als Warteschlange organisiert, mit einem Zeiger auf den ältesten kopierten, aber nicht gescannten Datensatz und einem freeZeiger auf die nächste freie Position im To -Space. Das Bild davon aus Wilsons Artikel ist:

Cheyneys Algorithmusbeispiel

Während Sie jedes Objekt in den Weltraum scannen, kopieren Sie seine untergeordneten Objekte aus dem Weltraum in den freeZeiger in den Weltraum und ändern dann den Zeiger in das untergeordnete Objekt aus dem Weltraum in die neue Kopie des untergeordneten Objekts in den Weltraum. Es gibt einen zusätzlichen Trick, den Sie anwenden müssen, wenn Ihre Datenstrukturen keine Bäume sind (wenn ein Kind mehr als ein Elternteil haben kann). In diesem Fall müssen Sie beim Kopieren eines untergeordneten Elements von Raum zu Raum die alte Version des untergeordneten Elements mit einem Weiterleitungszeiger auf die neue Kopie des untergeordneten Elements überschreiben . Wenn Sie dann jemals einen anderen Zeiger auf die alte Version des Kindes scannen, stellen Sie fest, dass er bereits kopiert wurde, und kopieren Sie ihn nicht erneut.

Wandering Logic
quelle
Wie in meiner Antwort erläutert, sind sowohl die Mark + Sweep- als auch die Copy-Sammlung derselbe abstrakte Graph-Algorithmus. MS- und Copy-Sammlung unterscheiden sich nur in der Art und Weise, wie vom abstrakten Algorithmus verwendete Mengen implementiert werden, und beide Familien sind mit vielen Varianten in einer Kombination der in meiner Antwort beschriebenen Mengenimplementierungstechniken enthalten. Einige GC-Varianten mischen tatsächlich MS und Copy im selben GC. Die Trennung von MS und Copy wird von manchen als eine bequeme Möglichkeit angesehen, Bücher zu strukturieren, aber es ist eine willkürliche und meiner Meinung nach veraltete Vision.
Babou
@babou: Wenn man einen Kopieralgorithmus verwendet, bei dem alles, was besucht wird, kopiert wird (langsam, kann aber auf kleinen Plattformen nützlich sein, auf denen der Arbeitssatz nie so groß ist), können einige Algorithmen etwas vereinfacht werden, da man sie verwenden kann Der Speicher, der früher von einem verschobenen Objekt als Notizblock belegt war. Es ist auch möglich, dass andere Threads während der Erfassung nur Lesezugriffe auf Objekte ausführen können, vorausgesetzt, vor und nach jedem Lesevorgang wird die Gültigkeit des Objekts überprüft und dem Weiterleitungszeiger gefolgt, wenn ein Objekt verschoben wurde.
Supercat
@supercat Ich bin mir nicht sicher, was du sagen willst, was deine Absicht ist. Einige Ihrer Aussagen scheinen richtig zu sein. Ich verstehe jedoch nicht, wie Sie From-Space verwenden können, bevor der GC-Zyklus beendet ist (er enthält Weiterleitungszeiger). Und für was wäre es ein Notizblock? Vereinfachen Sie den Algorithmus wie? In Bezug auf mehrere Mutator-Threads, die ausgeführt werden, während GC ausgeführt wird, handelt es sich weitgehend um ein orthogonales Problem, obwohl dies die Implementierung erheblich beeinträchtigen kann. Ich würde nicht versuchen, das in Kommentaren anzusprechen. Es sollte weniger Probleme beim Nur-Lese-Zugriff aufwerfen, aber der Teufel steckt im Detail.
Babou