Hoe de ingebouwde Map van Go werkt met Swiss Tables

Deze update bespreekt hoe maps zich gedragen en de interne werking van de nieuwe runtime. Waar de officiële Go-blog dieper ingaat op de details en meer voorkennis veronderstelt, kiezen we hier voor een geleidelijke en visuele benadering om de werking van Go inzichtelijk te maken.

Wat is een map tijdens runtime?

Laten we beginnen met wat een map feitelijk is.

m := make(map[string]int)

De functie make initialiseert de map. map[string]int is het type op taalniveau, wat aangeeft dat de map strings als sleutels en integers als waarden gebruikt. Onder dit type is de runtime-representatie van m een pointer naar internal/runtime/maps.Map.

type Map struct {
    used uint64
    seed uintptr
    dirPtr unsafe.Pointer
    dirLen int
    ...
}

Als je m kopieert naar een andere map-variabele, kopieer je deze pointer. Beide variabelen verwijzen dan naar dezelfde runtime Map en dezelfde entries.

De eerste twee velden beschrijven de map zelf, niet de opslag van de entries:

  • used: Telt hoeveel entries er momenteel zijn opgeslagen. Wanneer je len(m) aanroept, vervangt Go dit door een toegang tot dit veld, waardoor len(m) een O(1)-operatie is in plaats van een scan van de hele map.
  • seed: Dit veld zorgt ervoor dat verschillende maps dezelfde sleutels op verschillende manieren distribueren. Go initialiseert dit veld met een willekeurig getal voor elke map.

Wanneer Go een sleutel in de opslag moet lokaliseren, hasht hij die sleutel met behulp van de seed van de map. Omdat elke map een eigen seed heeft, kunnen dezelfde sleutels in twee verschillende maps verschillende hash-waarden en dus verschillende opslaglocaties opleveren.

Groep (Group)

De manier waarop een map zijn opslag inricht, hangt af van het aantal sleutel-waarde-paren dat hij bevat. In de kleinste vorm slaat een map tot 8 paren op in een structuur die een groep wordt genoemd. Dit is de kleinste opslageenheid die de Swiss Table-implementatie van Go in één keer bekijkt.

Elke groep bevat:

  • 8 slots voor sleutel-waarde-entries.
  • 8 controlebytes (één voor elk slot), die samen worden opgeslagen in één uint64.

De concrete type van de groep hangt af van de gebruikte sleutel- en waardetypes. Conceptueel ziet de layout voor een map[string]int er als volgt uit:

type group struct {
    ctrl uint64
    slots [8]struct {
        key  Key
        elem Elem
    }
}

(Opmerking: Go test momenteel een nieuwe layout met gescheiden arrays voor sleutels en waarden om de locality van sleutelzoekopdrachten te verbeteren; zie de sectie over split group layout).

Controlebytes en het controlewoord

De 8 controlebytes vormen samen het 8-byte controlewoord. Elk controlebyte beschrijft het slot direct daaronder.

De herkomst van deze bytes is als volgt: Go hasht de sleutel met de seed uit de Map en verdeelt die hash in twee delen. Op de meeste 64-bit systemen zijn de bovenste 57 bits H1 en de onderste 7 bits H2. (Op 32-bit systemen en Wasm wordt een 32-bit layout gebruikt).

  • H1 wordt gebruikt om te bepalen waar een zoekopdracht in de opslag begint.
  • H2 is het deel dat in het controlebyte boven een actieve slot wordt opgeslagen.

Een controlebyte heeft 8 bits, terwijl H2 er slechts 7 gebruikt. Go gebruikt de hoogste bit om aan te geven of het slot een actieve entry bevat of een speciale status heeft:

  • Bit is 0: De onderste 7 bits bevatten H2. De slot bevat een live entry.
  • Bit is 1: De volledige byte representeert een speciale status:
  • 10000000: Leeg (empty).
  • 11111110: Verwijderd (deleted), ook wel een tombstone genoemd.

Een zoekopdracht kan stoppen bij een 'leeg' slot, maar moet doorgaan bij een 'verwijderd' slot.

Voorbeeld van insertie

Stel dat we de sleutel "cow" toevoegen met een waarde van 4.

  1. Go berekent de hash; stel dat H2 voor "cow" 42 is.
  2. Go controleert of de sleutel al bestaat door H2 te vergelijken met de controlebytes.
  3. Als er andere slots zijn met H2 = 42 (bijv. "dog"), voert Go een volledige gelijkheidscontrole (==) uit op de sleutels.
  4. Als "cow" niet wordt gevonden, selecteert Go het eerste lege slot, schrijft de sleutel en waarde, en zet H2 (42) in het bijbehorende controlebyte.

Zoeken met SIMD

Bij het zoeken naar een sleutel bezoekt Go de 8 slots niet één voor één. Op AMD64-architecturen gebruikt Go SIMD-instructies om H2 in één keer met alle 8 controlebytes te vergelijken. Dit resulteert in een bitmap waarbij slechts de bits van de kandidaat-slots zijn ingesteld. Alleen voor deze specifieke slots voert Go daarna de volledige sleutelvergelijking uit.

Tabel (Table)

Wanneer een map meer dan 8 paren bevat, kan hij niet meer in één groep passen. Go verdubbelt het aantal groepen en introduceert een tabel om deze te beheren.

type table struct {
    used       uint16
    capacity   uint16
    growthLeft uint16
    ...
    groups groupsReference
}

Redistributie en H1

Bij de overgang naar een tabel moeten bestaande entries worden herverdeeld. Go gebruikt hiervoor H1 om de startgroep te berekenen: startgroep = H1 % aantal_groepen

