Tables de hachage et conflits de cache : benchmarks

Tables de hachage : Éviter les ratés de cache dans les projets réels

Les tables de hachage promettent des accès en O(1), mais en pratique, elles sont souvent surpassées par des parcours linéaires de tableaux à cause des ratés de cache. Dans la table des symboles d'un optimiseur de compilateur avec 500 entrées réparties sur 1024 seaux, nous avons observé 1,2 million de ratés de cache sur 5 millions d'instructions. Passer à un simple tableau a accéléré les choses 3 fois. Le coupable ? Des motifs d'accès qui évinculent les lignes de cache.

Implémentation de base et collisions

Une table de hachage simple à mappage direct ne scale pas à cause des collisions. Voici le code de base :

typedef struct {
    char *key;
    int value;
} entry_t;

#define TABLE_SIZE 1024

entry_t *table[TABLE_SIZE];

int hash(const char *key) {
    unsigned int h = 0;
    while (*key) {
        h = h * 31 + *key++;
    }
    return h % TABLE_SIZE;
}

L'insertion et la recherche nécessitent des allocations mémoire et des comparaisons de chaînes, mais sans gestion des collisions, la table est inutilisable.

Stratégies de résolution des collisions

Une collision se produit quand des clés différentes hachent vers le même indice. Deux approches principales :

Chaînage

Une liste chaînée par seau disperse les accès mémoire :

typedef struct entry {
    char *key;
    int value;
    struct entry *next;
} entry_t;

void insert(const char *key, int value) {
    int index = hash(key);
    entry_t *entry = malloc(sizeof(entry_t));
    entry->key = strdup(key);
    entry->value = value;
    entry->next = table[index];
    table[index] = entry;
}

La recherche suit les pointeurs, chaque étape risquant un raté de cache.

Adressage ouvert

Le sondage linéaire dans un tableau contigu préserve la localité :

typedef struct {
    char *key;
    int value;
    int occupied;
} entry_t;

entry_t table[TABLE_SIZE];

void insert(const char *key, int value) {
    int index = hash(key);
    while (table[index].occupied) {
        index = (index + 1) % TABLE_SIZE;
    }
    table[index].key = strdup(key);
    table[index].value = value;
    table[index].occupied = 1;
}

L'accès séquentiel minimise les ratés : le premier chargement de ligne de cache couvre 7–8 éléments.

| Stratégie | Ratés de cache par recherche | Localité |

|----------------|------------------------------|----------|

| Chaînage | 3–10 (pour longueur de chaînon 3) | Mauvaise |

| Sondage | 1–2 | Bonne |

Analyse des ratés de cache

Dans le chaînage, chaque nœud nécessite un chargement séparé : seau (1 raté), entrée (2–3), pointeur next (1). Total : jusqu'à 10 ratés.

Le sondage charge une ligne de cache entière, donc les sondages suivants touchent le cache. C'est 3–5 fois moins de ratés.

Benchmark : 1000 insertions, 10 000 recherches (facteur de charge 0,5, 2048 seaux) :

• Chaînage : 450k cycles insertion, 2,1M cycles recherche, 45k ratés
• Sondage : 180k cycles insertion, 650k cycles recherche, 12k ratés

Le sondage est 3,2 fois plus rapide au global.

Qualité de la fonction de hachage

Une mauvaise fonction comme key[0] % size regroupe les clés par premier caractère, avec une longueur moyenne de chaînon de 38,5.

FNV-1a distribue uniformément :

uint32_t fnv1a_hash(const char *key) {
    uint32_t hash = 2166136261u;
    while (*key) {
        hash ^= (uint8_t)*key++;
        hash *= 16777619u;
    }
    return hash;
}

Fonctions de hachage spécialisées :

• Pour entiers : return key;
• Pour pointeurs : (uintptr_t >> 3) * 2654435761u

Benchmark : FNV-1a donne une longueur moyenne de chaînon de 0,98 contre 38,5 pour une mauvaise fonction.

Facteur de charge et redimensionnement

Facteur de charge = entrées / seaux.

• Chaînage : >1,0 OK mais dégrade
• Sondage : Maintenir <0,7–0,8

À 0,9 : 10,5 sondages moyen ; à 0,95 : 20,5.

Redimensionner à 0,7 (doubler la taille, amorti O(1)) :

void insert(const char *key, int value) {
    if (count >= table_size * 0.7) {
        resize_table();
    }
    // insert
}

Structure optimisée pour le cache

• Adressage ouvert + taille puissance de 2 (hach & masque au lieu de %).
• Empaquetage serré :

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12 octets, 5 par ligne de cache

• Clés/valeurs séparées pour gros payloads.
• Sondage SIMD (AVX2 vérifie 8 éléments d'un coup).

Hachage Robin Hood

Variante de sondage : Lors de l'insertion, "voler" à des éléments avec distance de sondage inférieure.

Exemple : key4 (hach=1) déplace key2 (dist=1 > 0), équilibrant les longueurs de sondage. Minimise la variance des sondages.

Points clés

• Adressage ouvert avec sondage linéaire est 3–5 fois plus efficace pour le cache que le chaînage.
• Bonne fonction de hachage (FNV-1a) réduit les collisions 40 fois.
• Facteur de charge <0,7 + redimensionnement par doublement = amorti O(1).
• Empaquetage serré + taille puissance de 2 minimisent les ratés.
• Hachage Robin Hood optimise la distribution des sondages.

— Editorial Team