Votre diplôme en informatique est un mensonge

La recherche binaire, pilier fondamental de l'enseignement de l'informatique, est le champion incontesté des algorithmes de recherche. Chaque cours d'introduction et manuel de structures de données vante son élégance et son efficacité, la présentant comme la méthode optimale pour trouver un élément dans un tableau trié. Cet algorithme, profondément ancré dans la psyché du développeur, représente le sommet théorique de la performance de recherche.

Sa perfection théorique est indéniable, affichant une complexité temporelle enviable de O(log N). Cette notation Big O, pierre angulaire de l'analyse algorithmique, signifie que le temps nécessaire pour effectuer une recherche ne croît que de manière logarithmique avec la taille de l'entrée (N). Cela fait de la recherche binaire la référence en matière d'efficacité, prédisant des performances ultra-rapides même avec d'immenses ensembles de données. L'hypothèse sous-jacente, cependant, est que chaque accès mémoire coûte le même prix, une prémisse profondément ancrée dans son modèle mathématique.

Mais que se passe-t-il si cette théorie fondamentale, si méticuleusement enseignée et largement acceptée, vacille dans le creuset du matériel informatique réel ? Le professeur Daniel Lemire, informaticien, a récemment publié un benchmark prouvant que sur les processeurs modernes, la recherche binaire standard laisse une tonne de performance inexploitée. Cette révélation remet directement en question l'idée que sa complexité Big O se traduit automatiquement par une vitesse pratique supérieure.

Le goulot d'étranglement n'est pas le nombre de comparaisons, comme le suggère la théorie classique. Au lieu de cela, la latence mémoire apparaît comme le véritable inhibiteur de performance. Lorsqu'un ordinateur saute au milieu d'un grand tableau lors d'une recherche binaire, le CPU se bloque fréquemment pendant des centaines de cycles. Ce délai se produit en attendant qu'un cache miss soit résolu depuis la RAM, sapant fondamentalement les gains théoriques promis par O(log N).

Cette perspicacité critique révèle que les métriques de performance que nous avons apprises à l'école divergent souvent considérablement de l'exécution réelle sur les architectures informatiques contemporaines. Le modèle traditionnel, qui traite toutes les opérations mémoire de manière égale, ne tient pas compte de la nature hiérarchique des systèmes de mémoire modernes et des pénalités associées à l'accès aux données non contiguës.

Ce changement de paradigme force une réévaluation de ce que 'performance' signifie réellement dans un monde accéléré par le matériel. Notre compréhension de l'efficacité algorithmique doit maintenant intégrer la manière dont l'architecture informatique sous-jacente se comporte *réellement*, allant au-delà des prédictions mathématiques abstraites. Préparez-vous ; la définition de la recherche optimale est sur le point de changer, suggérant de nouvelles stratégies qui privilégient le parallélisme matériel plutôt que le simple nombre de comparaisons.

L'efficacité théorique de la recherche binaire, longtemps célébrée pour son nombre logarithmique de comparaisons, s'effondre sur les processeurs modernes. Le véritable goulot d'étranglement de la performance n'est pas le nombre de comparaisons qu'un CPU exécute, mais plutôt l'attente agonisante des données pour effectuer ces comparaisons. Ce changement fondamental dans l'architecture matérielle rend la notation Big O, qui suppose des coûts d'accès mémoire uniformes, une métrique trompeuse pour la performance réelle.

Les CPU modernes fonctionnent à des vitesses étonnantes, exécutant souvent des milliards d'instructions par seconde. Cependant, leur puissance de traitement brute dépasse fréquemment leur capacité à accéder rapidement aux données. Le coupable critique est la latence mémoire, le délai inhérent encouru lorsque le CPU demande des données qui ne sont pas immédiatement disponibles. Lorsqu'un processeur a besoin d'informations non présentes dans son cache local ultra-rapide, il subit un CPU stall, restant inactif pendant des centaines de cycles pendant qu'il récupère les données de la mémoire principale (RAM) beaucoup plus lente.

