Kapazität und Reallocation

len und capacity

Bevor wir in die Mechanik des Wachstums einsteigen, müssen die zwei zentralen Begriffe sauber getrennt sein. Sie werden oft synonym genutzt, sind aber etwas Verschiedenes — und genau dieser Unterschied macht das Performance-Spiel rund um Collections aus.

fn main() {
    let mut v: Vec<i32> = Vec::new();
    println!("len = {}, cap = {}", v.len(), v.capacity());   // 0, 0

    v.push(1);
    println!("len = {}, cap = {}", v.len(), v.capacity());   // 1, 4

    v.extend([2, 3, 4]);
    println!("len = {}, cap = {}", v.len(), v.capacity());   // 4, 4

    v.push(5);
    println!("len = {}, cap = {}", v.len(), v.capacity());   // 5, 8 (Realloc!)
}

len() ist die einfache Größe: wie viele Elemente sind tatsächlich im Container. Diese Zahl wächst mit jedem push um eins, schrumpft mit jedem pop um eins. Sie ist die Antwort auf die Frage „wie viele Daten habe ich?".

capacity() ist die innere Größe: wie viele Slots der Container im Heap bereits reserviert hat. Diese Zahl ist immer größer oder gleich len. Sie wächst nur dann, wenn ein neuer Heap-Block alloziert werden muss, weil der bisherige voll ist; sie schrumpft normalerweise nie automatisch.

Im Beispiel siehst du die Mechanik: Start bei 0/0 (kein Heap-Speicher). Beim ersten push springt die Kapazität auf 4 — der Container alloziert direkt einen kleinen Initial-Block. Die nächsten drei Pushes passen ohne Wachstum hinein (Kapazität bleibt 4). Beim fünften Push muss reallokiert werden — der Block wird verdoppelt auf 8. Das ist die zentrale Verdopplungsstrategie des Rust-Container-Wachstums.

Wenn du in einem Profile siehst, dass viel Zeit in Allocator-Aufrufen wie malloc oder realloc verbracht wird, ist meistens ungeplantes Container-Wachstum die Ursache — und die Lösung ist with_capacity.

Wachstumsstrategie: Verdopplung

Die Wahl, wie schnell ein Container bei Bedarf wächst, ist eine fundamentale Designentscheidung. Sie balanciert zwei gegensätzliche Ziele: möglichst wenig Reallocations zu haben (das spricht für aggressives Wachstum) und möglichst wenig ungenutzten Speicher zu reservieren (das spricht für sparsames Wachstum). Rusts Antwort — wie die der meisten modernen Sprachen — ist die geometrische Verdopplung: bei Bedarf wird die Kapazität immer verdoppelt.

fn main() {
    let mut v: Vec<i32> = Vec::new();
    let mut letzte = 0;
    for i in 0..20 {
        v.push(i);
        if v.capacity() != letzte {
            println!("push #{i}: cap = {}", v.capacity());
            letzte = v.capacity();
        }
    }
    // Typische Ausgabe:
    // push #0: cap = 4
    // push #4: cap = 8
    // push #8: cap = 16
    // push #16: cap = 32
}

Die Verdopplung ist mathematisch elegant: über n Pushes hinweg fallen insgesamt nur log₂(n) Reallocations an, und die Gesamtkosten aller Memory-Operationen bleiben linear in n. Dadurch ist push amortisiert O(1) — ein einzelner Push kann zwar teuer sein (wenn er gerade die Verdopplung auslöst), aber über alle Pushes gerechnet bleibt der Durchschnitt konstant. Diese amortisierte Analyse ist der Schlüssel, warum Vec eine so produktive Datenstruktur ist.

Warum Verdopplung und nicht Konstante?

Würde Vec immer nur um einen festen Wert wachsen — sagen wir +1 oder +10 —, wäre jeder volle Push eine Reallokation mit O(n)-Umkopieren der bisherigen Elemente. Über n Pushes hätte man n / k Reallocations mit jeweils O(n)-Kosten, gesamt O(n²/k). Das wäre für große Container desaströs. Verdopplung dagegen liefert das gewünschte amortisierte O(1).

