Kapitel 06: Collections (Datenstrukturen der Standardbibliothek)

In den vorherigen Kapiteln haben wir gelernt, wie wir einzelne Werte (wie Zahlen, Zeichen oder Textketten) im Speicher ablegen. In der echten Programmierung müssen wir jedoch meist mit einer Vielzahl von Werten gleichzeitig arbeiten – zum Beispiel einer Liste von Benutzern, den Artikeln in einem Einkaufswagen oder einer Zuordnung von Postleitzahlen zu Städten.

In diesem Kapitel lernen Sie die verschiedenen Datensammlungen (Collections) kennen, die Rust bereitstellt. Wir besprechen ihre Funktionsweise, ihre Speichereigenschaften und wann Sie welche Struktur wählen sollten.

In diesem Kapitel bieten wir Ihnen drei verschiedene Perspektiven auf das Thema an. Wählen Sie die Sicht, die am besten zu Ihrem Hintergrund passt:

• Für Anfänger: Konzentriert sich auf grundlegende Sichten auf Arrays, Tupel, Vektoren und HashMaps anhand einprägsamer Analogien und eines Einkaufswagen-Beispiels.
• Für Profis: Behandelt Algorithmen- und Cache-Vergleiche, Performance-Optimierungen durch Entry-API, Custom Keys (Hash/Eq/PartialEq), Custom Hasher (FNV-1a) und heterogene Sammlungen.
• Hardware-Sicht: Analysiert das physikalische Stack/Heap-Speicherlayout von Vektoren und Fat Pointern, CPU-Bounds-Checks bei Arrays, Heap-Reallokation auf Kernel-Ebene, SwissTable-SIMD-Suchen und Robin-Hood-Kollisionsauflösung.

Kapitel 6: Daten aufräumen und sortieren – Collections für Einsteiger

Herzlich willkommen zu Kapitel 6! In den vorherigen Kapiteln hast du bereits gelernt, wie man einzelne Werte in Variablen speichert – zum Beispiel eine Zahl oder einen Text. Aber was machst du, wenn du eine ganze Einkaufsliste verwalten, die Highscores eines Spiels speichern oder ein Telefonbuch programmieren möchtest?

Wenn wir für jeden einzelnen Eintrag eine eigene Variable anlegen müssten (wie eintrag1, eintrag2, eintrag3 …), würden wir sehr schnell den Überblick verlieren. Unser Code würde riesig, unordentlich und extrem schwer zu erweitern sein.

Hier kommen Datenstrukturen (in Rust oft Collections genannt) ins Spiel. Sie sind wie praktische Ordnungshelfer oder Aufbewahrungsboxen in deinem Zimmer. Sie helfen dir, viele Daten sauber zu sortieren, zu durchsuchen und zu verwalten.

In diesem Kapitel schauen wir uns die fünf wichtigsten Ordnungshelfer in Rust an. Wir erklären sie dir mit einfachen Beispielen aus dem Alltag, sodass du sie sofort verstehst – selbst wenn du noch nie zuvor programmiert hast!

Die Lernziele dieses Kapitels

Am Ende dieses Kapitels wirst du:

1. Wissen, wann du ein Tupel oder ein Array verwendest.
2. Verstehen, warum der Vektor (Vec\<T\>) der König unter den Listen in Rust ist und wie du sicher auf seine Elemente zugreifst, ohne dass dein Programm abstürzt.
3. Begreifen, wie ein Slice wie ein Suchscheinwerfer auf deine Daten wirkt.
4. Mit einer HashMap wie in einem Telefonbuch blitzschnell Werte nachschlagen können.
5. Die geniale Entry-API nutzen können, um Werte (wie in einem Einkaufswagen) elegant zu zählen.

1. Das Tupel: Die gemischte Pralinenschachtel

Stell dir vor, du kaufst eine edle Pralinenschachtel. In dieser Schachtel ist jedes Fach genau für eine bestimmte Praline geformt.

• Das erste Fach hält eine runde Marzipan-Praline (eine Zahl).
• Das zweite Fach hält eine eckige Nougat-Praline (einen Text).
• Das dritte Fach hält eine weiße Kokos-Praline (einen Wahrheitswert: ja oder nein).

Die Schachtel hat eine feste Anzahl an Fächern. Du kannst nachträglich keine neuen Fächer hineinkleben oder Fächer herausreißen. Und das Besondere ist: Die Pralinen in den Fächern dürfen völlig unterschiedliche Sorten (Datentypen) haben!

Genau das ist ein Tupel in Rust.

Wie sieht ein Tupel in Rust aus?

Hier ist ein komplettes, kompilierbares Beispiel. Kopiere es gerne in dein Projekt und probiere es aus!

fn main() {
    // Wir erstellen unsere "Pralinenschachtel" (das Tupel).
    // Es enthält eine ganze Zahl (i32), einen Text (&str) und einen Wahrheitswert (bool).
    let pralinenschachtel: (i32, &str, bool) = (3, "Nougat-Traum", true);

    // Methode 1: Die Pralinen einzeln über ihre Fachnummer (Index) herausholen.
    // Achtung: In der Informatik fangen wir fast immer bei 0 an zu zählen!
    let anzahl = pralinenschachtel.0;
    let name = pralinenschachtel.1;
    let lecker = pralinenschachtel.2;

    println!("In der Schachtel liegen {} Stück der Sorte '{}'.", anzahl, name);
    if lecker {
        println!("Urteil: Super lecker!");
    }

    // Methode 2: Die Schachtel auf einmal auspacken (Destrukturierung).
    // Dabei weisen wir den Inhalt der Fächer direkt neuen Variablen zu.
    let (stueck, sorte, ist_lecker) = pralinenschachtel;
    println!("Ausgepackt: {}x {} (Lecker: {})", stueck, sorte, ist_lecker);
}

Zeile für Zeile erklärt:

• let pralinenschachtel: (i32, &str, bool) = ...: Hier definieren wir das Tupel. Die Typen stehen in runden Klammern, getrennt durch Kommas. Das sagt dem Rust-Compiler genau, was in jedem Fach liegt.
• pralinenschachtel.0: Mit dem Punkt . gefolgt von der Nummer greifen wir auf das jeweilige Fach zu. 0 ist das erste Fach, 1 das zweite und so weiter.
• let (stueck, sorte, ist_lecker) = pralinenschachtel;: Das nennen wir Destrukturierung (ein großes Wort für ein einfaches Prinzip). Rust nimmt das Tupel auseinander und packt die Werte in die drei neuen Variablen stueck, sorte und ist_lecker. Das ist oft viel übersichtlicher als die Punkt-Schreibweise!

2. Das Array: Die Bahnhofs-Schließfächer

Stell dir nun eine lange Reihe von Schließfächern am Bahnhof vor.

• Jedes Schließfach ist exakt gleich groß. Du kannst also nur Dinge desselben Typs hineinlegen (zum Beispiel nur Rucksäcke).
• Die Anzahl der Schließfächer ist fest in die Wand gemauert. Wenn der Bahnhof gebaut wird, steht fest: Es gibt genau 5 Fächer. Du kannst nicht spontan ein sechstes Fach anbauen, ohne den Bahnhof umzubauen.

Das ist ein Array (auf Deutsch manchmal auch Feld genannt) in Rust. Es speichert eine feste Anzahl von Elementen, die alle den gleichen Datentyp haben müssen.

Wie programmieren wir ein Array?

fn main() {
    // Wir erstellen eine Reihe von 5 Schließfächern, in denen wir die Temperaturen der letzten Tage speichern.
    // Der Typ des Arrays wird als [Typ; Anzahl] geschrieben: hier [i32; 5]
    let temperaturen: [i32; 5] = [12, 15, 14, 18, 16];

    // Wir greifen auf das erste Schließfach (Index 0) zu:
    let montag = temperaturen[0];
    println!("Die Temperatur am Montag war: {}°C", montag);

    // Wir können die Werte auch in einer Schleife durchlaufen:
    for temp in temperaturen {
        println!("Gemessene Temperatur: {}°C", temp);
    }
}

Was passiert, wenn wir einen Fehler machen? (Compilerfehler & Abstürze)

Da Rust extrem auf Sicherheit bedacht ist, passt es gut auf unsere Schließfächer auf. Schauen wir uns an, was passiert, wenn wir versuchen, auf ein Fach zuzugreifen, das es gar nicht gibt!

Stell dir vor, du schreibst folgenden Code:

fn main() {
    let temperaturen = [12, 15, 14, 18, 16]; // Ein Array mit 5 Elementen (Index 0 bis 4)
    
    // Wir versuchen, auf das Schließfach mit Index 5 zuzugreifen (das wäre das 6. Fach!):
    let kaputt = temperaturen[5]; 
    println!("{}", kaputt);
}

Wenn du diesen Code kompilieren möchtest, schlägt Rust sofort Alarm! Der Compiler merkt schon beim Übersetzen, dass hier etwas schief läuft:

error: this operation will panic at runtime
 --> src/main.rs:5:18
  |
5 |     let kaputt = temperaturen[5];
  |                  ^^^^^^^^^^^^^^^ index out of bounds: the length is 5 but the index is 5

Der Compiler schützt uns vor uns selbst! Er sagt: “Halt! Dein Schrank hat nur 5 Fächer. Du versuchst, auf das Fach mit der Nummer 5 (das sechste Fach) zuzugreifen. Das erlaube ich nicht!”

Aber Vorsicht: Wenn der Index nicht direkt als feste Zahl im Code steht (sondern zum Beispiel vom Benutzer eingegeben wird), kann der Compiler das nicht im Voraus prüfen. In diesem Fall stürzt das Programm zur Laufzeit mit einer sogenannten Panic ab. Das wollen wir natürlich vermeiden. Wie das geht, lernen wir gleich beim Vektor!

3. Der Vektor (Vec\<T\>): Die magische, ausziehbare Schublade

Arrays sind toll, wenn man genau weiß, wie viele Elemente man hat (z. B. die 12 Monate des Jahres). Aber im echten Leben wissen wir das oft nicht. Wie viele Artikel legt ein Kunde in seinen Einkaufswagen? Wie viele Gegner tauchen im Spiel auf?

Für solche Fälle gibt es den Vektor (Vec\<T\>).

Stell dir eine magische Kommoden-Schublade vor. Sie hat anfangs vielleicht Platz für drei Paar Socken. Sobald du aber ein viertes Paar Socken hineinlegst, dehnt sich die Schublade wie von Zauberhand aus! Sie wächst dynamisch mit deinen Anforderungen. Genau wie beim Array müssen aber auch im Vektor alle Elemente vom gleichen Typ sein (zum Beispiel nur Socken bzw. nur i32 Zahlen).

