Static search trees : quand une bonne structure met la binary search à 40× dans les choux

Un article de 2024, revenu en tête de Hacker News aujourd'hui, montre comment un layout mémoire mieux pensé rend une structure statique 40× plus rapide qu'une binary search. Le vrai enseignement n'est pas le chiffre - c'est le raisonnement.

Cas concret : vous devez rechercher une clé dans un tableau trié de 100 millions d'entrées. Votre premier réflexe, appris en école, c'est la binary search - log₂(n) ≈ 27 comparaisons. Théoriquement optimal.

Sauf que… en 2026, sur un CPU moderne, la binary search est catastrophique. Pourquoi ? Parce que chaque comparaison lit une case dont l'adresse dépend du résultat précédent. Le processeur ne peut ni prédire, ni pré-charger, ni pipeliner. À chaque étape, il attend le cache miss (environ 100 cycles CPU, soit ~30 ns sur du DDR5 récent).

Ce que fait l'article

L'article « Static search trees: 40x faster than binary search » (2024, republié en tête de HN aujourd'hui) creuse exactement ce problème. La solution proposée est un B-tree statique - pas un B-tree dynamique de manuel de bases de données, mais une version optimisée pour la CPU :

• Layout Eytzinger (nom d'un généalogiste autrichien du XVIᵉ siècle qui a inventé un système de numérotation d'arbre) ou B-tree branchless : les fils d'un nœud sont contigus en mémoire.
• Nœuds calibrés sur une ligne de cache (typiquement 64 octets, soit 16 clés de 4 octets).
• Comparaisons SIMD (Single Instruction Multiple Data - une instruction qui traite plusieurs données à la fois) : dans un nœud, comparer les 16 clés en une seule instruction AVX2/AVX-512.
• Prefetch software : dès qu'on entre dans un nœud, on lance le pré-chargement (__builtin_prefetch) du nœud fils probable.

Résultat mesuré dans l'article : sur 100 millions d'entrées, la recherche descend d'environ 150 ns à 4 ns. Soit 40× plus rapide.

Ce qu'il faut retenir

La leçon n'est pas « la binary search est morte ». C'est que la complexité algorithmique classique (O log n) ignore la mémoire cache. Sur un CPU moderne, la structure qui minimise les cache misses bat presque toujours celle qui minimise les comparaisons.

Autres exemples que nous croisons dans nos projets :

• Hash maps « robin hood » (Emmanuel Goossaert, Google Abseil flat_hash_map) vs. std::HashMap classique.
• PDQ sort (Pattern-Defeating Quicksort, Orson Peters - utilisé par Rust slice::sort_unstable) vs. quicksort scolaire.
• Bloom filters avant lookups exacts pour éliminer les négatifs rapidement.
• Column-oriented storage (Parquet, ClickHouse) qui exploite les cache lines pour l'analytique.

À lire ensuite

• Le papier de Paul-Virak Khuong et Pat Morin (2015) : Array Layouts for Comparison-Based Searching - le socle académique de tout ce champ.
• « What Every Programmer Should Know About Memory » d'Ulrich Drepper (2007) - daté sur certains détails, mais le socle mental reste sain.
• Le crate Rust static-search-tree ou équivalent pour un exemple productif.

À retenir

Quand vous optimisez une hot loop, votre premier profiler à sortir n'est pas cachegrind - c'est perf stat -e cache-misses,cache-references sous Linux (ou Instruments sur macOS). C'est là que se joue la vraie perf en 2026. La théorie de la complexité vous dit ce qui est possible ; la mémoire cache vous dit ce qui est atteignable.