Pourquoi un tableau trié est-il traité plus rapidement ? Explication avec Java

Introduction : le paradoxe qui a explosé Stack Overflow

Imaginez : vous écrivez une simple boucle en Java qui additionne les éléments d'un tableau en fonction d'une condition (par exemple, si le nombre est supérieur à 128). Vous exécutez le code sur un tableau trié — et il s'exécute 2 à 3 fois plus rapidement que sur un tableau non trié. Cela ressemble à de la magie ? En réalité, ce n'est pas de la magie, mais le branch prediction (prédiction de branchement) — l'une des caractéristiques clés des processeurs modernes.

La question « Why is conditional processing of a sorted array faster than of an unsorted array? » a recueilli plus de 30 000 votes sur Stack Overflow et est devenue un classique pour l'étude de l'optimisation de bas niveau. Dans cet article, nous n'allons pas seulement analyser la théorie, mais aussi écrire du code réel en Java pour observer l'effet de nos propres yeux. Et surtout, vous apprendrez comment utiliser cette connaissance en pratique.

Si vous voulez comprendre plus en profondeur comment fonctionne l'optimisation de code en Java et pourquoi le branch prediction peut à la fois accélérer et ralentir votre programme — vous êtes au bon endroit.

1. Expérience : le code qui montre tout

Commençons par une simple application Java. Nous allons créer deux tableaux : un trié, l'autre aléatoire. Ensuite, nous parcourrons chacun d'eux et calculerons la somme des éléments supérieurs à une valeur seuil (par exemple, 128). Nous mesurerons le temps d'exécution.

import java.util.Arrays;\nimport java.util.Random;\n\npublic class BranchPredictionDemo {\n    private static final int SIZE = 100_000;\n    private static final int THRESHOLD = 128;\n\n    public static void main(String[] args) {\n        // Création d'un tableau non trié\n        int[] unsorted = new int[SIZE];\n        Random rand = new Random();\n        for (int i = 0; i < SIZE; i++) {\n            unsorted[i] = rand.nextInt(256); // 0..255\n        }\n\n        // Création d'un tableau trié (copie et tri)\n        int[] sorted = unsorted.clone();\n        Arrays.sort(sorted);\n\n        // Mesure du temps pour le tableau non trié\n        long start = System.nanoTime();\n        long sumUnsorted = processArray(unsorted);\n        long end = System.nanoTime();\n        System.out.println("Non trié : " + (end - start) / 1_000_000 + " ms, somme = " + sumUnsorted);\n\n        // Mesure du temps pour le tableau trié\n        start = System.nanoTime();\n        long sumSorted = processArray(sorted);\n        end = System.nanoTime();\n        System.out.println("Trié : " + (end - start) / 1_000_000 + " ms, somme = " + sumSorted);\n    }\n\n    private static long processArray(int[] arr) {\n        long sum = 0;\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] >= THRESHOLD) {\n                sum += arr[i];\n            }\n        }\n        return sum;\n    }\n}\n

Résultats sur mon ordinateur portable (Intel i7, Java 17) :

\n
• Tableau non trié : ~22 ms
\n
• Tableau trié : ~8 ms
\n

Une différence de presque 3 fois ! Pourquoi ? Pourtant, le nombre d'opérations est identique. La réponse réside dans la façon dont le processeur traite la condition if (arr[i] >= THRESHOLD).

2. Branch Prediction : le cerveau du processeur

Les processeurs modernes utilisent une architecture pipeline — ils prédisent quel chemin d'exécution (branche) sera choisi et commencent à exécuter les instructions à l'avance. Si la prédiction est correcte, tout va vite. Si elle est erronée, le pipeline est vidé et le processeur perd des cycles à se nettoyer.

Dans un tableau trié, les valeurs sont d'abord longtemps inférieures à 128, puis supérieures. Le processeur « apprend » rapidement : si les 1000 fois précédentes c'était false, alors la suivante sera très probablement false aussi. La prédiction fonctionne presque parfaitement.

Dans un tableau non trié, les valeurs sautent de manière aléatoire au-dessus et en dessous du seuil. Le processeur se trompe dans environ 50 % des cas, ce