Kernoperationen eines Vektors

Wir können Elemente hinzufügen (push), vom Ende wegschmeißen (pop) oder sicher auslesen (get).

Schauen wir uns das in Aktion an:

fn main() {
    // 1. Einen neuen, leeren Vektor erstellen. 
    // Wir müssen die Variable "mut" (veränderbar) machen, da wir später Dinge hinzufügen!
    let mut einkaufsliste: Vec<&str> = Vec::new();

    // Alternativ können wir einen Vektor direkt mit Startwerten über das vec!-Makro erstellen:
    // let mut einkaufsliste = vec!["Äpfel", "Brot"];

    // 2. Elemente am Ende hinzufügen mit .push()
    einkaufsliste.push("Äpfel");
    einkaufsliste.push("Brot");
    einkaufsliste.push("Käse");

    println!("Meine Einkaufsliste nach dem Hinzufügen: {:?}", einkaufsliste);

    // 3. Das letzte Element wieder entfernen mit .pop()
    // .pop() gibt uns das Element zurück, falls eines da war.
    let gelöscht = einkaufsliste.pop(); 
    println!("Ich habe das letzte Element gelöscht: {:?}", gelöscht);
    println!("Aktuelle Liste: {:?}", einkaufsliste);
}

Der sichere Zugriff mit .get() (Absturzsicherung)

Erinnerst du dich an den Absturz beim Array, als wir auf ein nicht existierendes Fach zugegriffen haben? Bei Vektoren passiert das auch, wenn wir die eckigen Klammern benutzen (z. B. einkaufsliste[10]).

Um das zu verhindern, stellt uns Rust eine wunderbare Funktion zur Verfügung: .get().

Die Funktion .get() gibt uns nicht direkt das Element zurück, sondern verpackt es in einer Sicherheitsbox namens Option. Eine Option kann zwei Zustände haben:

• Some(&wert): Ja, das Element existiert und hier ist eine Referenz darauf!
• None: Nein, dieses Fach ist leer (Index existiert nicht).

Das zwingt uns als Programmierer dazu, den Fall einzubalkulieren, dass das Element vielleicht gar nicht existiert. Das Programm stürzt dadurch niemals unvorhergesehen ab!

Hier ist das Beispiel, wie man das in der Praxis macht:

fn main() {
    let einkaufsliste = vec!["Äpfel", "Brot"];

    // Wir fragen nach dem Fach mit Index 1 (das zweite Element: "Brot")
    // und nach dem Fach mit Index 10 (das gibt es nicht!).
    let index_erlaubt = 1;
    let index_zu_gross = 10;

    // Wir testen beide Zugriffe mit .get()
    for index in [index_erlaubt, index_zu_gross] {
        match einkaufsliste.get(index) {
            Some(artikel) => {
                println!("Erfolg! An Index {} steht: {}", index, artikel);
            }
            None => {
                println!("Fehler! An Index {} gibt es keinen Eintrag.", index);
            }
        }
    }
}

Warum ist das genial?

Durch die Struktur von Option können wir mit einem match-Block sauber entscheiden, was passieren soll. Wenn der Benutzer nach einem ungültigen Index sucht, zeigen wir ihm einfach eine nette Fehlermeldung, statt dass das gesamte Programm mit einem lauten Knall (Panic) abstürzt!

4. Der Slice: Der Suchscheinwerfer auf eine Häuserzeile

Manchmal möchtest du nicht die ganze Liste an eine andere Funktion übergeben oder kopieren, sondern nur einen kleinen Ausschnitt davon betrachten.

Stell dir eine lange Häuserzeile vor. Ein Slice (auf Deutsch Ausschnitt oder Scheibe) ist wie ein Suchscheinwerfer, den du auf einen Teil dieser Häuserzeile richtest.

• Du kopierst die Häuser nicht (das wäre viel zu schwer und würde zu viel Speicherplatz verbrauchen).
• Du schaust dir einfach nur einen bestimmten Ausschnitt an (zum Beispiel von Haus 2 bis Haus 4).
• Ein Slice ist immer eine Referenz (gekennzeichnet durch das &-Zeichen), da es sich die Daten nur ausleiht.

Wie sieht ein Slice im Code aus?

fn main() {
    // Ein Vektor mit 6 Zahlen
    let zahlen = vec![10, 20, 30, 40, 50, 60];

    // Wir erstellen einen Slice, der die Elemente von Index 1 bis vor Index 4 anleuchtet.
    // Das heißt: Index 1, 2 und 3 (20, 30, 40).
    // Schreibweise: &vektor[start..ende_exklusive]
    let ausschnitt: &[i32] = &zahlen[1..4];

    println!("Der gesamte Vektor: {:?}", zahlen);
    println!("Der angeleuchtete Ausschnitt (Slice): {:?}", ausschnitt);
    
    // Wir können auf den Slice zugreifen wie auf ein Array:
    println!("Das erste Element im Ausschnitt ist: {}", ausschnitt[0]); // Gibt 20 aus
}

Der Borrow-Checker passt auf! (Deep Dive)

Weil ein Slice eine Referenz (eine Ausleihe) auf die Originaldaten ist, passt der Rust Borrow Checker extrem gut auf uns auf. Er sorgt dafür, dass sich die Daten unter unserem Suchscheinwerfer nicht plötzlich verändern!

Stell dir vor, du hast einen Ausschnitt (Slice) ausgeliehen und versuchst dann, den Vektor zu verändern:

fn main() {
    let mut zahlen = vec![10, 20, 30];
    
    // Wir leihen uns einen Slice aus
    let ausschnitt = &zahlen[0..2]; 
    
    // Jetzt versuchen wir, ein neues Element an den Vektor anzuhängen!
    zahlen.push(40); 
    
    // Und hier wollen wir den Slice benutzen
    println!("Ausschnitt: {:?}", ausschnitt);
}

Wenn du versuchst, das auszuführen, wird dir der Compiler wütend auf die Finger klopfen:

error[E0502]: cannot borrow `zahlen` as mutable because it is also borrowed as immutable
 --> src/main.rs:8:5
  |
5 |     let ausschnitt = &zahlen[0..2]; // Hier wird 'zahlen' unveränderbar ausgeliehen
  |                       ------ immutable borrow occurs here
6 |     
7 |     // Jetzt versuchen wir, den Vektor zu verändern
8 |     zahlen.push(40); // Fehler! Hier versuchen wir eine veränderbare Ausleihe
  |     ^^^^^^^^^^^^^^^ mutable borrow occurs here
9 |     
10|     println!("Ausschnitt: {:?}", ausschnitt); // Hier wird die unveränderbare Ausleihe noch gebraucht
  |                                  ---------- immutable borrow later used here

Warum macht Rust das? Wenn ein Vektor wächst (durch .push()), kann es sein, dass im Arbeitsspeicher des Computers kein Platz mehr direkt hinter dem Vektor frei ist. Rust muss dann den gesamten Vektor an einen anderen Ort im Speicher umziehen lassen. Wenn das passiert, würde unser ausschnitt plötzlich auf eine alte Speicheradresse zeigen, wo gar keine Daten mehr liegen! Das nennt man einen Dangling Pointer (einen Zeiger ins Nichts). In C oder C++ führt so etwas zu fiesen Sicherheitslücken oder Abstürzen. Rust verhindert das komplett, indem es das Programm gar nicht erst kompiliert!

5. Die HashMap: Das Telefonbuch

Bisher haben wir unsere Elemente immer über eine Zahl (den Index 0, 1, 2...) gesucht. Aber was ist, wenn du die Telefonnummer von “Anna” suchst? Du willst nicht wissen, ob Anna an Stelle 5 steht, sondern du willst direkt nach dem Namen “Anna” suchen!

Dafür gibt es die HashMap (oft auch als Assoziatives Array oder Dictionary bezeichnet).

Stell dir ein klassisches Telefonbuch vor. Zu jedem eindeutigen Schlüssel (Key, z. B. Name “Anna”) gehört genau ein Wert (Value, z. B. Telefonnummer 12345).

• Der Schlüssel muss einzigartig sein (es kann im Telefonbuch nur einen Eintrag für “Anna Müller” geben, sonst weiß das Buch nicht, welche Nummer gemeint ist).
• Die HashMap ordnet die Elemente intern so an, dass sie extrem schnell gefunden werden – egal wie viele Millionen Einträge im Buch stehen!

Die geniale Entry-API: Der Einkaufswagen

Eine der häufigsten Aufgaben beim Programmieren ist das Zählen von Dingen. Zum Beispiel: Wir haben einen Einkaufswagen und möchten zählen, wie oft ein bestimmtes Produkt hineingelegt wurde.

Wenn wir das Produkt zum ersten Mal sehen, müssen wir es in der HashMap eintragen (mit dem Zählerwert 1). Wenn wir es schon einmal gesehen haben, wollen wir den Zähler um 1 erhöhen.

In vielen Programmiersprachen muss man dafür viel Code schreiben: Prüfen, ob der Schlüssel existiert, wenn nein einfügen, wenn ja auslesen, erhöhen, neu speichern. In Rust gibt es dafür die Entry-API, die das mit einer einzigen, wunderschönen Zeile erledigt:

#![allow(unused)]
fn main() {
map.entry(schluessel).or_insert(0);
}

Schauen wir uns ein vollständiges, gut kommentiertes Code-Beispiel an:

// Wichtig: Die HashMap gehört nicht zum Standard-Sprachumfang, der immer geladen ist.
// Wir müssen sie aus der Standardbibliothek importieren!
use std::collections::HashMap;

fn main() {
    // Wir erstellen eine neue, leere HashMap für unseren Einkaufswagen.
    // Der Schlüssel (Key) ist der Name des Produkts (&str).
    // Der Wert (Value) ist die Anzahl (i32).
    let mut einkaufswagen: HashMap<&str, i32> = HashMap::new();

    // Wir simulieren das Scannen von Produkten an der Kasse.
    // Diese Produkte landen nacheinander in unserem Wagen:
    let gescannte_produkte = vec![
        "Apfel", 
        "Banane", 
        "Apfel", 
        "Brot", 
        "Apfel", 
        "Banane"
    ];

    // Wir gehen jedes Produkt in einer Schleife durch
    for produkt in gescannte_produkte {
        // HIER PASSIERT DIE MAGIE:
        // 1. .entry(produkt) schaut nach, ob das Produkt bereits in der HashMap existiert.
        // 2. .or_insert(0) sagt: "Wenn das Produkt noch nicht da ist, trage es mit dem Wert 0 ein."
        //    Diese Funktion gibt uns eine veränderbare Referenz (&mut) auf den Wert in der HashMap zurück!
        // 3. Mit dem Sternchen * (Dereferenzierung) greifen wir auf die Zahl dahinter zu und erhöhen sie um 1.
        let anzahl_referenz = einkaufswagen.entry(produkt).or_insert(0);
        *anzahl_referenz += 1;
    }

    // Wir geben das Endergebnis aus
    println!("--- Kassenbon ---");
    for (produkt, anzahl) in &einkaufswagen {
        println!("{}: {}x", produkt, anzahl);
    }
}

