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.
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
- Rust lernen (Teil 3): Ownership erklärt die Regeln, die diesen Speicher verwalten.
- Was passiert eigentlich bei
python skript.py? zeigt, was der Interpreter vom Bytecode bis zu den Frames tut.
Tastenkürzel
- j k
- nach unten / oben scrollen
- n p
- nächster / vorheriger Abschnitt
- g G
- Anfang / Ende des Artikels
- t
- Gliederung zeigen
- ?
- diese Hilfe zeigen
- Esc
- schließen
0 Kommentare
Noch keine Kommentare. Sei der/die Erste!
Anmelden um einen Kommentar zu hinterlassen.