Würde die Verwendung einer Hash-Tabelle in der Garbage Collection das weltweite Problem von Mark und Sweep lösen?

Im Mark-Sweep-Compact-Garbage-Collection-Algorithmus müssen Sie die Welt stoppen, wenn Sie Objekte verschieben, da das Referenzdiagramm inkonsistent wird und Sie die Werte aller Referenzen ersetzen müssen, die auf das Objekt verweisen.

Aber was wäre, wenn Sie eine Hash-Tabelle mit einer Objekt-ID als Schlüssel und einem Zeiger als Wert hätten und Referenzen auf diese ID anstatt auf die Objektadresse verweisen würden? Dann müssten Sie zum Beheben von Referenzen nur einen Wert ändern, und eine Pause wäre nur erforderlich, wenn ein Objekt vorhanden ist wird versucht, während des Kopierens beschrieben zu werden ...

Gibt es einen Fehler in meiner Denkrichtung?

Das Aktualisieren von Referenzen ist nicht das einzige, was eine Pause erfordert. Die Standardalgorithmen, die üblicherweise unter "Mark-Sweep" zusammengefasst werden, gehen alle davon aus, dass der gesamte Objektgraph unverändert bleibt, während er markiert wird. Die korrekte Behandlung von Änderungen (neue Objekte erstellt, Referenzen geändert) erfordert recht knifflige alternative Algorithmen wie den Dreifarbenalgorithmus. Der Überbegriff lautet "gleichzeitige Speicherbereinigung".

Aber ja, das Aktualisieren von Referenzen nach der Komprimierung erfordert auch eine Pause. Und ja, die Verwendung der Indirektion (z. B. über eine permanente Objekt-ID und eine Hash-Tabelle zu echten Zeigern) kann die Unterbrechung erheblich reduzieren. Es könnte sogar möglich sein, dieses Teil sperren zu lassen, wenn man dies wünscht. Es wäre immer noch so schwierig, das Gleichzeitige zu tun, wie dies bei einem gemeinsamen Speicher auf niedriger Ebene der Fall ist, aber es gibt keinen fundamentalen Grund, warum dies nicht funktionieren würde.

Allerdings wäre es gravierende Nachteile haben. Abgesehen davon, dass mehr Platz benötigt wird ( mindestens zwei zusätzliche Wörter für alle Objekte), verteuert dies jede Dereferenzierung erheblich . Sogar etwas so Einfaches wie das Abrufen eines Attributs umfasst jetzt eine vollständige Hashtabellensuche. Ich würde den Leistungseinbruch als weitaus schlechter einschätzen als bei der inkrementellen Verfolgung.

Alle Probleme in der Informatik können durch eine andere Indirektionsebene gelöst werden… mit Ausnahme des Problems zu vieler Indirektionsebenen

Ihr Ansatz löst das Problem der Speicherbereinigung nicht sofort, sondern verschiebt es nur um eine Ebene nach oben. Und zu welchem ​​Preis! Jetzt durchläuft jeder Speicherzugriff eine weitere Zeiger-Dereferenzierung. Der Ergebnisspeicherort kann nicht zwischengespeichert werden, da er möglicherweise in der Zwischenzeit verschoben wurde. Wir müssen immer die Objekt-ID durchgehen. In den meisten Systemen ist diese Indirektion nicht akzeptabel, und es wird angenommen, dass das Stoppen der Welt geringere Gesamtlaufzeitkosten verursacht.

Ich sagte, dass Ihr Vorschlag das Problem nur bewegt, nicht löst. Das Problem liegt in der Wiederverwendung von Objekt-IDs. Die Objekt-IDs entsprechen jetzt unseren Zeigern, und es gibt nur eine begrenzte Anzahl von Adressen. Es ist vorstellbar (insbesondere auf einem 32-Bit-System), dass während der Lebensdauer Ihres Programms mehr als INT_MAX-Objekte erstellt wurden, z. B. in einer Schleife wie

while (true) {
    Object garbage = new Object();
}

Wenn wir nur die Objekt-ID für jedes Objekt erhöhen, gehen uns irgendwann die IDs aus. Daher müssen wir herausfinden, welche IDs noch verwendet werden und welche frei sind, damit sie zurückgefordert werden können. Klingt bekannt? Wir sind jetzt wieder auf dem ersten Platz.

Es liegt kein Fehler in Ihrer Überlegung vor. Sie haben gerade etwas sehr Ähnliches beschrieben, wie der ursprüngliche Java-Garbage Collector funktioniert hat

Die ursprüngliche Java Virtual Machine [6] und einige Smalltalk Virtual Machines verwenden indirekte Zeiger, die in [6] als Handles bezeichnet werden, um auf Objekte zu verweisen. Handles ermöglichen ein einfaches Verschieben von Objekten während der Garbage Collection, da es bei Handles nur einen direkten Zeiger auf jedes Objekt gibt: den in seinem Handle. Alle anderen Verweise auf das Objekt erfolgen indirekt über den Handgriff. In solchen handelbasierten Speichersystemen bleiben die Handle-Adressen konstant, während sich die Objektadressen über die Lebensdauer der Objekte ändern und daher nicht für das Hashing verwendet werden können.

Raum- und zeiteffizientes Hashing von müllsammelnden Objekten

In der aktuellen Implementierung der Java Virtual Machine von Sun ist ein Verweis auf eine Klasseninstanz ein Zeiger auf ein Handle, das selbst ein Zeigerpaar ist: einer auf eine Tabelle, die die Methoden des Objekts enthält, und ein Zeiger auf das Class-Objekt, das das darstellt Typ des Objekts und der andere für den vom Java-Heap für die Objektdaten zugewiesenen Speicher.

Die Java Virtual Machine-Spezifikation (1997)

Es funktioniert also, es wurde ausprobiert, und seine Ineffizienz führte zur Entwicklung generativer Markierungs- und Kehrsysteme.