Zeile für Zeile erklärt:

• use std::collections::HashMap;: Hiermit sagen wir Rust, dass wir die HashMap benutzen möchten. Sie liegt im Modul collections der Standardbibliothek (std).
• let mut einkaufswagen: HashMap<&str, i32> = HashMap::new();: Wir erstellen die leere HashMap. Die Typen in den spitzen Klammern <Key, Value> sagen Rust, dass wir Text als Schlüssel und ganze Zahlen als Werte nutzen.
• einkaufswagen.entry(produkt): Diese Methode sucht den Eintrag für das Produkt. Sie gibt uns eine Struktur vom Typ Entry zurück. Dieser Entry weiß, ob der Schlüssel existiert oder nicht.
• .or_insert(0): Das ist die wichtigste Methode auf dem Entry. Wenn der Schlüssel existiert, tut sie nichts und gibt uns einfach den aktuellen Wert. Wenn der Schlüssel nicht existiert, fügt sie ihn mit dem Wert 0 ein. Am Ende bekommen wir eine veränderbare Referenz (&mut i32) auf den Speicherplatz in der HashMap, wo die Zahl liegt.
• *anzahl_referenz += 1;: Weil anzahl_referenz eine Referenz (ein Wegweiser) auf die Zahl in der HashMap ist, müssen wir das Sternchen * benutzen, um dem Wegweiser zu folgen und die echte Zahl im Speicher zu verändern (zu dereferenzieren). Wir addieren 1 hinzu. Beim nächsten Schleifendurchlauf für dasselbe Produkt ist der Wert also bereits um 1 höher!

Zusammenfassung: Welcher Ordnungshelfer für welche Aufgabe?

Damit du nie wieder den Überblick verlierst, ist hier ein schnelles Spickzettel-Cheat-Sheet:

Herzlichen Glückwunsch! Du hast nun die wichtigsten Collections in Rust verstanden. Mit diesem Wissen kannst du bereits komplexe Programme schreiben, die große Mengen an Daten verwalten und verarbeiten.

Im nächsten Schritt kannst du dieses Wissen in den Übungen festigen!

Fortgeschrittene Collections: Architektur, CPU-Caches & Performance-Optimierung

Willkommen im Profi-Abschnitt von Kapitel 6. In der alltäglichen Rust-Programmierung greift man intuitiv zu Vec für Sequenzen und zu HashMap für Schlüssel-Wert-Paare. Für viele Anwendungsfälle ist das völlig ausreichend. Wenn Sie jedoch hochperformante Systeme, Spiele-Engines, Compiler oder speichersensitive Netzwerkdienste entwickeln, müssen Sie die Mechanik unter der Haube verstehen.

In diesem Abschnitt betrachten wir die Standard-Collections aus der Perspektive der Hardware, des Compilers und des API-Designs. Wir strukturieren diesen Abschnitt in konkrete, praxisrelevante Empfehlungen (Items), die Ihnen helfen, fundierte architektonische Entscheidungen zu treffen.

Item 11: Wähle die passende Datenstruktur basierend auf Komplexität und CPU-Cache-Verhalten

Ein weit verbreiteter Irrglaube in der Softwareentwicklung ist, dass die Wahl einer Datenstruktur ausschließlich anhand ihrer asymptotischen Laufzeitkomplexität (der O-Notation wie $O(1)$ oder $O(\log n)$) erfolgen sollte. In der Realität moderner Hardware-Architekturen spielt das CPU-Cache-Verhalten eine oft dominierende Rolle. Eine theoretisch langsame Operation auf einer cache-lokalen Datenstruktur kann eine theoretisch schnelle Operation auf einer cache-unfreundlichen Struktur um ein Vielfaches schlagen.

1. Didaktische Alltagsanalogie: Der geordnete Aktenordner vs. Die Zettelwirtschaft im Haus

Um den Unterschied zwischen cache-freundlichen und cache-unfreundlichen Strukturen zu verstehen, stellen wir uns folgendes Szenario vor: Sie müssen ein Rezept mit 10 Schritten kochen.

• Der Vektor (Vec\<T\>) – Der geordnete Aktenordner: Alle Schritte des Rezepts stehen direkt nacheinander auf einer einzigen Seite in einem Aktenordner, der vor Ihnen auf dem Küchentisch liegt. Da der Küchentisch Ihr CPU-Cache ist, haben Sie das gesamte Blatt sofort im Blickfeld. Um von Schritt 1 zu Schritt 2 zu gelangen, müssen Sie lediglich Ihren Blick um eine Zeile senken. Das geht extrem schnell, da keine physische Bewegung im Raum erforderlich ist.
• Die verkettete Liste (LinkedList\<T\>) – Die Zettelwirtschaft im Haus: Jeder einzelne Kochschritt steht auf einem separaten Zettel. Auf Zettel 1 (auf dem Küchentisch) steht: “Schneide die Zwiebeln. Der nächste Zettel befindet sich im Keller hinter der Waschmaschine.” Sie laufen in den Keller (Hauptspeicher-Zugriff / RAM). Auf Zettel 2 steht: “Bratsch die Zwiebeln an. Der nächste Zettel liegt auf dem Dachboden im alten Koffer.” Sie laufen auf den Dachboden. Das nennt man in der Informatik Zeigerjagen (Pointer Chasing). Obwohl Sie auch hier nur 10 Schritte ausführen, verbringen Sie 99 % Ihrer Zeit mit dem Laufen durch das Haus (Warten auf den RAM), anstatt mit dem Kochen (Rechnen der CPU).

2. Theorie & Konzepte: Cache-Lines und Speicherlokalität

Moderne CPUs arbeiten nicht direkt auf dem Hauptspeicher (RAM). Der Zugriff auf den RAM ist im Vergleich zur Taktfrequenz der CPU extrem langsam (ca. 50–100 Nanosekunden gegenüber weniger als 0,5 Nanosekunden für einen CPU-Zyklus). Um diese Lücke zu schließen, besitzen CPUs hierarchische Caches (L1, L2, L3).

Wenn die CPU ein bestimmtes Byte aus dem Hauptspeicher anfordert, lädt sie nicht nur dieses eine Byte, sondern einen ganzen Block von typischerweise 64 Bytes – eine sogenannte Cache-Line.

• Räumliche Lokalität (Spatial Locality): Wenn ein Programm auf eine Speicheradresse zugreift, ist die Wahrscheinlichkeit hoch, dass es bald auf benachbarte Speicheradressen zugreift.
• Vec<T>: Garantiert, dass alle Elemente in einem einzigen, kontinuierlichen Speicherbereich im Heap liegen. Greifen Sie auf vec[0] zu, lädt die CPU die gesamte Cache-Line (die je nach Elementgröße auch vec[1], vec[2] etc. enthält). Der Zugriff auf die Folgeelemente ist somit ein “Cache-Hit” (L1/L2-Zugriff) und geschieht nahezu verzögerungsfrei.
• LinkedList<T>: Jedes Element (Knoten) wird einzeln auf dem Heap allokiert. Diese Knoten können kreuz und quer im RAM verstreut sein. Jeder Schritt zum nächsten Element (node.next) erfordert das Verfolgen eines Zeigers auf eine neue, unvorhersehbare Speicheradresse. Dies führt fast immer zu einem Cache-Miss, wodurch die CPU untätig auf den RAM warten muss. Nutzen Sie LinkedList in Rust daher fast nie.

Die wichtigsten Standard-Collections im Vergleich:

3. Compilerfehler verstehen & reparieren

Ein häufiger Fehler bei Einsteigern beim Umgang mit sequentiellen Collections ist der Versuch, Elemente über einen Index direkt zu konsumieren (Ownership zu verschieben), während die Collection noch die Ownership hält.

Fehlerhafter Code:

struct Benutzer {
    name: String,
    aktiv: bool,
}

fn verarbeite_ersten_benutzer(benutzer_liste: Vec<Benutzer>) {
    // FEHLER: Wir versuchen, die Ownership aus dem Vektor herauszubewegen!
    let erster = benutzer_liste[0]; 
    println!("Verarbeite: {}", erster.name);
}

fn main() {
    let liste = vec![
        Benutzer { name: String::from("Anna"), aktiv: true },
        Benutzer { name: String::from("Ben"), aktiv: false },
    ];
    verarbeite_ersten_benutzer(liste);
}

Compiler-Fehlermeldung:

error[E0507]: cannot move out of index of `Vec<Benutzer>`
  --> src/main.rs:8:19
   |
8  |     let erster = benutzer_liste[0]; 
   |                  ^^^^^^^^^^^^^^^^^
   |                  |
   |                  move occurs because value has type `Benutzer`, which does not implement the `Copy` trait
   |                  help: consider borrowing here: `&benutzer_liste[0]`

Warum lehnt der Compiler das ab?

Der Vektor benutzer_liste besitzt seine Elemente. Wenn wir let erster = benutzer_liste[0] schreiben, versuchen wir, das Element an Index 0 aus dem Vektor herauszubewegen. Das würde den Vektor in einem ungültigen Zustand hinterlassen, da Rust verlangt, dass alle Plätze in einem Vektor mit gültigen Werten belegt sind. Da Benutzer einen String enthält, implementiert es nicht das Copy-Trait.

Die Reparatur:

Wir haben drei Möglichkeiten, je nachdem, was wir architektonisch erreichen wollen:

1. Ausleihen (Borrowing), wenn wir die Liste danach noch verwenden wollen: let erster = &benutzer_liste[0];
2. Entfernen (Entnehmen der Ownership), wenn wir das Element aus der Liste löschen wollen: let erster = benutzer_liste.remove(0); (Achtung: Verschiebt alle nachfolgenden Elemente, $O(n)$!).
3. Austauschen (Inplace Swap) für $O(1)$ Entnahme, wenn die Reihenfolge egal ist: let erster = benutzer_liste.swap_remove(0); (Ersetzt das erste Element mit dem letzten und gibt das erste zurück).