Imaginez un chef étoilé Michelin préparant un plat complexe. Le chef travaille à la vitesse de l'éclair, préparant les ingrédients avec une précision incroyable. Mais son efficacité chute s'il doit constamment attendre les fournitures. Imaginez que le chef ait besoin d'une épice spécifique et exotique, mais qu'au lieu de la prendre dans le réfrigérateur bien approvisionné à côté de lui, il doive envoyer un assistant à un entrepôt lointain de l'autre côté de la ville. Cette longue attente improductive, malgré le talent inégalé du chef, définit le véritable goulot d'étranglement.

Sur un ordinateur, ce scénario d'« entrepôt lointain » est un cache miss. Chaque fois qu'une recherche binaire traditionnelle « saute » vers un nouvel emplacement, souvent non contigu, au sein d'un grand tableau, elle déclenche fréquemment un cache miss. Le CPU doit alors faire une pause, parfois pendant des centaines de cycles d'horloge, en attendant que les données demandées voyagent de la RAM principale vers son cache local avant de pouvoir procéder à la comparaison suivante. Les récents benchmarks de Daniel Lemire démontrent de manière frappante que ces blocages accumulés l'emportent de loin sur les avantages théoriques de la minimisation du nombre de comparaisons. Il a prouvé que la recherche binaire standard laisse des performances significatives sur la table, en particulier sur le matériel x64 et ARM actuel, où elle peut être plus de 2 fois plus lente que les alternatives optimisées.

L'opération fondamentale de la recherche binaire, qui consiste à diviser répétitivement l'espace de recherche, génère intrinsèquement un modèle d'accès mémoire non séquentiel, presque aléatoire. L'algorithme calcule un indice de point médian, accède à cet emplacement mémoire, puis recalcule un nouveau point médian. Ce processus signifie que les requêtes mémoire successives sont souvent très éloignées, traversant de vastes régions de mémoire imprévisibles.

Les CPU modernes sont dotés de prefetchers sophistiqués – des composants matériels conçus pour anticiper et précharger les données dans une mémoire cache plus rapide. Ces prefetchers excellent à reconnaître et à exploiter les modèles d'accès mémoire linéaires et séquentiels. Si le code lit `array[0]`, puis `array[1]`, le prefetcher charge rapidement `array[2]`, `array[3]`, et les éléments suivants dans le cache, prêts à être utilisés immédiatement. Cela réduit considérablement la latence mémoire.

L'approche de la recherche binaire consistant à « sauter au milieu » déjoue cependant complètement ces systèmes de préchargement optimisés. Les accès mémoire erratiques empêchent le prefetcher de prédire de manière fiable les prochaines données requises. Il ne peut pas prévoir si l'algorithme accèdera ensuite à `array[N/4]` ou à `array[3N/4]`, et encore moins au byte spécifique.

Cet échec conduit directement à des cache misses fréquents et coûteux. Au lieu de trouver les données dans les caches L1 ou L2 ultra-rapides, le CPU doit souvent arrêter l'exécution, récupérant les données de la RAM principale beaucoup plus lente. Ce processus introduit des centaines de cycles d'horloge de latence pour chaque miss, éclipsant complètement l'avantage algorithmique théorique de la recherche binaire de moins de comparaisons.

Les récents benchmarks du scientifique informatique Daniel Lemire illustrent de manière frappante ce problème, prouvant que la recherche binaire traditionnelle laisse des performances significatives sur la table sur les processeurs modernes. Il démontre que le goulot d'étranglement n'est pas le nombre de comparaisons, mais la latence d'accès à la mémoire. Pour une exploration plus approfondie de ces benchmarks et de l'implémentation en C++, consultez l'article de blog séminal de Daniel Lemire, You can beat the binary search.

