JKs Back-Link On Demand Garbage Collection
Autor: Johann E. Klasek

Inhalt

  1. Technische Aspekte
  2. Laufzeitverhalten
  3. Download
  4. Urheberrechtshinweis
  5. Pläne
  6. Referenzen

Technische Aspekte

Wie ist die BLOD-GC in die BASIC-Umgebung eingebunden?

BASIC-Interpreter-Patch-Einbindung

Die Einbettung der BLOD-GC wird durch das 4 Änderungen im Interpreter vorgenommen. Das BASIC-ROM wird ins RAM kopiert, um den Einsprungspunkt der originalen GC-Routine zu kapern und zur neuen, separat im RAM liegenden Routine (innerhalb von $C000-$D000) zu verzweigen. Es müssen zusätzlich an 3 weiteren Stellen des Interpreters Patchungen vorgenommen werden, die dafür sorgen, dass nicht mehr am String-Heap benutzte Strings entsprechend als frei markiert werden.

  1. Variablen-Zuweisung: Ein bereits der zugewiesenen Variable befindlicher String wird am Heap als frei markiert.
  2. String-Addition: Die beiden an der Addition beteiligen Operanten werden, sofern am Heap befindlich und temporär angelegt als frei markiert.
  3. Teil-String-Ermittlung: Die bei der Funktion LEFT$, RIGHT$, MID$ verwendete Eingabe-String wird, sofern am Heap befindlich und temporär als frei markiert.

In allen anderen Fällen, werden temporäre Strings sofort nach dem Gebrauch auch gleich wieder vom String-Heap entfernt. Diese muss man also nicht zuvor explizit als frei markieren.

Wie funktioniert das Verfahren?

Diese Implementierung braucht, wie etwa bei CBM BASIC 4.0 oder später bei BASIC 3.5 und BASIC 7.0 für jeden String keine zusätzlichen 2 Bytes je String am String-Heap, denn der Back-Link wird im String selbst angelegt und die dabei überschriebenen Bytes werden vorübergehend im Descriptor gespeichert. Für den Sonderfall eines Strings mit Länge 1 wird am Heap eine spezielle "Lückenmarkierung" mit dem Wert "1" hinterlegt. Sonst beginnen Lückenmarkierungen mit einem $FF-Byte, in der Speicherstelle davor befindet sich der Wert für die Länge der Lücke.
Nur aktive Strings enthalten in den letzten beiden Bytes den sogenannten "Back-Link" auf den Descriptor (der sich im String-Descriptor-Stack, in einer einfachen Variablen oder in einem Array-Element befinden kann) zeigt.

Hier eine Darstellung der Variablen, des String-Descriptor-Stacks und des String-Heaps für folgende Befehlssequenz:

B$="Y"
A$="X"
A$="ABC"+"DEF"
PRINT FRE(0)

Der Collection-Prozess ist in der Stufen aufgeteilt:
  1. Stufe (Stage): Alle aktiven Strings erhalten am String-Stack einen Rückwärtsverweis auf den Descriptor (in den letzen beiden Bytes, die überschriebenen Bytes werden im Descriptor statt der String-Adresse gerettet). Bei Strings der Länge 1 werden diese mit dem Wert 1 überschrieben (als Markierung für einer Einserlücke) und der String-Inhalt wird im String-Descriptor im Low-Byte der Adresse gerettet.
    Der Rest sollten dann nur noch die markierten Lücken sein.
  2. Stufe (Stage): Der Heap wird kompaktiert, indem nun von der obersten Adresse des Heaps in Richtung Heap-Top Lücken und aktive Strings durchgegangen werden. Voraussetzung ist, dass nicht mehr gebrauchte Lücken als frei markiert wurden (siehe oben) und Stufe 1 die aktiven Strings mit einem Backlink versehen hat. Die aktiven Strings (wenn also weder ein $FF oder $01 als High-Byte eines Back-Links vorliegt) werden nach "oben" kopiert, die Lücken werden übergangen, also schieben sich ohne Lücken zusammen. Nach dem Kopieren werden die letzen beiden Bytes des Strings wieder hergestellt und der Descriptor erhält nun die neue Adresse des Strings.
  3. Stufe (Stage): Es fehlen noch die Länge-1-Strings, die nun alle gesucht werden. Dabei werden nur solche betrachtet, die auch vorher tatsächlich am Heap lagen, welche entsprechend markiert wurden (mit einer $00xx-Adresse, die sonst nicht vorkommen kann) und auf den Heap gelegt werden. Der String-Wert stammt aus dem Descriptor, im Descriptor wird die neue String-Adresse hinterlegt.

Laufzeitverhalten

Im Vergleich zum Standard-BASIC-V2 kommt es im Extremfall zu einer rund 2300-fachen Beschleunigung (bei 9600 Strings).
BLOD-GC kann mit der
Super-Garbage-Colllection mithalten und ist etwas schneller als unter BASIC 7.0 auf einem C128 oder unter BASIC 3.5 auf einem Plus/4 oder C16. Am C64 ist nur die ebenfalls lineare Implementierung GarbColl schneller, allerdings mit dem Nachteil, pro String 2 Byte mehr zu verbrauchen (weshalb der 9600-String-Test nicht lauffähig ist).
Die Testprogramme befinden sich auf dem D64-Image, im Abschnitt Download.

Programm GC-DEMO - Stresstest
[h:mm:s]
GC-TEST 9600 Strings
[h:mm:s]
BLOD-GC 1:43 3,1
BASIC V2 26:22 2:04:27,0
SuperGC 1:43 3,1
Garbage64 (NG) 1:46 2,8
GarbColl (NG) 1:38
BASIC 3.5 1:48 3,2
BASIC 7.0 2:11 3,6
BASIC 7.0 FAST 1:03 1,8
BASIC 4.0 CBM 8xxx 1:30
BASIC 4.0 CBM 4xxx 1:26
BASIC 4.0+ CBM-II (2 MHz 6509) 1:10 2,1

Download


Urheberrechtshinweis

Die Programme und Dateien können frei verwendet, kopiert und verteilt werden, solange die Hinweise zum Autor erhalten bleiben.

Pläne

Referenzen

  1. C64-Wiki.de: Garbage Collection
  2. ROM-Listing Original-Routine:
    Die automatisiert ergänzten Kommentare dazu sind kaum brauchbar.
  3. Jim Butterfield Artikel-Liste Compute!
    1. Compute! Issue 10 - March 1981: Learning About Garbage Collection
    2. Compute! Issue 49 - June 1984: Garbage Collection On Commodore Computers
    3. Compute! Issue 50 - July 1984: Commodore Garbage Collection Part 2
  4. Artikel in Magazin c't 1984/6 S. 72: BASIC intern - Was nicht im Handbuch steht: Teil 3: Strings und 'Garbage collection'
  5. Buch "Microsoft-Basic: Konzepte, Algorithmen und Datenstrukturen", Luidger Röckrath, Franzis' Verlag, ISBN: 3772380115
    6.2.3 Die Stringspace-Reorganisation Garbage collection (GARCOL), S. 123

 


Best viewed with any browser zurück zur Startseite