Programmieren Teil 8 – Der Heap

So, nach längerer, einem privaten Projekt geschuldeten Pause, nun endlich der nächste Artikel in der Reihe zum Programmieren mit C++. Im letzten Artikel haben wir uns allgemein mit dem Thema Datentypen und insbesondere einem bestimmten Typ, nämlich den Arrays, beschäftigt. Dabei ist uns ein Problem begegnet: wir können zwar wunderbar Arrays mit einer genau bekannten Größe deklarieren – ein Array mit erst zur Laufzeit bekannter Größe können wir aber noch nicht anlegen, da der Compiler nicht weiß, wie viel Speicherplatz er auf dem Stack für das Array reservieren soll. An dieser Stelle kommt nun ein neuer Speicherbereich ins Spiel, der uns bei der Lösung dieses Problems hilft: der Heap.

Nun kann man sich natürlich fragen, warum hier überhaupt ein Problem existiert; warum kann der Programmcode nicht einfach so durch den Compiler übersetzt werden, dass beim Anlegen eines Arrays mit erst zur Laufzeit bekannter Größe einfach der benötigte Speicherplatz auf dem Stack reserviert wird?

Wir erinnern uns: Variablen stellen im Programmcode lediglich eine Referenz auf eine bestimmte Speicherzelle dar, die relativ zum ebp (extended base pointer, ein in einem Register gespeicherter Wert) angegeben wird. Der ebp ändert sich auch bei jedem Funktionsaufruf. Um dieses Konzept aber umsetzen zu können, muss für alle Variablen innerhalb einer Funktion die genaue Distanz vom ebp bekannt sein, und zwar bereits in dem Moment, in dem das Programm compiliert wird (da hier die Variablen zu relativen Speicheradressen aufgelöst werden). Auf dem Stack können deswegen nur feste, das heißt zur Compile-Zeit in ihrer Größe bekannte Speicherbereiche reserviert werden. Hätte man einen variablen Bereich, wüsste man für nachfolgende Variablen ja gar nicht, ab welcher Adresse (relativ zum ebp) man sie referenzieren sollte.

Um das Dilemma zu lösen, wird also ein weiterer Speicherbereich benötigt, und zwar der bereits erwähnte Heap. Ebenso wie der Stack ist der Heap ein für ein Programm reservierter Bereich im Arbeitsspeicher. Er arbeitet im Unterschied zu jenem aber nicht streng linear – neue Daten können also an beliebigen (noch nicht belegten) Stellen abgelegt und wieder gelöscht werden. Er ist damit perfekt geeignet, um unsere Arrays mit unbekannter Größe zu verwalten.

Erinnern wir uns kurz: ein Array mit bekannter Größe wird in C++ folgendermaßen angelegt:

int as[10];

Obschon es logisch erscheint, können wir ein Array unbekannter Größe nicht so anlegen (die Variable n wird mit einem beliebigen Wert belegt):

int n;
...
n = ...
...
int as[n];

Stattdessen benötigen wir einen anderen Mechanismus. Insbesondere müssen wir dem Compiler mitteilen, dass das Array auf dem Heap und nicht auf dem Stack angelegt werden soll. Zu diesem Zweck verfügt C++ über ein eigenes Schlüsselwort: new. Benutzt werden kann es auf die folgende Art und Weise:

int n;
...
n = ...
...
int* as = new int[n];

Die Schlüsselzeile ist diese hier:

int* as = new int[n];

Fangen wir von hinten mit dem einfachen an: new int[n]. Dieser Ausdruck bewirkt einfach, dass der Compiler veranlasst, ein Array der Länge n (die erst zur Laufzeit bekannt ist) auf dem Heap anzulegen, oder, um genauer zu sein: im Heap wird ein Speicherbereich der Länge n * 4 Bytes (ein int-Wert benötigt 4 Bytes Speicher) reserviert.

Das Gleichheitszeichen = deutet zudem an, dass der Ausdruck einen Wert zurückgibt. Und in der Tat: das “Ergebnis” eines new-Ausdrucks ist immer die Speicheradresse im Heap, ab welcher der gewünschte Speicherbereich reserviert wurde. Diese wird ja benötigt, um den Speicherbereich später wieder aufzufinden.