Contrastez cela avec une simple exploration linéaire. Bien que plus lente algorithmiquement avec une complexité en O(N), une exploration linéaire accède à la mémoire dans un ordre séquentiel parfait. Ce modèle est le rêve d'un préchargeur ; il charge efficacement des lignes de cache entières, garantissant que les données sont presque toujours disponibles.

Le professeur Daniel Lemire, informaticien, remet directement en question des décennies de sagesse conventionnelle concernant les algorithmes fondamentaux, en particulier le règne incontesté de la recherche binaire. Il soutient que les approches des manuels, optimisées pour une époque révolue de traitement séquentiel et d'accès mémoire uniforme, sont fondamentalement inadaptées au parallélisme massif et aux hiérarchies de mémoire complexes inhérents aux CPU modernes.

Lemire affirme que l'accent traditionnel mis sur la minimisation des comparaisons, bien que mathématiquement élégant, ignore de manière critique le véritable goulot d'étranglement du matériel contemporain : la latence mémoire. La stratégie de 'saut au milieu' de la recherche binaire standard génère des modèles d'accès mémoire très non séquentiels, entraînant des échecs de cache fréquents et coûteux qui peuvent bloquer le CPU pendant des centaines de cycles en attendant les données d'une RAM beaucoup plus lente. Ce modèle d'accès aléatoire va activement à l'encontre des mécanismes de préchargement des CPU modernes.

Son travail ne vise pas à réfuter l'efficacité théorique en O(log N) de la recherche binaire, mais plutôt à la faire évoluer pour les architectures actuelles et futures. Lemire préconise une approche sensible au matériel, réingénierant les algorithmes de recherche pour tirer parti des fonctionnalités contemporaines telles que les instructions Single Instruction, Multiple Data (SIMD) et le parallélisme au niveau de la mémoire. Ce changement de paradigme privilégie le débit et le mouvement efficace des données plutôt qu'un simple compte d'étapes de calcul, reconnaissant les véritables moteurs de performance du CPU.

Le billet de blog influent de Lemire du 27 avril 2026, intitulé de manière provocatrice "You can beat the binary search" (Vous pouvez battre la recherche binaire), a suscité d'importantes discussions au sein de la communauté informatique. Ses benchmarks convaincants, menés sur du matériel x64 et ARM moderne, y compris les processeurs Apple M4 et Intel Emerald Rapids, ont constamment démontré un gain de vitesse de plus de 2x par rapport à la recherche binaire traditionnelle, même dans des conditions de cache froid difficiles. Ce gain de performance indéniable souligne la nécessité critique de concevoir des algorithmes avec une compréhension intime du comportement réel du matériel aujourd'hui, plutôt que de se fier uniquement à des modèles théoriques abstraits.

L'algorithme "SIMD Quad" de Lemire repense fondamentalement la recherche, allant au-delà des comparaisons théoriques pour embrasser les capacités matérielles informatiques modernes. Il utilise une stratégie hybride sophistiquée, adaptant son approche en fonction de la taille du tableau pour maximiser l'efficacité et minimiser la latence mémoire. Cette conception assure des performances optimales sur une large gamme d'échelles de données.

Pour les très petits tableaux, spécifiquement ceux contenant moins de 16 éléments, l'algorithme opte pour une exploration linéaire directe. Cette approche apparemment basique est une optimisation délibérée ; elle évite la surcharge associée à des configurations algorithmiques plus complexes, qui s'avéreraient contre-productives pour de si petits ensembles de données. Au lieu de cela, une vérification séquentielle simple fournit le résultat le plus rapide.

Lorsqu'il s'agit de tableaux plus grands, la méthode de Lemire segmente astucieusement les données en blocs fixes et gérables de 16 éléments. Cette organisation basée sur des blocs constitue l'épine dorsale de son efficacité, permettant à l'algorithme de traiter des ensembles de données substantiels non pas comme un problème monolithique, mais comme une série de tâches plus petites et parallélisables. Cette segmentation est cruciale pour tirer parti de l'architecture CPU moderne.

