Arbres binaires de recherche : O(log n) et performances du cache

Arbres Binaires de Recherche en Pratique : Pourquoi O(log n) n'est pas toujours rapide

Dans le domaine de l'informatique théorique, les Arbres Binaires de Recherche (ABR) et leurs variantes auto-équilibrées, comme les arbres Rouge-Noir, sont souvent considérés comme la référence en matière d'efficacité pour les structures de données dynamiques. Leur complexité asymptotique de O(log n) pour les opérations d'insertion, de recherche et de suppression semble idéale. Cependant, en pratique, dans les conditions des architectures de processeurs modernes avec des mémoires cache multi-niveaux, la performance des ABR peut être nettement inférieure à celle de structures plus simples, même si elles possèdent une complexité théorique similaire. Cet article explore les raisons de cette divergence et propose des recommandations pratiques pour le choix des structures de données.

Une Chute de Performance Inattendue pour un Compilateur

Imaginez un scénario : un compilateur passe 60 % de son temps non pas à l'analyse syntaxique ou à la génération de code, mais à la recherche de symboles dans une table. Pour les systèmes embarqués avec des milliers de symboles, c'est inacceptable. La table des symboles, qui stocke les noms de variables, les fonctions et les types, était implémentée à l'aide d'un arbre Rouge-Noir — un ABR auto-équilibré classique. Théoriquement, O(log n) aurait dû garantir une vitesse élevée.

Cependant, le profileur perf a révélé une image préoccupante :

$ perf stat -e cache-misses,instructions ./compiler test.c
  Performance counter stats:
    2,847,234 cache-misses
    8,500,000 instructions

Près de 2,8 millions de cache misses (défauts de cache) pour 8,5 millions d'instructions — c'est un défaut de cache pour trois instructions. Une telle métrique indique de graves problèmes d'accès mémoire. À titre expérimental, l'arbre Rouge-Noir a été remplacé par un tableau trié utilisant la recherche binaire, qui a également une complexité théorique de O(log n). Le résultat fut stupéfiant : le compilateur a été accéléré par un facteur de 3.

Comment deux structures de données avec une complexité asymptotique identique peuvent-elles présenter des performances aussi radicalement différentes ? La réponse réside dans les spécificités du fonctionnement de la mémoire cache.

Enquête sur les Causes : Mémoire Cache et Défauts

Une analyse détaillée à l'aide de perf a confirmé les soupçons. La comparaison entre l'arbre Rouge-Noir et le tableau trié a révélé une différence critique dans le comportement du cache :

# Red-Black Tree Version
$ perf stat -e cache-references,cache-misses,cycles ./compiler_rbtree test.c
  Performance counter stats:
    3,247,832  cache-references
    2,847,234  cache-misses  (87.7% miss rate)
   24,000,000  cycles

# Sorted Array Version
$ perf stat -e cache-references,cache-misses,cycles ./compiler_array test.c
  Performance counter stats:
    1,123,456  cache-references
      234,567  cache-misses  (20.9% miss rate)
    8,000,000  cycles

L'arbre Rouge-Noir a présenté un taux de défauts de cache de 87,7 %, tandis que le tableau trié n'affichait que 20,9 %. Sur les systèmes RISC-V, chaque défaut de cache peut coûter jusqu'à 100 cycles CPU. Cela signifie que l'arbre Rouge-Noir passait la majeure partie de son temps inactif, à attendre les données de la mémoire principale, plutôt qu'à effectuer des calculs.

Théorie vs. Pratique : Le Problème de la Chasse aux Pointeurs

Les manuels sur les structures de données mettent souvent en avant les ABR pour leurs performances équilibrées sur diverses opérations. Ils garantissent O(log n) pour l'insertion, la recherche et la suppression, et maintiennent les éléments dans un ordre trié. Les variantes équilibrées, comme les arbres AVL ou les arbres Rouge-Noir, empêchent la dégradation des performances à O(n) dans le pire des cas, assurant une hauteur logarithmique.

Cependant, ces avantages théoriques ne tiennent pas compte de la hiérarchie de la mémoire des ordinateurs modernes. Le problème fondamental avec les ABR réside dans la chasse aux pointeurs (pointer chasing). Chaque parcours d'un nœud à son enfant (gauche ou droit) implique de suivre un pointeur vers une adresse mémoire arbitraire. Cela réduit drastiquement l'efficacité de l'utilisation du cache.

Tableau Trié : Localité des Données

Lors de l'utilisation d'un tableau trié, les éléments sont stockés de manière contiguë en mémoire. Par exemple :

Memory: [10][20][30][40][50][60][70][80]
          ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
       0x1000 ...contiguously, cache-friendly...

