Zum Inhalt springen

cat posts/stack-und-heap.md

Stack und Heap – und wie Python das macht

Was auf dem Stack liegt und was im Heap, nachgemessen in Rust und Python: warum ein String 24 Bytes hat, ein Move fast nichts kostet und eine Million Zahlen in Python zehnmal so viel Platz brauchen.

Retro-Foto: Auf einer Kommode liegen ordentlich gefaltete Kleiderstapel, daneben verschwindet ein Holzstuhl unter einem chaotischen Haufen zerknüllter Kleidung.

In Teil 3 von „Rust lernen“ stand ein Satz, der viel voraussetzt: Ein String liegt mit Zeiger, Länge und Kapazität auf dem Stack (Stapelspeicher), seine Zeichen liegen im Heap. Dieser Artikel misst nach, was das heißt, und vergleicht es mit Python. Dort stellt sich die Frage nämlich nie, und das hat seinen Preis.

Zwei Arten von Speicher

Jeder Thread bekommt einen eigenen Stack, einen zusammenhängenden Speicherbereich fester Größe. Ruft eine Funktion eine andere auf, legt sie oben einen Rahmen (Frame) mit deren lokalen Variablen ab. Kehrt die Funktion zurück, wird der Frame (Rahmen) wieder weggenommen. Anlegen und Freigeben kosten fast nichts: Ein Register zeigt auf das obere Ende, und das wird verschoben. Dafür muss die Größe jedes Frames schon beim Kompilieren feststehen.

Der Heap ist der Rest. Dort fordert das Programm zur Laufzeit Speicher beliebiger Größe an, und eine Speicherverwaltung (Allocator) sucht dafür einen freien Platz. Das ist deutlich langsamer, und jemand muss den Speicher wieder freigeben. In C ist das der Programmierer, in Python der Interpreter. In Rust passiert es, wenn der Besitzer seinen Scope verlässt.

Nachgemessen in Rust

size_of liefert die Größe eines Typs in Bytes, also den Platz, den eine Variable auf dem Stack belegt:

fn main() {
    println!("u16:              {:>4} Bytes", size_of::<u16>());
    println!("usize:            {:>4} Bytes", size_of::<usize>());
    println!("[u8; 1024]:       {:>4} Bytes", size_of::<[u8; 1024]>());
    println!("&str:             {:>4} Bytes", size_of::<&str>());
    println!("String:           {:>4} Bytes", size_of::<String>());
    println!("Vec<u32>:         {:>4} Bytes", size_of::<Vec<u32>>());
    println!("Box<u64>:         {:>4} Bytes", size_of::<Box<u64>>());
    println!("Option<Box<u64>>: {:>4} Bytes", size_of::<Option<Box<u64>>>());
}
u16:                 2 Bytes
usize:               8 Bytes
[u8; 1024]:       1024 Bytes
&str:               16 Bytes
String:             24 Bytes
Vec<u32>:           24 Bytes
Box<u64>:            8 Bytes
Option<Box<u64>>:    8 Bytes

Gemessen auf einem 64-Bit-System. Zahlen und Arrays liegen vollständig auf dem Stack, auch ein Array mit 1024 Bytes. Ein &str besteht aus Zeiger und Länge, zusammen 16 Bytes. Ein String hat zusätzlich die Kapazität, also 24 Bytes, egal ob er drei Zeichen enthält oder drei Millionen. Ein Vec ist genauso aufgebaut. Box<u64> legt einen einzelnen Wert in den Heap und behält auf dem Stack nur den Zeiger.

Die letzte Zeile ist eine kleine Optimierung: Ein Zeiger in einer Box ist nie null, also kann Rust den Fall „kein Wert“ als Null darstellen und braucht kein zusätzliches Byte dafür. Was Option ist, kommt in Teil 6geplant der Serie.

Wie die Kapazität wächst, zeigt ein String, an den Stück für Stück etwas angehängt wird:

let mut text = String::new();
for wort in ["404", " ", "/favicon.ico", " ", "/wp-login.php"] {
    text.push_str(wort);
    println!("len {:>2}, capacity {:>2}", text.len(), text.capacity());
}
len  3, capacity  8
len  4, capacity  8
len 16, capacity 16
len 17, capacity 32
len 30, capacity 32

Reicht der Platz nicht, holt String einen größeren Bereich aus dem Heap, mindestens doppelt so groß, und kopiert den Inhalt um, falls der alte Bereich nicht an Ort und Stelle wachsen kann. Die genauen Zahlen sind ein Implementierungsdetail der Standardbibliothek. Weißt Du vorher, wie groß der Text wird, spart String::with_capacity(n) das Umkopieren.

Was ein Move kostet

Damit wird klar, warum ein Move in Rust billig ist. let b = a; kopiert die 24 Bytes auf dem Stack, Zeiger, Länge und Kapazität. Die Zeichen im Heap bleiben, wo sie sind, und gehören jetzt b. Deshalb muss a ungültig werden: Sonst gäbe es zwei Zeiger auf denselben Heap-Bereich und zwei Besitzer, die ihn freigeben wollen.