La localisation de la valeur cible s'effectue ensuite via une stratégie de recherche multi-voies. L'algorithme effectue une interpolation quaternaire en base 4, identifiant intelligemment le bloc spécifique de 16 éléments où la position cible est la plus susceptible de se trouver. Cette étape réduit drastiquement l'espace de recherche, diminuant le nombre d'accès mémoire qui entraînent des échecs de cache coûteux.

Une fois que l'algorithme a identifié le bloc probable, il déploie toute la puissance des instructions SIMD (Single Instruction, Multiple Data). Les 16 éléments de ce bloc spécifique sont chargés dans un seul registre CPU. Le processeur compare ensuite simultanément chaque élément à la valeur cible en une seule opération parallèle, atteignant une vitesse inégalée au sein de ce segment de données localisé.

Les éléments qui ne s'intègrent pas parfaitement dans un bloc complet de 16 éléments font l'objet d'une recherche linéaire rapide et localisée. Cette stratégie complète surpasse constamment la recherche binaire traditionnelle, offrant un gain de vitesse de plus de 2x sur le matériel moderne x64 et ARM, y compris des plateformes comme les processeurs Apple M4 et Intel Emerald Rapids, en priorisant le parallélisme au niveau de la mémoire plutôt que de simples comptes de comparaisons.

La conception de Lemire repense fondamentalement la recherche, allant au-delà de la division stricte des données en deux de la recherche binaire. Sa méthode intègre une recherche par interpolation quaternaire en base 4, une technique sophistiquée qui accélère considérablement la phase initiale de la recherche. Au lieu de bissecter l'espace de recherche, cette approche le divise efficacement en quarts, en se concentrant sur les limites des blocs.

La recherche binaire traditionnelle fait une seule supposition, puis attend. L'algorithme de Lemire, cependant, utilise une stratégie multi-voies. Pour les tableaux plus grands, il segmente d'abord les données en blocs fixes de 16 éléments. La recherche quaternaire opère ensuite sur ces limites de blocs, spécifiquement le dernier élément de chaque bloc, pour localiser rapidement le bloc le plus susceptible de contenir la valeur cible. C'est une distinction cruciale, car elle permet un balayage initial plus large et plus efficace.

De manière cruciale, ce branchement multi-voies permet au CPU de l'ordinateur d'émettre plusieurs requêtes mémoire en parallèle. En évaluant jusqu'à quatre emplacements potentiels de fin de bloc simultanément, l'algorithme effectue un saut plus informé et plus profond. Les processeurs modernes excellent dans la gestion de multiples récupérations de données en attente, une capacité connue sous le nom de parallélisme au niveau de la mémoire. En superposant ces requêtes, l'algorithme de Lemire masque stratégiquement la latence inhérente à l'accès à la mémoire principale ; l'ordinateur ne reste pas inactif.

La recherche binaire, à l'inverse, fonctionne avec une dépendance strictement séquentielle. Elle doit attendre le résultat de sa seule récupération mémoire 'saut au milieu' avant de calculer le prochain point médian potentiel. Si cette récupération initiale entraîne un échec de cache, le CPU se bloque pendant des centaines de cycles, un goulot d'étranglement critique en termes de performances. Toute comparaison ultérieure dépend entièrement de cette opération mémoire précédente, souvent lente, créant une chaîne de dépendances sérielle.

Cette limitation séquentielle handicape la recherche binaire sur le matériel moderne, où la latence, et non les comparaisons, domine le temps d'exécution. L'approche quaternaire de Lemire contourne cela en récupérant proactivement des données pour plusieurs étapes potentielles suivantes, garantissant que le processeur a du travail à faire en attendant la mémoire distante. Le passage d'un accès mémoire unique et dépendant à l'émission de multiples requêtes parallèles transforme le goulot d'étranglement d'un blocage CPU en une opportunité d'exécution parallèle. Pour plus d'informations sur la conception d'algorithmes tenant compte du matériel, envisagez d'explorer des ressources comme Better Stack. Cette approche innovante démontre une compréhension profonde du comportement réel du matériel moderne.

