Garbage Collection

Aus C64-Wiki
Wechseln zu: Navigation, Suche

Die Garbage Collection (kurz: GC) ist die Müllsammlung (und Beseitigung) für nicht mehr verwendete Strings des BASIC-Interpreters. Er ist das Schreckgespenst der BASIC-Programmierer, denn die GC schlägt unvermittelt zu und 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.

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.

Funktionsweise[Bearbeiten]

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[Bearbeiten]

Hier ein Provokationsprogramm für die GC, 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:

 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!

Als Beispiel die Programmvariante getestet auf dem VICE-Emulator, wo sich die reale Laufzeit Dank Warp-Modus auf wenige Minuten (je nach Leistungsfähigkeit der Emulatorumgebung) reduzieren lässt:

Listing und Durchlauf Garbage Collection Testprogramm

Umgang mit der GC[Bearbeiten]

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.

Mit der Hinauszögerungstaktik wird versucht Ausdrücke zu vermeiden, die - im schlimmsten Fall sogar iterativ - Zwischenergebnisse (Garbage) erzeugen, welche sofort wieder verworfen werden. Beispielsweise bei PRINT mit mindestens zwei "+"-Verknüpfungen (ein einzelnes "+" behandelt der Interpreter genauso wie ein ";"):

10 PRINT A$+B$+C$

produziert ein temporäres Ergebnis, dass am String-Heap landet und nicht mehr weiter gebraucht wird. 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[Bearbeiten]

Im BASIC V2 des C64 befindet sich die GC-Routine im BASIC-ROM an Adresse $B526/46374.

Aufgerufen wird die Routine im

Alternative Implementierungen[Bearbeiten]

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 8 KByte groß) in einigen wenigen Durchläufen reorganisiert. Die Datenstruktur String bleibt dabei unberührt.
    Nachteil: Es wird ein relativ großer Speicherbereich (für den Puffer) exklusiv benötigt (z.B. das ungenutzte RAM unterhalb der ROMs).
  2. Back-Pointer: Die String-Datenstruktur wird geändert, sodass mit zusätzlichen Verwaltungsinformationen (engl. back pointer, beim String am String-Heap) die Lücken bzw. noch aktiven Strings am String-Heap ohne aufwändige Suche auszumachen sind und damit alle noch in Gebrauch befindlichen Strings in einem Schwung zusammen geschoben werden können.
    Nachteil: Zusätzlicher Speicherverbrauch (für jeden String 2 Bytes) und der BASIC-Interpreter muss an etlichen Stellen entsprechend modifiziert werden.
    Diese Methode wird von
benutzt.

Implementierungen für den C64:

  • Super Garbage Collection (Johann Klasek)
    Dies ist eine pufferbasierte Implementierung. Die GC verwendet das ungenutzte RAM unterhalb des KERNAL-ROMs als Pufferspeicher. Der zeitliche Aufwand nimmt einen linearen Verlauf. Die Laufzeit des obigen Beispiels reduziert sich auf 3,4 s.
  • Garbage64
    Ebenso eine pufferbasierte Implementierung. Publiziert im 64'er-Magazin Februar/1986
  • Garbcol
    Eine Implementierung mit geänderten String-Datenstruktur. Publiziert im 64'er-Magazin Oktober/1988.

Weblinks[Bearbeiten]

WP-W11.png Wikipedia: Garbage Collection