Warum nicht eine schnellere Wachstumsrate, etwa Verdrei- oder Vervierfachung? Theoretisch könnte man — aber dann wird der Speicher-Overhead schnell schmerzhaft. Bei Verdopplung verschwendest du im Worst Case etwa 50 % zusätzlichen Speicher (genau zwischen zwei Verdopplungen). Bei Verdreifachung wären es 66 %. In der Praxis hat sich Verdopplung als guter Kompromiss durchgesetzt — auch C++ std::vector, Go-Slice, Java-ArrayList nutzen sie.

Warum Reallocation teuer ist

Eine Reallocation ist keine triviale Operation — sie ist die teuerste Einzeloperation, die ein Container normalerweise macht. Wer das mentale Modell dafür hat, versteht auch, warum with_capacity so wirkungsvoll ist. Reallocation umfasst vier Schritte:

1. Allokation eines neuen, größeren Buffers (Systemcall, Mutex-Kontention im Allocator).
2. Memcpy aller existierenden Elemente in den neuen Buffer (O(n)).
3. Freigabe des alten Buffers.
4. Bei komplexen Werten: Pointer-Updates in beliebigen Strukturen, die auf den alten Speicher zeigten — was Rust durch Move-Semantik elegant verhindert, aber für den CPU-Cache trotzdem kostet.

Bei einem Vec<i32> mit 10 Millionen Elementen sind das 40 MB, die bei jeder Reallokation umkopiert werden müssen. Bei der finalen Verdopplung von 8M auf 16M Slots wird der 8M-große Block gelesen, in den neuen 16M-Block geschrieben, und der alte freigegeben. Wenn dein Profile-Tool zeigt, dass viel Zeit in malloc, memcpy oder Vec::reserve_for_push verbracht wird, ist das ein klares Indiz für ungeplantes Wachstum. Die Lösung ist immer dieselbe: vorab reservieren.

Bei HashMap sind die Reallokations-Kosten noch höher, weil zusätzlich alle Keys neu gehasht und in das neue Bucket-Layout einsortiert werden müssen. Eine HashMap-Reallokation bei einer Million Einträgen kann sich in den Millisekunden-Bereich addieren — also gut sichtbar in Latency-Diagrammen.

with_capacity — der wichtigste Trick

Wenn du die ungefähre Endgröße eines Containers im Voraus weißt — oder auch nur schätzen kannst —, eliminiert with_capacity praktisch alle Reallocations. Statt mehrere Wachstumsschritte durchlaufen zu müssen, startet der Container direkt mit der passenden Größe. Das ist mit Abstand der wichtigste Performance-Hebel, den die Stdlib bietet.

fn main() {
    // Schlecht: 5-6 Reallocs für 1000 Elemente
    let mut v: Vec<i32> = Vec::new();
    for i in 0..1000 { v.push(i); }

    // Gut: 0 Reallocs
    let mut v: Vec<i32> = Vec::with_capacity(1000);
    for i in 0..1000 { v.push(i); }
}

Gilt für alle Standard-Collections:

use std::collections::{HashMap, HashSet, VecDeque, BTreeMap};

let v: Vec<i32> = Vec::with_capacity(1000);
let s: String = String::with_capacity(256);
let q: VecDeque<u8> = VecDeque::with_capacity(64);
let h: HashMap<String, i32> = HashMap::with_capacity(100);
let s: HashSet<u64> = HashSet::with_capacity(500);
// BTreeMap / BTreeSet haben keine Capacity — Baumstruktur

Im Beispiel sieht man den krassen Unterschied: ohne Reservierung würden bei 1000 Pushes etwa 8-9 Reallocations stattfinden (Wachstumsschritte 4, 8, 16, 32, 64, 128, 256, 512, 1024). Mit with_capacity(1000) ist es genau eine Allokation, danach laufen alle Pushes ohne weitere Speicher-Aktivität. Bei einer Million Pushes ist der Effekt entsprechend dramatischer.

Wichtige Eigenheit: with_capacity ist eine untere Schranke für die tatsächliche Kapazität. Bei Vec::with_capacity(1000) bekommst du mindestens 1000 Slots, eventuell mehr (auf einer typischen 64-bit-Plattform rundet der Allocator oft auf Vielfache der Page-Größe auf). Bei HashMap rundet die Implementation immer auf eine Potenz von 2 auf, weil die interne Bucket-Logik darauf angewiesen ist; HashMap::with_capacity(100) ergibt also eine tatsächliche Kapazität von 128 oder 256.

