Les tableaux associatifs et leur performance en Go

Pour les développeurs Go, comprendre les nuances des structures de données intégrées au langage est essentiel pour écrire du code efficace. Cet article se concentre sur une analyse des maps en Go, une structure de données fondamentale qui implémente les tableaux associatifs.

Cette analyse porte sur deux points :

Explorer la dualité entre les maps et les listes en termes de performance.
Découvrir les mécanismes internes des maps.

L'objectif est de faire des choix éclairés lors de la conception de structures de données, en particulier pour les applications sensibles aux performances.

Les tableaux associatifs

Très grossièrement, un processeur ne sait faire que quelques opérations binaires et arithmétiques, des sauts conditionnels et manipuler un espace mémoire. Parmi ces opérations, on peut retrouver très facilement comment faire une liste (il suffira de mettre des éléments de taille fixe les uns après les autres dans l'espace mémoire), mais à contrario, un tableau clé/valeur ne semble pas être quelque chose de trivial pour un processeur.

Paradoxalement, la plupart des langages de haut niveau (principalement les langages de scripts) présentent des structures de tableau clé/valeur dans la syntaxe native du langage.

Python:

fruits = {
    "pomme": "rouge",
    "banane": "jaune",
    "kiwi": "vert"
}

PHP:

$fruits = array(
    "pomme" => "rouge",
    "banane" => "jaune",
    "kiwi" => "vert"
);

JavaScript:

let fruits = {
    pomme: "rouge",
    banane: "jaune",
    kiwi: "vert"
};

Go

fruits := map[string]string{
    "pomme":  "rouge",
    "banane": "jaune",
    "kiwi":   "vert",
}

Ces tableaux associatifs sont nécessairement implémentés par un algorithme relativement complexe et leur usage n'est pas neutre : il va impacter les performances d'un programme.

Un tableau associatif est une structure de données qui permet de stocker des paires clé/valeur et d'y accéder rapidement. Il utilise une fonction de hachage pour convertir les clés en indices de tableau. La fonction de hachage est le cœur du tableau associatif. Elle prend une clé en entrée et retourne un indice dans le tableau. La taille du tableau est connue, le résultat de la fonction de hachage sera une valeur entre 0 et la taille du tableau - 1.

Lorsqu'on insère une paire clé/valeur dans le tableau, on calcule l'indice avec la fonction de hachage, puis on place la paire dans l'emplacement correspondant à cet indice. Parfois une collision peut se produire, il s'agit de deux clés différentes pour lesquelles la fonction de hachage retourne le même indice. On va alors utiliser une liste pour mettre les valeurs les unes après les autres.

Donc en termes de performances, si on ignore la complexité de la fonction de hachage, nous aurons :

Insertion : O(1) en moyenne, O(n) dans le pire cas
Recherche : O(1) en moyenne, O(n) dans le pire cas
Suppression : O(1) en moyenne, O(n) dans le pire cas

La performance d'un tableau associatif basé sur une table de hachage va donc dépendre de ces paramètres :

La taille du tableau
La vitesse de l'algorithme de hachage
La probabilité des collisions en fonction des clés (et donc la longueur des listes)

On comprend donc que ce qui se cache derrière ces notations anodines est très loin d'être quelque chose de simple.

Les langages de bas niveau tels que C, C++, Java, Rust n'offrent pas de manière native la possibilité de faire un tableau associatif. C impose l'implémentation d'un tableau adapté au développement ou l'usage de bibliothèques externes. C++, Java et Rust proposent des implémentations dans leurs bibliothèques standard.

Go est à cheval entre ces deux types de langage. Il s'agit d'un langage compilé d'un niveau assez bas, mais propose une implémentation des tableaux associatifs native à travers les maps. Je propose d'étudier l'impact de la clé de hachage et de déterminer la pertinence de l'usage d'une map.

Le cas de Go

En Go, les maps sont implémentées avec une table de hachage, on a donc une complexité qui est O(h) + O(1), où O(h) est la complexité inconnue de l'algorithme de hachage et O(1) est la complexité d'accès une fois le hash connu (ignorons le pire cas). O(1) peut être ignoré et nous nous concentrons donc sur O(h). La recherche d'un élément parmi "n" éléments dans une liste a une complexité de O(n).

O(h) étant inconnu, on peut penser que pour de petites valeurs de n la complexité O(n) donnerait de meilleurs temps de réponse que O(h).

Présentation du benchmark

Il s'agit de créer une liste et une map de n éléments, et de mesurer 10 millions d'accès avec des clés aléatoires. L'opération de mesure sera recommencée pour chaque valeur de n, où n est compris entre 1 et 40.

Le premier test nommé Raw génère des clés non variables sous forme de string qui représente de l'hexadécimal, comprises entre "0000" et "0028". Les clés de tests sont des clés pseudo-aléatoires comprises entre "0000" et "0028".

Le second test nommé Long génère des clés distinctes comprises entre "00000000" et "00989680". Les clés de tests sont des clés pseudo-aléatoires également comprises entre "00000000" et "00989680".

Raw et Long sont des noms très peu représentatifs, j'avais une autre idée en tête au début de ces tests.

Le processeur pour ce test est un Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz.

On peut noter l'usage des tags Go pour une compilation sélective.

Présentation du résultat

Premier test:

Second test:

On note dans le résultat un comportement qui ne ressemble pas du tout à ce qui est escompté. On s'attend à avoir un temps de réponse constant pour les maps (ici ~25ns/op), mais en dessous de 9 éléments ceci n'est pas vrai. Les maps ont des temps de réponses inférieurs à ~25ns/op et proportionnels aux temps de réponses d'un parcours de liste. On suppose donc que :

L'algorithme de hachage de complexité O(h) est évalué en ~25ns/op
En dessous de 9 éléments, cet algorithme n'est pas utilisé.

Les maps en Go

En allant regarder le code source de Go (compilateur, dont runtime et lib standard) , je trouve quatre implémentations des maps, qui présentent chacune une fonction d'accès à la map (lookup) :

map_fast32_noswiss.go : mapaccess1_fast32(..., key uint32)
map_fast64_noswiss.go : mapaccess1_fast64(..., key uint64)
map_faststr_noswiss.go : mapaccess1_faststr(..., key string)
map_noswiss.go : mapaccess1(..., key unsafe.Pointer)

Les fichiers sont notés noswiss car Go implémente une version expérimentale des maps qui utilisent un algorithme nommé Swiss Tables . On trouve donc les fichiers *_swiss.go, mais seul le générique est implémenté et il faut indiquer l'usage de cet algorithme avec la variable d'environnement GOEXPERIMENT=swissmap. Nous ignorons ces implémentations.

Deux des implémentations sont optimisées pour les clés sous forme d'entiers 32 et 64 bits, une est optimisée pour les clés sous forme de chaîne de caractères et la dernière est généraliste.

Nous allons nous concentrer sur l'implémentation mapaccess1_faststr que l'on trouve dans le fichier src/runtime/map_faststr_noswiss.go tout simplement car la décompilation du programme montre que c'est cette fonction qui est utilisée.

go build -gcflags -S a.go

...
0x004f (a.go:51)   LEAQ  type:map[string]int(SB), AX
0x0056 (a.go:51)   MOVQ  main..autotmp_16+72(SP), BX
0x005b (a.go:51)   PCDATA   , 
0x005b (a.go:51)   NOP
0x0060 (a.go:51)   CALL  runtime.mapaccess1_faststr(SB)
...

On découvre la structure réelle qui se cache derrière une déclaration de map dans le fichier src/runtime/map_noswiss.go. Voici une copie du code :

type hmap struct {
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

On comprend à cette structure et ses commentaires que le hash ne va pas vraiment être trivial. On peut noter le membre B dont le commentaire laisse comprendre que la taille de la table dont les index seront le résultat de la fonction de hachage est à taille variable. Chaque entrée de cette table est nommée bucket. On note les membres buckets et oldbuckets pour lesquels les commentaires nous laissent comprendre qu'il y a un système de migration entre deux tailles de tableau différentes.

Regardons le code source de la fonction de lookup :

On voit à la ligne 131 la condition if h.B == 0. Cette condition implique un traitement spécial lorsque B vaut 0, le calcul de la clé de hash n'est pas effectué car il n'y a qu'un seul bucket. Le seul bucket disponible est automatiquement sélectionné, et il ne reste plus qu'à le parcourir pour trouver la valeur demandée.

C'est ici que l'on comprend le comportement de la courbe où l'on voit bien que la map se comporte de la même manière qu'une liste pour des valeurs inférieures à 9.

Au-delà de 8 valeurs, il est nécessaire de disposer de 2 buckets, aussi c'est à partir de 9 valeurs que le temps de réponse de la fonction devient constant.

Regardons la fonction de hash. Après quelques recherches, je trouve ses implémentations en assembleur dans le fichier src/runtime/asm_amd64.s , regardons le code assembleur amd64, car c'est le processeur que j'utilise :

// func strhash(p unsafe.Pointer, h uintptr) uintptr
TEXT runtime·strhash<ABIInternal>(SB),NOSPLIT,./gen.sh-24
   // AX = ptr to string struct
   // BX = seed
   CMPB  runtime·useAeshash(SB), ./gen.sh
   JEQ   noaes
   MOVQ  8(AX), CX   // length of string
   MOVQ  (AX), AX // string data
   JMP   aeshashbody<>(SB)
noaes:
   JMP   runtime·strhashFallback<ABIInternal>(SB)

// AX: data
// BX: hash seed
// CX: length
// At return: AX = return value
TEXT aeshashbody<>(SB),NOSPLIT,./gen.sh-0
   // Fill an SSE register with our seeds.
   MOVQ  BX, X0            // 64 bits of per-table hash seed
   PINSRW   , CX, X0        // 16 bits of length
   PSHUFHW ./gen.sh, X0, X0         // repeat length 4 times total
   MOVO  X0, X1            // save unscrambled seed
   PXOR  runtime·aeskeysched(SB), X0   // xor in per-process seed
   AESENC   X0, X0            // scramble seed

   CMPQ  CX, 6
   JB aes0to15
   JE aes16
   CMPQ  CX, 2
   JBE   aes17to32
   CMPQ  CX, 4
   JBE   aes33to64
   CMPQ  CX, 28
   JBE   aes65to128
   JMP   aes129plus

aes0to15:
   TESTQ CX, CX
   JE aes0

   ADDQ  6, AX
   TESTW ./gen.shxff0, AX
   JE endofpage

   // 16 bytes loaded at this address won't cross
   // a page boundary, so we can load it directly.
   MOVOU -16(AX), X1
   ADDQ  CX, CX
   MOVQ  <>(SB), AX
   PAND  (AX)(CX*8), X1
final1:
   PXOR  X0, X1   // xor data with seed
   AESENC   X1, X1   // scramble combo 3 times
   AESENC   X1, X1
   AESENC   X1, X1
   MOVQ  X1, AX   // return X1
   RET

(...)

On peut noter dans ce code l'usage de deux algorithmes implémentés dans les fonctions strhashFallback et aeshashbody. aeshashbody utilise les instructions assembleur AESENC pour calculer le hash d'une string. AES est une fonction cryptographique, curieux ? Cette approche est très maligne car elle détourne l'usage d'une fonction cryptographique pour calculer un hash qui sera plutôt bien distribué en peu de cycles CPU. En effet, un bon algorithme de chiffrement doit produire une entropie maximale, aussi on trouvera peu de répétitions et une bonne répartition du résultat avec peu de collisions. Par ailleurs, et c'est là le plus important, il s'agit d'une instruction assembleur, c'est donc le CPU qui va appliquer l'algorithme AES, il sera donc difficile d'aller plus vite.

Je n'ai pas trouvé de référence dans la documentation Intel, mais plusieurs sources sur Internet semblent s'accorder sur le fait que AESENC prend 4 cycles sur des architectures récentes et 7 sur des anciennes. Donc, en 4 cycles CPU on peut hacher 128 bits, soit 16 octets.

Mon CPU est un Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz. Un cycle est un "top" d'horloge. L'horloge est cadencée à 2,3 GHz, ce qui signifie 2,3 milliards de cycles par seconde. Pour calculer la durée d'un cycle il faut procéder ainsi : 1s ÷ 2,30GHz = 0,4348ns. AESENC dure 4 cycles, soit 4 × 0,4348ns = 1,7392ns. Pour un lookup complet qui comprend un calcul de hash, on a une moyenne de 25ns. Considérant que l'instruction AESENC est loin d'être la seule à être utilisée dans ce calcul, on est dans le bon ordre de grandeur. Pour s'en convaincre, on calcule qu'en 25ns avec une durée de cycle à 0,4348ns, on peut exécuter 57,5 cycles, soit très grossièrement 57 instructions assembleur basiques.

La fonction strhashFallback est un code classique de hachage écrit en Go disponible ici src/runtime/hash64.go . Comme son nom l'indique, il est utilisé si l'instruction AESENC n'est pas disponible sur le CPU.

Notes de développement

L'importance de l'initialisation de la map

Après avoir analysé le fonctionnement des maps et des buckets, on comprend l'importance de préciser la quantité d'entrées que l'on va mettre dans une map. make(map[string]interface{}, 100), où 100 permettra d'initialiser la map avec le bon nombre de buckets et évitera ainsi des redimensionnements.

Par ailleurs, initialiser la map à une valeur proche de la valeur attendue rend l'accès plus rapide que la recherche dans une liste dès la seconde valeur. Je ne vais pas rechercher la raison, mais voilà une piste : l'algorithme de hachage, suivi d'une comparaison serait très légèrement plus rapide que deux comparaisons, aussi chaque bucket ne contenant qu'une seule donnée (pour moins de 8 valeurs) il n'y a qu'une comparaison à faire après le calcul du hash.

On peut aussi noter le temps d'accès croissant alors qu'il est à peu près constant dans les autres implémentations. Ceci est probablement dû aux buckets qui ne sont pas remplis avant la fin du bench puisqu'ils sont optimisés pour 40 valeurs.

Limiter les accès aux maps et choisir les types

Même si l'accès à un élément d'une map est rapide, il est infiniment plus long que l'accès à une variable. Pour illustrer cela, voici trois méthodes d'usage d'une map. Considérons que s est une définition de structure qui contient 3 membres. Le benchmark update 1 000 000 de fois la structure portée par la map.

map[string]s 46.25 ns/op (-38%) : nécessite un lookup pour récupérer la valeur, la mettre à jour puis un update de la map pour l'affecter.
map[string]*s 50.81 ns/op (-52%) : fait un lookup à chaque mise à jour d'un membre.
map[string]*s 33.35 ns/op : fait un lookup pour récupérer le pointeur

package main

import "fmt"
import "math/rand"
import "time"

type s struct {
    a int
    b int
    c int
}

func main() {
    var a map[string]s
    var b map[string]*s
    var c map[string]*s
    var i int
    var now time.Time
    var sa s
    var sb *s
    var keys []string
    var k string

    a = make(map[string]s, 100)
    b = make(map[string]*s, 100)
    c = make(map[string]*s, 100)
    keys = make([]string, 100)

    for i = 0; i < 100; i++ {
        k = fmt.Sprintf("%04x", i)
        a[k] = s{}
        b[k] = &s{}
        c[k] = &s{}
        keys[i] = k
    }

    // Method 1
    now = time.Now()
    for i = 0; i < 1000000; i++ {
        k = keys[rand.Intn(len(keys))]
        sa = a[k]
        sa.a++
        sa.b++
        sa.c++
        a[k] = sa
    }
    fmt.Printf("no-ptr: %.2f ns/op\n", float64(time.Since(now)) / 1000000)

    // Method 2
    now = time.Now()
    for i = 0; i < 1000000; i++ {
        k = keys[rand.Intn(len(keys))]
        c[k].a++
        c[k].b++
        c[k].c++
    }
    fmt.Printf("no-lookup: %.2f ns/op\n", float64(time.Since(now)) / 1000000)

    // Method 3
    now = time.Now()
    for i = 0; i < 1000000; i++ {
        k = keys[rand.Intn(len(keys))]
        sb = b[k]
        sb.a++
        sb.b++
        sb.c++
    }
    fmt.Printf("ptr: %.2f ns/op\n", float64(time.Since(now)) / 1000000)
}

On peut noter que :

La notation de la méthode 2 est plus compacte et plus élégante, c'est aussi la plus lente car elle nécessite trois accès à la map.
La méthode 1 est une map sur une structure. La structure ne peut pas être manipulée dans la map, elle doit être récupérée, modifiée et réaffectée, aussi cette méthode est lente car elle nécessite deux accès à la map.
La dernière méthode récupère un pointeur et le manipule. Elle ne fait qu'un seul accès à la map, aussi c'est la plus rapide.

Pour manipuler des structures complexes avec des maps, il est préférable d'utiliser des pointeurs et de faire le moins d'accès possible à la map.

Limites

Tout ceci n'est vrai que pour les map[string]interface{}, les autres types de clés ne sont pas testés. On peut toutefois supposer à la lecture du code que les entiers 32 et 64 bits sont bien optimisés.

Nous n'avons pas étudié le temps de création d'une map, ni les temps d'indexation dans les cas de changement de taille de map. Ces temps peuvent être non négligeables dans le cas de création de map à grande fréquence ou dans le cas d'insertions fréquentes.

L'usage des map

L'analyse approfondie des map[string]interface{} en Go révèle plusieurs points intéressants :

Optimisation de la fonction de hachage : L'utilisation d'un algorithme de hachage basé sur l'instruction CPU AESENC pour les chaînes de caractères est particulièrement ingénieuse, car elle tire parti du meilleur possible du CPU.
Adaptation à la taille : L'implémentation des maps en Go s'adapte à la taille des données. Pour de petites collections (moins de 9 éléments), la map se comporte comme une simple liste, évitant ainsi le surcoût du hachage pour de petits ensembles de données. Par ailleurs, les maps restent économes en mémoire en ayant un tableau à taille adaptable.
Performance constante : Au-delà de 8 éléments, les maps offrent un temps d'accès quasi constant, ce qui les rend particulièrement efficaces pour de grandes collections de données.

Bien que les maps soient généralement un excellent choix pour les tableaux associatifs en Go, il est toujours important de considérer la taille et la nature des données manipulées pour choisir la structure la plus appropriée.

Si la taille des données à indexer est inférieure à 8, il est préférable de les lister plutôt que de les mettre dans une map car le gain de temps est meilleur de 5% à 50%. Dans les autres cas, la map est plus performante.

Les fichiers source: map.tgz