Bleibt nur noch die seltsame Art der Variablendeklaration mit dem Stern, konkret das int* as zu klären. Aber auch das ist im Grunde einfach: hier wird lediglich eine Variable as deklariert, welche vom Typ int* ist. Und was ist nun int* für ein Typ? Ganz einfach: ein Typ, welcher eine Adresse (durch den Stern * markiert) speichert, ab welcher Integer-Werte (durch int markiert) gespeichert werden. Eine Adresse ist (auf einem 32-Bit-System) übrigens immer 4 Byte groß (auf einem 64-Bit-System dann 8 Byte).

Im Weiteren lässt sich eine Variable vom Typ int* genauso benutzen wie etwa eine Variable vom Typ int[10], indem etwa etwas in der folgenden Art geschrieben werden kann:

int n;
...
n = ...
...
int* as = new int[n];
as[2] = 42;

Das funktioniert, weil der Compiler weiß, was er bei einer solchen Anweisung zu tun hat; er muss einfach die unter as gespeicherte Adresse laden, von dieser aus 8 Byte weiterspringen (wir wollen die 3. Stelle im Integer-Array, überspringen also 2 * 4 Byte) und an die entsprechende Stelle den Wert 42 schreiben. Schauen wir uns zum besseren Verständnis noch die konkrete Situation im Speicher an.

Natürlich benötigen wir nun 2 Speicherbereiche, nämlich den Stack und den Heap. Gehen wir von folgendem Code aus:

void f( int n )
{
    int* as = new int[n];
    as[2] = 42;
}

Wie wir aus einem früheren Artikel wissen, ergibt sich dafür für den Stack unmittelbar nach Aufruf der Funktion f der folgende Aufbau mit den zugehörigen Variablen-Positionen; nehmen wir für n zusätzlich einen Eingabewert von 5 an, leere Zellen enthalten beliebige Werte, die uns (noch) nicht weiter interessieren:

Der Heap im (frei angenommenen) Adressbereich 345678 sieht folgendermaßen aus (er enthält momentan noch keine für uns relevanten Werte):

Gehen wir nun in der Funktion f einen Schritt weiter, nach Ausführung der Anweisung int* as = new int[n];. Nehmen wir an, dass der new-Ausdruck den gewünschten Speicher (für 5 Integer-Werte) auf dem Heap ab der Adresse 345678 reserviert hat; Der Stack sieht dann folgendermaßen aus:

Der Inhalt der Speicherzellen, welche as entsprechen (nämlich 4E 46 05 00) mag etwas seltsam aussehen, ist aber einfach zu verstehen: Zahlen werden im Speicher immer byteweise abgespeichert, und zwar auf regulären Prozessor-Architekturen in umgekehrter Reihenfolge der Bytes. Zur Notation greift man dabei meist auf die hexadezimale Schreibweise zurück, also die Notation der Zahlen in einem System zur Basis 16 (wir selber rechnen tagtäglich in einem System zur Basis 10; Binärzahlen sind zur Basis 2 notiert). Da wir nur über 10 Ziffern (0-9) verfügen, werden die fehlenden 6 “Ziffern” durch die Buchstaben A bis F dargestellt. Der Inhalt des Speichers entspricht also der Zahl 0x0005464E (das 0x markiert die hexadezimale Schreibweise), was genau der Zahl 345678 (die angenommene zurückgegebene Adresse) entspricht. So weit, so einfach.

Und wie sieht der Heap nun aus? Folgendermaßen (<-- *as markiert die Speicheradresse, welche in as gespeichert ist):

Wer jetzt keine Änderung entdeckt, liegt richtig – im Heap hat sich noch nichts getan. Das Reservieren von Speicher allein ändert prinzipiell nichts am Inhalt des reservierten Speichers, zumindest dann, wenn Speicher für ein Array im Heap reserviert wird (es kann auch Speicher für andere Dinge reserviert werden, aber das werden wir später noch sehen). Für echte Änderungen muss noch etwas in den Speicher geschrieben werden, so wie es durch den Ausdruck as[2] = 42; passiert. Nach dessen Ausführung sieht der Heap folgendermaßen aus (im Stack hat sich natürlich nichts geändert):