4. Vollständiges, kompilierbares Praxisbeispiel: Job-Queue mit VecDeque

Das folgende Beispiel demonstriert eine effiziente Implementierung einer Job-Warteschlange (FIFO). Wir nutzen VecDeque, um das ineffiziente Verschieben von Elementen zu vermeiden, das bei einem normalen Vec beim Entfernen am Anfang auftreten würde.

use std::collections::VecDeque;

#[derive(Debug)]
struct Job {
    id: u64,
    beschreibung: String,
}

struct JobQueue {
    jobs: VecDeque<Job>,
}

impl JobQueue {
    fn new() -> Self {
        JobQueue {
            jobs: VecDeque::new(),
        }
    }

    // Einen neuen Job hinten anfügen - O(1)
    fn job_hinzufuegen(&mut self, job: Job) {
        self.jobs.push_back(job);
    }

    // Den ältesten Job vorne entnehmen - O(1)
    fn naechsten_job_holen(&mut self) -> Option<Job> {
        self.jobs.pop_front()
    }

    fn verbleibende_jobs(&self) -> usize {
        self.jobs.len()
    }
}

fn main() {
    let mut warteschlange = JobQueue::new();

    // Jobs einreihen
    warteschlange.job_hinzufuegen(Job {
        id: 1,
        beschreibung: String::from("Datenbank-Backup erstellen"),
    });
    warteschlange.job_hinzufuegen(Job {
        id: 2,
        beschreibung: String::from("Cache leeren"),
    });

    println!("Warteschlange enthält {} Jobs.", warteschlange.verbleibende_jobs());

    // Jobs abarbeiten
    while let Some(job) = warteschlange.naechsten_job_holen() {
        println!("Verarbeite Job {}: {}", job.id, job.beschreibung);
    }

    println!("Warteschlange leer. Verbleibend: {}", warteschlange.verbleibende_jobs());
}

Item 12: Nutze die Entry-API zur Eliminierung redundanter Map-Lookups

Wenn Sie mit einer HashMap oder BTreeMap arbeiten, müssen Sie häufig prüfen, ob ein Schlüssel bereits existiert, um den Wert entweder zu aktualisieren oder einen neuen Standardwert einzufügen. Ein naiver Ansatz führt zu doppelten Suchoperationen im Baum oder in der Hash-Tabelle. Die Entry-API löst dieses Problem auf elegante und hocheffiziente Weise.

1. Didaktische Alltagsanalogie: Der Postbote und das Paketfach

Stell dir vor, ein Postbote möchte ein Paket in ein elektronisches Schließfach legen.

• Ohne Entry-API (Der umständliche Weg):
  1. Der Postbote geht zum Schließfach 42 und schaut nach, ob es belegt ist (1. Lookup).
  2. Er sieht: Das Schließfach ist leer.
  3. Er läuft zurück zu seinem Lieferwagen (Rückgabe der Kontrolle an den aufrufenden Code).
  4. Er holt das Paket, läuft wieder zu Schließfach 42, tippt die Nummer erneut ein, öffnet es und legt das Paket hinein (2. Lookup). Dieser doppelte Weg kostet unnötig viel Zeit.
• Mit Entry-API (Der effiziente Weg):
  1. Der Postbote geht direkt zu Schließfach 42 (Einziger Lookup).
  2. Er öffnet die Tür. Ist das Fach leer (Vacant), legt er das Paket hinein. Ist es belegt (Occupied), klebt er einen Hinweiszettel auf das vorhandene Paket. Er muss den Weg kein zweites Mal laufen.

2. Theorie & Konzepte: Das Entry-Enum

Die Methode map.entry(key) gibt ein Enum namens std::collections::hash_map::Entry zurück. Dieses repräsentiert eine Stelle in der Map, die entweder belegt oder frei ist:

#![allow(unused)]
fn main() {
pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}
}

Da die Methode entry eine exklusive Referenz (&mut) auf die Map benötigt, sichert sie den Speicherplatz intern ab. Der Compiler weiß nach dem Aufruf von entry genau, an welcher Speicheradresse der Schlüssel liegt. Wenn wir nun eine Modifikation vornehmen, muss die Map nicht erneut nach dem Schlüssel suchen.

Die wichtigsten Methoden auf Entry:

• .or_insert(default): Fügt den Standardwert ein, falls der Eintrag leer ist, und gibt eine veränderbare Referenz (&mut V) auf den Wert zurück.
• .or_insert_with(|| default): Wie or_insert, wertet den Standardwert aber träge (lazy) über ein Closure aus. Perfekt, wenn die Erstellung des Standardwerts teuer ist (z.B. bei Heap-Allokationen).
• .and_modify(|val| *val += 1): Erlaubt das direkte Modifizieren des Werts, falls der Eintrag existiert.

3. Code-Vergleich: Wortzähler (Naiv vs. Entry-API)

Der naive (ineffiziente) Ansatz:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn wort_zaehler_naiv(text: &str) -> HashMap<&str, usize> {
    let mut stats = HashMap::new();

    for wort in text.split_whitespace() {
        // 1. Lookup: contains_key berechnet den Hash und sucht das Bucket
        if stats.contains_key(wort) {
            // 2. Lookup: get_mut berechnet den Hash erneut und sucht das Bucket
            if let Some(counter) = stats.get_mut(wort) {
                *counter += 1;
            }
        } else {
            // 2. Lookup: insert berechnet den Hash erneut und sucht das Bucket
            stats.insert(wort, 1);
        }
    }
    stats
}
}

Problem: Für jedes Wort in einem Text führen wir mindestens zwei vollständige Suchoperationen in der Hash-Tabelle durch. Bei großen Maps und langen Keys (wie Strings) führt das zu spürbaren Performance-Einbußen.

Der professionelle (idiomatische) Ansatz mit Entry-API:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn wort_zaehler_entry(text: &str) -> HashMap<&str, usize> {
    let mut stats = HashMap::new();

    for wort in text.split_whitespace() {
        // Ein einziger Lookup!
        // or_insert gibt eine veränderbare Referenz &mut usize auf den Wert zurück.
        // Diese dereferenzieren wir mit '*', um den Wert zu erhöhen.
        *stats.entry(wort).or_insert(0) += 1;
    }
    stats
}
}

Erklärung: stats.entry(wort) sucht das Wort genau einmal in der Map. Ist das Wort nicht vorhanden, wird 0 eingefügt. In beiden Fällen erhalten wir ein &mut usize auf den Zähler im Speicher, den wir über den Dereferenzierungs-Operator * direkt im Speicher inkrementieren können. Das ist nicht nur kürzer, sondern auch maximal effizient.

Item 13: Eigene Typen als Map-Schlüssel: Implementierung von Hash, Eq und PartialEq

Um einen eigenen Typen als Schlüssel (Key) in einer HashMap zu verwenden, verlangt Rust, dass der Typ drei Traits implementiert: PartialEq, Eq und Hash. Während dies meist einfach über #[derive(PartialEq, Eq, Hash)] gelöst werden kann, erfordern komplexere Architekturen oft eine manuelle Implementierung dieser Schnittstellen.

1. Didaktische Alltagsanalogie: Das Aktenarchiv nach PLZ und Nachnamen

Stell dir vor, du sortierst Kundenakten in einem großen Hängeregister.

1. Der Hashwert (Der Postleitzahlen-Karton): Du nimmst die Adresse des Kunden und berechnest eine Kennzahl – zum Beispiel die Postleitzahl. Du legst die Akte in den Karton für diese PLZ. Das ist die Hash-Funktion. Sie sagt dir grob, in welchem “Eimer” (Bucket) die Akte liegt.
2. Die Gleichheit (Der Ausweisabgleich): Wenn du nach einem Kunden suchst, gehst du direkt zum Karton für seine PLZ (Hash-Lookup). Im Karton liegen aber 50 verschiedene Akten. Jetzt nimmst du jede Akte in die Hand und vergleichst den exakten Vor- und Nachnamen mit deinem Suchauftrag. Das ist die Gleichheitsprüfung (Eq).

Die goldene Regel der Konsistenz: Zwei Akten von Personen, die laut Ausweis absolut identisch sind (Eq), müssen zwingend dieselbe PLZ aufweisen (denselben Hashwert haben). Wenn Person A und Person B identisch sind, aber du A in den Karton 10000 und B in den Karton 20000 legst, wirst du Person B niemals finden, wenn du im Karton 10000 suchst.

2. Theorie & Konzepte: Das Zusammenspiel der Traits

• PartialEq<Rhs>: Definiert die partielle Äquivalenzrelation. Sie erfordert Symmetrie (wenn a == b, dann b == a) und Transitivität (wenn a == b und b == c, dann a == c).
• Eq: Ein reines Marker-Trait, das die mathematische Reflexivität zusichert (a == a muss immer wahr sein). Gleitkommazahlen (f32/f64) implementieren beispielsweise PartialEq, aber nicht Eq, da in der IEEE-754 Spezifikation definiert ist, dass NaN != NaN (Not a Number) gilt.
• Hash: Nimmt eine Instanz eines Hasher-Typs entgegen und speist die relevanten Daten des Structs in diesen ein.

Kritische Entwickler-Regel:

Important

Wenn Sie PartialEq manuell implementieren, müssen Sie auch Hash manuell implementieren. Es muss ausnahmslos gelten: if a == b { hash(a) == hash(b) } Ist diese Bedingung verletzt, verhält sich die HashMap fehlerhaft (Elemente können trotz Vorhandenseins nicht gefunden werden).

3. Compilerfehler verstehen & reparieren

Versuchen wir, ein Struct ohne diese Traits als Schlüssel zu verwenden, blockiert uns der Compiler sofort schützend.

Fehlerhafter Code:

use std::collections::HashMap;

struct BenutzerId {
    abteilung: String,
    personal_nummer: u32,
}

fn main() {
    let mut daten = HashMap::new();
    let key = BenutzerId {
        abteilung: String::from("IT"),
        personal_nummer: 1024,
    };
    
    // FEHLER: BenutzerId erfüllt die Anforderungen für Keys nicht!
    daten.insert(key, String::from("Thorsten"));
}

Compiler-Fehlermeldung:

error[E0277]: the trait bound `BenutzerId: Eq` is not satisfied
   --> src/main.rs:15:18
    |
15  |     daten.insert(key, String::from("Thorsten"));
    |           ------ ^^^ the trait `Eq` is not implemented for `BenutzerId`
    |           |
    |           required by a bound introduced by this call

