Garbage Collection

Die Garbage Collection (kurz: GC) ist die Müllsammlung (und Beseitigung) für nicht mehr verwendete Strings des BASIC-Interpreters. Je nach Aufbau und Anzahl der verwendeten (String-)Variablen kann in Extremfällen die Dauer dieses Vorgangs Minuten (sogar Stunden) dauern, was sich dem Benutzer gegenüber wie ein Systemabsturz darstellt - der Rechner friert quasi während des Aufräumvorgangs ein. Solange das Programm nur wenige Dutzend Strings benutzt, ist die Laufzeit der GC allerdings (mit z. B. ca. einer Sekunde Laufzeit für 100 aktive String-Variablen) unproblematisch und wird meist kaum auffallen, aber selbst ein kurzer Aussetzer, auch wenn dieser nur einige Sekunden dauert, kann etwa bei interaktiver Benutzerführung oder in einem zeitlich strikten Umfeld irritierend wirken, insbesondere auch für Entwickler, die sich dieser vermeintlich sporadisch auftretenden "Pausen" nicht bewusst sind.

Neben der implizit einsetzenden GC gibt es auch die Möglichkeit, die GC gezielt durchführen zu lassen, was z.B. mit PRINT FRE(0) (zeigt gleichzeitig den noch verfügbaren freien Speicher für den BASIC-Interpreter an) eingeleitet wird.
Weitere Hinweise im Umgang mit der GC finden sich im Abschnitt "Umgang mit der GC".

Funktionsweise

Der für Strings zur Verfügung stehende Speicherbereich (englisch: string heap) ist der gesamte nach dem Programm und dessen Variablen (STREND) frei verbleibende Speicher bis zum Speicherende (FRETOP), der dem BASIC-Interpreter zugänglich ist, wie die Speicherbelegung (BASIC) zeigt.
Ein String selbst wird intern durch einen String-Descriptor dargestellt, welcher aus einem Längen-Byte (damit die mögliche String-Längen von 0-255) und einer Adresse (2 Bytes), auf die eigentlichen String-Daten verweisend, besteht. Eine einfache Variable enthält im Falle eines Strings einen solchen String-Descriptor, wobei auch hier trotzdem 5 Bytes verbraucht, aber nur 3 davon genutzt werden. Bei String-Arrays benötigt ein Element tatsächlich die 3 Bytes.
String-Descriptoren können somit an folgenden Stellen liegen:

• am String-Stack, der temporäre Strings bei der Auswertung von Ausdrücken hält,
• in einfachen Variablen,
• in Arrays.

Die eigentliche Daten eines String befindet sich dort, wo die Adresse im String-Descriptor zeigt, also entweder

• im Programmtext (als String-Konstante) oder
• am String-Heap.

Durch diese Organisation, können Strings hinsichtlich ihrer Länge variabel und flexibel organisiert werden, allerdings mit dem Nebeneffekt, dass die GC den String-Heap von Zeit zu Zeit aufräumen muss.

Die Zeichenketten- bzw. String-Operationen (+) und Zuweisungen zu Stringvariablen mit neuen Werten führen dazu, dass vorher enthaltene Strings nicht mehr gebraucht werden. Der BASIC-Interpreter lässt jedoch die ungenutzten Strings im Speicher und nimmt sich für neue Strings aus dem freien Bereich einfach einen neuen Platz. Das geht allerdings nur solange gut, bis schließlich der freie Platz zur Gänze aufgebraucht ist. Übrig bleiben dann mehr oder weniger freie Lücken, die nicht mehr referenziert werden und bunt mit den genutzten Strings ineinander verzahnt sind. Da diese ungenützten Lücken nicht organisatorisch erfasst sind (sondern nur die genutzten Strings selbst und diese ohne irgendeine Ordnung), müssen die Lücken nun mühsam getilgt werden, indem die vorhandenen, noch gültigen Strings kompaktiert werden. Hier tritt dann (meist unvorhersehbar) die GC auf den Plan. Dies wäre an sich nicht so schlimm, aber die GC hat die betrübliche Eigenschaft, dass ihre Dauer mit der Anzahl der vorhandenen Strings quadratisch steigt.

Der interne Ablauf der GC sieht in etwa so aus:

