Die Speicherbereiche Heap und Stack

In vielen Programmiersprachen werden die Konzepte Heap und Stack vom Benutzer ferngehalten. Da in Rust auch systemnahes und effizientes Programmieren möglich ist, hilft dem gemeinen Rustprogrammierer ein grundlegendes Verständnis von Heap und Stack durchaus. Heap und Stack sind unterschiedliche Speicherbereiche die einem Programm zur Laufzeit zur Verfügung stehen.

Statische Speicherverwaltung auf dem Stack

Der Stack funktioniert wie ein Stapel nach dem last-in-first-out-Prinzip. Der Stack besteht aus mehreren Stack-Frames. Für jede Funktion wird ein Stack-Frame auf den Stack gelegt. Der Stack-Frame einer Funktion beinhaltet ihre Parameter, die lokalen Variablen in ihrem Geltungsbereich und ihre Rücksprungadresse. Die Parameter, Variablen und die Rücksprungadresse wird bei Aufruf auf den Stack gelegt. Sobald der aktuelle Gültigsbereich verlassen wird, werden auch die Variablen, die im Stack liegen, aufgeräumt. Nach dem Ende der Funktion läuft das Programm ab er Rücksprungadresse weiter. Im Folgenden betrachten wir ein stark vereinfachtes Beispiel.

Der Kommentar // <<<<<<<<< zeigt an, welche Stelle im Programm der rechts daneben stehenden Stacktabelle entspricht.

fn add(a: f64, b: f64) 
-> f64 {
    a + b
}
fn main() {
    let x = 1;
    let y = 2;
    // <<<<<<<<<
    let z = add(x, y);
}

| address | name | value |
| ------- | ---- | ----- |
| 0x2010  |      |       |
| 0x2008  |      |       |
| ---------------------- |
| 0x2000  | z    | ?     |
| 0x1008  | y    | 2     | stack frame
| 0x1000  | x    | 1     | von main
| ---------------------- |

fn add(a: f64, b: f64) 
-> f64 {
    a + b
    // <<<<<<<<<
}
fn main() {
    let x = 1;
    let y = 2;
    let z = add(x, y);
}

| address | name      | value  |
| ---------------------------- |
| 0x2018  | b         | 2      |
| 0x2010  | a         | 1      | stack frame
| 0x2008  | jump addr | 0x2000 | von add
| ---------------------------- |
| 0x2000  | z         | ?      |
| 0x1008  | y         | 2      | stack frame
| 0x1000  | x         | 1      | von main
| ---------------------------- |

fn add(a: f64, b: f64) 
-> f64 {
    a + b
}
fn main() {
    let x = 1;
    let y = 2;
    let z = add(x, y);
    // <<<<<<<<<
}

| address | name | value |
| ---------------------- |
| 0x2010  |      |       |
| 0x2008  |      |       |
| ---------------------- |
| 0x2000  | z    | 3     |
| 0x1008  | y    | 2     | stack frame
| 0x1000  | x    | 1     | von main
| ---------------------- |

Die Verwendung des Stacks wird bereits zur Kompilierzeit festgelegt. Daher muss auch die Größe aller Objekte, die auf dem Stack landen, zur Kompilierzeit bekannt sein. Diese Tatsache begründet den Namen statische Speicherverwaltung. Der Datentyp Array, den wir bereits kennenlernen durften, lebt beispielsweise wie alle primitiven Typen komplett auf dem Stack. Daher muss seine Größe auch zur Kompilierzeit feststehen. Wie man Arrays dynamischer größe auf dem Heap ablegen kann, lernen wir im nächsten Abschnitt.

Dynamische Speicherwaltung auf dem Heap

Objekte deren Größe erst zur Laufzeit feststeht, müssen auf dem Heap gespeichert werden. Arrays deren Größe erst während der Laufzeit festgelegt wird sind ein omnipräsentes Beispiel. Die Rust Standardbibliothek stellt dazu glücklicherweise den Typ Vec zur Verfügung¹. Es gibt Platformen vor allem im Embeddedbereich, in denen dem Programmierer kein Heap zur Verfügung steht. Dementsprechend muss man auch auf Vec und viele andere Implementierungen aus der Standardbibliothek verzichten ². Die Syntax zur Erstellung eines Vec ist vergleichbar zum Array. Man verwendet zusätzlich jedoch das Macro vec. Der Schnipsel

#![allow(unused)]
fn main() {
let v = vec![73; 100];
}

legt z.B. einen Vec mit 100 Nullen an. Im Speicher lässt sich das anlegen des Vecs folgendermaßen skizzieren.

Stack                              Heap

| address | name | value    |      | address | value |
| ------- | ---- | -------- |      | ------- | ----- |
|         |      |          |      | ...     | ...   |
|         |      |          |      | 0x2044  | 73    |
|         |      |          |      | 0x2040  | 73    |
|         |      |          |      | 0x2036  | 73    |
| ?       |      | ?        |      | 0x2032  | 73    |
| ------  | ---- | -------- |      | 0x2028  | 73    |
| 0x1064  | v    | len, ... |      | 0x2024  | 73    |
|         |      | 0x2020   | ---> | 0x2020  | 73    |
| ------  | ---- | -------  |      | 0x2016  | ?     |
| 0x1008  |      | ?        |      | 0x2012  | ?     |

Wenn man also einen Vec als lokale Variable in einer Funktion verwendet, wird ein kleiner Overhead zur Verwaltung mit fester Größe auf den Stack gelegt. Die damit assoziierten Daten landen auf dem Heap. Das praktische ist, dass sobald der Verwaltungsbereich eines Vecs aufgeräumt wird, dieser dafür sorgt, dass auch der Speicher auf dem Heap freigegeben wird.
Üblicherweise ist auf dem Heap deutlich mehr Speicher vorhanden als auf dem Stack. Wenn wir versuchen eine Millionen 128-Bit Nullen auf dem Stack anzulegen, ist es gar nicht so unwahrscheinlich, dass das Programm zur Laufzeit mit der Meldung stack overflow abbricht. Die Grenze ist platformabhängig.

#![allow(unused)]
fn main() {
let arr: [i128; 1_000_000] = [0; 1_000_000];
}

Der Heap verträgt deutlich mehr.

#![allow(unused)]
fn main() {
let v: Vec<i128> = vec![0; 100_000_000];
}

Zugriffe auf den Stack sind deutlich schneller.

1: Vec ist also kein primitiver Typ, da er nicht von der Sprache Rust sondern von ihrer Standardbibliothek implementiert wird.

2: Auf einem handeslüblichen PC muss man nicht damit rechnen, über keinen Heapspeicher zu verfügen.