Der Compiler fordert uns auf, Eq (und implizit Hash und PartialEq) zu implementieren.

4. Vollständiges, kompilierbares Praxisbeispiel (Manuelle Implementierung)

Wir implementieren nun einen Schlüssel ProjektSchluessel, bei dem wir die Gleichheit und das Hashing manuell definieren. Im echten Leben könnte das nötig sein, wenn wir beim Vergleich der Abteilung Groß- und Kleinschreibung ignorieren wollen (Case-Insensitivity).

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct ProjektSchluessel {
    abteilung: String,
    projekt_id: u32,
}

// Manuelle Implementierung von PartialEq: Case-Insensitiver Vergleich für abteilung
impl PartialEq for ProjektSchluessel {
    fn eq(&self, other: &Self) -> bool {
        self.projekt_id == other.projekt_id
            && self.abteilung.to_lowercase() == other.abteilung.to_lowercase()
    }
}

// Eq zusichern, da unsere eq-Implementierung reflexiv ist
impl Eq for ProjektSchluessel {}

// Manuelle Implementierung von Hash: 
// WICHTIG: Da wir in eq() die Abteilung zu Kleinbuchstaben konvertieren, 
// müssen wir das auch im Hasher tun, um die Konsistenz zu wahren!
impl Hash for ProjektSchluessel {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.projekt_id.hash(state);
        self.abteilung.to_lowercase().hash(state);
    }
}

fn main() {
    let mut projekte = HashMap::new();

    let key1 = ProjektSchluessel {
        abteilung: String::from("Marketing"),
        projekt_id: 42,
    };

    let key2 = ProjektSchluessel {
        abteilung: String::from("marketing"), // Unterschiedliche Schreibweise
        projekt_id: 42,
    };

    projekte.insert(key1, "Kampagne Sommer 2026");

    // Da key1 == key2 (dank case-insentivem PartialEq und konsistentem Hash),
    // liefert das Auslesen mit key2 den Wert von key1!
    if let Some(projektname) = projekte.get(&key2) {
        println!("Projekt gefunden: {}", projektname);
    } else {
        println!("Projekt wurde nicht gefunden!");
    }
}

Item 14: Optimiere Hashing-Performance mit nicht-kryptografischen Hashern

Standardmäßig verwendet Rusts HashMap einen Hashing-Algorithmus namens SipHash 1-3. Dieser Algorithmus wurde gezielt gewählt, weil er hochgradig resistent gegen sogenannte Hash-Flooding-DDoS-Angriffe (Denial of Service) ist. Für Webserver, die unbereinigte Benutzereingaben als Schlüssel in einer Map speichern, ist dies überlebenswichtig. In geschlossenen Systemen jedoch bremst SipHash die CPU unnötig aus.

1. Didaktische Alltagsanalogie: Das Panzerschloss am Küchenschrank

Stell dir vor, du möchtest deine Gewürze in der Küche sortieren.

• SipHash (Das Panzerschloss): Jedes Mal, wenn du Salz aus dem Schrank nehmen willst, musst du ein 10-stelliges Zahlenschloss an der Schranktür öffnen. Das Schloss ist absolut sicher gegen Profi-Einbrecher. Für deine Küche ist es jedoch massiver Overhead und bremst das Kochen extrem aus.
• FxHash / FnvHash (Der Magnetschnapper): Ein einfacher Magnetverschluss hält die Schranktür zu. Jeder kann sie mit einem leichten Ruck in Millisekunden öffnen. In deiner privaten Wohnung (ein geschlossenes System ohne bösartige Angreifer von außen) ist das die perfekte Wahl, weil es maximal schnell ist.

2. Theorie & Konzepte: DDoS-Sicherheit vs. Rohgeschwindigkeit

• Hash-Flooding: Wenn ein Angreifer weiß, dass eine HashMap einen simplen, deterministischen Hashing-Algorithmus nutzt, kann er tausende Schlüssel generieren, die alle exakt denselben Hashwert erzeugen. Dies führt in der Map zu maximalen Kollisionen, wodurch die Zugriffszeit von $O(1)$ auf $O(n)$ ansteigt. Die CPU-Last steigt auf 100 %, und der Server stürzt ab. SipHash verhindert dies durch die Verwendung eines kryptografisch sicheren Schlüssels, der bei jedem Programmstart zufällig generiert wird.
• Nicht-kryptografische Hasher: Algorithmen wie FNV-1a oder FxHash (welches intern im Rust-Compiler rustc genutzt wird) verzichten auf diese mathematischen Schutzbarrieren. Sie bestehen oft nur aus einer Handvoll einfacher CPU-Instruktionen (Multiplikation und XOR). Für interne Caches, Spiele, Compiler oder Datenanalyse-Tools sind sie der Schlüssel zu massiven Geschwindigkeitsvorteilen (oft 2- bis 5-mal schneller als SipHash).

3. Implementierung eines eigenen FNV-1a Hashers in Rust

Um zu verstehen, wie Hasher in Rust auf Systemebene integriert werden, implementieren wir einen eigenen FNV-1a (Fowler-Noll-Vo) Hasher für 64-Bit-Ganzzahlen komplett selbst. So vermeiden wir externe Abhängigkeiten und verstehen die Hasher- und BuildHasher-Traits der Standardbibliothek im Detail.

use std::collections::HashMap;
use std::hash::{BuildHasher, Hasher};

// 1. Der Hasher-Typ: Hält den aktuellen Hash-Zustand
struct Fnv64Hasher {
    state: u64,
}

impl Fnv64Hasher {
    // FNV-1a Konstanten für 64-Bit
    const FNV_PRIME: u64 = 0x00000100000001B3;
    const FNV_OFFSET_BASIS: u64 = 0xcbf29ce484222325;

    fn new() -> Self {
        Fnv64Hasher {
            state: Self::FNV_OFFSET_BASIS,
        }
    }
}

// Implementierung des Hasher-Traits: Beschreibt, wie Bytes verarbeitet werden
impl Hasher for Fnv64Hasher {
    // Gibt das Endergebnis des Hashings zurück
    fn finish(&self) -> u64 {
        self.state
    }

    // Kernmethode: Verarbeitet einen rohen Byte-Slice
    fn write(&mut self, bytes: &[u8]) {
        for &byte in bytes {
            // FNV-1a Algorithmus: Erst XOR, dann Multiplikation
            self.state ^= byte as u64;
            self.state = self.state.wrapping_mul(Self::FNV_PRIME);
        }
    }
}

// 2. Der BuildHasher-Typ: Erzeugt Instanzen unseres Hashers.
// Dies ist notwendig, da die HashMap für jede Operation einen frischen Hasher benötigt.
#[derive(Default)]
struct BuildFnvHasher;

impl BuildHasher for BuildFnvHasher {
    type Hasher = Fnv64Hasher;

    fn build_hasher(&self) -> Self::Hasher {
        Fnv64Hasher::new()
    }
}

fn main() {
    // 3. Einbinden in die HashMap über den dritten Typparameter.
    // Standardmäßig ist dies `RandomState` (SipHash). Wir setzen unseren `BuildFnvHasher` ein.
    let mut schnelle_map: HashMap<u32, String, BuildFnvHasher> = 
        HashMap::with_hasher(BuildFnvHasher);

    schnelle_map.insert(1, String::from("Hochleistungs-Daten"));
    schnelle_map.insert(2, String::from("Optimierter Speicher"));

    if let Some(wert) = schnelle_map.get(&1) {
        println!("Wert gelesen: {}", wert);
    }
}

Item 15: Heterogene Datensammlungen: Enums vs. Trait-Objekte

Rust-Collections wie Vec\<T\> sind homogen – sie können nur Elemente eines einzigen Typs T aufnehmen. In der Praxis benötigt man jedoch oft Sammlungen unterschiedlicher Typen (heterogene Collections), beispielsweise eine Liste von UI-Elementen (Buttons, Textfelder, Bilder). Rust bietet hierfür zwei grundlegende Lösungswege mit unterschiedlichen Trade-offs: Statische Polymorphie über Enums und Dynamische Polymorphie über Trait-Objekte.

1. Didaktische Alltagsanalogie: Der geformte Besteckkasten vs. Die Werkzeugtasche

• Das Enum – Der Besteckkasten (Statisch): Ein Besteckkasten hat vordefinierte Aussparungen für Messer, Gabeln und Löffel. Sie wissen im Voraus genau, welche drei Arten von Besteck es geben kann. Es passt kein Schraubenzieher hinein. Der Zugriff ist extrem schnell: Sie greifen blind in das Fach und haben sofort das richtige Besteckteil in der Hand. Der Speicherplatz ist starr, passt sich aber dem größten Besteckteil an.
• Das Trait-Objekt – Die Werkzeugtasche (Dynamisch): Eine Tasche, in die Sie alles hineinwerfen können, was das Label “Werkzeug” (das Trait) trägt. Sie können heute einen Hammer hineintun und morgen eine Bohrmaschine, die bei der Herstellung der Tasche noch gar nicht erfunden war. Wenn Sie jedoch hineingreifen, wissen Sie nicht blind, wie schwer oder groß das Werkzeug ist. Sie müssen es herausholen und die Bedienungsanleitung (Virtuelle Methodentabelle / vtable) lesen, um zu wissen, wie man es benutzt. Das ist flexibler, aber durch das Nachschlagen langsamer.

2. Theorie & Konzepte: Statische vs. Dynamische Polymorphie

Variante A: Statische Polymorphie (Enums)

• Funktionsweise: Alle möglichen Typen werden als Varianten in einem einzigen Enum gekapselt.
• Speicherlayout: Die Größe des Enums im Speicher entspricht der Größe seiner größten Variante plus einem kleinen Tag (Discriminant, meist 1 Byte), das angibt, welche Variante gerade aktiv ist.
• Vorteile:
  • Kein Speicherzugriff über Zeiger (keine Indirektion).
  • Exzellente CPU-Cache-Lokalität: Alle Elemente liegen direkt hintereinander im kontinuierlichen Speicher des Vektors.
  • Der Compiler kann den Code vollständig inlinen und optimieren (kein Laufzeit-Overhead).
• Nachteile:
  • Unflexibel: Das Enum ist geschlossen. Möchte eine externe Bibliothek einen neuen Typ hinzufügen, muss das Enum im Quellcode geändert werden.
  • Speicherverschwendung, wenn eine Variante extrem groß und alle anderen winzig sind, da jedes Element die Größe der größten Variante beansprucht.

