java algorithme algorithmes - Pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié?





10 Answers

Prédiction de branche.

Avec un tableau trié, les data[c] >= 128 condition data[c] >= 128 sont d'abord false pour une série de valeurs, puis deviennent true pour toutes les valeurs ultérieures. C'est facile à prédire. Avec un tableau non trié, vous payez le coût de branchement.

par selection code

Voici un morceau de code C ++ qui semble très particulier. Pour une raison étrange, trier les données miraculeusement rend le code presque six fois plus rapide.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Sans std::sort(data, data + arraySize); , le code s'exécute en 11,54 secondes.
  • Avec les données triées, le code s'exécute en 1,93 seconde.

Au départ, je pensais que cela pourrait être simplement une anomalie de langage ou de compilateur. Alors je l'ai essayé en Java.

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Avec un résultat un peu similaire mais moins extrême.

Ma première pensée a été que le tri amène les données dans la mémoire cache, mais je me suis dit à quel point cela était idiot, car le tableau venait d'être généré.

  • Que se passe-t-il?
  • Pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié?
  • Le code récapitule certains termes indépendants, et l'ordre ne devrait pas avoir d'importance.



Si vous souhaitez en savoir plus sur les optimisations pouvant être apportées à ce code, tenez compte de ceci:

En commençant par la boucle d'origine:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Avec l'échange de boucle, nous pouvons changer cette boucle en toute sécurité pour:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Ensuite, vous pouvez voir que le conditionnel if est constant tout au long de l'exécution de la boucle i , vous pouvez donc lever le if :

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Ensuite, vous voyez que la boucle interne peut être réduite en une seule expression, en supposant que le modèle en virgule flottante le permette (/ fp: fast est jeté, par exemple).

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Celui-ci est 100 000 fois plus rapide qu'avant




Je viens de lire sur cette question et ses réponses, et j'estime qu'il me manque une réponse.

Un moyen courant d'éliminer la prédiction de branche que j'ai trouvé particulièrement efficace dans les langages gérés est la recherche de table au lieu d'utiliser une branche (bien que je ne l'aie pas testée dans ce cas).

Cette approche fonctionne en général si:

  1. C'est une petite table et est susceptible d'être mis en cache dans le processeur
  2. Vous exécutez les choses dans une boucle assez étroite et / ou le processeur peut pré-charger les données

Contexte et pourquoi

Pfew, alors qu'est-ce que c'est censé vouloir dire?

Du point de vue du processeur, votre mémoire est lente. Pour compenser la différence de vitesse, ils construisent deux caches dans votre processeur (cache L1 / L2) qui compensent cela. Alors, imaginez que vous faites de beaux calculs et que vous ayez besoin d’un morceau de mémoire. Le processeur effectue son opération de "chargement" et charge la mémoire dans le cache - puis utilise le cache pour effectuer le reste des calculs. Parce que la mémoire est relativement lente, ce "chargement" ralentira votre programme.

Comme la prédiction de branche, celle-ci a été optimisée dans les processeurs Pentium: le processeur prédit qu'il doit charger une donnée et tente de la charger dans le cache avant que l'opération n'atteigne réellement le cache. Comme nous l’avons déjà vu, la prédiction de branche est parfois terriblement fausse. Dans le pire des cas, vous devez revenir en arrière et attendre réellement un chargement de mémoire, ce qui prendra une éternité ( en d’autres termes: échec de la prédiction de branche est mauvais, une mémoire charger après l'échec d'une prédiction de branche est simplement horrible! ).

Heureusement pour nous, si le modèle d'accès à la mémoire est prévisible, le processeur le chargera dans son cache rapide et tout va bien.

La première chose à savoir, c'est ce qui est petit . Bien que plus petit soit généralement préférable, une règle empirique est de s’en tenir aux tables de consultation d’une taille <= 4096 octets. En tant que limite supérieure: si votre table de recherche dépasse 64 Ko, il est probablement utile de la réexaminer.

Construire une table

Nous avons donc compris que nous pouvions créer une petite table. La prochaine chose à faire est de mettre en place une fonction de recherche. Les fonctions de recherche sont généralement de petites fonctions qui utilisent quelques opérations entières de base (et, ou, xor, shift, ajouter, supprimer et éventuellement se multiplier). Vous voulez que votre entrée soit traduite par la fonction de recherche en une sorte de "clé unique" dans votre tableau, qui vous donne alors simplement la réponse à tout le travail que vous souhaitiez qu'elle fasse.

