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:

Adresse Inhalt Inhalt Inhalt Inhalt
123450 <– esp
123455 <– as [= ebp - 4]
123458 <– ebp
123462
123466 05 00 00 00 <– n
123490 <– bottom

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

Adresse Inhalt Inhalt Inhalt Inhalt
345678
345682
345686
345690
345694

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:

Adresse Inhalt Inhalt Inhalt Inhalt
123450 <– esp
123455 4E 46 05 00 <– as [= ebp - 4]
123458 <– ebp
123462
123466 05 00 00 00 <– n
123490 <– bottom

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):

Adresse Inhalt Inhalt Inhalt Inhalt
345678 <– *as
345682
345686
345690
345694

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):

Adresse Inhalt Inhalt Inhalt Inhalt
345678 <– *as
345682
345686 2A 00 00 00
345690
345694

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.

Kommentare

  1. #1 Sascha
    Juli 18, 2013

    Daran sieht man wieder, dass Mehrfachdeklarationen in einer Zeile immer problematisch sein können.
    Lieber ein paar Zeilen mehr, dafür aber sauber deklarierte Variablen.

  2. #2 Frank Wappler
    http://lang--lang.ist's.her...
    Juli 18, 2013

    Marcus Frenkel schrieb (Juli 17, 2013):
    > [...] 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.

    > nehmen wir für n zusätzlich einen Eingabewert von 5 an

    > 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: [...]

    Cliffhanger:
    Was wäre, falls ein zweiter Speicherbereich (z.B. der Länge “k * 4 Bytes”) zu reservieren und zu nutzen sein soll, bevor der beschriebene “eine Speicherbereich der Länge n * 4 Bytes, ab Adresse 345678” wieder freigegeben wird?

    Wird vom Compiler ein weiterer “Adresse-Wert ausdrücklich angewiesen?
    Oder weist der Compiler (per Programm) lediglich an, dass und wie ein weiterer “Adresse-Wert erst zur Laufzeit errechnet und in den Stack geschrieben wird?

  3. #3 Marcus Frenkel
    Juli 18, 2013

    @Frank Wappler
    So ungefähr. Durch das new-Schlüsselwort wird dynamisch zur Laufzeit Speicher reserviert; *wo* das gemacht wird, hängt mehr oder weniger vom Betriebssystem ab, das wird noch nicht während der Kompilierungszeit bestimmt. Das Betriebssystem verwaltet die freien Speicherbereiche und sorgt dafür, dass der neue Speicher an einer passenden Stelle reserviert wird. Zur Zeit der Kompilierung sind also die Adressen der dynamisch reservierten Speicherbereiche noch nicht bekannt, immer erst zur Laufzeit – und potentiell liefert jedes “new” eine neue Adresse (falls nicht vorher etwas per “delete” freigegeben wurde natürlich).

  4. #4 rolak
    Juli 18, 2013

    new-Schlüsselwort

    ‘Schlüsselwort’ (also analog zu ‘class’) halte ich für unangemessen – ist doch ‘new’ nur ein leichter zu schreibender Deckel für die Speicherreservierung, zB getmem(_type_, _count_, _init_), eher so etwas wie ein überladenes Makro.

    *wo* das gemacht wird, hängt mehr oder weniger vom Betriebssystem ab, das wird noch nicht während der Kompilierungszeit bestimmt

    Falls es um den Ort des Speichers geht: Nein bis Jein, siehe unten – falls um den Prozeß der Reservierung geht: Nein, das ist schon eine ordinäre RTL-Prozedur, die sich darum kümmert.

    Das Betriebssystem verwaltet die freien Speicherbereiche und sorgt dafür, dass der neue Speicher an einer passenden Stelle reserviert wird.

    Falls nicht von vorneherein die maximale Heapgröße feststeht und beim Programmstart akquiriert wird, ist es ein zweistufiger Prozeß. Im bisher vom Programm beschlagnahmten Speicher für den Heap lebt eine Datenstruktur (Liste, Heap, …), die von new() und delete() gepflegt wird. Sollte der Platz für den Erfolg eines new() nicht ausreichen und sowohl Compiler als auch OS dies zulassen, kann durch Anfrage beim OS evtl das Programm seinen Heap vergößern (und selbstverständlich im gegenteiligen Falle verkleinern), doch generell verwaltet das Programm mittels des Compilers RTL seinen Heap selber.

    Wegen der Verwaltungsdaten paßt auch das Heapabbild des posts nicht ganz: Wenn 345678 die Adresse des ersten passenden freien Blocks ist, erhält as den Wert 345678+x, wobei das x je nach Verwaltungsaufwand verschieden ist.

    dass der Compiler veranlasst, ein Array .. auf dem Heap anzulegen

    Vielleicht wäre es sinnvoll, entwirrenderweise umzuformulieren in etwas wie

    dass der Compiler Code generiert, der zur Laufzeit Speicher für ein Array .. auf dem Heap reserviert

    Abgesehen von der Verwaltung des Variablenplatzes ergibt ein “int ivar = const” den Code

    mov ivar,const

    während “int *ivar = new _type_ [n]” irgendwas ergeben dürfte wie

    mov eax,n
    imul eax, SizeOf(_type_)
    push eax
    call _getmem
    inc esp,4
    mov ivar,eax

  5. #5 michael
    Juli 19, 2013

    Ein im Programmcode bewirkt schon etwas mehr als reine Speicherbereitstellung.

    von: http://www.cplusplus.com/reference/new/operator%20new%5B%5D/

    operator new[] can be called explicitly as a regular function, but in C++, new[] is an operator with a very specific behavior: An expression with the new operator on an array type, first calls function operator new (i.e., this function) with the size of its array type specifier as first argument (plus any array overhead storage to keep track of the size, if any), and if this is successful, it then automatically initializes or constructs every object in the array (if needed). Finally, the expression evaluates as a pointer to the appropriate type pointing to the first element of the array

  6. #6 rolak
    Juli 20, 2013

    Es ist schwer zu sehen, worauf sich Dein Korrektur-Kommentar womit bezieht, michael, doch für die im blogpost genannten Beispiele (Variationen über ‘int’) gibt es afaik keine Initialisierung. Und meine Wenigkeit geruhte, diese allgemein als Pseudoargument einzuführen.

  7. #7 Havok
    August 25, 2013

    Wann geht’s weiter? :-]

  8. #8 Marcus Frenkel
    August 25, 2013

    Bald! ;)
    Der nächste Artikel ist in Arbeit. In letzter Zeit dauert es immer etwas länger – ich bitte das zu entschuldigen. ;)