StartseiteVon Bits und Bytes

Programmieren Teil 8 – Der Heap

Von / 17. Juli 2013 / 8 Kommentare / Seite 1 von 3 / Auf einer Seite lesen
Mehr

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

1 / 2 / 3 / Auf einer Seite lesen
Stichworte: , , ,
Mehr

Kommentare (8)

  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
    https://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: https://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. 😉