a.clone() dagegen fordert einen neuen Heap-Bereich an und kopiert alle Zeichen. Bei einem Log mit 2 GB sind das 2 GB. Deshalb verlangt Rust, dass Du clone hinschreibst. Für Copy-Typen wie u16 gibt es den Unterschied nicht: Sie besitzen keinen Speicher im Heap, also ist die bitweise Kopie schon die vollständige.

Wenn der Stack voll ist

Der Stack ist klein. Unter Linux hat der Haupt-Thread meist 8 MiB (ulimit -s), Threads, die ein Rust-Programm selbst startet, bekommen standardmäßig 2 MiB. Rekursion ohne Abbruch füllt ihn schnell:

fn tiefer(n: u64) -> u64 {
    let puffer = [0u8; 1024];
    puffer[0] as u64 + tiefer(n + 1)
}

fn main() {
    println!("{}", tiefer(0));
}

Schon der Compiler hat Bedenken:

warning: function cannot return without recursing
 --> src/main.rs:1:1
  |
1 | fn tiefer(n: u64) -> u64 {
  | ^^^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing
2 |     let puffer = [0u8; 1024];
3 |     puffer[0] as u64 + tiefer(n + 1)
  |                        ------------- recursive call site
  |
  = help: a `loop` may express intention better if this is on purpose
  = note: `#[warn(unconditional_recursion)]` on by default

Startest Du das Programm trotzdem als Debug-Build, legt jeder Aufruf ein weiteres Kilobyte auf den Stack, bis nichts mehr geht:

thread 'main' (10764) has overflowed its stack

Danach ist der Prozess beendet. Das ist ein Absturz, kein Panic: Anders als einen Panic kann das Programm ihn nicht abfangen. Python schützt sich davor mit einer Obergrenze für die Rekursionstiefe: sys.getrecursionlimit() liefert standardmäßig 1000, darüber kommt ein RecursionError: maximum recursion depth exceeded. Das ist eine gewöhnliche Exception.

Wie Python das macht

In CPython liegt fast jedes Objekt im Heap, auch eine Zahl wie 1000. Nur ein paar fest eingebaute Objekte wie None und die kleinen Zahlen (dazu gleich mehr) stecken im Interpreter selbst. Ein Python-Frame hält für seine lokalen Variablen nur Zeiger auf solche Objekte. Jedes Objekt trägt einen Kopf mit Referenzzähler und Typzeiger mit sich:

>>> import sys
>>> sys.getsizeof(1)
28
>>> sys.getsizeof(2**70)
36
>>> sys.getsizeof([])
56

Gemessen mit Python 3.14 auf 64 Bit. Eine kleine Ganzzahl belegt 28 Bytes, ein u16 in Rust 2. Den Zähler kannst Du sogar sehen:

>>> logs = []
>>> sys.getrefcount(logs)
2
>>> alias = logs
>>> sys.getrefcount(logs)
3

Die 2 statt 1 kommt vom Aufruf selbst, der als Argument einen weiteren Verweis hält. Jedes alias = logs erhöht den Zähler, jedes Ende eines Verweises senkt ihn. Fällt er auf null, gibt CPython das Objekt frei. Das ist dieselbe Frage, die Rust mit Ownership beantwortet, nur zur Laufzeit und mit beliebig vielen Besitzern.

Ein paar Zahlen werden nie neu angelegt. CPython hält die Ganzzahlen von -5 bis 256 als fertige Objekte vor:

>>> a = 256; b = int("256"); a is b
True
>>> a = 257; b = int("257"); a is b
False

Das spart Speicher für die häufigsten Werte, ist aber ein Implementierungsdetail. Vergleiche Zahlen immer mit ==, nie mit is.

Eine Million Zahlen

Wie sich das summiert, zeigt eine Liste mit einer Million Ganzzahlen. In Python, gemessen mit tracemalloc:

import tracemalloc

tracemalloc.start()
zahlen = list(range(1000, 1_001_000))
print(tracemalloc.get_traced_memory()[0])
39999640

Knapp 40 MB. Die Liste selbst enthält eine Million Zeiger zu je 8 Bytes, das sind 8 MB. Der Rest sind die Zahlen selbst, jede ein eigenes Objekt im Heap. Das macht rund 32 Bytes pro Zahl, also etwas mehr als die 28, die getsizeof meldet. Die Zahlen beginnen bei 1000, damit der Cache für kleine Zahlen nicht mitspielt.

In Rust:

let zahlen: Vec<u32> = (1000..1_001_000).collect();
println!("{} Bytes", zahlen.capacity() * size_of::<u32>());
4000000 Bytes

4 MB, ein Zehntel. Die Zahlen liegen ohne Kopf und ohne Zeiger direkt nebeneinander im Heap. Das spart auch Zeit: Läuft ein Programm über die Zahlen, liest der Prozessor sie am Stück aus dem Cache, statt für jede einem Zeiger an eine andere Stelle zu folgen. Das ist einer der Gründe, warum numerische Python-Bibliotheken wie NumPy ihre Daten genauso ablegen wie Rust.

Weiterlesen

0 Kommentare

Noch keine Kommentare. Sei der/die Erste!