Dans ce cas:> = 128 signifie que nous pouvons conserver la valeur, <128 signifie que nous nous en débarrassons. Le moyen le plus simple de le faire est d'utiliser un 'AND': si nous le conservons, nous l'utilisons AND avec 7FFFFFFF; si nous voulons nous en débarrasser, nous l’avons AND avec 0. Notez également que 128 est une puissance de 2 - nous pouvons donc aller de l’avant et créer un tableau de 32768/128 entiers et le remplir avec un zéro et beaucoup de 7FFFFFFFF's.

Langues gérées

Vous pourriez vous demander pourquoi cela fonctionne bien dans les langues gérées. Après tout, les langues gérées vérifient les limites des tableaux avec une branche pour vous assurer de ne pas gâcher ...

Eh bien, pas exactement ... :-)

Il y a eu beaucoup de travail sur l'élimination de cette branche pour les langues gérées. Par exemple:

for (int i=0; i<array.Length; ++i)
   // Use array[i]

Dans ce cas, il est évident pour le compilateur que la condition limite ne sera jamais atteinte. Au moins le compilateur Microsoft JIT (mais j’espère que Java fait la même chose) le remarquera et supprimera complètement la vérification. WOW - cela signifie pas de branche. De même, il traitera d'autres cas évidents.

Si vous rencontrez des problèmes avec les recherches sur les langues gérées, il est essentiel d’ajouter un & 0x[something]FFF à votre fonction de recherche afin de rendre la vérification des limites prévisible - et de l’observer plus rapidement.

Le résultat de cette affaire

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();



Une façon d'éviter les erreurs de prédiction de branche consiste à créer une table de recherche et à l'indexer à l'aide des données. Stefan de Bruijn en a parlé dans sa réponse.

Mais dans ce cas, nous savons que les valeurs sont comprises dans l'intervalle [0, 255] et nous nous intéressons uniquement aux valeurs> = 128. Cela signifie que nous pouvons facilement extraire un bit qui nous dira si nous voulons une valeur ou non: en déplaçant les données aux 7 bits de droite, il nous reste un bit 0 ou un bit, et nous voulons seulement ajouter la valeur lorsque nous avons un bit 1. Appelons ce bit le "bit de décision".

En utilisant la valeur 0/1 du bit de décision comme index dans un tableau, nous pouvons créer un code qui sera tout aussi rapide, que les données soient triées ou non. Notre code ajoutera toujours une valeur, mais lorsque le bit de décision est 0, nous ajoutons la valeur à un endroit qui ne nous intéresse pas. Voici le code:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Ce code gaspille la moitié des ajouts mais n’a jamais d’échec de prédiction de branche. Il est extrêmement rapide sur des données aléatoires que la version avec une instruction if réelle.

Mais lors de mes tests, une table de recherche explicite était légèrement plus rapide que cela, probablement parce que l'indexation dans une table de recherche était légèrement plus rapide que le transfert de bits. Cela montre comment mon code configure et utilise la table de consultation (appelé de manière non imaginative lut"Table de consultation" dans le code). Voici le code C ++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

Dans ce cas, la table de recherche ne contenait que 256 octets. Elle s’insère donc parfaitement dans un cache et tout était rapide. Cette technique ne fonctionnerait pas bien si les données étaient des valeurs 24 bits et que nous ne voulions que la moitié d'entre elles ... la table de correspondance serait beaucoup trop volumineuse pour être pratique. D'autre part, nous pouvons combiner les deux techniques présentées ci-dessus: décaler d'abord les bits, puis indexer une table de correspondance. Pour une valeur de 24 bits pour laquelle nous ne voulons que la moitié supérieure, nous pourrions éventuellement décaler les données de 12 bits vers la droite et laisser une valeur de 12 bits pour un index de table. Un index de table 12 bits implique une table de 4096 valeurs, ce qui peut être pratique.

EDIT: Une chose que j'ai oublié de mettre en

