String-Heap

Der String-Heap (engl. heap = dt. Haufen) ist der Speicherbereich für dynamische Zeichenketten des BASIC-Interpreters. Er liegt beim C64, wie bei allen 8-Bit Microsoft BASICs, am Ende des Basic-Speichers, die Standardadresse (MEMTOP) ist 40960/$A000. Andere CBM-BASIC-Varianten mit mehr als 64 KByte Speicherausstattung verlagern den String-Heap mitunter sogar in eine andere Speicher-Bank (gemeinsam mit anderen Variablen oder sogar separat).
Als weitere Bezeichnung sind auch String Storage Area, String Space, String-Bereich, String-Speicher in verschiedenen Quellen bekannt und mehr oder weniger geläufig.

Aufbau

Die Elemente des Heaps bestehen aus Zeichenketten, die eine Länge von 1 bis 255 Zeichen aufweisen. Diese werden von einem String-Descriptor (z.B. in einer String-Variablen oder vom String-Descriptor-Stack) referenziert, wenn eine Zeichenkette noch in Verwendung ist. Ausgehend von den am Heap befindlichen Zeichenketten lassen sich eventuell dazugehörige String-Descriptoren und die nicht mehr verwendeten Zeichenketten (engl. garbage, also der Zeichenkettenmüll, auch als unbenutzte "Lücken" bezeichnet) nicht direkt ermitteln, was eine Reorganisation und Kompaktierung des Heaps aufwendig macht.
Ab BASIC 3.5 (hervorgegangen aus dem älteren Vorfahren BASIC 4.0 der PET-Ära, wo eine neue Art der Organisation erstmalig zu finden ist) und in späteren BASIC-Versionen wird dieser Nachteil mit folgenden Strukturmaßnahmen am Heap beseitigt:

1. Ein zusätzlicher Rückwärtsverweis zum String-Descriptor (Back-Link) bei jeder Zeichenkette erlaubt das Lokalisieren eines Descriptors und dessen Korrektur, sollte sich die Zeichenkette verschieben.
2. Einer Längenangabe einer zurückgelassenen Lücke, wodurch der Heap eine einzige Struktur wird, wo aktive Zeichenketten und unbenutzte Teile identifiziert werden können.

Neu angelegte Zeichenketten lassen den Heap "abwärts" wachsen, in Richtung niedrigerer Adressen, dem Ende des Speicherbereichs für indizierte Variablen (STREND) entgegen. Die aktuelle "Spitze" (engl. Top of Heap) des Haufens markiert der Zeiger FRETOP.
Ist der String-Heap ausgeschöpft (wenn also FRETOP bei STREND angelangt ist), wird mit Hilfe der Garbage Collection versucht, diesen so zu kompaktieren, dass nicht mehr verwendete Zeichenketten (also nicht von einem String-Descriptor referenzierte "Lücken") wieder zu einem zusammenhängenden freien Bereich zusammengefasst werden.

Nach dem Aufruf folgender Befehle im Direktmodus:

A$="ABC"
B$(2)=A$+"XYZ"

sieht der String-Heap im Speicher wie folgt aus:

          ├─             ─┤
MEMTOP    │               │◄─────┐           BASIC-Speicherende, üblicherweise $A000
          └───────────────┘      │
          ┌───────────────┐      │
$9FFF     │      'C'      │      │
          ├─             ─┤      │
          │      'B'      │      │
          ├─             ─┤      │
          │      'A'      │◄───┐ │           String "ABC" von A$
          ├───────────────┤    │ │       ─┐
          │      'Z'      │    │ │        │ 
          ├─             ─┤    │ │        │
          │      'Y'      │    │ │        │  ungenützter Speicherblock ("Lücke"), der nach der String-Addition übrig geblieben ist
          ├─             ─┤    │ │        │  (nicht mehr von einem Descriptor referenziert)
          │      'X'      │    │ │        │
          ├───────────────┤    │ │       ─┘
          │      'Z'      │    │ │
          ├─             ─┤    │ │
          │      'Y'      │    │ │
          ├─             ─┤    │ │
          │      'X'      │    │ │
          ├─             ─┤    │ │
          │      'C'      │    │ │
          ├─             ─┤    │ │
          │      'B'      │    │ │
          ├─             ─┤    │ │
          │      'A'      │◄─┐ │ │◄┐         Zusammengesetzter String "ABCXYZ" von B$(2)
          ├───────────────┤  │ │ │ │     ─┐
          │               │  │ │ │ │      │
          ├─             ─┤  │ │ │ │      │
          │               │  │ │ │ │      │
                  .          │ │ │ │      │
                  .          │ │ │ │      │  Freier, noch zuweisbarer Platz des String-Heaps
                  .          │ │ │ │      │
          │               │  │ │ │ │      │
          ├─             ─┤  │ │ │ │      │
