Verbesserte Garbage Collections

Zitat von Hoogo

Als ich mir gestern frische Luft in den Schädel gepumpt habe kam mir der GEdanke, dass es sehr praktisch wäre, wenn alle Pointer absteigend sortiert wären.

Ich hatte aber noch keinen brauchbaren Gedanken, wie man den Zustand erreichen könnte.

Ja, von dem hab ich auch schon geträumt. Das ist ungefähr so, wenn ich auf den Mond fliegen möchte und mir vorstelle, wie schön es wäre schon dort zu sein.

Die Garbage-Collection hat gewisse Eigenschaften eines Sortieralgorithmus'. Die Standard-Implementierung entspricht dem Bubble-Sort, die Puffervariante irgendwie dem Fächersortieren. Die genau "Ordnung" innerhalb eines Fachs braucht man im letzteren Fall gar nicht erreichen, da ja Ziel ist, nur die Lücken zu eliminieren.

Zitat von Hoogo

Vielleicht lohnt es sich, nicht den String-Inhalt, sondern Zeiger auf die Descriptoren in den Puffer zu schreiben und die dann zu sortieren? Das könnte sich lohnen, wenn es um eher wenig Strings geht.

Durch all diese Überlegung bin ich auch schon durch.

Aber warum denn sortieren, wenn das doch gar nicht erforderlich ist (als Ziel). Das nützt einem nur, wenn man schon beim Aufbau des Heaps die Sortierung gewährleisten wäre.
Fächersortierung ist bereits vom Aufwand her optimal. Alles andere hätte N*LOG(N) oder N*N-Aufwand und wäre aufwändiger.

Zitat von Diddl

Das GC Problem ist wirklich ärgerlich.

Besonders ärgerlich ist, dass Commodore zum Zeitpunkt, als der C64 kam schon eine perfekte Lösung dafür hatte ...

Die großen CBM Kisten hatten ab BASIC-4 eine komplett überarbeitete GC.

Viele glauben das BASIC 4 hat einfach nur eine handvoll unnötiger Disk Befehle mehr als BASIC-2.

Aber intern hat sich eben doch einiges getan, speziell bei der String Verarbeitung.

Alles anzeigen

Das Problem ist, das die "Microsoft"-Version der Back-Pointer-GC aus BASIC 4.0 zu groß gewesen wäre (also so einfach 1:1) übernehmen (im Sinne von String-Modul des BASIC einfach austauschen).

Commodore hat es 1:1 ins BASIC 3.5 und BASIC 7.0 übernommen (keinerlei Optimierungen oder sonstige Überlegungen). War auch auch keine Not, denn da hatte man ja genügend ROM ...