La technique de l'indexation dans un tableau, au lieu d'utiliser une ifinstruction, peut être utilisée pour décider du pointeur à utiliser. J'ai vu une bibliothèque implémenter des arbres binaires, et au lieu d'avoir deux pointeurs nommés ( pLeftet ainsi de suite pRight), ils avaient un tableau de pointeurs de longueur 2 et utilisaient la technique du "bit de décision" pour décider lequel suivre. Par exemple, au lieu de:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

cette bibliothèque ferait quelque chose comme:

i = (x < node->value);
node = node->link[i];

Voici un lien vers ce code: Red Black Trees , Eternally Confuzzled




Le comportement ci-dessus est dû à la prédiction de branche.

Pour comprendre la prédiction de branche, il faut d’abord comprendre Instruction Pipeline :

Toute instruction est décomposée en une séquence d’étapes afin que différentes étapes puissent être exécutées simultanément et en parallèle. Cette technique est connue sous le nom de pipeline d’instructions et est utilisée pour augmenter le débit des processeurs modernes. Pour mieux comprendre cela, veuillez voir cet exemple sur Wikipedia .

Généralement, les processeurs modernes ont des pipelines assez longs, mais pour simplifier, considérons ces 4 étapes seulement.

  1. IF - Récupère l'instruction de la mémoire
  2. ID - Décoder l'instruction
  3. EX - Exécuter l'instruction
  4. WB - Réécriture dans le registre de la CPU

Pipeline en 4 étapes en général pour 2 instructions.

Pour revenir à la question ci-dessus, considérons les instructions suivantes:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Sans prédiction de branche, les événements suivants se produiraient:

Pour exécuter l'instruction B ou l'instruction C, le processeur doit attendre que l'instruction A n'atteigne pas le stade EX du pipeline, car la décision de passer à l'instruction B ou à l'instruction C dépend du résultat de l'instruction A. Le pipeline ressemblera à ceci.

quand si la condition redevient vraie:

Quand si la condition retourne fausse:

En conséquence de l'attente du résultat de l'instruction A, le nombre total de cycles de la CPU dépensés dans le cas ci-dessus (sans prédiction de branche; à la fois pour vrai et pour faux) est de 7.

Alors, quelle est la prédiction de branche?

Le prédicteur de branche essaiera de deviner quelle direction prendra une branche (une structure if-then-else) avant que cela ne soit connu avec certitude. Il n'attendra pas que l'instruction A atteigne l'étape EX du pipeline, mais il devinera la décision et se rendra à cette instruction (B ou C dans le cas de notre exemple).

Dans le cas d'une estimation correcte, le pipeline ressemble à ceci:

S'il est détecté par la suite que la conjecture était fausse, les instructions partiellement exécutées sont ignorées et le pipeline recommence avec la branche correcte, ce qui entraîne un retard. Le temps perdu en cas de mauvaise prédiction d'une branche est égal au nombre d'étapes du pipeline allant de l'étape d'extraction à l'étape d'exécution. Les microprocesseurs modernes ont tendance à avoir des pipelines assez longs, de sorte que le délai de prédiction erronée est compris entre 10 et 20 cycles d'horloge. Plus le pipeline est long, plus il est nécessaire de disposer d’un bon prédicteur de branche .

Dans le code de l'OP, la première fois que le conditionnel est conditionnel, le prédicteur de branche ne dispose d'aucune information sur laquelle fonder la prédiction. La première fois, il choisit de manière aléatoire l'instruction suivante. Plus tard dans la boucle for, il peut baser la prédiction sur l'historique. Pour un tableau trié par ordre croissant, il existe trois possibilités:

  1. Tous les éléments sont inférieurs à 128
  2. Tous les éléments sont supérieurs à 128
  3. Certains nouveaux éléments de départ sont inférieurs à 128 et plus tard, ils deviennent supérieurs à 128.

Supposons que le prédicteur assume toujours la branche vraie lors de la première exécution.

Donc, dans le premier cas, il prendra toujours la vraie branche car historiquement toutes ses prédictions sont correctes. Dans le second cas, il prédira initialement faux, mais après quelques itérations, il prédira correctement. Dans le 3ème cas, il prédira initialement correctement jusqu'à ce que les éléments soient inférieurs à 128. Après quoi, il échouera pendant un certain temps et se corrigera lui-même lorsqu'il verra un échec de la prédiction de branche dans l'historique.