Variante B: Dynamische Polymorphie (Trait-Objekte)

• Funktionsweise: Die Elemente implementieren ein gemeinsames Trait. Im Vektor speichern wir Zeiger auf diese Elemente, verpackt in Box<dyn Trait> oder &dyn Trait.
• Speicherlayout: Ein Trait-Objekt ist ein Fat Pointer. Er besteht aus zwei Zeigern: Einem Zeiger auf die eigentlichen Daten im Heap und einem Zeiger auf die vtable (virtuelle Methodentabelle), die die Funktionszeiger der konkreten Implementierung enthält.
• Vorteile:
  • Offenes System: Jeder beliebige Typ (auch aus Drittanbieter-Crates) kann in die Collection eingefügt werden, solange er das Trait implementiert.
  • Speichereffizient im Vektor selbst, da dort nur Zeiger gleicher Größe liegen.
• Nachteile:
  • Heap-Allokation pro Element erforderlich (Box).
  • Schlechte Cache-Lokalität durch Pointer-Chasing.
  • Dynamic Dispatch: Bei jedem Methodenaufruf muss die CPU über die vtable nachschlagen, welche Funktion aufgerufen werden soll. Dies verhindert Inlining und erschwert CPU-Branch-Prediction-Optimierungen.

3. Vollständiges, kompilierbares Praxisbeispiel: GUI-Rendering

Das folgende Beispiel zeigt beide Ansätze zur Speicherung einer Liste von GUI-Komponenten.

// Das Trait, das die gemeinsame Funktionalität definiert
trait Renderable {
    fn zeichnen(&self);
}

// Konkrete GUI-Komponente A
struct Button {
    text: String,
}

impl Renderable for Button {
    fn zeichnen(&self) {
        println!("[Button] Zeichne mit Text: {}", self.text);
    }
}

// Konkrete GUI-Komponente B
struct TextFeld {
    inhalt: String,
    breite: u32,
}

impl Renderable for TextFeld {
    fn zeichnen(&self) {
        println!("[TextFeld] Breite: {}, Inhalt: {}", self.breite, self.inhalt);
    }
}

// =========================================================================
// ANSATZ 1: Statische Polymorphie via Enum (Geschlossenes System, schnell)
// =========================================================================
enum GuiKomponenteEnum {
    Knopf(Button),
    Eingabe(TextFeld),
}

// Wir implementieren Renderable für das Enum, um das Zeichnen zu delegieren
impl Renderable for GuiKomponenteEnum {
    fn zeichnen(&self) {
        match self {
            GuiKomponenteEnum::Knopf(btn) => btn.zeichnen(),
            GuiKomponenteEnum::Eingabe(tf) => tf.zeichnen(),
        }
    }
}

// =========================================================================
// HIER FÜHREN WIR BEIDE ANSÄTZE ZUSAMMEN
// =========================================================================
fn main() {
    // --- Test von Ansatz 1 (Enum) ---
    // Speicherlayout: Ein kontinuierliches Array im Heap.
    // Keine Zeiger-Indirektionen beim Iterieren. Maximal performant.
    println!("--- Ansatz 1: Statische Polymorphie (Enum) ---");
    let mut enum_liste: Vec<GuiKomponenteEnum> = Vec::new();
    
    enum_liste.push(GuiKomponenteEnum::Knopf(Button {
        text: String::from("Senden"),
    }));
    enum_liste.push(GuiKomponenteEnum::Eingabe(TextFeld {
        inhalt: String::from("Thorsten"),
        breite: 250,
    }));

    for komponente in &enum_liste {
        // Aufruf über statischen Dispatch (wird vom Compiler optimiert)
        komponente.zeichnen();
    }

    // --- Test von Ansatz 2 (Trait-Objekt) ---
    // Speicherlayout: Ein Vektor von Fat Pointern im Heap.
    // Jedes Element liegt an einer anderen Heap-Stelle.
    println!("\n--- Ansatz 2: Dynamische Polymorphie (Trait-Objekt) ---");
    let mut trait_liste: Vec<Box<dyn Renderable>> = Vec::new();

    trait_liste.push(Box::new(Button {
        text: String::from("Abbrechen"),
    }));
    trait_liste.push(Box::new(TextFeld {
        inhalt: String::from("Suche..."),
        breite: 150,
    }));

    for komponente in &trait_liste {
        // Aufruf über Dynamic Dispatch (Nachschlagen in der vtable zur Laufzeit)
        komponente.zeichnen();
    }
}

Zusammenfassung für die Praxis:

• Wählen Sie Enums, wenn Sie die Menge der Typen kontrollieren können und die maximale Performance auf CPU-Ebene benötigen (Spiele, Parser, mathematische Berechnungen).
• Wählen Sie Trait-Objekte, wenn Sie ein Plugin-System bauen, bei dem andere Entwickler eigene Typen hinzufügen sollen, oder wenn die Größenunterschiede der Typen so groß sind, dass ein Enum zu viel Speicher verschwenden würde.

6.4 Unter der Haube: Collections auf Hardware- und Systemebene

Willkommen im Maschinenraum! In den vorherigen Abschnitten haben wir gelernt, wie wir Vektoren, Slices und HashMaps in unseren Rust-Programmen nutzen. Für Anwendungsentwickler reicht dieses Wissen meist völlig aus. Doch du bist hier, weil du wissen willst, was wirklich unter der Haube passiert. Du willst wissen, wie sich die Elektronen im RAM bewegen, warum manche Operationen deine CPU zum Schnurren bringen, während andere sie in eine gähnende Warteschleife schicken.

In diesem Abschnitt legen wir die Abstraktionen beiseite. Wir nehmen das Skalpell und sezieren das Speicherlayout unserer Datenstrukturen auf Byte-Ebene. Wir schauen uns an, wie moderne CPUs mit Speicher interagieren und warum die Wahl der richtigen Collection den Unterschied zwischen einer trägen Schnecke und einer Rakete ausmachen kann.

1. Arrays: Die Formel 1 des Direktzugriffs

Fangen wir mit der fundamentalsten aller Collections an: dem Array (z. B. [T; N]). Arrays sind die reinsten und direktesten Datenstrukturen überhaupt. Sie spiegeln eins zu eins wider, wie physikalischer Arbeitsspeicher strukturiert ist.

Die Alltagsanalogie: Der Apothekerschrank

Stell dir einen Apothekerschrank mit 10 nebeneinander liegenden Schubladen vor. Jede Schublade ist exakt gleich breit – sagen wir 10 Zentimeter. Wenn du die 5. Schublade öffnen willst, musst du nicht bei Schublade 0 anfangen und dich mühsam vorwärtstasten. Da du weißt, dass jede Schublade 10 Zentimeter breit ist und der Schrank an einer festen Wand beginnt, kannst du im Bruchteil einer Sekunde ausrechnen, wo sich der Griff der 5. Schublade befindet: $5 \times 10\text{ cm} = 50\text{ cm}$ von der Wand entfernt. Du greifst direkt dorthin. Das ist der Direktzugriff.

Das Speicherlayout im Detail

In Rust hat ein Array [T; N] eine feste Länge N, die bereits zur Kompilierzeit feststehen muss. Das erlaubt es dem Compiler, das Array komplett auf dem Stack (oder als Teil einer größeren Struktur auf dem Heap) anzulegen. Die Elemente liegen lückenlos und fortlaufend hintereinander im Speicher.

Nehmen wir ein einfaches Array von fünf 32-Bit-Ganzzahlen (i32):

#![allow(unused)]
fn main() {
let zahlen: [i32; 5] = [10, 20, 30, 40, 50];
}

Da ein i32 genau 4 Bytes belegt, sieht das Layout im Speicher so aus:

Adresse:    0x1000      0x1004      0x1008      0x100C      0x1010
            +-----------+-----------+-----------+-----------+-----------+
Inhalt:     |    10     |    20     |    30     |    40     |    50     |
            +-----------+-----------+-----------+-----------+-----------+
Index:            0           1           2           3           4
Größe:      |< 4 Bytes >|< 4 Bytes >|< 4 Bytes >|< 4 Bytes >|< 4 Bytes >|

Der O(1)-Zugriff auf CPU-Ebene: Die Adressberechnung

Warum sagen Informatiker stolz, dass der Zugriff auf ein Array-Element eine $O(1)$-Operation ist – also unabhängig von der Größe des Arrays immer gleich schnell is? Weil die CPU die genaue Speicheradresse des gewünschten Elements mit einer einzigen mathematischen Formel berechnen kann:

$$\text{Adresse}(i) = \text{Basisadresse} + i \times \text{Größe eines Elements}$$

• Basisadresse: Der Startpunkt des Arrays im Speicher (im obigen Beispiel 0x1000).
• $i$: Der gewünschte Index (z. B. 3).
• Größe eines Elements: Die Bytegröße des Typs T (im Fall von i32 also 4).

Für Index 3 rechnet die CPU: $$\text{Adresse}(3) = 0\text{x}1000 + 3 \times 4 = 0\text{x}1000 + 12 = 0\text{x}100\text{C}$$

Moderne CPUs (wie die x86_64-Architektur) sind für genau diese Berechnung im Silizium optimiert. Sie verfügen über spezielle Adressierungsmodi, die diese Multiplikation und Addition in einem einzigen Taktzyklus direkt im Befehlsdecoder ausführen. Ein Assembler-Befehl wie:

mov eax, [rbx + rcx * 4]

bedeutet: “Lade den Wert aus der Adresse Basisadresse (in rbx) + Index (in rcx) * Elementgröße (4) in das Register eax”. Schneller geht es physikalisch nicht.

Compiler-Sicherheitsnetz vs. nackte Hardware

In Sprachen wie C oder C++ wird bei dieser Adressberechnung blind vertraut. Wenn du dort auf Index 10 eines 5-Element-Arrays zugreifst, rechnet die CPU stur weiter, liest Speicher außerhalb des Arrays und dein Programm stürzt entweder mit einem Segfault ab oder – noch schlimmer – liest geheime Daten.

Rust schützt dich davor. Bei jedem Indexzugriff (z. B. zahlen[i]) fügt Rust zur Laufzeit einen kleinen Check ein (Bounds Check):

#![allow(unused)]
fn main() {
if i >= zahlen.len() {
    panic!("index out of bounds: the len is {} but the index is {}", zahlen.len(), i);
}
}

Dieser Check kostet minimale Performance, rettet dich aber vor schwerwiegenden Sicherheitslücken. Wenn der Compiler jedoch zur Kompilierzeit beweisen kann (z. B. in einer for-Schleife über die Range 0..5), dass der Index niemals außerhalb liegt, optimiert er diesen Check komplett weg!