1. Suche von allen Strings jenen, der die höchste Speicheradresse aufweist (im noch nicht aufgeräumten Bereich liegend).
2. Verschiebe den gefundenen String an die höchste freie Speicheradresse (nur bei diesem kann man sich sicher sein, dass er keinen anderen - außer vielleicht sich selbst - überdeckt) und verkleinere den unaufgeräumten Bereich entsprechend.
3. Setze bei Punkt 1 fort, bis alle Strings im aufgeräumten Bereich liegen (also kein höchst liegender String mehr gefunden werden kann).

Obiger Algorithmus klammert dabei jene Strings aus, die ihren Wert von einer im Programmtext befindlichen String-Konstante per Zuweisungen oder via READ erhält. In diesen Fällen wird tatsächlich der String im Programmtext referenziert und befindet sich damit nicht am String-Heap.

Es gibt bei einer Anzahl von N Strings somit (N × N) Durchläufe, da bei jeder Suche nach dem höchst liegenden String immer auch jene durchlaufen werden, die bereits "aufgeräumt" wurden.

Damit werden die ungenutzten Lücken zwischen den genutzten Strings geschlossen, indem alle Strings in Richtung oberer Speicherrand zusammen geschoben werden. Ähnlich einer Defragmentierung von Dateien auf Floppys und Festplatten (allerdings mit jeweils etwas anderem Ziel dahinter).
Kann bei einer implizit aufgerufenen GC etwa infolge einer Speicherplatzanforderung (z.B. für einen neu anzulegenden String) trotzdem nicht genug Platz frei gemacht werden, dann kommt es zum Abbruch mit der Ausgabe der Fehlermeldung ?OUT OF MEMORY ERROR.

Beispiel

Hier ein Testprogramm, das ein String-Array mit 9000 Strings der Länge 1 anlegt. Jeder einzelne String verbraucht in Summe je 4 Byte des Speichers, insgesamt also nahezu den vollständig zur Verfügung stehenden BASIC-Speicher. FRE(0) stößt hier die Garbage Collection an, die in diesem Fall gar keinen Speicher freigibt, aber trotzdem sehr lange braucht.

 1 M=9000
10 DIM A$(M)
20 PRINT "FREIER STRINGSPEICHER: " FRE(0)
30 B$=CHR$(65)
40 PRINT "ARRAY SETUP ..."
50 FOR I=0 TO M : A$(I)=B$: NEXT
60 PRINT "GARBAGE COLLECTION ..."
70 TI$="000000"
80 PRINT FRE(0) "BYTES FREI"
90 PRINT "DAUER (HHMMSS): " TI$ " /" INT(TI/3600+1) "MINUTEN"

Das funktionell gleichwertige Programm für den Direktmodus fällt etwas kompakter aus, da hier bei der Initialisierung des Arrays String-Konstanten nicht im Programmcode eingebettet sein können und somit gezwungenermaßen auf den String-Heap landen:

M=9000
DIM A$(M)
FOR I=0 TO M: A$(I)="A": NEXT
TI$="000000": PRINT FRE(0) "BYTES FREI"
PRINT "DAUER (HHMMSS): " TI$ " /" INT(TI/3600+1) "MINUTEN"

Beiden Varianten ist gleich, dass die GC hier auf einem normalen C64 1 Stunde 49 Minuten benötigt!

Bei einer kleinen Anzahl aktiver Strings dauert die GC deutlich weniger lang: Bei 10 Strings 0,07 Sekunden, bei 30 Strings 0,34 Sekunden, bei 100 Strings rund eine Sekunde, bei 200 Strings rund vier Sekunden.

Diese Beispiele lassen sich auf dem VICE-Emulator testen, wo sich die reale Laufzeit Dank Warp-Modus auf wenige Minuten (je nach Leistungsfähigkeit der Emulatorumgebung) reduziert:

Umgang mit der GC

Die Garbage Collection kann kaum durch Programmierstil und -techniken beeinflusst, geschweige denn dauerhaft verhindert werden. Der Einsatz der GC kann lediglich

1. durch das Vermeiden gewisser String-Ausdrücke hinausgezögert,
2. durch möglichst geringe Anzahl von Strings in Variablen und Arrays in der Laufzeit geringer gehalten und
3. zu gewissen Zeitpunkten kontrolliert ausgelöst

werden.

Nicht jeder temporärer String trägt zu Anhäufen des String-Mülls bei. Der einfache Fall, bei dem ein String sofort im Anschluss nicht mehr gebraucht wird, kann vom System unmittelbar bereinigt werden, indem die Spitze des "Müllhaufens" abgetragen wird. Typisches Beispiel:

100 FOR C=64 TO 95: PRINT CHR$(C); : NEXT