Dans tous ces cas, le nombre de pannes sera trop réduit et, par conséquent, il ne sera nécessaire que quelques fois de supprimer les instructions partiellement exécutées et de recommencer avec la branche correcte, ce qui réduira le nombre de cycles du processeur.

Mais dans le cas d'un tableau aléatoire non trié, la prévision devra ignorer les instructions partiellement exécutées et recommencer la plupart du temps avec la branche correcte, ce qui entraînera plus de cycles de processeur que le tableau trié.




Dans la même ligne (je pense que cela n’a pas été souligné dans aucune réponse), il est bon de mentionner que parfois (spécialement dans les logiciels où les performances sont importantes, comme dans le noyau Linux), vous pouvez trouver des instructions if telles que:

if (likely( everything_is_ok ))
{
    /* Do something */
}

ou similaire:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Les deux likely()et unlikely()sont en fait des macros qui sont définies en utilisant quelque chose comme les GCC __builtin_expectpour aider le compilateur à insérer le code de prédiction pour favoriser la condition en tenant compte des informations fournies par l'utilisateur. GCC prend en charge d'autres éléments intégrés susceptibles de modifier le comportement du programme en cours d'exécution ou d'émettre des instructions de bas niveau, tels que l'effacement du cache, etc. Consultez cette documentation qui décrit les éléments intégrés de GCC disponibles.

Normalement, ce type d’optimisation concerne principalement les applications en temps réel ou les systèmes embarqués dans lesquels le temps d’exécution est important. Par exemple, si vous recherchez une condition d'erreur ne se produisant que 1/10000000 fois, pourquoi ne pas en informer le compilateur? De cette façon, par défaut, la prédiction de branche supposerait que la condition est fausse.




C'est sûr! ...

La prédiction de branche ralentit le déroulement de la logique, à cause du basculement qui se produit dans votre code! C'est comme si tu allais dans une rue droite ou dans une rue avec beaucoup de virages, c'est sûr que la ligne droite va se faire plus rapidement! ...

Si le tableau est trié, votre condition est fausse à la première étape data[c] >= 128:, devient alors une valeur vraie pour tout le chemin jusqu'à la fin de la rue. C'est ainsi que vous arrivez à la fin de la logique plus rapidement. D'autre part, en utilisant un tableau non trié, vous avez besoin de beaucoup de retournements et de traitements qui ralentissent votre code, c'est sûr ...

Regardez l'image que j'ai créée pour vous ci-dessous. Quelle rue va être fini plus vite?

Donc, par programmation, la prédiction de branche ralentit le processus ...

Aussi, à la fin, il est bon de savoir que nous avons deux types de prédictions de branche qui affecteront votre code différemment:

1. statique

2. dynamique

La prédiction de branche statique est utilisée par le microprocesseur la première fois qu'une branche conditionnelle est rencontrée, et la prédiction de branche dynamique est utilisée pour les exécutions suivantes du code de branche conditionnelle.

Afin d'écrire efficacement votre code afin de tirer parti de ces règles, lors de l'écriture d' instructions if-else ou switch , vérifiez d'abord les cas les plus courants et progressez progressivement jusqu'au moins commun. Les boucles n'exigent pas nécessairement un classement spécial du code pour la prédiction de branche statique, car seule la condition de l'itérateur de boucle est normalement utilisée.




Gain de prédiction de branche!

Il est important de comprendre que la mauvaise prédiction de branche ne ralentit pas les programmes. Le coût d'une prévision manquée est comme si la prévision de branche n'existait pas et que vous attendiez l'évaluation de l'expression pour décider du code à exécuter (explications supplémentaires dans le paragraphe suivant).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Chaque fois qu'il y a une instruction if-else\ switch, l'expression doit être évaluée pour déterminer quel bloc doit être exécuté. Dans le code d'assemblage généré par le compilateur, des instructions de branch conditionnelles sont insérées.

Une instruction de branchement peut faire en sorte qu'un ordinateur commence à exécuter une séquence d'instructions différente et s'écarte donc de son comportement par défaut consistant à exécuter les instructions dans l'ordre (c'est-à-dire si l'expression est fausse, le programme ignore le code du ifbloc) en fonction de certaines conditions, qui sont: l'évaluation de l'expression dans notre cas.

