Hardware Assisted Garbage Collection

Question

Ich habe über Möglichkeiten nachgedacht, dass funktionale Sprachen direkter an ihre Hardware gebunden sein könnten und habe mich über Hardware-Implementierungen von Garbage Collection Gedanken gemacht.

Dies würde die Dinge erheblich beschleunigen, da die Hardware selbst implizit die gesamte Sammlung handhaben würde, anstatt die Laufzeit einiger Umgebungen.

Haben LISP Machines das gemacht? Wurde diese Idee weiter erforscht? Ist das zu domänenspezifisch?

Gedanken? Einwände? Diskutieren.

Answer 1

Wegen Generations-Sammlung, ich würde sagen müssen, dass das Verfolgen und Kopieren nicht große Engpässe zu GC sind.

Was helfen würde, sind hardwaregestützte READ-Barrieren, die die Notwendigkeit von "Stop the world" -Pausen bei Stack-Scans und der Markierung des Heaps beseitigen.

Azul Systems hat dies getan: http://www.azulsystems.com/products/compute_appliance.htm Sie gaben eine Präsentation bei JavaOne darüber, wie ihre Hardware-Modifikationen völlig pauseless GC ermöglicht.

Eine weitere Verbesserung wären hardwaregestützte Schreibbarrieren für die Verfolgung von gespeicherten Mengen.

Generative GCs, und noch mehr für G1 oder Garbage First, reduzieren die Anzahl der zu scannenden Heaps, indem sie nur eine Partition scannen und eine Liste der gemerkten Sets für zonenübergreifende Zeiger führen.

Das Problem ist, das bedeutet, JEDERMAL setzt der Mutator (lustiges Wort für das 'echte Programm') einen Zeiger, der auch einen Eintrag in die entsprechende, gemerkte Menge setzen muss. Sie haben also (kleinen) Overhead, auch wenn Sie nicht GCing sind. Wenn Sie dies reduzieren können, reduzieren Sie sowohl die für GCing erforderlichen Pausenzeiten als auch die Gesamtleistung des Programms.

Answer 2

Warum sollte es die Dinge beschleunigen? Was genau sollte die Hardware machen? Es muss immer noch alle Referenzen zwischen Objekten durchlaufen, was bedeutet, dass es einen großen Teil der Daten im Hauptspeicher durchlaufen muss, was der Hauptgrund dafür ist, dass es Zeit braucht. Was würdest du dadurch gewinnen? Welche bestimmte Operation ist Ihrer Meinung nach schneller mit Hardwareunterstützung möglich? Die meiste Arbeit in einem Garbage Collector folgt nur Zeigern/Verweisen und gelegentlich kopiert Live-Objekte von einem Heap zu einem anderen. Wie unterscheidet sich das von den Anweisungen, die eine CPU bereits unterstützt?

Mit dem genannten, warum denken Sie, wir brauchen schneller Garbage Collection? Ein moderner GC kann bereits sehr schnell und effizient sein, bis zu dem Punkt, an dem es im Grunde ein gelöstes Problem ist.

Answer 3

Ich bin mir ziemlich sicher, dass einige Prototypen existieren sollten. Aber Hardware-spezifische Features zu entwickeln und zu produzieren ist sehr teuer. Es hat sehr lange gedauert, MMU oder TLB auf Hardwareebene zu implementieren, die recht einfach zu implementieren sind.

Der GC ist zu groß, um auf Hardwareebene effizient implementiert werden zu können.

Answer 4

Eine offensichtliche Lösung bestand darin, Speicherzeiger zu haben, die größer als Ihr verfügbarer RAM sind, z. B. 34-Bit-Zeiger auf einer 32-Bit-Maschine. Oder verwenden Sie die obersten 8 Bits einer 32-Bit-Maschine, wenn Sie nur 16 MB RAM (2^24) haben. Die Oberon machines an der ETH Zürich nutzte ein solches Schema mit viel Erfolg, bis RAM zu billig wurde. Das war um 1994, also ist die Idee ziemlich alt.

Dies gibt Ihnen ein paar Bits, wo Sie Objektstatus speichern können (wie "das ist ein neues Objekt" und "Ich habe gerade dieses Objekt berührt"). Wenn Sie den GC verwenden, bevorzugen Sie Objekte mit "Dies ist neu" und vermeiden Sie "nur berührt".