BTreeMap und BTreeSet haben dagegen keine with_capacity — und das ist kein Versehen. Bei einem B-Baum ist jeder Knoten eine eigene Allokation; es gibt keinen einzigen Buffer, der vorbelegt werden könnte. Die Konsequenz: BTreeMap allokiert pro Insertion einen kleinen Knoten (mit Slot-Reserve für weitere Inserts in denselben Knoten). Mehrere Allocations sind unvermeidbar, aber jede einzelne ist klein.

reserve und reserve_exact

Manchmal kennst du die finale Größe nicht zur Konstruktions-Zeit, sondern erst später — etwa wenn du einen Header gelesen hast, der die Anzahl folgender Records ansagt. Für solche Fälle gibt es reserve als Laufzeit-Variante von with_capacity. Sie macht logisch dasselbe: stellt sicher, dass genug Platz für weitere Inserts vorhanden ist. Daneben gibt es eine spannlose Variante reserve_exact, deren Unterschied in der Speicher-Effizienz liegt.

fn main() {
    let mut v: Vec<i32> = Vec::new();
    v.push(1);

    // Reserviere Platz für 999 zusätzliche Elemente
    v.reserve(999);
    println!("{}", v.capacity());     // >= 1000

    // reserve_exact: weniger overallokation
    v.reserve_exact(500);
}

reserve(additional) stellt sicher, dass mindestens additional weitere Elemente ohne Reallocation Platz haben. Der Container darf intern mehr reservieren — typisch auf die nächste Potenz von 2. Das ist sinnvoll, wenn nach diesem Reserve weitere Pushes kommen, die ebenfalls wachsen lassen würden. Die zusätzliche Reserve verhindert dann gleich mehrere künftige Reallocations.

reserve_exact(additional) verlangt vom Allocator, genau additional zusätzliche Slots bereitzustellen — keine Reserve darüber hinaus. Spart Speicher, aber wenn du nach diesem Reserve nochmal pushst, hast du sofort wieder eine Reallocation. Das ist die richtige Wahl, wenn du genau weißt, dass der Container nach den additional Elementen seine endgültige Größe erreicht hat.

Faustregel: reserve ist der Default, wenn du im Loop weiterhin Pushes machen wirst. reserve_exact nur dann, wenn die finale Größe definitiv erreicht ist und kein weiteres Wachstum mehr kommt — etwa direkt vor einem letzten extend_from_slice-Aufruf, der das Wachstum abschließt.

shrink_to_fit — Speicher zurückgeben

Eine Eigenschaft, die viele Anfänger überrascht: Container schrumpfen nicht automatisch, wenn du Elemente entfernst. Wenn dein Vec einmal auf 100 000 Einträge gewachsen ist und du dann 99 990 davon wieder entfernst, behält er die Kapazität von ungefähr 131 072 (der nächsten Verdopplung über 100 000). Die 10 verbleibenden Einträge sitzen in einem völlig überdimensionierten Heap-Block.

Das ist Absicht: Schrumpfen würde eine neue Allokation auslösen, und in vielen Anwendungen würde der Container danach wieder wachsen — die Schrumpfung wäre Verschwendung. Wer aber wirklich Speicher zurückgewinnen will, ruft shrink_to_fit auf.

fn main() {
    let mut v: Vec<i32> = (0..10_000).collect();
    v.truncate(10);
    println!("{}, {}", v.len(), v.capacity());      // 10, 10000

    v.shrink_to_fit();
    println!("{}, {}", v.len(), v.capacity());      // 10, 10
}

shrink_to_fit() löst eine Reallokation auf die aktuelle Länge aus — der überdimensionierte Block wird durch einen passgenauen ersetzt. Die Elemente werden in den neuen Block kopiert, der alte freigegeben. Damit gibst du Speicher tatsächlich an den OS-Allocator zurück; in einem langlaufenden Prozess sinkt die Speicher-Auslastung sichtbar.

Sinnvolle Anwendungsfälle:

