ART Arbres Préfixes : Optimisation de la Mémoire et du Cache

Optimisation des arbres de préfixes : de 825 Mo à 18 Mo pour la complétion automatique

Un arbre de préfixes (trie) pour rechercher 50 000 commandes consommait 825 Mo de mémoire et était 8 fois plus lent qu'une table de hachage (4,8 millions de cycles contre 600 000). Chaque nœud faisait 2 064 octets avec un tableau de 256 pointeurs, provoquant fréquemment des pertes de cache lors des recherches.

Le benchmark perf stat a révélé 125 000 pertes de cache contre seulement 18 000 pour la table de hachage. La recherche d'une chaîne de 5 caractères déclenchait 5 pertes de cache car chaque nœud ne tenait pas dans une seule ligne de cache.

Structure des nœuds et utilisation mémoire

Implémentation standard :

typedef struct trie_node {
    struct trie_node *children[256];  // 2048 octets
    void *value;                      // 8 octets
    bool is_end;                      // 1 octet
    // Total : 2064 octets
} trie_node_t;

Pour un jeu de données de 50 000 commandes (longueur moyenne de 8 caractères), environ 400 000 nœuds étaient nécessaires — soit 825 Mo contre seulement 1,2 Mo pour une table de hachage, soit une différence de 687 fois.

Arbres compacts : compression des chaînes

Solution : arbres compacts (tries de Patricia), où les chaînes de nœuds à enfant unique sont compressées en préfixes. Les nœuds stockent des chaînes de préfixe au lieu de caractères individuels.

typedef struct radix_node {
    char *prefix;
    int prefix_len;
    struct radix_node *children[256];
    void *value;
} radix_node_t;

Algorithme de recherche :

void* radix_search(radix_node_t *node, const char *key) {
    while (node) {
        int i = 0;
        while (i < node->prefix_len && key[i] == node->prefix[i]) {
            i++;
        }
        if (i < node->prefix_len) return NULL;
        if (key[i] == '\0') return node->value;
        node = node->children[(unsigned char)key[i]];
        key += i + 1;
    }
    return NULL;
}

Résultat : la mémoire est tombée à 330 Mo, les cycles à 2,4 millions, et les pertes de cache à 6,8 — une accélération de 2 fois.

Arbres radicaux adaptatifs (ART)

Le problème subsistait : 98 % des tableaux de 256 pointeurs étaient vides. Solution : nœuds adaptatifs basés sur le nombre d'enfants.

• Node4 (1–4 enfants) : 40 octets
• Node16 (5–16 enfants) : 152 octets
• Node48 (17–48 enfants) : 640 octets
• Node256 (49+ enfants) : 2048 octets

Stratégie d'expansion : Node4 → Node16 → Node48 → Node256 lorsque les limites sont dépassées.

Taille moyenne du nœud : 40–152 octets contre 2048 — économie de mémoire de 10 à 50 fois.

Résultats des benchmarks

Comparaison sur 1 million de recherches sur 50 000 commandes :

| Structure | Mémoire | Cycles | Pertes de cache | Accélération |

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

| Trie | 825 Mo | 4 800 | 12,5 | 1× |

| Radix | 330 Mo | 2 400 | 6,8 | 2× |

| ART | 18 Mo | 1 200 | 3,2 | 4× |

| Hash | 1,2 Mo | 600 | 1,8 | 8× |

L'ART est 45 fois plus compact qu'un trie standard ; les nœuds Node4/Node16 tiennent dans 1 à 2 lignes de cache.

Cas d'utilisation des arbres de préfixes

Utilisez l'ART quand vous avez besoin d'opérations de préfixe :

• Complétion automatique : parcours du sous-arbre en O(k + m), où m est le nombre de correspondances. Les tables de hachage exigent un balayage complet.
• Routeur IP : correspondance du préfixe le plus long par bits d'adresse.
• Vérification orthographique : recherche via distance d'édition utilisant les préfixes.
• Tableaux creux : comme utilisé dans le noyau Linux (cache de pages, IDR, XArray).

Évitez pour les recherches exactes, les petits jeux de données (< 1 000 éléments) ou les chaînes sans préfixes communs.

Arbres compacts dans le noyau Linux

Le noyau utilise radix_tree_node avec 64 emplacements (6 bits par niveau). Pour un index 32 bits, cela fait 6 niveaux — environ 6 pertes de cache contre 32 pour un arbre binaire équilibré.

Avantages :

• Support des opérations sur plage
• Complexité prédicable O(log₆₄ n)
• Efficace pour les données creuses

Points clés

• Les tries standards utilisent 687 fois plus de mémoire à cause des tableaux de 256 pointeurs
• L'ART réduit la mémoire à 18 Mo et les pertes de cache à 3,2 grâce à des nœuds adaptatifs
• Utilisez pour les requêtes de préfixe ; les tables de hachage gagnent aux recherches exactes
• Les arbres compacts compressent les chaînes, offrant une accélération de 2 fois
• Le noyau Linux les utilise pour les tableaux creux et l'allocation d'ID

— Editorial Team