Lorsque le processeur accède à array[4], il charge un bloc mémoire, par exemple de 64 octets, dans une ligne de cache. Ce bloc inclut array[4] et plusieurs éléments adjacents (par exemple, array[5], array[6]). Les accès ultérieurs à ces éléments adjacents seront des succès de cache (cache hits), ne prenant qu'un seul cycle CPU.

Arbre Binaire de Recherche : Dispersion des Données

Dans un ABR, chaque nœud est généralement alloué dynamiquement (par exemple, via malloc()) et peut être situé à une position arbitraire dans le tas. Cela conduit à une fragmentation de la mémoire :

       40 (@ 0x5000)
      /  \
    20    60 (@ 0x2000, @ 0x8000)
   /  \   /  \
  10  30 50  70 (@ 0x1000, @ 0x3000, @ 0x6000, @ 0x9000)

Lors d'une recherche dans un ABR, chaque parcours de pointeur nécessitera probablement l'accès à une région mémoire complètement nouvelle qui ne se trouve pas dans la ligne de cache actuelle. Cela entraîne des défauts de cache (cache misses), occasionnant une latence de centaines de cycles CPU jusqu'à ce que les données soient chargées depuis la mémoire principale.

Considérons la recherche de la valeur 70 :

Tableau Trié (Recherche Binaire) :

* Étape 1 : Accès à l'élément médian [40] @ 0x1020. DÉFAUT DE CACHE (100 cycles). Une ligne de cache contenant [30][40][50][60] est chargée.

* Étape 2 : Accès à [60] @ 0x1030. SUCCÈS DE CACHE (1 cycle).

* Étape 3 : Accès à [70] @ 0x1038. SUCCÈS DE CACHE (1 cycle).

* Total : ~102 cycles, 1 défaut de cache.

Arbre Binaire de Recherche :

* Étape 1 : Accès à la racine [40] @ 0x5000. DÉFAUT DE CACHE (100 cycles). Une ligne de cache à 0x5000 est chargée.

* Étape 2 : Parcours à droite, accès à [60] @ 0x8000. DÉFAUT DE CACHE (100 cycles). Adresse dans une ligne de cache différente.

* Étape 3 : Parcours à droite, accès à [70] @ 0x9000. DÉFAUT DE CACHE (100 cycles). Encore une nouvelle adresse.

* Total : ~300 cycles, 3 défauts de cache.

Les deux algorithmes effectuent le même nombre de comparaisons logiques, mais en raison des défauts de cache, l'ABR est significativement plus lent.

Comparaison des Performances et du Code

À titre d'illustration, voici des exemples de code pour la recherche et les résultats de benchmarks.

Recherche dans un ABR :

// Binary Search Tree Node
typedef struct bst_node {
    int key;
    void *value;
    struct bst_node *left;
    struct bst_node *right;
} bst_node_t;

void* bst_search(bst_node_t *root, int key) {
    while (root) {
        if (key == root->key) return root->value;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

Recherche dans un Tableau Trié :

typedef struct {
    int key;
    void *value;
} array_entry_t;

void* array_search(array_entry_t *arr, int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].key == key) return arr[mid].value;
        if (key < arr[mid].key) right = mid - 1;
        else left = mid + 1;
    }
    return NULL;
}

Des tests de 10 000 opérations de recherche aléatoires sur des ensembles de données de tailles différentes ont montré :

Ensemble de données : 1000 éléments

* ABR : 2400 cycles par opération de recherche

* Tableau trié : 800 cycles par opération de recherche

* Accélération : 3×

Ensemble de données : 10000 éléments

* ABR : 3200 cycles par opération de recherche

* Tableau trié : 1100 cycles par opération de recherche

* Accélération : 2.9×

Statistiques de défauts de cache perf :

ABR : 8,5 défauts par opération de recherche
Tableau trié : 2,1 défauts par opération de recherche

Le tableau trié démontre constamment une performance 3 fois supérieure. Les raisons en sont :

Disposition mémoire contiguë : Les éléments du tableau sont stockés dans un bloc contigu, ce qui est idéal pour le cache.
Utilisation efficace des lignes de cache : À chaque défaut, une ligne de cache entière (par exemple, 64 octets) est chargée, contenant plusieurs éléments du tableau à la fois, ce qui minimise les défauts futurs.
Prérécupération matérielle : Les processeurs modernes disposent de mécanismes de prérécupération matérielle (hardware prefetchers) qui reconnaissent les modèles d'accès séquentiels et chargent proactivement les données dans le cache, réduisant ainsi davantage les latences.