Dies produziert zwar 32 einzelne Strings, die aber bereits ohne GC und unmittelbar am Ende des PRINT-Kommandos "entsorgt" werden.

Mit der Hinauszögerungstaktik wird versucht den String-Heap klein zu halten, wobei Ausdrücke vermieden werden, die - im schlimmsten Fall sogar iterativ - Zwischenergebnisse (Garbage) erzeugen, sodass das Endergebnis sofort wieder verworfen werden kann (wie zuvor beschrieben). Beispielsweise produziert PRINT von mindestens drei durch "+" verknüpften String-Variablen String-Müll (ein einzelnes "+" erzeugt zwar auch einen temporären String, der jedoch gleich wieder verworfen werden kann):

10 PRINT A$+B$+C$

Der Ausdruck von PRINT produziert ein temporäres Zwischenergebnis (jenes von A$+B$), dass am String-Heap landet und nicht mehr weiter gebraucht wird, aber dennoch nicht unmittelbar entsorgt werden kann (weil nun das Endergebnis zuletzt am Heap liegt).
Hingegen vermeidet die folgende Variante dies einfach:

10 PRINT A$;B$;C$

Generell sollten Strings (in Variablen und als Konstanten im BASIC-Code) so angelegt werden, dass sie ohne weitere Verknüpfung direkt verwendet werden können. So ist z.B. folgendes Unterprogramms ungünstig, da mit jedem Aufruf der String-Heap mit 16 Zeichen verunreinigt wird:

1000 REM HEXADEZIMALE ZIFFER ERMITTELN: DEC -> HEX$
1010 NUMERIC$="0123456789"
1020 ALPHA$="ABCDEF"
1030 HEX$=MID$(NUMERIC$+ALPHA$,DEC+1,1)
1040 RETURN

Die Variablen NUMERIC$ oder ALPHA$ sind vielleicht einzeln woanders auch in Verwendung (eventuell auch außerhalb des Unterprogramms definiert), aber die gut gemeinte Ersparnis wirkt sich zur Laufzeit dann schlussendlich negativ aus.
Besser gleich

1030 HEX$=MID$("0123456789ABCDEF",DEC+1,1)

verwenden, auch auf die Gefahr hin, dass der String im Programm öfter vorkommt (was wiederum durch Zuweisung an String-Variablen, die als Konstanten verwendet werden, effizienter gestaltet werden kann).

Eine weitere Methode wäre, die Garbage Collection durch X=FRE(0) regelmäßig gezielt in Programmbereichen auszuführen, in denen sie wenig stört bzw. nicht auffällt, etwa am Ende von leeren Warteschleifen oder unmittelbar nach einem Löschen des Bildschirms.
Vorteil: Die Wahrscheinlichkeit, dass die Garbage Collection sichtbar den Programmablauf stört, z.B. mitten beim Bildschirmaufbau, sinkt erheblich.
Dieses Verfahren ist aber nur effektiv, wenn das BASIC-Programm nicht zu viele String-Variablen verwendet, da die Dauer der GC mit dem Quadrat der Anzahl dieser Variablen dennoch unakzeptabel lang sein könnte.

Effektiv die Nebenwirkungen der GC zu vermeiden, gelingt nur mit alternativen Implementierungen, die die originale GC-Routine ersetzen.

Implementierung

Im BASIC V2 des C64 befindet sich die GC-Routine im BASIC-ROM an Adresse $B526/46374 (mit ausführlichen, englischen Kommentaren). Diese Routine entspricht jener der MS-BASIC-Implementierung in der Variante "Commodore BASIC 2".

Aufgerufen wird die Routine im

• im Kontext der Funktion FRE, siehe BASIC-ROM an Adresse $B37D/45949,

• in der Routine für das Anfordern von Speicher am String-Heap, siehe BASIC-ROM an Adresse $B4F4/46324 Allocate Space for String,

• bei der Änderung von Basic-Bereichen (etwa im Zuge des Anlegens eines Arrays), siehe BASIC-ROM an Adresse $A408/41992: Check Memory Overlap.

Alternative Implementierungen

Folgende Ansätze sind bekannt bzw. in Verwendung:

1. Pufferspeicher: Die noch aktiven Strings werden in einem möglichst großen Pufferspeicher (typisch 4 bis 16 KByte groß) in einigen wenigen Durchläufen reorganisiert. Die Datenstruktur String bleibt dabei unberührt.
   Laufzeit faktisch linear von der Anzahl der Strings abhängig (je nach Puffergröße könnten auch mehrere Durchläufe nötig sein).
   Keine zusätzlicher Verbrauch durch Verwaltungsinformationen auf dem String-Heap (Kompatibiltität zu bestehenden Programmen, sofern nicht der Speicher unter dem ROM ebenso verwendet wird).
   Es wird ein relativ großer Speicherbereich (für den Puffer) exklusiv benötigt (z.B. das ungenutzte RAM unterhalb der ROMs).
   Eventuell Einfluss auf Interrupt-Verhalten, wenn RAM-unter-ROM-Zugriffe (je nach konkreter Implementierung).
2. Back-Pointer: Die String-Datenstruktur wird geändert, sodass mit zusätzlichen Verwaltungsinformationen (engl. back pointer, am Ende eines Strings am String-Heap) die Lücken und die noch aktiven Strings am String-Heap ohne aufwändige Suche auszumachen sind. So können alle noch in Gebrauch befindlichen Strings in einem Schwung zusammen geschoben werden können.
   Laufzeit ist nur noch − und das strikt − von der Anzahl der Strings abhängig.
   Zusätzlicher Speicherverbrauch (für jeden String, zumindest 2 Bytes), was die Kompatibilität zu Bestandssoftware gefährdet (siehe "Dungeon" für PET 2001).
   Ausnahme: Die Back-Link-On-Demand-Implementierung kommt ohne diesen aus!
   Der BASIC-Interpreter muss zumindest an drei Stellen entsprechend modifiziert werden (Eintrittspunkte für Speicheranforderungs-, Collection-Routine und Korrektur/Auslassung der String-House-Keeping-Routine, in der BLOD-Implementierung den Collection-Routine, Variablenzuweisung, String-Addition und String-Teil-Ermittlung).
   Diese Methode wird benutzt von:
   • BASIC 4.0 der CBM 4000-/8000-Serie und CBM-II-Modelle.
   • BSOS-8296, ein verbessertes ROM für CBM 8296
   • BASIC 3.5 der 264-Serie (C16/C116/Plus4)
   • BASIC 7.0 beim C128
   • Garbcol, Alternativimplementierung für BASIC V2 des C64 (siehe Implementierungen für den C64).
   • Back-Link-On-Demand (BLOD) GC, alternative Implementierung für BASIC V2 des C64 (siehe Implementierungen für den C64).

Implementierungen für den C64:

• Super Garbage Collection (Johann Klasek)
  Dies ist eine pufferbasierte Implementierung. Es gibt zwei Einbindungsvarianten: Patching der Interpreter-Kopie im RAM oder die Interrupt-basierte, die ohne RAM-Kopie des Interpreters auskommt. Die GC verwendet je nach Einbindungsvariante das ungenutzte RAM unterhalb des KERNAL- oder BASIC-ROMs als Pufferspeicher. Der zeitliche Aufwand nimmt einen linearen Verlauf. Die Laufzeit des obigen Beispiels reduziert sich auf 3,4 s.

• Back-Link-On-Demand-GC (Johann Klasek)
  Eine Implementierung basierend auf Back-Pointer-Technik, allerdings ohne die bestehende Datenstruktur zu ändern, sondern es werden die freigegebene Strings entsprechend markiert und entsprechende Strukturen zum Zeitpunkt der "Collection" im bestehenden Datenbestand temporär ein- und aufgebaut (in den Strings am String-Heap und im String-Descriptor).
• Garbage64
  Ebenso eine pufferbasierte Implementierung, die das ungenutzte RAM unterhalb des BASIC- und KERNAL-ROMs verwendet. Allerdings fehlerbehaftet und nur limitiert einsetzbar.
  Publiziert im 64'er-Magazin Februar 1986, Seite 52: "Weg mit dem Müll"
• Garbcol
  Eine Implementierung mit geänderten String-Datenstruktur, wie sie bei BASIC 4.0 erstmalig umgesetzt und später bei BASIC 3.5 und BASIC 7.0 übernommen wurde. Die veröffentlichte Version weist einen Fehler auf.
  Publiziert im 64'er-Magazin Oktober 1988, Seite 54: "High-Speed-Strings".

Weblinks

Wikipedia: Garbage Collection

• Thema: Ergebnisse der BASIC Garbage Collection Compo auf Forum64.de
• Garbage Collection der MS-BASIC-Implementierung in der Variante "Commodore BASIC 2"

Quellen