• Eine Collection lebt lange und enthält dauerhaft wenige Daten (z. B. ein Cache, der nach einem Burst auf Spitzenlast wieder geleert wurde).
• Du serialisierst die Collection auf Disk oder ins Netzwerk — übrige Kapazität würde nur die Datenmenge aufblähen.
• Du willst Speicher-Spikes nach einem Pre-Allocation-Setup zurückgeben.

Nicht sinnvoll: wenn die Collection bald wieder wachsen wird. Dann ist shrink_to_fit nur eine unnötige Realloc, die kurz danach durch eine zweite Realloc beim erneuten Wachstum verdoppelt wird.

shrink_to(min)

fn main() {
    let mut v: Vec<i32> = (0..10_000).collect();
    v.truncate(10);
    v.shrink_to(100);       // mind. 100 behalten
    println!("{}", v.capacity());       // ~ 100
}

shrink_to(min) ist die nuancierte Variante: sie schrumpft den Container, aber nur bis zu einer Mindest-Kapazität min. Falls die aktuelle Länge größer als min ist, ändert sie nichts; ansonsten reduziert sie auf max(len, min). Damit kannst du Speicher freigeben, aber gleichzeitig einen kleinen Puffer behalten, in den künftige Pushes ohne Reallokation passen würden.

Das ist eine Mischung aus den beiden Extremen: „komplett schrumpfen" (shrink_to_fit) und „nichts ändern". In der Praxis selten gebraucht, aber in Long-running-Diensten mit gelegentlichen Spitzen ein guter Kompromiss.

Praxis: Wo Kapazität den Unterschied macht

Die folgenden Beispiele zeigen typische Stellen, an denen Kapazitäts-Management den entscheidenden Unterschied macht. Bei den meisten ist das Pattern sehr einfach — eine Größen-Schätzung, dann with_capacity. Aber genau diese kleine Disziplin ist es, die produktiven Rust-Code von naivem unterscheidet.

Bulk-Parser

pub fn parse_logs(input: &str) -> Vec<String> {
    // Wenn input n Bytes hat, sind grob n/50 Zeilen zu erwarten
    let mut zeilen: Vec<String> = Vec::with_capacity(input.len() / 50);
    for line in input.lines() {
        if line.starts_with("ERROR") {
            zeilen.push(line.to_string());
        }
    }
    zeilen
}

Bei einem Log-Parser kennst du nicht die exakte Anzahl der ERROR-Zeilen, aber du kannst eine Obergrenze schätzen: bei einem typischen Log-Format ist jede Zeile etwa 50-200 Bytes lang, also liegt die maximale Zeilenanzahl bei input.len() / 50. Wenn wenige davon ERROR sind, hast du etwas Reserve; in jedem Fall ist die Schätzung deutlich besser als die Default-Strategie „bei 4 anfangen und verdoppeln".

Dieser Pattern — eine Schätzung aus der Eingabe-Größe ableiten — passt fast überall, wo du etwas verarbeitest und ein Ergebnis sammelst. Bei JSON-Parsing wäre es input.len() / 30, bei XML input.len() / 80. Auch wenn die Schätzung daneben liegt, ist sie besser als nichts.

CSV-Reader

pub fn lese_csv(zeilen: &[&str]) -> Vec<Vec<String>> {
    let mut datensaetze: Vec<Vec<String>> = Vec::with_capacity(zeilen.len());
    for zeile in zeilen {
        let felder: Vec<&str> = zeile.split(',').collect();
        let mut rec: Vec<String> = Vec::with_capacity(felder.len());
        for feld in felder {
            rec.push(feld.to_string());
        }
        datensaetze.push(rec);
    }
    datensaetze
}

Bei verschachtelten Strukturen lohnt sich die Kapazitäts-Strategie auf beiden Ebenen. Der äußere Vec weiß genau, wie viele Zeilen er bekommt — zeilen.len() ist die exakte Anzahl. Pro Zeile wird felder.len() als Größe für den inneren Vec genutzt — ebenfalls exakt.

In dieser Form sind beide Vecs ohne eine einzige Reallocation aufgebaut. Bei einer CSV mit 100 000 Zeilen à 20 Feldern sparst du dir damit etwa 1,4 Millionen unnötige Allocator-Operationen.

