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
- 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.
- 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:
- 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.
- 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.
- 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
- 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.
- 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:
- 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".
- 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.
- 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. 