Omdat het aantal groepen verandert, wordt deze berekening voor elke bestaande sleutel opnieuw uitgevoerd.

Driehoekige probe-sequentie (Triangular Probe Sequence)

Als de startgroep vol is, moet Go andere groepen controleren. In plaats van simpelweg de volgende groep te pakken, gebruikt Go een driehoekige sequentie: hij beweegt met stappen van +1, daarna +2, +3, enzovoort, en springt terug naar het begin bij het bereiken van het einde van de tabel. Omdat het aantal groepen een macht van twee is, bezoekt Go elke groep exact één keer voordat de sequentie zich herhaalt.

Groei en Load Factor

Een tabel kan groeien tot maximaal 128 groepen (1024 slots). Go wacht niet tot elke slot is gevuld voordat hij de tabel vergroot of splitst. Dit wordt geregeld door de load factor:

load = (live entries + deleted slots) / table slots

De maximale load factor is 7/8 (87,5%). Zodra deze limiet is bereikt (of wanneer growthLeft op 0 komt), gebeurt het volgende:

  • Als de tabel minder dan 1024 slots heeft: het aantal groepen wordt verdubbeld.
  • Als de tabel al 1024 slots heeft: de tabel wordt gesplitst in twee nieuwe tabellen van elk 1024 slots.

Bij een split gebruikt Go het meest linkse bit van H1 om te bepalen in welke van de twee nieuwe tabellen een sleutel terechtkomt.

Directory

De directory lost het probleem van dure redistributies op. In plaats van de hele map opnieuw op te bouwen, herbouwt Go alleen de tabel die meer ruimte nodig heeft.

De directory is een array van pointers. De meest linkse bits van H1 selecteren een entry in de directory, en die entry wijst naar de betreffende tabel. Dit stelt Go in staat om één tabel te splitsen zonder dat alle andere tabellen in de map mee moeten splitsen.

Globale en lokale diepte

Om te bepalen of de directory moet groeien tijdens een split, gebruikt Go globalDepth en localDepth:

  • Global Depth (globalDepth): Het aantal high-hash-bits dat wordt gebruikt om een directory-entry te selecteren.
  • Local Depth (localDepth): Het aantal high-hash-bits dat nodig is om een specifieke tabel te identificeren.

Als de localDepth van een tabel kleiner is dan de globalDepth, kan de tabel splitsen zonder dat de directory zelf hoeft te groeien. Is de localDepth gelijk aan de globalDepth, dan verdubbelt Go eerst de directory en verhoogt hij de globalDepth voordat de tabel splitst.

Wat is er veranderd in Go 1.24?

Vergelijking met de oude implementatie

De oude implementatie gebruikte "buckets". Als een bucket vol was, werd er een overflow bucket aan gekoppeld. Dit leidde tot:

  • Kosten: Zoekopdrachten moesten pointers volgen naar overflow buckets, wat resulteerde in meerdere afhankelijke geheugenladingen.
  • Allocaties: Het uitbreiden van de keten vereiste nieuwe allocaties.

De nieuwe Swiss Table-implementatie zet groepen in één aaneengesloten array. In plaats van overflow buckets te volgen, gebruikt hij de driehoekige probe-sequentie binnen de tabel.

Prestaties

Volgens microbenchmarks van het Go-team zijn map-operaties tot 60% sneller dan in Go 1.23. In volledige applicatie-benchmarks is er een gemiddelde verbetering van de CPU-tijd van ongeveer 1,5%.

Bonus

Verwijdering (Deletion)

Wanneer een sleutel wordt verwijderd, wordt het slot niet altijd direct "leeg" (empty).

  • In een kleine map (1 groep) wordt een slot altijd leeg.
  • In een grotere tabel wordt een slot alleen leeg als de groep al minstens één ander leeg slot bevat.
  • Als er geen lege slots zijn, wordt het slot gemarkeerd als verwijderd (deleted).

Dit is essentieel voor de zoekopdracht: een empty slot betekent dat de zoekopdracht kan stoppen, maar een deleted slot betekent dat Go moet doorgaan naar de volgende groep in de probe-sequentie, omdat er mogelijk sleutels zijn ingevoegd ná de verwijdering.

Waarom een load factor van 7/8?

Hoe voller een tabel, hoe langer de probe-sequentie kan worden bij een mislukte zoekopdracht. Door de load factor op 7/8 te houden, garandeert Go dat er voldoende lege slots aanwezig zijn om zoekopdrachten relatief snel te beëindigen.

De split-groep-layout (Experimenteel)

In Go 1.27 is er een experimentele layout genaamd mapsplitgroup (te activeren via GOEXPERIMENT=mapsplitgroup).

Standaard layout: Sleutels en waarden staan naast elkaar in de slots. Split layout: Alle sleutels staan in één array en alle waarden in een andere array.

Dit biedt twee voordelen:

  1. Cache-efficiëntie: Tijdens het zoeken hoeft Go alleen de array met sleutels te scannen. De waarden worden pas gelezen zodra de juiste sleutel is gevonden.
  2. Geheugenefficiëntie: Het voorkomt onnodige padding (opvulling). Bij een map[int64]struct{} (gebruikt als set) bespaart de split layout aanzienlijk veel geheugen per groep omdat de lege waarden niet meer zorgen voor padding per slot.

Bronnen

  • De Go-specificatie: Map types
  • Go 1.24 release notes: Runtime
  • Faster Go maps with Swiss Tables
  • Go 1.27 runtime source: map.go, table.go, group.go, en runtime.go
  • Abseil Swiss Tables Design Notes