2. Vec\<T\>: Der dynamische Vektor im Detail

Ein normales Array ist wunderbar, aber unelastisch. Was ist, wenn wir erst zur Laufzeit wissen, wie viele Elemente wir speichern müssen? Hier kommt der Vektor (Vec\<T\>) ins Spiel. Ein Vektor ist im Grunde ein dynamisch wachsendes Array, das seine Zelte auf dem Heap aufschlägt.

Die Alltagsanalogie: Der Koffer mit Anhänger

Stell dir vor, du gehst auf Reisen. Du hast einen Gepäckanhänger (den Stack), den du fest in der Hand hältst. Auf diesem Anhänger stehen drei wichtige Dinge:

1. Eine Adresse, wo dein eigentlicher Koffer im Frachtraum des Flugzeugs liegt.
2. Die maximale Größe (Kapazität) des Koffers (wie viele T-Shirts reinpassen).
3. Die aktuelle Anzahl an T-Shirts, die du bereits eingepackt hast.

Der eigentliche Koffer (mit den T-Shirts) reist im Frachtraum (dem Heap) und kann bei Bedarf gegen einen größeren Koffer ausgetauscht werden.

Das Speicherlayout von Vec\<T\>

Ein Vec\<T\> besteht aus zwei Teilen: einem festen Kontrollblock auf dem Stack und den eigentlichen Daten auf dem Heap.

Der Stack-Teil eines Vektors hat auf einer 64-Bit-CPU eine feste Größe von 24 Bytes (3 Feldern à 8 Bytes bzw. 1 “Word”):

1. Pointer (8 Bytes): Die Speicheradresse, die auf den Beginn des allokierten Heap-Speicherbereichs zeigt.
2. Capacity (8 Bytes): Die Anzahl der Elemente, die der aktuelle Heap-Speicherbereich maximal aufnehmen kann, ohne dass neuer Speicher angefordert werden muss.
3. Length (8 Bytes): Die Anzahl der Elemente, die sich aktuell tatsächlich im Vektor befinden.

STACK (24 Bytes)                               HEAP
+------------------+-----------+-----------+   +-----------+-----------+-----------+---
| Pointer (8 Byte) | Cap (8 B) | Len (8 B) |-->| Element 0 | Element 1 | Element 2 |...
+------------------+-----------+-----------+   +-----------+-----------+-----------+---
  |                  |           |
  |                  |           +-- Aktuelle Anzahl (z.B. 2)
  |                  +-- Reservierter Platz (z.B. 4)
  +-- Zeigt auf Heap-Adresse

Egal, ob dein Vektor leer ist oder eine Million Elemente enthält: Auf dem Stack belegt er immer exakt 24 Bytes!

Let’s verify this with code. Hier ist ein vollständig kompilierbares Beispiel, das uns die genauen Byte-Größen zeigt:

use std::mem::size_of;

fn main() {
    // Wir erstellen einen Vektor mit Elementen
    let mut v: Vec<i32> = Vec::with_capacity(4);
    v.push(10);
    v.push(20);

    // 1. Größe auf dem Stack ermitteln
    let stack_groesse = size_of::<Vec<i32>>();
    println!("Größe des Vec-Kontrollblocks auf dem Stack: {} Bytes", stack_groesse);

    // 2. Zustand des Vektors abfragen
    let laenge = v.len();
    let kapazitaet = v.capacity();
    let heap_adresse = v.as_ptr(); // Holt den rohen Zeiger auf den Heap

    println!("Länge: {}, Kapazität: {}", laenge, kapazitaet);
    println!("Startadresse auf dem Heap: {:p}", heap_adresse);

    // Jedes Element ist ein i32 (4 Bytes). Bei Kapazität 4
    // belegt der Heap-Bereich also 4 * 4 = 16 Bytes.
}

3. Slices &[T]: Die schlanken Fat Pointer

Ein Slice &[T] (gesprochen: “Slice von T”) ist eine Referenz auf ein zusammenhängendes Stück Speicher. Es besitzt die Daten nicht selbst, sondern borgt sie sich nur aus. Ein Slice kann auf ein Array auf dem Stack zeigen, auf einen Teil eines Vektors auf dem Heap oder auf statische Daten im Programmbereich.

Die Alltagsanalogie: Der Lichtkegel

Stell dir eine Theaterbühne vor, auf der 20 Schauspieler nebeneinander stehen. Ein Vektor besitzt die gesamte Bühne. Ein Slice ist wie ein Scheinwerfer: Er beleuchtet nur einen bestimmten Ausschnitt (z. B. Schauspieler 5 bis 12). Der Scheinwerfer muss wissen:

1. Wo beginnt der Lichtkegel (Startadresse)?
2. Wie breit ist der Lichtkegel (Anzahl der beleuchteten Schauspieler)? Er muss nicht wissen, wie groß die gesamte Bühne ist oder wie viele Leute maximal draufpassen.

Das Speicherlayout: Der Fat Pointer (16 Bytes)

Während eine normale Referenz auf ein einzelnes Element (z. B. &i32) ein einfacher Zeiger von 8 Bytes ist, ist ein Slice-Zeiger ein sogenannter Fat Pointer (breiter Zeiger). Er belegt auf dem Stack exakt 16 Bytes:

1. Pointer (8 Bytes): Zeiger auf das erste Element des Slices.
2. Length (8 Bytes): Die Anzahl der Elemente, die zum Slice gehören.

Da der Slice die Daten nicht besitzt, braucht er kein Capacity-Feld. Es gibt nichts zu vergrößern.

STACK (16 Bytes Fat Pointer)                   HEAP / STACK (Datenquelle)
+------------------+------------------+        +-----+-----+-----+-----+-----+
| Pointer (8 Byte) | Length (8 Bytes) |------->| 10  | 20  | 30  | 40  | 50  |
+------------------+------------------+        +-----+-----+-----+-----+-----+
  |                  |                           ^           ^
  |                  +-- Länge des Slices (3)    |           |
  +-- Zeigt auf das Start-Element ---------------+-----------+

Das folgende kompilierbare Code-Beispiel demonstriert den Größenunterschied im Speicher:

use std::mem::size_of;

fn main() {
    let daten: [i32; 5] = [10, 20, 30, 40, 50];

    // Wir erstellen ein Slice auf die mittleren drei Elemente
    let slice: &[i32] = &daten[1..4]; // Enthält [20, 30, 40]

    println!("Größe eines normalen Zeigers (&i32): {} Bytes", size_of::<&i32>());
    println!("Größe des Slices (&[i32]) auf dem Stack: {} Bytes", size_of::<&[i32]>());

    println!("Slice-Länge: {}", slice.len());
    println!("Adresse des ersten Slice-Elements: {:p}", &slice[0]);
    println!("Adresse des ersten Original-Elements: {:p}", &daten[0]);
}

4. Die Anatomie der Heap-Reallokation bei Vektoren

Was passiert eigentlich, wenn wir in einen Vektor schreiben und dieser seine maximale Kapazität erreicht? Nehmen wir an, wir haben einen Vektor mit Kapazität 4 und Länge 4. Wir rufen nun ein weiteres Mal push() auf.

Das Problem

Der Vektor muss wachsen. Da der Heap-Speicher jedoch von vielen verschiedenen Programmteilen genutzt wird, können wir nicht einfach hoffen, dass der Speicherbereich direkt hinter unserem Vektor noch frei ist. Der Speicher allokiert dort vielleicht schon ein anderes Objekt. Wir können den Vektor also nicht einfach “nach hinten verlängern”.

Die Wachstumsstrategie (Capacity Doubling)

Rusts Standardbibliothek verdoppelt bei einer Reallokation in der Regel die bisherige Kapazität. Das hat mathematische Gründe: Durch die Verdopplung müssen wir immer seltener neuen Speicher anfordern, je größer der Vektor wird. Die Zeitkomplexität für das Einfügen bleibt dadurch im Schnitt (amortisiert) bei $O(1)$.

Der 3-Schritte-Tanz der CPU

Wenn die Kapazität erschöpft ist, führt die Laufzeitumgebung drei hardwareintensive Schritte aus:

Schritt 1: Neuen, doppelt so großen Speicherbereich auf dem Heap finden & allokieren.
Alt (Kapazität 4):  [ A | B | C | D ]
Neu (Kapazität 8):  [   |   |   |   |   |   |   |   ]

Schritt 2: Daten per schnellem CPU-Befehl (memcpy) kopieren.
Neu (Kapazität 8):  [ A | B | C | D |   |   |   |   ]

Schritt 3: Alten Speicherbereich freigeben und Pointer im Stack-Kontrollblock aktualisieren.

Die Gefahren dieses Prozesses

1. Speicher-Fragmentierung: Häufige Reallokationen hinterlassen “Löcher” im Heap, da alte, kleinere Speicherblöcke freigegeben werden, die der Allokator erst mühsam wieder an andere, passende Daten vergeben muss.
2. Performance-Einbruch (Latenz-Spitzen): Das Kopieren von Daten per memcpy ist zwar extrem schnell, da die CPU ganze Speicherblöcke über breite Datenbusse verschiebt. Dennoch kostet es Zeit. Wenn dein Vektor eine Million Elemente enthält, bremst eine Reallokation dein Programm spürbar aus.
3. Spitzen-Speicherbedarf: Während des Kopiervorgangs belegt dein Vektor kurzzeitig das Dreifache der Kapazität im RAM: Der alte Block, der neue Block und das Element, das du gerade hineinkopieren willst.

Die Rettung: Vec::with_capacity

Wenn du im Vorhinein weißt (oder gut schätzen kannst), wie viele Elemente in deinem Vektor landen werden, nutze immer Vec::with_capacity. Damit reservierst du den Speicher einmalig und verhinderst teure Reallokationen.

Hier ist ein Experiment, das die Reallokation live im Speicher sichtbar macht:

fn main() {
    let mut v = Vec::new();
    let mut letzte_adresse = std::ptr::null();

    for i in 0..10 {
        v.push(i);
        let aktuelle_adresse = v.as_ptr();

        // Wenn sich die Heap-Adresse ändert, gab es eine Reallokation!
        if aktuelle_adresse != letzte_adresse {
            println!(
                "Element {}: Reallokation! Kapazität: {} -> Heap-Adresse: {:p}",
                i,
                v.capacity(),
                aktuelle_adresse
            );
            letzte_adresse = aktuelle_adresse;
        }
    }
}

