Go 1.24 Maps: Wie Swiss Tables die Speicherung revolutionieren
How Swiss tables work in Go built-in map
Go 1.24 ersetzt die bisherige Map-Implementierung durch ein Design basierend auf Swiss Tables. Dieser Artikel erklärt Schritt für Schritt, wie Go-Maps nun intern funktionieren: von der Runtime-Struktur über Gruppen mit Kontrollbytes bis hin zur Tabellenverwaltung. Dabei wird gezeigt, wie Hashing, Seeds und SIMD-Instruktionen die Leistung verbessern. Ein visueller Ansatz macht die komplexen Konzepte verständlich, ohne dass Vorkenntnisse aus dem vorherigen Artikel nötig sind.
Statt die 8 Slots einzeln zu durchsuchen und H2 mit jedem Kontrollbyte separat zu vergleichen, nutzt Go auf AMD64 SIMD-Instruktionen, um H2 42 mit allen 8 Kontrollbytes gleichzeitig zu vergleichen.
- nasso_dev
Swiss Tables wurden von Ingenieuren im Google-Büro in Zürich erfunden, daher der Name. Ich bin überrascht, dass Go, eine Programmiersprache, die ebenfalls von Google stammt, sie nicht verwendet hat! Für einen hervorragenden Vortrag über die Entwicklung von Swiss Tables empfehle ich diesen Vortrag von Matt Kulukundis auf der CppCon 2017: "Designing a fast, efficient, cache-friendly hash table, step by step" https://youtu.be/ncHmEUmJZf4
- bruce343434
Ich habe das Gefühl, dass dieser Artikel eine Tiefensuche darüber macht, was Swiss Tables sind, und sich kopfüber in die winzigsten Implementierungsdetails stürzt, aber mir fehlt die Breitensuche. Was ist die oberste `struct` einer Swiss Table? Ein Array von Gruppen? Warum nicht alles auf lineares offenes Addressing mit einer Schrittweite von 8 für SIMD vereinfachen? Warum die dreieckigen Sprünge? Welche Probleme löst dieses Design?
- Surac
Go hat dieselbe Krankheit wie Rust. Zuerst Variablenname, dann Typ. Das hatten wir schon in Basic und ich hasse es. Manche argumentieren, es wäre besser, wenn man mehr als eine Variable in derselben Zeile deklariert. Das habe ich nie gemacht. Warum können wir keine schönen Dinge haben?