String-Builder

pub fn render_html(items: &[&str]) -> String {
    // ca. 50 Byte HTML pro Item
    let mut out = String::with_capacity(items.len() * 50);
    out.push_str("<ul>");
    for item in items {
        out.push_str("<li>");
        out.push_str(item);
        out.push_str("</li>");
    }
    out.push_str("</ul>");
    out
}

Beim String-Building rentiert sich with_capacity besonders, weil String dieselbe Verdopplungsstrategie wie Vec hat. Bei einer Liste mit 100 Items und durchschnittlich 50 Bytes pro generiertem HTML-Stück landest du bei etwa 5 KB Output. Ohne Vorreservierung musst du durch alle Verdopplungsstufen von 4 nach 8192 Bytes — 11 Reallocations. Mit Vorreservierung null.

Die Schätzung muss nicht exakt sein. Selbst eine Untergrenze hilft schon erheblich; falls die finale Größe doch darüber liegt, kommen wenige zusätzliche Verdopplungen hinzu — viel besser als von null an alle Stufen durchzulaufen.

Aggregations-HashMap

use std::collections::HashMap;

pub fn zaehle_zugriffe(events: &[(String, u32)]) -> HashMap<String, u64> {
    // Worst Case: alle Schlüssel verschieden
    let mut zaehler: HashMap<String, u64> = HashMap::with_capacity(events.len());
    for (key, _) in events {
        *zaehler.entry(key.clone()).or_insert(0) += 1;
    }
    zaehler
}

HashMap-Reallocations sind besonders schmerzhaft, weil sie nicht nur Bytes umkopieren, sondern für jeden bestehenden Key den Hash neu berechnen und ihn in die neue Bucket-Struktur einordnen. Bei großen Maps oder teuren Hash-Funktionen (z. B. komplexe Composite-Keys) kann eine einzige Reallokation deutlich teurer sein als bei Vec.

Der events.len() ist hier eine Obergrenze: wenn alle Keys verschieden wären, hättest du genau so viele Einträge. In der Realität sind es oft weniger (manche Keys wiederholen sich), also reservierst du etwas zu viel — das ist nicht schlimm. Die clone() ist nötig, weil die HashMap einen besitzten Key braucht, wir aber nur einen Borrow auf den String haben.

Buffered Network Reader

use std::io::{BufReader, Read, Result};

pub fn lese_alles<R: Read>(mut r: R) -> Result<Vec<u8>> {
    let mut buf: Vec<u8> = Vec::with_capacity(8192);
    r.read_to_end(&mut buf)?;
    buf
}

Bei Network- oder File-Reads weißt du oft die Datenmenge im Voraus — etwa über den Content-Length-Header bei HTTP, die Datei-Metadaten oder eine Protokoll-Spezifikation. Wenn das so ist, sollte diese Information in with_capacity einfließen. Der hier gewählte Default-Wert von 8192 Bytes ist ein guter Startpunkt für unbekannte Größen: er entspricht typischen Filesystem-Page-Größen, sodass der erste read_to_end-Aufruf mit einer Page-Allocation arbeitet, ohne dass die Verdopplung schon vor dem ersten Byte einsetzen muss.

Bei sehr kleinen Reads ist die initiale Allokation etwas verschwenderisch; bei sehr großen sparst du dir die ersten paar Verdopplungen. Auf der modernen Hardware ist 8 KB der Sweet-Spot für die meisten Anwendungen.

Image-Processing

pub fn grayscale_pixels(rgb: &[u8]) -> Vec<u8> {
    let pixel_count = rgb.len() / 3;
    let mut grau: Vec<u8> = Vec::with_capacity(pixel_count);
    for chunk in rgb.chunks_exact(3) {
        let g = (chunk[0] as u32 + chunk[1] as u32 + chunk[2] as u32) / 3;
        grau.push(g as u8);
    }
    grau
}

Image-Processing ist ein Paradebeispiel für „finale Größe ist immer bekannt". Ein Graustufen-Bild aus einem RGB-Bild hat exakt ein Drittel der Pixelmenge (eigentlich der Bytemenge, weil RGB drei Bytes pro Pixel hat, Graustufen ein Byte). Bei einem 1920×1080-Bild sind das 2 073 600 Bytes Output. Mit with_capacity ist das eine einzige Allokation; ohne wären es 20 Verdopplungs-Schritte mit immer größeren memcpys.