Wenn du dieses Programm ausführst, wirst du sehen, wie die Kapazität sprunghaft ansteigt ($0 \rightarrow 4 \rightarrow 8 \rightarrow 16$) und sich dabei jedes Mal die Hexadezimal-Adresse des Heap-Zeigers ändert.

5. CPU-Caching, Datenlokalität und Hardware Prefetching

Nun kommen wir zum absoluten Königsthema der Systemprogrammierung. Warum ist ein Vektor in der Praxis fast immer dramatisch schneller als eine verkettete Liste (LinkedList), obwohl beide theoretisch die gleichen Komplexitätsklassen für viele Operationen haben?

Die Antwort liegt nicht in der Software, sondern im Silizium deiner CPU: Datenlokalität und Caches.

Die Alltagsanalogie: Der Schreibtisch und das Außenlager

Stell dir vor, du bist ein Handwerker in einer Werkstatt:

• Die CPU-Register sind die Werkzeuge, die du direkt in deiner Hand hältst.
• Der L1/L2/L3-Cache ist deine Werkbank direkt vor dir. Hier liegen Werkzeuge griffbereit. Der Zugriff dauert 1 Sekunde.
• Der Hauptspeicher (RAM) ist ein Außenlager am anderen Ende der Stadt. Jedes Mal, wenn du ein Werkzeug von dort holen musst, musst du ins Auto steigen und hinfahren. Das dauert 2 Stunden.

Wenn du nun ein Projekt bearbeitest, bei dem du nacheinander 10 Schrauben eindrehen musst, schickt dich dein Lehrling (der Hardware Prefetcher) nicht für jede einzelne Schraube einzeln zum Außenlager. Wenn du nach der ersten Schraube greifst, fährt er zum Lager und bringt dir eine ganze Kiste mit 64 Schrauben mit (eine Cache Line). Da die Schrauben im Lager alle nebeneinander in einer Schachtel lagen, konnte er sie auf einmal mitnehmen.

Was ist Hardware Cache Line Prefetching?

Wenn die CPU Daten aus dem langsamen RAM anfordert, liest sie niemals nur das einzelne angeforderte Byte. Sie lädt immer einen zusammenhängenden Block von meist 64 Bytes (eine sogenannte Cache-Zeile oder Cache Line) in den schnellen L1-Cache.

Der Hardware Prefetcher ist eine spezialisierte Schaltung in der CPU. Er analysiert die Speicherzugriffsmuster deines Programms. Erkennt er, dass dein Programm sequenziell auf den Speicher zugreift (z. B. Adresse 0x1000, 0x1004, 0x1008…), lädt er die nächsten Cache-Zeilen bereits präventiv in den Cache, bevor dein Code den nächsten Befehl ausführt. Der Zugriff erfolgt dann direkt aus dem L1-Cache (ein sogenannter Cache Hit). Das dauert oft weniger als einen Taktzyklus!

Das Duell: Vec\<T\> vs. LinkedList\<T\>

Der Vektor: Der Traum der CPU

Da im Vektor alle Elemente lückenlos nebeneinander im Speicher liegen, ist er der beste Freund des Prefetchers.

Speicher:   [ Elem 0 ][ Elem 1 ][ Elem 2 ][ Elem 3 ][ Elem 4 ]
            |================== Cache Line 1 ==================|

Beim Zugriff auf Elem 0 lädt die CPU die gesamte Cache Line. Die Elemente 1 bis 3 landen gratis und ohne Verzögerung im L1-Cache. Der Prefetcher sieht den Trend und lädt bereits die nächste Cache Line für die Elemente 4 und folgende. Die CPU läuft unter Volldampf, ohne jemals auf den RAM warten zu müssen.

Die LinkedList: Der Albtraum der CPU

Eine verkettete Liste besteht aus einzelnen Knoten, die wild verstreut auf dem Heap liegen. Jeder Knoten enthält neben den Nutzdaten einen Zeiger auf die Adresse des nächsten Knotens.

Heap:      [ Elem 0 | Pointer ] --------> (irgendwo im Heap) --------> [ Elem 1 | Pointer ]
           |== Cache Line A ==|                                      |== Cache Line B ==|

Wenn du die Liste durchläufst, greifst du auf Elem 0 zu. Die CPU lädt Cache Line A. Nun liest du den Zeiger auf den nächsten Knoten. Dieser zeigt auf eine Adresse weit entfernt im Heap. Die CPU muss die aktuelle Cache Line verwerfen, eine neue Anfrage an den RAM schicken und warten (ein schwerer Cache Miss bzw. Pointer Chasing). Während dieser Hunderte von Taktzyklen langen Wartezeit (der sogenannten Memory Wall) tut die CPU absolut nichts – sie heizt nur den Raum. Der Prefetcher ist völlig blind, da er kein sequenzielles Muster erkennen kann.

Important

Bevorzuge in Rust fast immer Vec\<T\> gegenüber LinkedList\<T\>, selbst wenn du Elemente am Anfang oder in der Mitte einfügen musst. Die CPU-Cache-Effizienz des kontinuierlichen Speichers macht das Kopieren von Elementen im Vektor bei fast allen praxisrelevanten Größen (bis zu zehntausenden Elementen) wett!

6. HashMaps unter der Lupe: SwissTable und Robin Hood

Eine HashMap\<K, V\> erlaubt es uns, Werte über einen Schlüssel in $O(1)$-Zeit zu suchen. Doch wie schafft sie das auf Systemebene, und wie löst sie das Problem, wenn zwei unterschiedliche Schlüssel denselben Hash-Wert erzeugen (eine Kollision)?

Das Prinzip der Hash-Tabelle

Eine HashMap besitzt intern ein flaches Array von “Buckets” (Speicherzellen). Die Hash-Funktion nimmt den Schlüssel (z. B. "Thorsten") und berechnet daraus eine scheinbar zufällige Zahl. Diese Zahl wird per Modulo-Operation auf die Größe des internen Arrays abgebildet. Das Ergebnis ist der Index, an dem wir nachschauen müssen.

Kollisionsauflösung mit Robin-Hood-Hashing

Wenn zwei Schlüssel (z. B. "Apfel" und "Birne") nach dem Hashen auf denselben Index zeigen, haben wir eine Kollision. Rust verwendet ein hocheffizientes Verfahren zur Kollisionsauflösung: Robin-Hood-Hashing kombiniert mit offener Adressierung (Linear Probing).

Die Alltagsanalogie: Der reiche und der arme Gast

Stell dir ein Hotel vor, in dem die Zimmernummern nach dem Namen der Gäste vergeben werden.

• Gast A reist an und erhält sein Wunschzimmer 10. Seine “Distanz zum Wunschzimmer” ist 0. Er ist “reich” (an Bequemlichkeit).
• Gast B reist an. Sein Wunschzimmer ist ebenfalls Zimmer 10. Da es besetzt ist, geht er ein Zimmer weiter zu Zimmer 11. Seine Distanz zum Wunschzimmer ist 1. Er ist “ärmer” als Gast A.
• Gast C reist an. Sein Wunschzimmer ist Zimmer 10. Da Zimmer 10 und 11 besetzt sind, müsste er eigentlich zu Zimmer 12 gehen. Seine Distanz wäre dann 2.

Nun kommt das “Robin-Hood-Prinzip”: Wir bestehlen die Reichen und geben es den Armen!

Wenn Gast C (Distanz 0 an Wunschzimmer 10) anreist und Zimmer 10 besetzt vorfindet, geht er zu Zimmer 11. Dort wohnt Gast B (dessen Distanz aktuell 1 ist). Gast C stellt fest: “Wenn ich hier einziehe, ist meine Distanz 1. Die von Gast B ist auch 1. Keine Verbesserung.” Er geht weiter zu Zimmer 12.

Was aber, wenn Gast D (Wunschzimmer 10, also an Zimmer 11 bereits Distanz 1) ankommt und in Zimmer 11 wohnt jemand, der dort sein absolutes Wunschzimmer hat (Gast X mit Distanz 0)? Gast D verdrängt den “reichen” Gast X einfach aus dem Zimmer! Gast X muss nun ausziehen und ein Zimmer weiter wandern (womit Gast X zum “Armen” wird mit Distanz 1).

Durch dieses ständige Verdrängen und Weiterreichen wird die Varianz der Distanzen extrem gering gehalten. Niemand ist extrem weit von seinem Wunschzimmer entfernt. Das sorgt dafür, dass die Suche nach einem Schlüssel im Worst-Case extrem schnell abgebrochen werden kann.

Das SwissTable-Design (Hashbrown)

Rusts Standard-HashMap basiert auf der hashbrown-Crate, einer Implementierung von Googles revolutionärem SwissTable-Design.

SwissTable optimiert die Suche im Speicher durch die Trennung von Kontroll- und Nutzdaten:

1. Nutzdaten-Array: Ein großes Array, das die eigentlichen Schlüssel und Werte enthält.
2. Metadaten-Array (Control Bytes): Ein paralleles Array, bei dem jedes Byte den Status eines Buckets beschreibt (z. B. ob es leer ist, gelöscht wurde oder die untersten 7 Bits des Hash-Werts des dort liegenden Elements enthält).

Metadaten:  [ 0x7F ][ 0x1A ][ 0xFF ][ 0x7F ] ... (1 Byte pro Bucket)
            |--------- SIMD Register --------|
Daten:      [ Key A | Val A ][ Key B | Val B ] ...

SIMD-Beschleunigung

Wenn wir nach einem Schlüssel suchen, berechnen wir dessen Hash. Die CPU lädt nun eine Gruppe von 16 Metadaten-Bytes auf einmal in ein spezielles SIMD-Register (Single Instruction, Multiple Data). Mit einem einzigen CPU-Befehl vergleicht die CPU diese 16 Bytes gleichzeitig mit den gesuchten Hash-Bits. Wir durchsuchen also 16 Buckets in einem einzigen Taktzyklus! Erst wenn wir in den Metadaten einen Treffer finden, greifen wir auf das teurere Nutzdaten-Array zu, um den eigentlichen Schlüssel auf Gleichheit zu prüfen.

Das macht Rusts HashMap zu einer der schnellsten Implementierungen in der gesamten Programmierwelt.

Zusammenfassung der Hardware-Regeln

Wenn du das nächste Mal eine Datenstruktur auswählst, denke nicht nur an die theoretische $O$-Komplexität. Denke an den Heap-Allokator, den L1-Cache und den fleißigen Hardware-Prefetcher. In 95 % aller Fälle lautet die richtige Antwort auf Hardware-Ebene: Nimm einen Vektor.