Libérer le véritable parallélisme matériel est au cœur de l'avantage de performance de Lemire. Son algorithme « SIMD Quad » exploite le SIMD (Single Instruction, Multiple Data), une capacité fondamentale des CPU modernes conçus pour le traitement parallèle. Au lieu d'exécuter des opérations sur un élément de données à la fois, le SIMD permet à une seule instruction CPU d'opérer sur plusieurs points de données simultanément, transformant le travail séquentiel en une rafale d'activité concurrente.

Les processeurs modernes disposent de jeux d'instructions dédiés aux opérations SIMD. Sur l'architecture x64, ceux-ci incluent des extensions comme SSE2, AVX et AVX2, tandis que les puces basées sur ARM exploitent NEON. Ces jeux d'instructions fournissent des registres spécialisés, souvent de 128 ou 256 bits de large, capables de contenir plusieurs types de données plus petits. Par exemple, un registre de 128 bits peut stocker efficacement seize entiers de 8 bits, huit entiers de 16 bits ou quatre entiers de 32 bits.

L'algorithme de Lemire exploite magistralement cette capacité. Une fois que la recherche par interpolation quaternaire en base 4 identifie un bloc cible, elle ne procède pas à des comparaisons scalaires. Au lieu de cela, l'algorithme charge les 16 éléments de ce bloc identifié dans un unique registre SIMD large. Cette opération de mémoire unique récupère un bloc de données contigu, ce qui est très favorable au cache et évite les pénalités d'accès aléatoire qui affligent la recherche binaire traditionnelle.

La véritable magie se révèle ensuite. Avec les 16 éléments résidant dans un seul registre, une seule instruction SIMD effectue 16 comparaisons simultanément. Cela signifie qu'un CPU qui nécessiterait généralement 16 cycles distincts pour comparer chaque élément individuellement peut désormais obtenir le même résultat en un seul cycle. Ce gain d'efficacité spectaculaire, une accélération de près de 16x pour la phase de comparaison au sein d'un bloc, réduit profondément le temps de traitement global. C'est une attaque directe contre le goulot d'étranglement de la mémoire, exploitant la puissance parallèle brute et sous-utilisée inhérente au silicium de votre ordinateur. Lemire prouve que la compréhension des capacités de votre matériel est primordiale pour atteindre des performances algorithmiques optimales.

La recherche de Lemire apporte une preuve indéniable : son algorithme de recherche multi-voies accéléré par SIMD surpasse fondamentalement la recherche binaire traditionnelle sur les processeurs modernes. Des benchmarks menés sur du matériel de pointe, y compris la puce M4 d'Apple et les processeurs Emerald Rapids d'Intel, révèlent une dure réalité pour la sagesse conventionnelle. Ces plateformes contemporaines, représentatives du calcul haute performance d'aujourd'hui, ont servi de creuset pour cette réévaluation.

À travers de nombreux tests, la méthode de Lemire a constamment atteint plus d'une accélération de 2x par rapport à l'implémentation standard de la recherche binaire. Ce n'est pas une amélioration marginale ; cela représente un bond générationnel profond en matière d'efficacité de recherche, remettant directement en question des décennies de pédagogie en informatique. Les résultats ont été robustes et reproductibles sur des ensembles de données et des tailles de tableaux variés, validant les principes de conception axés sur le matériel.

