Super Garbage Collection > Klasek Homecomputers

JKs Super Garbage Collection

Geschichtliches

Das Projekt stammt aus dem Jahr 1985, als die BASIC-programmierten Projekte auf dem C64 begannen umfangreicher zu werden. Die Garbage-Collection (GC) des Commodore Basic V2 erwies sich dabei nicht nur als äußerst störend, sondern war sogar hinderlich. Nach dem der Autor ein Projekt übernahm und völlig neu überarbeitete (eine Programmbibliothek, wie es sie in ähnlicher Form zig-fach gab und gibt), waren die Anforderungen hinsichtlich "Usability", Zuverlässigkeit und Stabilität entsprechend hoch vorgegeben - um sich auch im ständigen rauen Betrieb des Freaks Computer- Clubs zu bewähren - was aber mit der originalen GC nicht im Entferntesten realisierbar war. Aus der Sicht des Autors war die Entwicklung einer besseren Implementierung einer Garbage Collection Routine daher unumgänglich.
Ohne die damals schon bekannten Implementierungen (es war damals wohl schon das verbesserte Verfahren in Basic 4.0, Basic 3.5 und 7.0 im Einsatz) zu kennen bzw. wahrzunehmen, bildete sich die Idee, die GC-Laufzeit durch Vewendung eines brachliegenden Speicherbereichs im C64 zu beschleunigen. Eine Änderung der String-Datenstruktur erschien dem Autor eigentlich als zu kompliziert, ein etwaiger zusätzlicher Speicherverbrauch als inakzeptabel und so wurde schon von vorn herein diese Variante verworfen.

Das Projekt wurde im Laufe des Jahres 1985 umgesetzt und bis zur Version 1.1 in eine fast veröffentlichungsreife Version gebracht. Die angestrebte Veröffentlichung in Zeitschrift 64'er wurde dann nicht mehr in Angriff genommen, da just im Februar 1986 eine andere Implementierung der GC namens "Garbage64" für den C64, mit gleicher Methodik (wenn auch fehlerhaft in der Implementierung) veröffentlicht wurde.

Technische Aspekte

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

Klassischer BASIC-Interpreter-Patch-Einbindung

Die Einbettung der Super-GC ist recht archaisch und konservativ. Man könnte sagen, nicht wirklich sonderlich elegant. Das BASIC-ROM wird ins RAM kopiert, nur um den Einsprungspunkt der originalen GC-Routine zu kapern und zur neuen, separat im RAM liegenden Routine (innerhalb von $C000-$D000) zu verzweigen.
Aus Vorsicht (vielleicht auch Unkenntnis) ist die Super-GC in der 1985er-Variante vollständig mit gesperrten Interrupts abgearbeitet worden, da ja das RAM unter dem KERNAL in Bearbeitung war. Wäre nicht notwendig, da das Schreiben unterhalb des KERNALs keine Wegblendung des ROM erforderlich macht. Die Interruptsperrung hätte für den Lesezugriff, nämlich beim blockweisen Kopieren zurück in den Stringheap-Bereich gereicht (in der 2013-Edition ist das behoben).
Interrupt-Einbindung (Standardmethode)

Es handelt sich um eine recht elegante Einbindungstechnik, die die IRQ-Behandlung anzapft. Dabei ist es nicht mehr notwendig das BASIC-ROM ins darunterliegende RAM zu kopieren, um dann im RAM den Patch zu setzen. Der Speicherbereich unterhalb des ROM kann somit anderweitig verwendet werden, etwa als Puffer für die Super-GC, während das RAM unter dem KERNAL etwa als Grafikspeicher (Hires-Bitmap) verwendet werden kann. In einer alternativen Variante, wird das RAM unter dem KERNAL-ROM als Puffer verwendet und jenes unter dem BASIC-ROM bleibt frei.
Die "alte" Garbage-Collection wird normal aufgerufen, aber innerhalb von 1/60 Sekunden wird sie von einem IRQ unterbrochen, wo überprüft wird, ob gerade die alte GC läuft. Hierzu ist eine relativ aufwändige Prozedur notwendig, die verschiedene Fälle erkennen und den Zustand von Stack und String-Heap/-Variablen korrigieren muss, bevor zur neuen GC verzweigt werden kann.
Eine leichte Einbuße der Variante ist, dass sie rund 200 Bytes mehr Platz benötigt, aber dennoch nur geringfühgig langsamer ist.

Historische Anwendung

Im Praxiseinsatz war diese GC-Implementierung ein Teil einer umfangreicheren "Library" mit etlichen Erweiterungen, um die gängigen Schwächen des BASIC V2 auszumerzen bzw. Vorgänge zu beschleunigen. Sie hat so viele Jahre im harten Praxisbetrieb einer Programmbibliothek (Diskettenmanagers) für den Freaks-Computer-Club seinen Dienst versehen.

Download

Version 1985: V1.1 (Rev. 8), 1985-12-27
Github repository (hyprass and acme)
1. Dokumentierte Quelldatei (ASCII) (ASCII-Format in Hypra-Ass-Syntax ohne Zeilennummern)
  Anmerkung:
  Es handelt sich hier um eine unkorrigierte Fassung, die nachträglich in realen Betrieb bzw. im folgenden Image als Binary mit Hilfe eines Monitors gepatcht wurde. Die Korrektur besteht im Tausch der Zeilen 1050-1100 mit 1105-1120 und Berücksichtigung des eines String-Überhangs durch eine Pufferreserve.