Dies könnte tatsächlich eine Renaissance erleben, denn niemand hat 2^64 Bytes RAM (= 2^67 Bits; es gibt ungefähr 10^80 ~ 2^240 Atome im Universum, also ist es vielleicht nicht möglich zu haben so viel RAM jemals). Das heißt, Sie könnten ein paar Bits in den heutigen Maschinen verwenden , wenn die VM dem Betriebssystem mitteilen kann, wie der Speicher zugeordnet wird.

Answer 5

Die wahrscheinlich relevanteste Datenmenge, die hier benötigt wird, ist, wie viel Zeit (Prozentsatz der CPU-Zeit) derzeit für die Speicherbereinigung aufgewendet wird? Es kann kein Problem sein.

Wenn wir danach gehen, müssen wir berücksichtigen, dass die Hardware mit Speicher "hinter unserem Rücken" täuscht. Ich denke, das wäre "ein anderer Thread", in der modernen Sprache. Ein gewisser Speicher ist möglicherweise nicht verfügbar, wenn er untersucht wird (vielleicht mit Dual-Port-Speicher lösbar), und sicherlich, wenn der HWGC Dinge herumbewegen wird, dann müsste er die anderen Prozesse sperren, so dass sie nicht gestört werden . Und tun Sie es so, dass es in die verwendete Architektur und Sprache passt. Also, ja, Domain-spezifisch.

Schau, was gerade erschien ... in another post ... Blick auf Java-GC-Protokoll.

Answer 6

Es gab an article on lambda the ultimate, die beschreiben, wie Sie einen GC-aware virtuellen Speichermanager benötigen, um einen wirklich effizienten GC zu haben, und das VM-Mapping wird heutzutage hauptsächlich von Hardware durchgeführt. Hier sind Sie :)

Answer 7

Ja. Schauen Sie sich die damit verbundenen Arbeiten Abschnitte dieser zwei Papiere:

https://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/index.htm http://www.filpizlo.com/papers/pizlo-ismm2007-stopless.pdf

Oder bei dieser:

http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon12StallFree.pdf

Answer 8

entnehme ich, das größte Problem CPU-Register und der Stapel ist. Eines der Dinge, die Sie während GC tun müssen, ist das Durchlaufen aller Zeiger in Ihrem System, was bedeutet, dass Sie wissen, was diese Zeiger sind. Wenn sich einer dieser Zeiger gerade in einem CPU-Register befindet, müssen Sie auch diesen durchlaufen. Ähnlich, wenn Sie einen Zeiger auf den Stapel haben. Also muss jeder Stack-Frame eine Art Map haben, die besagt, was ein Pointer ist und was nicht, und bevor Sie GC-Traversing durchführen, müssen Sie irgendwelche Pointer in den Speicher bringen.

Sie stoßen auch auf Probleme mit Schließungen und Fortsetzungen, weil Ihr Stapel plötzlich aufhört, eine einfache LIFO-Struktur zu sein.

Der offensichtliche Weg ist, niemals Zeiger auf dem CPU-Stack oder in Registern zu halten. Stattdessen haben Sie jeden Stack-Frame als ein Objekt, das auf seinen Vorgänger verweist. Aber das tötet Leistung.

Answer 9

Ältere Sparc-Systeme hatten Speicher (33 Bits) gekennzeichnet, der zum Markieren von Adressen verwendet werden konnte. Heute nicht eingebaut?

Dies kam von ihrer LISP Erbe IIRC.

Einer meiner Freunde baute einen Generations-GC, der sich durch einfaches Stehlen von Primitiven auszeichnete. Es hat besser funktioniert.

Also, ja, es kann gemacht werden, aber Nodody stört Dinge mehr zu markieren.

Die Kommentare von runT1mes über hardwareunterstützte Generationen GC sind lesenswert.

Bei einem ausreichend großen Gate-Array (Vertex-III kommt mir in den Sinn) wäre eine erweiterte MMU möglich, die GC-Aktivitäten unterstützt.

Answer 10

Sie sind ein Student, klingt wie ein gutes Thema für ein Forschungsstipendium für mich. Schauen Sie in FPGA-Design und Computer-Architektur gibt es viele kostenlose Prozessor-Design zur Verfügung http://www.opencores.org/

Garbage Collection kann als Hintergrund-Task implementiert werden, ist es bereits für den Parallelbetrieb vorgesehen.

Pete

Answer 11

Mehrere große Geister am MIT in den 80er Jahren schuf die SCHEME-79 Chip, der direkt einen Dialekt von Schema interpretiert wurde mit LISP DSLs entworfen, und hatte Hardware-gc eingebaut.