De manière cruciale, ces gains spectaculaires ne dépendaient pas de conditions optimales. Même avec un cache froid, représentant un scénario du pire où le CPU de l'ordinateur récupère fréquemment des données directement de la RAM plus lente, l'algorithme de Lemire a maintenu son avance significative. Cela démontre sa résilience aux goulots d'étranglement de latence mémoire qui paralysent la recherche binaire traditionnelle, prouvant son efficacité même face à des modèles d'accès mémoire imprévisibles.

Les performances ont encore grimpé avec un cache chaud. Ici, les données fréquemment accédées résident dans la mémoire CPU plus rapide, permettant à l'algorithme d'exploiter pleinement son parallélisme au niveau de la mémoire et ses instructions SIMD. Par exemple, sur la plateforme Intel Emerald Rapids avec un cache chaud, le nouvel algorithme a terminé en moins de la moitié du temps de son homologue conventionnel. La cohérence sur diverses architectures modernes – ARM-based Apple M4 et x64 Intel Emerald Rapids – souligne les avantages fondamentaux de l'algorithme, prouvant sa supériorité au-delà des benchmarks théoriques et dans les applications du monde réel.

La recherche révolutionnaire de Lemire va bien au-delà de l'optimisation d'une simple fonction de recherche ; elle exige une réévaluation fondamentale de la manière dont les développeurs de logiciels et les informaticiens abordent la performance. Pendant des décennies, la notation Big O a régné en maître, offrant d'élégantes garanties de complexité théorique. Mais sur les processeurs modernes, cette abstraction mathématique diverge de plus en plus des performances réelles mesurées. L'hypothèse selon laquelle chaque accès mémoire coûte le même prix, centrale à l'analyse Big O, est un mythe total, en particulier lorsqu'il s'agit de grands ensembles de données.

Comprendre l'architecture hardware n'est plus un luxe optionnel pour les travaux critiques en performance – c'est une exigence fondamentale. Les CPUs pénalisent notoirement les sauts de mémoire aléatoires, précisément ce que l'approche de « saut au milieu » de la recherche binaire traditionnelle crée. Ces modèles d'accès non séquentiels déclenchent fréquemment des défauts de cache coûteux, bloquant le CPU pendant des centaines de cycles en attendant les données de la RAM plus lente. Cette latence mémoire, et non le nombre de comparaisons, apparaît comme le goulot d'étranglement dominant pour les applications du monde réel.

Cette déconnexion croissante entre l'efficacité théorique et l'exécution réelle exige un nouvel état d'esprit dans l'industrie. Les développeurs doivent dépasser la conception d'algorithmes purement logiques et adopter la conception d'algorithmes hardware-aware. Ce paradigme priorise la manière dont les données sont méticuleusement organisées en mémoire, comment elles sont accédées, et comment les capacités parallèles inhérentes au CPU – comme les instructions Single Instruction, Multiple Data (SIMD) – peuvent être exploitées efficacement. L'algorithme « SIMD Quad » de Daniel Lemire en est un excellent exemple de cette philosophie en action.

Considérez les profondes implications pratiques : concevoir des algorithmes qui tiennent explicitement compte des cache lines, de l'memory alignment et des caractéristiques spécifiques des vector processing units. Au lieu de simplement compter les opérations abstraites, les ingénieurs doivent maintenant minimiser stratégiquement les cache misses et maximiser le parallélisme au niveau de la mémoire. Les benchmarks convaincants de Lemire, démontrant que sa méthode est constamment 2x plus rapide que la recherche binaire traditionnelle sur le hardware x64 ou ARM moderne, fournissent une preuve indéniable de cette nécessité. Ce changement de paradigme exige une compréhension plus profonde et plus intégrée de l'ensemble du système informatique, de la logique de haut niveau jusqu'au silicium, remodelant fondamentalement la manière dont nous enseignons et pratiquons l'computer science.