2. Dokumentierte Quelldatei (PRG) (Hypra-Ass-Format als PRG-Datei)
3. Dokumentierte Listing-Ausgabe (ASCII) (Hypra-Ass List-Ausgabeformat)
4. Code/Binary (PRG) (erstellt von Hypra-Ass, mit Bugfix-Patches, PRG-Datei)
5. D64 Image Super Garbage Collection (Binary, Basic-Loader, Demo)
  Binary: $CDEF-$CFFF
  Verwendung:
```
LOAD "GARBAGE COLLECT",8,1
NEW
LOAD "GC-DEMO",8
RUN
```
  In Zeile 1 ist die Initialisierung der Super-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 ;) ).
Version 2020: V2.2 Release 3, 2020-12-14
Github repository
1. Quelldatei (ASCII-Format in ACME-Syntax, englische Kommentare)
  Quelldatei (ASCII-Format in ACME-Syntax, deutsche Kommentare)
  Löst die Version V2.1 von 2019 ab.
  Wichtig:
  Diese Version ersetzt auch die Version 2013 V2.0, die 2 Bugs beseitig, die mit der Optimierung zu 2.0 hineingekommen sind. Während der eine Bug fast nie auftritt (wenn, dann kann aber die GC hängen bleiben!) kann der zweite Bug Daten korrumpieren.
  Die alte V2.0-Version daher nicht einsetzen!
  Anmerkung:
  Es handelt sich hier um eine überarbeitete Fassung, die kleinere Optimierungen und Korrekturen aufweist. Außerdem wird ein während die Garbage-Collection läuft mit einem "*" in der rechten unteren Ecke angezeigt.
  Außerdem werden Interrupts nur genau zu für den Zugriff auf das unter dem ROM liegende RAM gesperrt, d.h. der interrupt-basierte Timer wird nur geringfügig gestört.
2. Makefile (erstellt aus Source die unterschiedlichen PRG-Versionen)
3. Quelldatei des Debug-Moduls (ASCII-Format in ACME-Ausgabeformat)
  Ist nur optional, wenn man mit aktivierter Debug-Option im Quellcode ein Debug-Programm assemblieren möchte. Diese zeigt dann während des GC-Laufs den Puffer als Hires-Bild an, wo man die GC bei der Arbeit "beobachten" kann.
4. Code/Binary BASIC-Patch-Einbindung mit Puffer unter KERNAL (PRG) (PRG-Datei)
  Reportdatei/Listing-Ausgabe (ASCII) für die BASIC-Patch-Einbindung (ASCII-Format in ACME-Ausgabeformat)
  Speicherbelegung (RAM):
  - $A000-$BFFF gepatchte BASIC-ROM-Kopie
  - $C500-$C710 SuperGC - das Binary
  - $E000-$FFFF Pufferspeicher
5. Code/Binary IRQ-Einbindung mit Puffer unter BASIC (PRG) (PRG-Datei)
  Reportdatei/Listing-Ausgabe (ASCII) für die IRQ-Einbindung mit Puffer unter BASIC (ASCII-Format in ACME-Ausgabeformat)
  Speicherbelegung (RAM):
  - $A000-$BFFF Pufferspeicher
  - $C500-$C7DE SuperGC - das Binary
6. Code/Binary IRQ-Einbindnug mit Puffer unter KERNAL (PRG) (PRG-Datei)
  Reportdatei/Listing-Ausgabe (ASCII) für die IRQ-Einbindung mit Puffer unter KERNAL (ASCII-Format in ACME-Ausgabeformat)
  Speicherbelegung (RAM):
  - $C500-$C7D4 SuperGC - das Binary
  - $E000-$FFFF Pufferspeicher
7. D64 Image Super Garbage Collection 2020-Edition (Binary, Basic-Loader, Demo-Programm, Standardtest-Programm)
  Kurze Dokumentation
  Inhalt:
```
0 "supergc-2020-dis" jk 2a
9     "gc-demo         "  prg
3     "gc-std-test     "  prg
2     "gc-test         "  prg
3     "supergc-basic   "  prg
3     "supergc-irqa    "  prg
3     "supergc-irqe    "  prg
1     "supergc-loader  "  prg
3     "supergc         "  prg
637 blocks free.
```
  Das PRG supergc ist dabei die Variante mit IRQ-Einbindung und Puffer bei $A000 (unter BASIC-ROM).
  
  Demo- und Test-Programme:
  Stresstest für die GC ...
```
LOAD "GC-DEMO",8
RUN
```
  Standardtest mit 5000 Strings ...
```
LOAD "GC-STD-TEST",8
RUN
```

Urheberrechtshinweis

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

Pläne

[_] Ausbau der Dokumentation (laufend).
[X] Verbesserung der Einbettung: ROM-fähiger Hook-Mechanismus per IRQ-Handler. (seit V2.2)
[X] Dezentere Interrupt-Blockierung
[X] Kleine Verbesserung der Routine in Details (eher ästhetischer Natur, auch etwas hinsichtlich Laufzeit).

Referenzen

C64-Wiki.de: Garbage Collection
ROM-Listing Original-Routine:
Die automatisiert ergänzten Kommentare dazu sind kaum brauchbar.
Jim Butterfield Artikel-Liste Compute!

64'er-Magazin Februar 1986: Garbage64 Alternativimplementierung mit Bufferverfahren (wie diese Variante).
Artikel in Magazin c't 1984/6 S. 72: BASIC intern - Was nicht im Handbuch steht: Teil 3: Strings und 'Garbage collection'
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

zurück zur Startseite
14.12.2020 Webmaster