Cela étant dit, le compilateur essaie de prédire le résultat avant son évaluation effective. Il va chercher les instructions du ifbloc, et si l'expression s'avère être vraie, alors merveilleux! Nous avons gagné le temps nécessaire pour l’évaluer et avons progressé dans le code; sinon, le code est incorrect, le pipeline est vidé et le bloc correct est exécuté.

Visualisation:

Supposons que vous deviez choisir la route 1 ou la route 2. En attendant que votre partenaire vérifie la carte, vous vous êtes arrêté à ## et avez attendu, ou vous pouvez simplement choisir route1 et si vous aviez de la chance (la route 1 est la bonne route), alors génial vous n'avez pas à attendre que votre partenaire vérifie la carte (vous avez économisé le temps qu'il lui aurait fallu pour consulter la carte), sinon vous reviendrez simplement en arrière.

Bien que le vidage des pipelines soit très rapide, prendre ce pari en vaut la peine. La prévision de données triées ou de données qui changent lentement est toujours plus facile et meilleure que de prévoir des changements rapides.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------



Il s'agit de prédiction de branche. Qu'Est-ce que c'est?

  • Un prédicteur de branche est l’une des anciennes techniques d’amélioration des performances qui trouve encore sa pertinence dans les architectures modernes. Bien que les techniques de prédiction simples fournissent une recherche rapide et une efficacité énergétique, elles souffrent d'un taux élevé de prédiction erronée.

  • D'autre part, les prédictions de branches complexes - qu'elles soient basées sur des neurones ou des variantes de la prédiction de branche à deux niveaux - offrent une meilleure précision de prévision, mais elles consomment plus d'énergie et leur complexité augmente de manière exponentielle.

  • De plus, dans les techniques de prévision complexes, le temps nécessaire pour prédire les branches est lui-même très élevé - allant de 2 à 5 cycles - ce qui est comparable au temps d'exécution des branches réelles.

  • La prédiction de branche est essentiellement un problème d’optimisation (minimisation) dans lequel l’accent est mis sur l’atteinte du taux de défaillance le plus faible possible, de la consommation électrique minimale et de la complexité réduite avec un minimum de ressources.

Il y a vraiment trois sortes de branches:

Branchements conditionnels en avant - Sur la base d'une condition d'exécution, le PC (compteur de programme) est modifié pour pointer vers une adresse en avant dans le flux d'instructions.

Branches conditionnelles en arrière - le PC est modifié pour pointer en arrière dans le flux d'instructions. La branche est basée sur certaines conditions, telles que le fait de revenir en arrière au début d'une boucle de programme lorsqu'un test à la fin de la boucle indique que la boucle doit être exécutée à nouveau.

Branches inconditionnelles - cela inclut les sauts, les appels de procédure et les retours sans condition spécifique. Par exemple, une instruction de saut inconditionnel peut être codée en langage assembleur simplement comme "jmp" et le flux d'instructions doit immédiatement être dirigé vers l'emplacement cible désigné par l'instruction de saut, tandis qu'un saut conditionnel pouvant être codé comme "jmpne" redirigerait le flux d'instructions uniquement si le résultat d'une comparaison de deux valeurs dans une instruction de "comparaison" précédente indique que les valeurs ne sont pas égales. (Le schéma d'adressage segmenté utilisé par l'architecture x86 ajoute une complexité supplémentaire, car les sauts peuvent être "proches" (au sein d'un segment) ou "éloignés" (en dehors du segment). Chaque type a des effets différents sur les algorithmes de prédiction de branche.)

Prédiction de branche statique / dynamique : le microprocesseur utilise la prédiction de branche statique la première fois qu'une branche conditionnelle est rencontrée, et la prédiction dynamique de branche est utilisée pour les exécutions suivantes du code de branche conditionnelle.

Références:




Outre le fait que la prédiction de branche peut vous ralentir, un tableau trié présente un autre avantage:

Vous pouvez avoir une condition d'arrêt au lieu de simplement vérifier la valeur. Ainsi, vous ne parcourez que les données pertinentes et ignorez le reste.
La prédiction de branche ne manquera qu'une fois.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }



Related