Ein platzoptimierte Version wäre nötig gewesen (die gäbe es, auch im Oktober 1988 im 64'er: Garbcol, aber auch hier fehlerhaft, habe eine fehlerbereinigte Version), die ins ROM gepasst hätte (fast aufs Byte genau). Die wäre simpler gestrickt und trotz gewisser Ineffizienzen wegen den Vereinfachungen faktisch genau so schnell, also darüber braucht man im Vergleich mit dem Standardverfahren gar nicht erst diskutieren). Das wäre sich also ausgegangen, aber wäre mit ziemlichem "Aufwand" verbunden gewesen das auszutüfteln.

Ich habe den Eindruck, dass sowohl VC-20 diese Option nicht in Diskussion stand. Da war das RAM ohnehin so eingeschränkt, dass man mit der Standardroutine zumutbar war.

Beim Sprung auf den C64 hat man das Problem glaub ich gar nicht erst am Schirm gehabt und mit Minimalaufwand mehr oder weniger die Umgebung VC-20 "übernommen". Das eigentliche Problem (alte GC + viel Speicher -> abartige Laufzeiten) wurd schlicht "übersehen".

Zitat von Mac Bacon

Und wenn man über einen solchen Hook selbst entscheidet, die eigene GC anzustoßen, sobald der freie Bereich eine bestimmte Größe unterschreitet? Damit dieser freie Speicher nicht komplett ungenutzt bleibt, böte es sich an, den dann gleich als Puffer zu benutzen...

Ja, hab ich auch schon überlegt. Aber das ist dann auch keine generelle Lösung, sondern geht nur gut, wenn genügend Platz bleibt. Also wenn man 4 oder 8 K übrig hat. Aber die GC kennt das Programm nicht. Da müsste man der GC schon vorab sagen, dass man sicher mit einem gewissen Platz hat. Oder die GC verwendet ein flexibles Fenster. Aber da kann es auch passieren, dass man bei wenig Platz, dann in eine Situation kommt, wo bei jeder Ausdrucksauswertung dann immer die GC ausgelöst wird ... auch suboptimal. Egal wie man es dreht oder wendet, man kommt von einer Nachjustiererei in die andere.

Zumindest das Stress-Demo (die bis ans letzte Byte geht) überlebt so eine Variante auch nicht wirklich gut. Natürlich, das ist vermutlich auch nicht der Standard Fall. Aber meiner Applikation hatte ich schon zig hundert Strings und da ist nicht mehr viel Platz als Spielraum übrig geblieben, also ein paar Hundert Bytes, wenn überhaupt. Unter 256 degeneriert dann die Routine wieder in Richtung Standard-Routine. Eine Laufzeitverschlechterung mit zunehmenden Platzmangel war für mich jedenfalls inakzeptabel.

All das war es mir nicht Wert solche Umstände auf mich zu nehmen, wenn ich zumindest beim C64 ohnehin das RAM unter dem ROM habe.

Zitat von Hoogo

Wenn ich mich richtig erinnere, dann sind die Variablen komplett unsortiert, einfach nach Reihenfolge, in der sie angelegt wurden.

Würde man vor der GC String-Variablen nach ihrem aktuellen Descriptor sortieren, wäre das eine gute Chance, dass das Basic-Programm anschließend schneller läuft, weil es häufig benutzte Strings schneller findet?

Nein. Für den Zugriff auf Variablen spielt nur die Variable selbst eine Rolle, nämlich wie weit entfernt sie vom Start des Variablenbereichs ist. Der in der Variable befindliche Descriptor, also u.a. die String-Adresse, die auf den Anfang des Strings am Heap zeigt, ist völlig egal, wohin der Descriptor zeigt.

Was hat die Aussage "häufig benutzte Strings" mit "sortierte Descriptoren" zu tun. Ich sehe da keine Verbindung (oder hab die Frage nicht verstanden).

Zitat von Hoogo

Strings, deren Descriptor auf eine kleine Speicheradresse zeigt, sind auch zuletzt verwendet worden.

Wenn man daraus schließt , dass die damit auch am häufigsten verwendet werden (also ein MRU-Cache), dann wäre es nicht falsch, wenn die auch früh im Variablenspeicher zu finden wären.

Kühne These, aber eigentlich nein. Also ohne zusätzliche Annahmen ist das eher ein Schuss in die Nebelbank.
Aus einem neu angelegten String kann man einfach nicht ableiten, dass die dazugehörige Variable häufiger gebraucht wird. Ohne Profiling eines Programms wird man nicht die wirkliche Nutzung feststellen können.

Z. B. legt man diverse Konstanten in Variablen ab. Diese werden mitunter wirklich extrem oft verwendet (Beispiel: ASC(A$+Z$), wobei Z$=CHR$(0) ist). Die Konstante würde dann am Ende des Heaps liegen (weil früh definiert und deswegen eine hohe Adresse). Wenn dann auf solche Variablen in Schleifen oft zugegriffen wird, gibt dann einen heftigen Abschlag dafür. Da verpufft jeder Hauch von Vorteil, dann man sich von einem MRU-Cache erwarten würde. Hier ist man besser dran mit DIM gezielt einfache Variablen nach den Häufigkeit des Zugriffs anzulegen und man kann. Da wird ein MRU-Cache auf dieser Basis nie hinkommen.

Die hier am 25. März begonnene, sich dann ausweitende Diskussion und die Überlegungen zu den hier gestellten Fragen (die ja eigentlich schon bereits vor 35 Jahren entstanden sind) hat zwar insofern keine neuen Erkenntnis gebracht, abgesehen für jene, die sich bislang mit dem Thema noch nicht auseinander gesetzt hatten. Aber die Überlegungen rund um diesen Komplex sind auch bei mir wieder intensiver entfacht worden.

Aber am 26. März wachte ich irgendwie unruhig auf, eine Unruhe, die wohl irgendwie die Diskussion hier ausgelöst hatte. Und plötzlich war da der "Gedanke": Wie wäre es, bei einem linearen Back-Link-Algorithmus ohne dabei für jeden String am String-Heap zwei Bytes für den Back-Link zu "verschwenden"? Die Back-Link kann man ja auch erst zum Zeitpunkt der GC erstellen (das macht die GarbColl-Implementierung für den C64 auch, die aber die 2 Bytes reserviert hat). Aber wo tut man den Back-Link hin? Natürlich, in den String selbst, beispielsweise ans Ende! Nun, der String würde ja dadurch zerstört, oder? Wir haben die Fälle ein String hat die

1. Länge >= 2, wo prinzipiell im String für den Back-Link Platz hat. Die beiden überschriebenen Bytes speichert man dann einfach in den Descriptor (wo normalerweise die String-Adresse ist, aber zu diesem Zeitpunkt nicht gebraucht wird), auf den ja der Back-Link zeigt.
2. Länge = 1, wo der Back-Link keinen Platz hat. Auch kein Problem: Der String-Inhalt von einem Byte wird eben so in den Descriptor verlagert. Das eine Byte am Heap wird als "Lücke" markiert. Den Back-Link ersparen wir uns überhaupt!

Gut, damit hätten wir am Heap alle "verwendeten" Strings behandelt. Aber was ist mit den verworfenen Strings, dem Müll, der zwischen den verwendeten herumliegt? Im Zuge der "Collection" muss der Heap mit den gebrauchten Strings und den Lücken zusammenhängend durchwandert werden können. Der gängige Algorithmus von BASIC 4.0 und folgende markiert schon bei der Anforderung eines Strings diesen grundsätzlich als Lücke, wobei der Back-Link keine Adresse darstellt, sondern im High-Byte $FF enthält (was eine String-Adresse nicht haben kann/darf) und im Low-Byte die Länge der Lücke aufweist. Nun, das kann ein Problem werden ... hier haben wir ja keine fest reservierten Bytes für diese Markierung. D. h. wir müssen die Strings zu dem Zeitpunkt als Müll markieren, zu dem er anfällt. Nach einer Analyse der BASIC-Interpreterroutinen kristallisieren sich drei Stellen heraus:

1. Die Zuweisung (LET, GET, INPUT, READ): Eine String-Variable, die bereits einen String (der am String-Heap liegt) zugewiesen hat, bekommt den Descriptor eines neuen Strings hineingeschrieben. -> Der "alte" String muss also als Lücke markiert werden.
2. Die String-Zusammenfügung (Concatenation bzw. String-Addition): Hier entstehen aus 2 Strings ein neuer, wo bei der neue String bereits angelegt wird, bevor die "Argument"-Strings freigegeben werden können, weshalb die Argumente mitunter als Lücken zu markieren sind.
3. Die String-Teilermittlung der Funktionen MID$, LEFT$, RIGHT$. Auch hier entsteht ein neuer String, noch bevor der Argument-String verworfen werden kann.

In all diesen Fällen geht es nur um Strings, die temporär am String-Heap angelegt sind. Solche, die als Konstanten im BASIC-Code eingebettet sind oder im Interpreter-ROM liegen oder Variablen zugeordnet sind, sind nicht betroffen. Wie erkennt man diese? Diese werden stets am String-Descriptor-Stack angelegt. Der Interpreter hat eine zentrale String-Housekeeping-Routine, die sich zwar um das Entfernen von solchen Strings kümmert, aber in den obigen 3 Fällen, wirkt das nicht, weil ein neu produzierter String entsteht, der verhindert, dass etwaige unmittelbar zuvor angelegt Strings gleich wieder vom Heap entfernt werden können. Zudem wird ein String bei Markieren als Lücke "zerstört", kann also dann nicht mehr (etwas für ein Kopieren) verwendet werden. Der Interpreter geht nämlich davon aus, dass auf den Inhalt eines freigegebenen String zugegriffen werden kann! Aber mit den drei für die obigen Stellen entsprechend platzierten Patches kommt man aus, um den entstandenen Müll zu markieren, wobei die Verwendung des Strings und dessen Freigabe entsprechend umgeordnet werden.
Die Markierung erfolgt nach dem Schema

1. Lückenlänge 1: Es wird als der Wert 1 hinterlegt. Als High-Byte eines etwaige Back-Links kann es keinen Back-Link darstellen, da ein String-Descriptor nicht in der Stack-Page ($0100 bis $01FF) zu liegen kommen kann. Damit haben wir eine spezielle Markierung für Einserlücken.
2. Lückenlänge >1: Es wird im High-Byte $FF hinterlegt, im Byte davor dann die Länge der Lücke.

In allen anderen Fällen, wo temporär Strings entstehen, sorgt die Housekeeping-Routine dafür, dass Strings sofort vom Heap verschwinden. Diese erzeugen erst gar keinen String-Müll.

Damit hat man die Voraussetzung geschaffen, dass der String-Heap in einem Zug, vom Anfang bis zum Ende durchgegangen werden kann.

Die Implementierung dafür habe ich Back-Link On-Demand Garbage Collection (BLOD-GC) genannt. Wer mag, hat auch Github-Repository dazu.

Die Beschreibung findet sich auch auf der genannten Seite. Zur Illustration der Arbeitsweise hilft das folgende Bild, das von eben dort kommt:

Es zeigt die Arbeitsweise an exemplarischen Befehlen. Im oberen Teil sieht man die Arbeitsweise der Lückenmarkierung, hier im Fall der String-Addition und mit dem FRE(0)-Aufruf und damit dem Auslösen der Garbage-Collection kommt dann der in 3 Stufen ablaufende Collection-Vorgang:

1. Alle aktiven Strings am Heap erhalten den Back-Link eingepflanzt, im Falle von Länge-1-String, wird das Byte am Heap als "Lücke" deklariert und das Byte im Descriptor des Strings "gesichert".
2. Es wird der Heap durchgegangen, wobei Lücken übersprungen werden und Strings nach "oben" kopiert (also der neue Heap ohne die Lücken aufgebaut). Nach dem Kopieren, wird der Back-Link wieder entfernt und der String restauriert (aus dem Descriptor) und dabei bekommt der Descriptor die neue String-Adresse.
3. Alle Strings mit Länge 1, die ursprünglich am String-Heap waren (und derzeit nur im String-Descriptor zwischen gespeichert sind), werden am String-Heap neu angelegt und der Descriptor mit der neuen String-Adresse versehen.

Damit befinden sich nur noch die "aktiven" Strings am Heap und alle Lücken sind eliminiert, der maximal möglich freie Platz am Heap ist wieder vorhanden.

Hinsichtlich der Laufzeit ist das Verfahren gleich schnell wie die pufferbasierte SuperGC und liegt gleichauf mit den anderen linearen Varianten. Das variiert dann nur noch hinsichtlich des Interpreter-Overheads der jeweiligen BASIC-Version und der jeweiligen CPU-Geschwindigkeit (wenn sie denn vom C64 abweicht). Im Grunde spielen die Abweichungen aber keine Rolle, da die Laufzeit eines solchen linearen Verfahrens im Vergleich zur Standard-Routine ja um Größenordnungen besser ist.

Zitat von Mike

Kann man sich nicht zusätzlich noch ein paar Kopieraktionen sparen, wenn Strings mit den Längen 1 und 2 (und 0 natürlich ohnehin) erst gar nicht im String-Heap abgelegt werden sondern nur im Deskriptor-Pointer 'leben'?

Ab String-Länge 3 geht dann der Tausch "Descriptor-Pointer gegen zwei End-Bytes im String" problemlos, wird ein String gelöscht geht immer die Markierung mit $FFxx an dessen Ende, und die Sonderfallbehandlung für Strings der Länge 1 fällt weg.

Oder hab' ich da was übersehen?

Gemeint ist hier ständig und nicht nur zum Zeitpunkt der Collection, oder? Das Konzept ist aber dann ein gänzlich anderes und habe ich zumindest schon länger verworfen (daher kam wohl zumindest der Grundgedanke, den Descriptor zweckzuentfremden), da hierbei im Interpreter mehr umgebaut werden müsste, wenn es um das String-Handling geht, ist das bei weitem - so finde ich - keine praktikable Lösung.

Im Interpreter müssten dann alle Stellen, die mit einem String-Descriptor hantieren, die Fälle für Strings mit Descriptor (Länge >2) und für Strings der Länge 1 und 2 ohne Descriptor unterscheiden. Dann sollte es auch keine Fälle geben, wo es doch einen Descriptor Länge 1 oder 2 gibt, also auch nicht für Strings, die im BASIC-Text sind. Auch da müsste der String in den Descriptor kopiert werden. So weit so gut. Der Schritt Descriptor-Pointer-zu-String-Adresse und das Schreiben des Descriptors ist mit der Fallunterscheidung zu behandeln, also keine uniforme Behandlung von Descriptoren mehr (die zu einer Union-Struktur in C-Nomenklatur mutiert sind). Nicht sehr elegant wie ich finde. Für eine Konzeptstudie mag es ja interessant sein, aber nicht wirklich für die Praxis, wo der Interpreter noch umfangreicher umgebaut werden müssten. Das geht über ein "Plugin-Replacement" etwas hinaus.

Abgesehen davon, das "Ersparen" von Kopieraktionen wird hier vielleicht überbewertet: Das macht bei einem linearen Algorithmus im Endeffekt und in der Praxis kaum mehr etwas aus. Selbst wenn man sich Stage 3 mit dem Aufbau der Strings der Länge 1 am Heap ersparen würde (also einen Durchlauf durch alle Discriptoren), ist selbst im praxisfremden "Worst Case" mit ca. 9600 Strings die Routine faktisch genauso schnell wie alle anderen linearen Implementierungen (die in der CBM-Variante sogar nur einen "Pass" haben). Vergleicht man mit Garbage Coll 64, die auch 2 Passes hat und man das als Maßstab nimmt, dann ist bei 5000 Strings mit einer Laufzeitersparnis in der Gegend von ca. 12 % zur rechnen (1,5 s statt 1,7 s). Ist eigentlich auch schon egal, wenn man ehrlich ist.

Nur im Vergleich dazu der Aufwand, der in der originalen CBM-Variante von BASIC 4.0 und folgend gemacht wird: Hier wird mit einem Flag und deutlichem Mehraufwand in der Logik getrachtet, dass bei einem bereits "intakter" Heap soweit es geht *nicht* extra kopiert wird in der guten Hoffnung, sich das "Kopieren" zu ersparen. Der Gewinn ist in der Praxis minimal. Die Implementierung Garbage Coll wie auch BLOD ersparen sich das komplett und kopieren selbst bei eine nahezu vollständig "in Ordnung" befindlichen Heap die Strings an die gleiche Stelle. Egal, sie sind unterm Strich in den Benchmarks dennoch schneller.
Natürlich, wenn ich in einer Schleife 1000 mal FRE(0) aufrufe, dann sieht/merkt man den Unterschied - hat dann aber auch nichts mit der Praxis zu tun.