Wenn ein Garbage Collector Objekte im Heap komprimiert, werden dann die Referenzen auf dem Stapel geändert?

18

Dies scheint eine einfache Frage zu sein, aber nachdem ich viel über das Thema gelesen habe, habe ich immer noch keine endgültige Antwort gefunden (vielleicht, weil es so einfach ist).

Meine Frage lautet: Wenn ein Garbage Collector Objekte im Heap komprimiert, wie werden die Verweise auf diese Objekte im Stack aktualisiert? Ich kann mir zwei mögliche Lösungen vorstellen:

  1. Durchsuchen Sie den Stapel (und die Verweise im Heap) und aktualisieren Sie den Verweis, um auf die neue Position des Objekts zu verweisen. In Analogie zum Umzug würde dies bedeuten, dass Sie jedem, der Ihre Adresse hat, einen Brief senden und ihn bitten, sein Adressbuch mit Ihrer neuen Adresse zu aktualisieren.
  2. Stellen Sie eine Art Nachschlagetabelle zur Verfügung. Das wäre so, als würde man eine Weiterleitungsadresse bei der örtlichen Post hinterlassen.

Wenden Müllsammler überwiegend eine dieser beiden Methoden an? Eine andere Methode? Beide?

garbage-collection todorojo
quelle
Siehe stackoverflow.com/questions/3799203/… und en.wikipedia.org/wiki/…
Gort the Robot
@StevenBurnap korrigiert mich, wenn ich mich irre, aber ich glaube, dass der Thread, mit dem Sie verlinkt haben, keine endgültigen Antworten hatte. Über genau diese Frage schienen sie auch zu spekulieren. Möglicherweise habe ich falsch gelesen. Wenn sie eine Antwort auf die Frage geben würden, wenn es Ihnen nichts ausmacht, wäre es meiner Meinung nach hilfreich, die Antwort für zukünftige SE-Benutzer (und mich selbst!) Hier zusammenzufassen
todorojo
Der Begriff für das, wovon Sie sprechen, ist ein "sich bewegender Müllsammler". Ich weiß ehrlich gesagt nicht, wie häufig sie verwendet werden.
Gort the Robot

Antworten:

9

Ich habe diesbezüglich keine speziellen Kenntnisse, aber ich verstehe, dass die erste Methode im Allgemeinen angewendet wird.

Der Müllsammler muss den Stapel trotzdem analysieren, um herauszufinden, auf welche Dinge im Heap vom Stapel verwiesen wird. Sobald es sich dazu entschließt, etwas zu verschieben, muss es dennoch die Verweise darauf korrigieren, und es gibt keinen Grund, an diesem Punkt zwischen Heap und Stack zu unterscheiden.

Der Lookup-Table-Ansatz könnte prinzipiell funktionieren. Dies würde jedoch dazu führen, dass alle Zeigerzugriffe 2 Schritte benötigen. Dies würde die Leistung erheblich beeinträchtigen und die normalen Laufzeiten beeinträchtigen. Besonders für den Anwendungsfall vieler kleiner Objekte. (Dies ist ein Fall, in dem GC-Programme auf dem neuesten Stand der Technik in der Regel die Referenzzählung übertreffen.)

btilly
quelle
3
Ich möchte hinzufügen , dass ich denke , GC wahrscheinlich versuchen , nicht die Dinge auf dem Heap zu bewegen , wenn sie nicht zu haben. In der heutigen Multiprozessor-Welt muss es ein Synchronisations-Albtraum sein, wenn alle Verweise auf etwas auf dem Heap aktualisiert werden müssen, während ein Programm ausgeführt wird, das diese Verweise verwendet. Die Nachschlagetabelle würde dies vereinfachen, aber ich denke, dass dies eher die Ausnahme als die Norm ist, sodass die meisten GCs wahrscheinlich einige Referenzen sperren, den Speicher verschieben und dann die Referenzen aktualisieren müssen. +1 Interessante Frage, +1 gute Antwort.
GlenPeterson
3
@ GlenPeterson Viele GCs bewegen tatsächlich keine Dinge auf dem Haufen und stehen diesem Problem nicht gegenüber. Ein komprimierender GC verschiebt jedoch per Definition lebende Objekte, um den Speicher zu defragmentieren.
btilly
@ GlenPeterson Es ist eine gute Beobachtung, dass das Bewegen von Dingen auf dem Haufen ein großer Synchronisationsschmerz ist. Dies wird oft übersehen, obwohl die GC-Komprimierung aufgrund dessen enorme Welligkeitseffekte auf einen laufenden Prozess hat. Dies ist der Hauptgrund, warum die Leute aufgefordert werden, alles zu tun, um Objekte so kurzlebig wie möglich zu halten, um zu vermeiden, dass große Heap-Aktualisierungen zu einer Komprimierung führen, die einen langen Mutex enthält. Unwissenheit über das Verhalten dieses Materials kann zu dem führen, was liebevoll als GC-Freakout-Modus bezeichnet wird.
Jimmy Hoffa
2
Der ursprüngliche Macintosh und Palm OS verwendeten beide einen Lookup-Table-Ansatz für die Speicherverwaltung. Zeiger in die Tabelle wurden als Handles bezeichnet. Ein umsiedelnder GC muss den Verbleib von absolut positiven Hinweisen auf Objekte, die sich bewegen, kennen. Die Verwendung einer einzelnen Tabelle für solche Zwecke vereinfacht die Dinge erheblich.
Supercat