Bei Bild-Verarbeitung in der Regel with_capacity als Pflicht-Methode — die paar Millisekunden, die du sparst, addieren sich bei Pipeline-Verarbeitung großer Bildmengen schnell.

Lange laufende Server-Caches

use std::collections::HashMap;

pub struct Cache {
    map: HashMap<String, Vec<u8>>,
    zugriffe: u64,
}

impl Cache {
    pub fn neu() -> Self {
        Cache { map: HashMap::with_capacity(1024), zugriffe: 0 }
    }

    pub fn set(&mut self, k: String, v: Vec<u8>) {
        self.map.insert(k, v);
        self.zugriffe += 1;
        if self.zugriffe % 10_000 == 0 {
            self.map.shrink_to_fit();
        }
    }
}

Lange laufende Caches sind genau die Stellen, an denen shrink_to_fit Sinn macht. Im normalen Betrieb wächst der Cache bei Spitzenlast — z. B. zur Stoßzeit. Wenn die Spitze vorbei ist und du viele Einträge entfernt hast, behält die HashMap ihre Kapazität, was den Speicher unnötig belegt. Ein periodisches shrink_to_fit (etwa alle 10 000 Operationen oder zeitgesteuert) gibt den Speicher zurück.

Der Trick mit dem Modulo (if self.zugriffe % 10_000 == 0) ist eine simple, deterministische Variante. In Produktivsystemen würde man das eher zeit- oder lastabhängig steuern; aber das Pattern ist identisch.

Iterator-Collecting mit Size-Hint

pub fn doppelte<I: Iterator<Item = i32>>(iter: I) -> Vec<i32> {
    let (lower, upper) = iter.size_hint();
    let cap = upper.unwrap_or(lower);
    let mut v: Vec<i32> = Vec::with_capacity(cap);
    for x in iter {
        v.push(x * 2);
    }
    v
}

Jeder Iterator in Rust hat eine size_hint()-Methode, die (lower, upper) zurückgibt — eine Unter- und Obergrenze der noch zu erwartenden Elemente. Manche Iteratoren kennen ihre exakte Größe (Range, Vec-Iterator), andere haben nur eine grobe Schätzung (filter, chain mit Unklarheit). Wenn du selbst Iterator-zu-Container-Logik schreibst, kannst du den Hint nutzen, um die richtige Anfangsgröße zu wählen.

collect() macht das übrigens automatisch — bei vec.iter().map(...).collect::<Vec<_>>() ruft die Vec-Implementation intern size_hint ab und reserviert entsprechend. Du musst es also nicht manuell tun, wenn collect der letzte Schritt ist. Aber für eigene Loops oder Sammler ist die explizite Nutzung sinnvoll.

Wann lohnt sich Kapazität wirklich?

Wie bei vielen Performance-Themen ist Vor-Reservierung kein Allheilmittel, das überall angewendet werden muss. Es gibt Situationen, in denen es sich nicht lohnt — und Situationen, in denen es Pflicht ist. Die folgende Tabelle fasst die Bandbreite zusammen.

Die Faustregel: bei sehr kleinen Sammlungen (unter 10 Elementen) ist der Effekt kaum messbar, bei mittleren und großen (über 100 Elementen) klar spürbar. „Premature optimization" gilt zwar als Anti-Pattern, aber with_capacity ist so billig im Code-Aufwand und so unkontrovers in der Wirkung, dass sie kaum als richtige „Optimierung" zählt — sie ist mehr ein guter Default, sobald du eine Größen-Schätzung hast. Nur in der Schnell-Hin-Skript-Phase ist es okay, sie wegzulassen.

Stolperfallen

Weiterführende Ressourcen

Externe Quellen

• Vec::with_capacity – std-Dokumentation
• Vec::reserve – std-Dokumentation
• Vec::shrink_to_fit – std-Dokumentation
• The Rustonomicon – Vec Layout

Verwandte Artikel

• Vec
• String als Collection
• HashMap
• VecDeque und LinkedList
• Collections – Übersicht