STREND    │               │  │ │ │ │◄┐    │
          └───────────────┘  │ │ │ │ │   ─┘
                  .          │ │ │ │ │
                  .          │ │ │ │ │
                  .          │ │ │ │ │
          ├───────────────┤  │ │ │ │ │
          │   High-Byte   ││ │ │ │ │ │
          ├─             ─┤├─┘ │ │ │ │
          │   Low-Byte    ││   │ │ │ │
          ├─             ─┤    │ │ │ │ 
          │   Länge (6)   │    │ │ │ │       String-Descriptor im Array B$(), Element B$(2)
          ├───────────────┤    │ │ │ │
                  .            │ │ │ │
                  .            │ │ │ │
                  .            │ │ │ │
          ├───────────────┤    │ │ │ │
          │   High-Byte   ││   │ │ │ │
          ├─             ─┤├───┘ │ │ │
          │   Low-Byte    ││     │ │ │
          ├─             ─┤      │ │ │ 
          │   Länge (3)   │      │ │ │       String-Descriptor der Variable A$
          ├───────────────┤      │ │ │ 
                  .              │ │ │
                  .              │ │ │
                  .              │ │ │
          ┌───────────────┐      │ │ │ 
$0038     │   High-Byte   ││     │ │ │
          ├─             ─┤├─────┘ │ │       MEMTOP - Ende des BASIC-Speichers: höchstmögliche Adresse des String-Heaps
$0037     │   Low-Byte    ││       │ │
          └───────────────┘        │ │
                  .                │ │
                  .                │ │
                  .                │ │
          ┌───────────────┐        │ │
$0034     │  High-Byte    ││       │ │
          ├─             ─┤├───────┘ │       FRETOP - Zeigt auf den zuletzt angeforderten String (auf des 1. belegte Byte)
$0033     │   Low-Byte    ││         │
          ├───────────────┤          │
$0032     │  High-Byte    ││         │
          ├─             ─┤├─────────┘       STREND - Ende des Array-Bereichs: niedrigstmögliche Adresse des String-Heaps
$0031     │   Low-Byte    ││                          (das erste Byte nach den Arrays)
          └───────────────┘


Legende:
   belegt
   unbelegt (Lücke)
   frei

Verwendung

Wenn eine Auswertung eines Ausdrucks (als Parameter von Funktionen, rechter Teil einer Zuweisung, Parameter von Ausgabefunktionen wie PRINT) einen Wert vom Typ String ergibt, wird dieser in der Regel am Heap angelegt. Dabei gibt es zwei Optimierungen im Interpreters, die besondere Umstände berücksichtigen, um den am Heap entstehenden "Müll" (engl. Garbage) zu reduzieren:

1. Der zuletzt am Heap angelegte String wird gleich wieder entfernt, wenn dieser nicht gebraucht wird (also am String-Descriptor-Stack "zuoberst" liegt und dieser String verworfen wird).
   Beispiel: PRINT "STR"+"ING"
   Zuerst wird "STR", dann "ING" auf den Heap gelegt und schließlich das Ergebnis "STRING". Letzteres wird nach der Ausgabe nicht mehr benötigt und wird durch diese Optimierung gleich wieder vom Heap entfernt. Es verbleiben aber die ersten beiden Teil-Strings als Garbage am Heap.
   Im Gegensatz dazu wird im Falle von PRINT "STR"; "ING" lediglich jeder String für sich auf dem Heap gelegt, ausgegeben und gleich wieder entfernt. Das "ING" nimmt dabei den Platz von "STR" am Heap ein und wird dann auch daraufhin entfernt, sodass in diesem Fall auch kein Müll am Heap verbleibt.
2. Ein konstanter String im Programmcode (also nicht in einer Direktmoduseingabe) wird nicht auf den Heap kopiert, sondern im String-Descriptor direkt referenziert.