JKs Back-Link On Demand Garbage Collection | |
Autor: Johann E. Klasek |
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.
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.
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:
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 |
0 "./blodgc-2024-di" jk 2a 1 "blodgc-loader " prg 4 "blodgc " prg 8 "gc-demo " prg 2 "gc-test " prg 649 blocks free.
Demo- und Test-Programme:
In Zeile 1 ist die Initialisierung der BLOD-GC auskommentiert.
Um sie zu aktivieren bzw. das Demo mit der GC ablaufen zu
lassen, muss man das REM davor entfernen.
Das Demo-
Programm verkappt den Stringheap künstlich (durch ein Float-
Array) und stoppelt fleißig 700 Strings unter heftiger Mistanhäufung
zusammen. Der Fortschritt wird durch "."-Schlange angezeigt, die sich auf
den Querstrich in Bildschirmmitte zu bewegt. In immer kleiner
werdenden Abständen schlägt die GC zu, wobei in der
Originalvariante die Pausen immer länger werden, sieht man bei
der Super-GC zwar nach wie vor die Stelle, an der die GC
einsetzt durch einen kurzen und merklichen Ausetzer, aber dieser
ändert sich in der Dauer kaum. Am Ende angelangt kann man sich
nach Drücken einer Taste die 700 erzeugten Strings anzeigen
lassen (um sich davon zu überzeugen, dass die Strings nicht durcheinander oder kaputt sind ;) ).
LOAD "GC-DEMO",8 RUNStandardtest mit 5000 Strings ...
LOAD "GC-TEST",8 RUN
Die Programme und Dateien können frei verwendet, kopiert und verteilt werden, solange die Hinweise zum Autor erhalten bleiben.
zurück zur Startseite |