Les ABR ne bénéficient pas de ces avantages. Chaque déréférencement de pointeur lors d'une recherche peut entraîner un nouveau défaut de cache.

Surcharge Mémoire et Arbres Équilibrés

Au-delà des problèmes de cache, les ABR ont souvent une surcharge mémoire plus importante en raison du stockage des pointeurs.

Nœud d'ABR (système 64 bits, avec alignement) :

```c

struct bst_node {

int key; // 4 octets

void *value; // 8 octets

struct bst_node *left; // 8 octets

struct bst_node *right; // 8 octets

// Padding: 4 octets

};

// Total : 32 octets par élément

```

Élément de Tableau Trié (avec alignement) :

```c

struct array_entry {

int key; // 4 octets

void *value; // 8 octets

// Padding: 4 octets (pour l'alignement)

};

// Total : 16 octets par élément

```

Pour 1000 éléments, un ABR nécessite 32 Ko, tandis qu'un tableau en requiert 16 Ko. L'empreinte mémoire accrue des ABR signifie que moins de nœuds peuvent tenir dans le cache, ce qui exacerbe le problème des défauts de cache.

Beaucoup de développeurs croient que les arbres équilibrés (par exemple, Rouge-Noir ou AVL) résolvent tous les problèmes des ABR. Ils garantissent effectivement une hauteur d'arbre logarithmique, empêchant la dégradation en liste chaînée avec des données d'entrée défavorables. Les rotations de nœuds, utilisées pour maintenir l'équilibre, sont des opérations de mise à jour de pointeurs à faible coût. Cependant, ces mécanismes ne résolvent pas le problème fondamental du cache : les nœuds restent dispersés en mémoire.

Les défauts de cache pour l'arbre Rouge-Noir dans le compilateur se produisaient presque à chaque étape :

$ perf stat -e cache-misses,L1-dcache-load-misses ./compiler_rbtree test.c
  Performance counter stats:
    2,847,234 cache-misses
    2,654,123 L1-dcache-load-misses

Les arbres équilibrés résolvent les problèmes de pire cas algorithmiques, mais pas les limitations matérielles liées à la hiérarchie de la mémoire.

Quand Utiliser les Arbres Binaires de Recherche ?

Malgré les inconvénients décrits, les ABR ne sont pas inutiles. Il existe des scénarios où leur utilisation est justifiée et même préférable.

L'avantage principal des ABR se manifeste dans les situations avec des opérations d'insertion et de suppression fréquentes. Dans un tableau trié, ces opérations nécessitent le décalage d'un grand nombre d'éléments, conduisant à une complexité de O(n) :

Insertion dans un tableau trié : O(n)
Suppression d'un élément dans un tableau trié : O(n)

Pour les ABR, l'insertion et la suppression restent des opérations en O(log n), car elles ne nécessitent que la mise à jour de quelques pointeurs et éventuellement quelques rotations pour maintenir l'équilibre. Un benchmark de 1000 opérations d'insertion/suppression aléatoires montre :

Tableau trié : 12000 cycles/opération (en raison des décalages)
Arbre Rouge-Noir : 3500 cycles/opération
Accélération de l'ABR : 3,4×

Ainsi, si votre structure de données est en constante évolution (nombreuses insertions et suppressions) et que les opérations de recherche ne dominent pas en fréquence, les ABR (surtout les équilibrés) peuvent être un meilleur choix, malgré les problèmes potentiels de cache. Sinon, pour les ensembles de données statiques ou rarement modifiés où les opérations de recherche prévalent, les tableaux triés ou d'autres structures optimisées pour le cache (par exemple, les B-arbres) démontrent souvent des performances supérieures.

Points Clés à Retenir

O(log n) ne garantit pas une performance pratique rapide : La complexité asymptotique ne tient pas compte de l'impact de la hiérarchie de la mémoire et du cache.
Le problème de la chasse aux pointeurs : Les ABR souffrent d'une mauvaise localité des données, entraînant de nombreux défauts de cache et des latences élevées.
Avantages des tableaux triés : Le placement contigu des éléments assure une localité des données élevée, une utilisation efficace des lignes de cache et une prérécupération matérielle efficace.
Surcharge mémoire : Les ABR nécessitent plus de mémoire en raison du stockage des pointeurs, ce qui réduit encore l'efficacité du cache.
Les arbres équilibrés ne résolvent pas le problème du cache : Ils empêchent la dégradation de la hauteur mais n'améliorent pas la localité des données.
Utilisez les ABR pour les insertions/suppressions fréquentes : Si les opérations de modification des données l'emportent sur les recherches, les ABR peuvent être plus efficaces que les tableaux triés.

— Editorial Team