Exploiter le parallelism est la clé incontestée pour débloquer le prochain niveau de performance dans les logiciels. L'algorithme « SIMD Quad » de Daniel Lemire, surpassant la recherche binaire traditionnelle de plus de 2x sur le hardware x64 et ARM moderne, prouve avec emphase que maximiser les opérations concurrentes, plutôt que minimiser les comparaisons, dicte désormais la véritable efficacité. L'ère de la pensée séquentielle pour les goulots d'étranglement critiques est définitivement révolue ; l'avenir exige des algorithmes qui exploitent chaque once de parallelism hardware disponible.

Cette philosophie de conception axée sur le matériel s'étend bien au-delà de la seule recherche. Des algorithmes fondamentaux comme le tri, le hachage et même la compression de données sont prêts pour des refontes similaires. Imaginez de futures routines de tri qui n'optimisent pas seulement les échanges, mais traitent simultanément plusieurs blocs de données à l'aide d'unités vectorielles, ou des fonctions de hachage méticuleusement conçues pour éviter les 'cache misses' et exploiter le parallélisme au niveau de la mémoire inhérent aux conceptions de CPU modernes, plutôt que de s'appuyer sur des hypothèses dépassées concernant les coûts d'accès mémoire uniformes.

Nous assistons à la fin de l'algorithme 'taille unique', une relique des époques informatiques plus simples. La solution idéale pour un problème donné sera de plus en plus une solution matérielle/logicielle co-conçue, adaptée aux nuances des architectures de processeurs spécifiques. Ce changement de paradigme exige une compréhension plus approfondie de la manière dont les ordinateurs modernes exécutent réellement les instructions et gèrent la mémoire, allant au-delà de la notation Big O abstraite vers des réalités matérielles tangibles comme les hiérarchies de cache et les 'pipeline stalls'.

Les développeurs doivent donc adopter une approche plus proactive et éclairée de la performance. Commencez par profiler rigoureusement votre code pour identifier les véritables goulots d'étranglement de performance, qui sont souvent enracinés dans les modèles d'accès mémoire et le comportement du cache, et pas seulement dans les cycles CPU passés sur les comparaisons. Ensuite, étudiez l'utilisation directe d'intrinsèques spécifiques au matériel, tels que les instructions SIMD (comme NEON sur ARM ou SSE2/AVX sur x64), pour vectoriser et paralléliser ces sections critiques. Cette optimisation ciblée, basée sur une compréhension intime de l'ordinateur sous-jacent, représente la voie la plus directe vers un logiciel véritablement plus rapide dans les décennies à venir.

Pourquoi la recherche binaire est-elle considérée comme lente sur les CPU modernes ?

La recherche binaire est lente non pas à cause de ses comparaisons, mais parce que son modèle d'accès mémoire aléatoire provoque de fréquents 'cache misses'. Cela force le CPU haute vitesse à s'arrêter pendant des centaines de cycles en attendant les données d'une RAM beaucoup plus lente.

Quelle est l'alternative plus rapide de Daniel Lemire à la recherche binaire ?

Le professeur Daniel Lemire a développé un algorithme 'SIMD Quad'. C'est une recherche multi-voies qui utilise l'interpolation pour trouver un bloc de données probable, puis charge ce bloc dans un registre spécial pour comparer tous ses éléments simultanément à l'aide d'instructions SIMD.

Qu'est-ce que le SIMD et comment accélère-t-il la recherche ?

SIMD signifie 'Single Instruction, Multiple Data'. C'est une fonctionnalité du CPU permettant à une instruction d'effectuer la même opération sur plusieurs points de données à la fois. Dans ce cas, il compare un bloc entier de 16 nombres à la valeur cible en une seule opération, réduisant drastiquement le temps de comparaison.

Cela signifie-t-il que la notation Big O est inutile ?

Non, la notation Big O reste un outil crucial pour comprendre l'évolutivité d'un algorithme. Cependant, cette recherche montre qu'elle est incomplète, car elle ne tient pas compte des facteurs matériels réels comme la latence mémoire et le parallélisme, qui peuvent dominer la performance.