Der Wert an Speicheradresse 345686 – 0x0000002A – in hexadezimaler Schreibweise entspricht dabei der Zahl 42; da wir an die 3. Stelle im Array geschrieben haben (wir erinnern uns: Arrays sind 0-indiziert, der erste Index beginnt also bei 0, nicht bei 1), befindet sich der Wert entsprechend 8 Bytes (entspricht 2 Integer-Zahlen) hinter der Adresse, auf welche as verweist.

War doch eigentlich ganz einfach, oder? 2 wichtige Dinge sind aber noch zu beachten!

Speicher, der auf dem Heap reserviert wurde, muss auch irgendwann wieder freigegeben werden. Stack-Speicher wird ja automatisch freigegeben, wenn das Ende der aktuell ausgeführte Funktion erreicht wird; mit dem Heap funktioniert das nicht so einfach, da der Compiler nicht dafür sorgt, dass reservierter Heap-Speicher nach dem Ende des Bereiches, wo er benutzt wird, automatisch freigegeben wird (den Grund hierfür werden wir auch später sehen). Die Freigabe muss also manuell erfolgen, wenn man nicht irgendwann sämtlichen verfügbaren Speicher verbraucht haben möchte (zwar wird der Speicher bei Programmende freigegeben, aber dann ist es oft zu spät). Dies geschieht über das Schlüsselwort delete[], etwa einfach so:

void f( int n )
{
    int* as = new int[n];
    as[2] = 42;
    delete[] as;
}

Ein wichtiger Hinweis: auf dem Heap reservierter Speicher muss immer freigegeben werden! Wird das nicht gemacht, hat man ein sogenanntes Speicherleck; Speicherlecks sorgen für einen hohen Arbeitsspeicherverbrauch und sind unter allen Umständen zu vermeiden.

Und ein zweiter Hinweis: C++ erlaubt die Deklaration mehrerer Variablen in einer einzelnen Zeile. Im folgenden Beispiel werden zum Beispiel 2 Integer-Variablen m und n deklariert:

int m, n;

Bei der Deklaration von Variablen, die Speicheradressen aufnehmen, gibt es leider eine etwas unschöne Sache in C++ (eine Altlast aus C-Zeiten; wer die Begründung für dieses Verhalten kennt, möge sich bitte in den Kommentaren melden). Schauen wir uns den folgenden Code an:

int* as, bs;

Der unbedarfte C++-Neuling wird hier wahrscheinlich vermuten, 2 Variablen as und bs deklariert zu haben, die zur Speicherung von Arrays verwendet werden. Leider ist dem nicht so: der Stern * zur Markierung einer Adress-Variablen hängt am Namen der Variablen, nicht am zugehörigen Datentyp; as nimmt also wirklich eine Adresse auf, bs dagegen regulär eine ganze Zahl. Für 2 Adress-Variablen müssen wir das folgende schreiben:

int *as, *bs;

Ungewöhnlich, aber leider ist es so. Wo die Leerzeichen gesetzt werden, ist übrigens egal. Ich habe mir angewöhnt, bei Deklaration einer einzelnen Variablen den Stern an den Typ zu setzen, bei der Deklaration mehrerer Variablen den Stern an den Variablennamen – aber das kann jeder halten, wie er möchte.

Eine letzte Anmerkung: da mit dem Stern * deklarierte Variablen Speicheradressen aufnehmen und daher auf eine bestimmte Adresse im Speicher verweisen – also darauf zeigen, spricht man bei derartigen Variablen dementsprechend von Zeigern, beziehungsweise englisch von Pointern.

Im nächsten Artikel werden wir dann sehen, was man mit Pointern noch alles anstellen kann – bleibt also gespannt! Und diesmal dauert es hoffentlich nicht wieder so lang.