Pourquoi le traitement d'un tableau trié est-il plus rapide que le traitement d'un tableau non trié?

Voici un morceau de code C ++ qui montre un comportement très particulier. Pour une raison étrange, le tri des 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 secondes.

Au départ, je pensais que cela pourrait être juste une anomalie de langage ou de compilateur, j'ai donc essayé 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 similaire mais moins extrême.

Ma première pensée a été que le tri amène les données dans le cache, mais j'ai pensé à quel point c'était stupide parce que le tableau venait d'être généré.

• Que se passe-t-il?
• Pourquoi le traitement d'un tableau trié est-il plus rapide que le traitement d'un tableau non trié?

Le code résume certains termes indépendants, donc l'ordre ne devrait pas avoir d'importance.

Vous êtes victime d'un échec de prédiction de branche .

Qu'est-ce que la prédiction de branche?

Considérons une jonction ferroviaire:

_{Image par Mecanismo, via Wikimedia Commons. Utilisé sous la licence CC-By-SA 3.0 .}

Maintenant, pour les besoins de l'argument, supposons que cela remonte aux années 1800 - avant les communications longue distance ou radio.

Vous êtes l'opérateur d'un carrefour et vous entendez arriver un train. Vous n'avez aucune idée de la direction à prendre. Vous arrêtez le train pour demander au conducteur dans quelle direction il veut. Et puis vous réglez le commutateur de manière appropriée.

Les trains sont lourds et ont beaucoup d'inertie. Ils mettent donc une éternité à démarrer et à ralentir.

Y a-t-il une meilleure façon? Vous devinez dans quelle direction le train ira!

• Si vous avez bien deviné, cela continue.
• Si vous vous trompez, le capitaine s'arrête, recule et vous crie dessus pour actionner l'interrupteur. Ensuite, il peut redémarrer sur l'autre chemin.

Si vous devinez à chaque fois , le train n'aura jamais à s'arrêter.
Si vous vous trompez trop souvent , le train passera beaucoup de temps à s'arrêter, à reculer et à redémarrer.

Considérons une instruction if: au niveau du processeur, il s'agit d'une instruction de branchement:

Vous êtes un processeur et vous voyez une branche. Vous n'avez aucune idée de la direction que cela prendra. Que faire? Vous arrêtez l'exécution et attendez que les instructions précédentes soient terminées. Ensuite, vous continuez sur le bon chemin.

Les processeurs modernes sont compliqués et ont de longs pipelines. Ils mettent donc une éternité à «s'échauffer» et à «ralentir».

Y a-t-il une meilleure façon? Vous devinez dans quelle direction ira la succursale!

• Si vous avez bien deviné, vous continuez à exécuter.
• Si vous vous êtes trompé, vous devez rincer le pipeline et revenir à la branche. Ensuite, vous pouvez redémarrer l'autre chemin.

Si vous devinez à chaque fois , l'exécution ne devra jamais s'arrêter.
Si vous vous trompez trop souvent , vous passez beaucoup de temps à caler, à reculer et à redémarrer.

Ceci est une prédiction de branche. J'avoue que ce n'est pas la meilleure analogie car le train pourrait simplement signaler la direction avec un drapeau. Mais dans les ordinateurs, le processeur ne sait pas dans quelle direction ira une branche jusqu'au dernier moment.

Alors, comment devineriez-vous stratégiquement pour minimiser le nombre de fois que le train doit reculer et descendre l'autre chemin? Vous regardez l'histoire passée! Si le train part à 99% du temps, alors vous devinez parti. S'il alterne, alors vous alternez vos suppositions. Si cela va dans un sens toutes les trois fois, vous devinez la même chose ...

En d'autres termes, vous essayez d'identifier un modèle et de le suivre. C'est plus ou moins comment fonctionnent les prédicteurs de branche.

La plupart des applications ont des branches bien comportées. Ainsi, les prédicteurs de branche modernes atteindront généralement des taux de réussite supérieurs à 90%. Mais face à des branches imprévisibles sans schémas reconnaissables, les prédicteurs de branche sont pratiquement inutiles.

Pour en savoir plus: article "Predicteur de branche" sur Wikipédia .

Comme laissé entendre ci-dessus, le coupable est cette instruction if:

if (data[c] >= 128)
    sum += data[c];

Notez que les données sont réparties uniformément entre 0 et 255. Lorsque les données sont triées, à peu près la première moitié des itérations n'entrera pas dans l'instruction if. Après cela, ils entreront tous dans l'instruction if.

Ceci est très convivial pour le prédicteur de branche car la branche va dans le même sens plusieurs fois de suite. Même un simple compteur saturant prédira correctement la branche, à l'exception des quelques itérations après avoir changé de direction.

Visualisation rapide:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Cependant, lorsque les données sont complètement aléatoires, le prédicteur de branche est rendu inutile, car il ne peut pas prédire des données aléatoires. Ainsi, il y aura probablement environ 50% d'erreurs de prédiction (pas mieux que des suppositions aléatoires).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Alors, que peut-on faire?

Si le compilateur n'est pas en mesure d'optimiser la branche dans un mouvement conditionnel, vous pouvez essayer quelques hacks si vous êtes prêt à sacrifier la lisibilité pour les performances.

Remplacer:

if (data[c] >= 128)
    sum += data[c];

avec:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Cela élimine la branche et la remplace par quelques opérations au niveau du bit.

_{(Notez que ce hack n'est pas strictement équivalent à l'instruction if d'origine. Mais dans ce cas, il est valide pour toutes les valeurs d'entrée de data[].)}

Repères: Core i7 920 @ 3,5 GHz

C ++ - Visual Studio 2010 - Version x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Observations:

• Avec la succursale: Il y a une énorme différence entre les données triées et non triées.
• Avec le Hack: il n'y a pas de différence entre les données triées et non triées.
• Dans le cas C ++, le hack est en fait un peu plus lent qu'avec la branche lorsque les données sont triées.

Une règle générale consiste à éviter la ramification dépendante des données dans les boucles critiques (comme dans cet exemple).

Mise à jour:

• GCC 4.6.1 avec -O3ou -ftree-vectorizesur x64 est capable de générer un déplacement conditionnel. Il n'y a donc aucune différence entre les données triées et non triées - les deux sont rapides.

  (Ou un peu rapide: pour le cas déjà trié, cmovpeut être plus lent, surtout si GCC le place sur le chemin critique plutôt que juste add, en particulier sur Intel avant Broadwell où la cmovlatence est à 2 cycles: l' indicateur d'optimisation gcc -O3 rend le code plus lent que -O2 )

• VC ++ 2010 est incapable de générer des mouvements conditionnels pour cette branche même sous /Ox.

• Intel C ++ Compiler (ICC) 11 fait quelque chose de miraculeux. Il échange les deux boucles , hissant ainsi la branche imprévisible à la boucle externe. Ainsi, non seulement il est immunisé contre les erreurs de prévision, mais il est également deux fois plus rapide que ce que VC ++ et GCC peuvent générer! En d'autres termes, ICC a profité de la boucle de test pour battre la référence ...

• Si vous donnez au compilateur Intel le code sans branche, il le vectorise juste à droite ... et est aussi rapide qu'avec la branche (avec l'échange de boucle).

Cela montre que même les compilateurs modernes matures peuvent varier considérablement dans leur capacité à optimiser le code ...

Prédiction de branche.

Avec un tableau trié, la condition data[c] >= 128est d'abord falsepour une séquence de valeurs, puis devient truepour toutes les valeurs ultérieures. C'est facile à prévoir. Avec un tableau non trié, vous payez les frais de branchement.

La raison pour laquelle les performances s'améliorent considérablement lorsque les données sont triées est que la pénalité de prédiction de branche est supprimée, comme expliqué magnifiquement dans la réponse de Mysticial .

Maintenant, si nous regardons le code

if (data[c] >= 128)
    sum += data[c];

nous pouvons constater que le sens de cette if... else...branche particulière est d'ajouter quelque chose quand une condition est remplie. Ce type de branche peut être facilement transformé en une instruction de déplacement conditionnel , qui serait compilée en une instruction de déplacement conditionnel:, cmovldans un x86système. La branche et donc la pénalité de prédiction de branche potentielle sont supprimées.

Dans C, ainsi C++, l'instruction, qui compilerait directement (sans aucune optimisation) dans l'instruction de déplacement conditionnel dans x86, est l'opérateur ternaire ... ? ... : .... Nous réécrivons donc la déclaration ci-dessus en une déclaration équivalente:

sum += data[c] >=128 ? data[c] : 0;

Tout en maintenant la lisibilité, nous pouvons vérifier le facteur d'accélération.

Sur un Intel Core i7 -2600K @ 3,4 GHz et le mode de sortie de Visual Studio 2010, la référence est (format copié depuis Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Le résultat est robuste dans plusieurs tests. Nous obtenons une grande accélération lorsque le résultat de la branche est imprévisible, mais nous souffrons un peu lorsqu'il est prévisible. En fait, lors de l'utilisation d'un déplacement conditionnel, les performances sont les mêmes quel que soit le modèle de données.

Examinons maintenant de plus près en examinant l' x86assemblage qu'ils génèrent. Pour simplifier, nous utilisons deux fonctions max1et max2.

max1utilise la branche conditionnelle if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2utilise l'opérateur ternaire ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

Sur une machine x86-64, GCC -Sgénère l'assembly ci-dessous.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2utilise beaucoup moins de code en raison de l'utilisation de l'instruction cmovge. Mais le vrai gain est quemax2 n'implique pas de sauts de branche jmp, ce qui entraînerait une pénalité de performance importante si le résultat prévu n'est pas correct.

Alors pourquoi un mouvement conditionnel fonctionne-t-il mieux?

Dans un x86processeur typique , l'exécution d'une instruction est divisée en plusieurs étapes. En gros, nous avons différents matériels pour faire face à différentes étapes. Il n'est donc pas nécessaire d'attendre la fin d'une instruction pour en commencer une nouvelle. C'est ce qu'on appelle le pipelining .

Dans un cas de branche, l'instruction suivante est déterminée par la précédente, donc nous ne pouvons pas faire de pipelining. Nous devons attendre ou prévoir.

Dans un cas de déplacement conditionnel, l'instruction de déplacement conditionnel d'exécution est divisée en plusieurs étapes, mais les étapes antérieures aiment Fetchet Decodene dépendent pas du résultat de l'instruction précédente; seules les dernières étapes ont besoin du résultat. Ainsi, nous attendons une fraction du temps d'exécution d'une instruction. C'est pourquoi la version à déplacement conditionnel est plus lente que la branche lorsque la prédiction est facile.

Le livre Computer Systems: A Programmer's Perspective, deuxième édition explique cela en détail. Vous pouvez consulter la section 3.6.6 pour les instructions de déplacement conditionnel , l'intégralité du chapitre 4 pour l' architecture du processeur et la section 5.11.2 pour un traitement spécial pour les pénalités de prédiction de branche et de mauvaise prévision .

Parfois, certains compilateurs modernes peuvent optimiser notre code en assembleur avec de meilleures performances, parfois certains compilateurs ne le peuvent pas (le code en question utilise le compilateur natif de Visual Studio). Connaître la différence de performances entre la branche et le mouvement conditionnel en cas d'imprévisibilité peut nous aider à écrire du code avec de meilleures performances lorsque le scénario devient si complexe que le compilateur ne peut pas les optimiser automatiquement.

Si vous êtes curieux de voir encore plus d'optimisations qui peuvent être apportées à ce code, considérez 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é en:

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 ifconditionnel est constant tout au long de l'exécution de la iboucle, vous pouvez donc hisser la ifsortie:

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 intérieure peut être réduite en une seule expression, en supposant que le modèle à virgule flottante le permet ( /fp:fastest levé, 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'auparavant.

Certains d'entre nous seraient sans doute intéressés par des moyens d'identifier le code problématique pour le prédicteur de branche du CPU. L'outil Valgrind cachegrinddispose d'un simulateur de prédicteur de branche, activé en utilisant l' --branch-sim=yesindicateur. L'exécuter sur les exemples de cette question, avec le nombre de boucles externes réduit à 10000 et compilé avec g++, donne les résultats suivants:

Trié:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Non trié:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

En descendant dans la sortie ligne par ligne produite par cg_annotatenous voyons pour la boucle en question:

Trié:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Non trié:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Cela vous permet d'identifier facilement la ligne problématique - dans la version non triée, la if (data[c] >= 128)ligne provoque 164 050 007 branches conditionnelles mal prédites ( Bcm) sous le modèle de prédicteur de branche de cachegrind, alors qu'elle ne cause que 10 006 dans la version triée.

Alternativement, sous Linux, vous pouvez utiliser le sous-système des compteurs de performances pour accomplir la même tâche, mais avec des performances natives à l'aide de compteurs CPU.

perf stat ./sumtest_sorted

Trié:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Non trié:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Il peut également faire des annotations de code source avec démontage.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted

 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Voir le didacticiel sur les performances pour plus de détails.

Je viens de lire cette question et ses réponses, et je sens qu'il manque une réponse.

Une méthode courante pour éliminer la prédiction de branche que j'ai trouvée particulièrement efficace dans les langages gérés est une recherche de table au lieu d'utiliser une branche (bien que je ne l'ai 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 mise en cache dans le processeur, et
2. vous exécutez des choses dans une boucle assez serrée et / ou le processeur peut précharger les données.

Contexte et pourquoi

Du point de vue du processeur, votre mémoire est lente. Pour compenser la différence de vitesse, deux caches sont intégrés à votre processeur (cache L1 / L2). Imaginez donc que vous faites vos bons calculs et comprenez que vous avez besoin d'un morceau de mémoire. Le processeur obtient son opération de «chargement» et charge le morceau de mémoire dans le cache - puis utilise le cache pour effectuer le reste des calculs. La mémoire étant relativement lente, cette «charge» 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 va parfois horriblement mal - dans le pire des cas, vous devez revenir en arrière et attendre une charge de mémoire, ce qui prendra une éternité ( en d'autres termes: l'échec de la prédiction de branche est mauvais, une mémoire charger après l'échec d'une prédiction de branche est tout 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 que nous devons savoir est ce qui est petit ? Bien que plus petit soit généralement meilleur, une règle de base est de s'en tenir aux tables de recherche dont la taille est <= 4096 octets. Comme limite supérieure: si votre table de recherche est supérieure à 64 Ko, cela vaut probablement la peine d'être reconsidéré.

Construire une table

Nous avons donc compris que nous pouvons 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 un couple d'opérations entières de base (et, ou, xor, shift, add, remove et peut-être multiplier). Vous voulez que votre entrée soit traduite par la fonction de recherche en une sorte de «clé unique» dans votre table, qui vous donne alors simplement la réponse de tout le travail que vous vouliez qu'elle fasse.

Dans ce cas:> = 128 signifie que nous pouvons conserver la valeur, <128 signifie que nous nous en débarrassons. La façon la plus simple de le faire est d'utiliser un 'ET': si nous le gardons, nous le faisons avec 7FFFFFFF; si nous voulons nous en débarrasser, nous ET avec 0. Notez également que 128 est une puissance de 2 - donc nous pouvons aller de l'avant et faire un tableau de 32768/128 entiers et le remplir avec un zéro et beaucoup de 7FFFFFFFF.

Langues gérées

Vous vous demandez peut-être pourquoi cela fonctionne bien dans les langues gérées. Après tout, les langages gérés 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 pas mal 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 aux limites ne sera jamais atteinte. Au moins le compilateur Microsoft JIT (mais je pense que Java fait des choses similaires) 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 dans les langues gérées - la clé est d'ajouter un & 0x[something]FFFà votre fonction de recherche pour rendre la vérification des limites prévisible - et regardez-la aller plus vite.

Le résultat de cette affaire

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

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

/*To keep the spirit of the code intact, 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();

Comme les données sont réparties entre 0 et 255 lorsque le tableau est trié, environ la première moitié des itérations n'entrera pas dans l' ifénoncé-(l' ifinstruction est partagée ci-dessous).

if (data[c] >= 128)
    sum += data[c];

La question est: qu'est-ce qui fait que l'instruction ci-dessus ne s'exécute pas dans certains cas comme dans le cas de données triées? Voici le "prédicteur de branche". Un prédicteur de branche est un circuit numérique qui essaie de deviner dans quelle direction if-then-elseira une branche (par exemple une structure) avant que cela ne soit sûr. Le prédicteur de branche a pour but d'améliorer le flux dans le pipeline d'instructions. Les prédicteurs de branche jouent un rôle essentiel dans l'obtention de performances efficaces élevées!

Faisons quelques repères pour mieux le comprendre

Les performances d'une ifinstruction dépendent du fait que sa condition présente un modèle prévisible. Si la condition est toujours vraie ou toujours fausse, la logique de prédiction de branchement dans le processeur reprendra le motif. En revanche, si le modèle est imprévisible, leif déclaration sera beaucoup plus chère.

Mesurons les performances de cette boucle avec différentes conditions:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Voici les timings de la boucle avec différents modèles vrai-faux:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

Un « mauvais » vrai-faux motif peut rendre une ifdéclaration jusqu'à six fois plus lente qu'un « bon » » motif! Bien sûr, quel modèle est bon et lequel est mauvais dépend des instructions exactes générées par le compilateur et du processeur spécifique.

Il n'y a donc aucun doute sur l'impact de la prédiction de branche sur les performances!

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 dans la plage [0, 255] et nous ne nous soucions que des valeurs> = 128. Cela signifie que nous pouvons facilement extraire un seul bit qui nous dira si nous voulons une valeur ou non: en décalant les données à droite 7 bits, nous nous retrouvons avec un bit 0 ou 1 bit, et nous voulons seulement ajouter la valeur lorsque nous avons un bit. 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 ajouterons la valeur quelque part qui nous importe peu. 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. C'est extrêmement plus rapide sur des données aléatoires que la version avec une instruction if réelle.

Mais dans 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 décalage de bits. Cela montre comment mon code s'installe et utilise la table de recherche (appelée sans lutambiguïté pour "LookUp Table" 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 n'était que de 256 octets, elle s'intègre donc bien dans un cache et tout était rapide. Cette technique ne fonctionnerait pas bien si les données étaient des valeurs 24 bits et nous n'en voulions que la moitié ... la table de recherche serait beaucoup trop grande pour être pratique. D'autre part, nous pouvons combiner les deux techniques présentées ci-dessus: d'abord décaler les bits, puis indexer une table de recherche. Pour une valeur de 24 bits que nous ne voulons que la moitié supérieure, nous pourrions potentiellement déplacer les données vers la droite de 12 bits et se retrouver avec une valeur de 12 bits pour un index de table. Un index de table de 12 bits implique une table de 4096 valeurs, ce qui pourrait être pratique.

La technique d'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 qui implémentait des arbres binaires, et au lieu d'avoir deux pointeurs nommés ( pLeftet pRightou autre) avait un tableau de pointeurs de longueur 2 et utilisé 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

Dans le cas trié, vous pouvez faire mieux que de vous fier à une prédiction de branche réussie ou à une astuce de comparaison sans branche: supprimez complètement la branche.

En effet, le tableau est partitionné dans une zone contiguë avec data < 128et une autre avec data >= 128. Vous devriez donc trouver le point de partition avec une recherche dichotomique (en utilisant des Lg(arraySize) = 15comparaisons), puis faire une accumulation directe à partir de ce point.

Quelque chose comme (décoché)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

ou, légèrement plus obscurci

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Une approche encore plus rapide, qui donne une solution approximative à la fois triée ou non triée, est la suivante: sum= 3137536;(en supposant une distribution vraiment uniforme, 16384 échantillons avec la valeur attendue 191,5) :-)

Le comportement ci-dessus se produit en raison de la prédiction de branche.

Pour comprendre la prédiction de branche, il faut d'abord comprendre le pipeline d'instructions :

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

Généralement, les processeurs modernes ont des pipelines assez longs, mais pour plus de facilité, considérons ces 4 étapes uniquement.

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 CPU

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

Revenant à 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 devra attendre que l'instruction A n'atteigne pas l'étape EX dans le pipeline, car la décision d'aller à l'instruction B ou à l'instruction C dépend du résultat de l'instruction A. Ainsi, le pipeline ressemblera à ceci.

quand si la condition retourne vraie:

Quand si la condition retourne false:

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

Alors, quelle est la prédiction de branche?

Le prédicteur de branche essaiera de deviner dans quelle direction une branche (une structure si-alors-autre) ira avant que cela ne soit sûr. Il n'attendra pas que l'instruction A atteigne l'étape EX du pipeline, mais il devinera la décision et ira à cette instruction (B ou C dans le cas de notre exemple).

En cas de supposition correcte, le pipeline ressemble à ceci:

S'il est détecté ultérieurement que la supposition était erronée, 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 de branche est égal au nombre d'étapes dans le pipeline de l'étape de récupération à l'étape d'exécution. Les microprocesseurs modernes ont tendance à avoir des pipelines assez longs, de sorte que le retard de mauvaise prévision se situe entre 10 et 20 cycles d'horloge. Plus le pipeline est long, plus le besoin d'un bon prédicteur de branche est grand .

Dans le code de l'OP, la première fois que le conditionnel, le prédicteur de branche n'a aucune information pour baser la prédiction, donc la première fois il choisira au hasard 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 vraie branche lors de la première exécution.

Donc dans le premier cas, il prendra toujours la vraie branche puisque historiquement toutes ses prédictions sont correctes. Dans le 2ème cas, au départ, il prédira mal, 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 prédiction de branche dans l'histoire.

Dans tous ces cas, l'échec sera trop peu nombreux et, par conséquent, il faudra seulement quelques fois ignorer les instructions partiellement exécutées et recommencer avec la bonne branche, ce qui entraînera moins de cycles CPU.

Mais dans le cas d'un tableau aléatoire non trié, la prédiction devra ignorer les instructions partiellement exécutées et recommencer avec la bonne branche la plupart du temps et entraîner plus de cycles CPU par rapport au tableau trié.

Une réponse officielle serait de

1. Intel - Éviter le coût des erreurs de prédiction des succursales
2. Intel - Réorganisation des succursales et des boucles pour éviter les erreurs
3. Articles scientifiques - architecture informatique de prédiction de branche
4. Livres: JL Hennessy, DA Patterson: Architecture informatique: une approche quantitative
5. Articles dans des publications scientifiques: TY Yeh, YN Patt en a fait beaucoup sur les prédictions de branche.

Vous pouvez également voir sur ce joli diagramme pourquoi le prédicteur de branche est confus.

Chaque élément du code d'origine est une valeur aléatoire

data[c] = std::rand() % 256;

donc le prédicteur changera de côté comme le std::rand()coup.

D'un autre côté, une fois qu'il est trié, le prédicteur passera d'abord dans un état de fortement non pris et lorsque les valeurs passeront à la valeur élevée, le prédicteur changera en trois passages de fortement non pris à fortement pris.

Dans la même ligne (je pense que cela n'a été mis en évidence par 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 comme les suivantes:

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 modules internes qui pourraient modifier le comportement du programme en cours d'exécution ou émettre des instructions de bas niveau comme la suppression du cache, etc. Consultez cette documentation qui passe par les modules internes disponibles de GCC.

Normalement, ce type d'optimisations se trouve principalement dans les applications en temps réel ou les systèmes embarqués où le temps d'exécution est important et critique. Par exemple, si vous recherchez une condition d'erreur qui ne se produit que 1/10000000 fois, alors 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.

Les opérations booléennes fréquemment utilisées en C ++ produisent de nombreuses branches dans le programme compilé. Si ces branches se trouvent à l'intérieur de boucles et sont difficiles à prévoir, elles peuvent ralentir considérablement l'exécution. Les variables booléennes sont stockées sous forme d'entiers 8 bits avec la valeur0 pour falseet 1pour true.

Les variables booléennes sont surdéterminées dans le sens où tous les opérateurs qui ont des variables booléennes en entrée vérifient si les entrées ont une autre valeur que 0ou 1, mais les opérateurs qui ont des booléens en sortie ne peuvent produire aucune autre valeur que0 ou 1. Cela rend les opérations avec des variables booléennes en entrée moins efficaces que nécessaire. Prenons l'exemple:

bool a, b, c, d;
c = a && b;
d = a || b;

Ceci est généralement implémenté par le compilateur de la manière suivante:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Ce code est loin d'être optimal. Les succursales peuvent prendre beaucoup de temps en cas de mauvaises prévisions. Les opérations booléennes peuvent être rendues beaucoup plus efficaces si l'on sait avec certitude que les opérandes n'ont pas d'autres valeurs que 0et 1. La raison pour laquelle le compilateur ne fait pas une telle hypothèse est que les variables peuvent avoir d'autres valeurs si elles ne sont pas initialisées ou proviennent de sources inconnues. Le code ci-dessus peut être optimisé si aetb a été initialisé aux valeurs valides ou si elles proviennent d'opérateurs qui produisent sortie booléenne. Le code optimisé ressemble à ceci:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charest utilisé à la place de boolafin de permettre d'utiliser les opérateurs au niveau du bit ( &et |) au lieu des opérateurs booléens ( &&et ||). Les opérateurs au niveau du bit sont des instructions uniques qui ne prennent qu'un seul cycle d'horloge. L'opérateur OR ( |) fonctionne même si aet ba d'autres valeurs que 0ou 1. L'opérateur ET ( &) et l'opérateur OU EXCLUSIF ( ^) peuvent donner des résultats incohérents si les opérandes ont d'autres valeurs que 0et 1.

~ne peut pas être utilisé pour NOT. Au lieu de cela, vous pouvez faire un booléen NOT sur une variable qui est connue pour être 0ou en le 1faisant XOR avec 1:

bool a, b;
b = !a;

peut être optimisé pour:

char a = 0, b;
b = a ^ 1;

a && bne peut pas être remplacé par a & bif best une expression qui ne doit pas être évaluée si ais false( &&n'évaluera pas b, &sera). De même, a || bne peut pas être remplacé par a | bif best une expression qui ne doit pas être évaluée si ais true.

L'utilisation d'opérateurs au niveau du bit est plus avantageuse si les opérandes sont des variables que si les opérandes sont des comparaisons:

bool a; double x, y, z;
a = x > y && z < 5.0;

est optimal dans la plupart des cas (sauf si vous vous attendez à ce que l' &&expression génère de nombreuses erreurs de prédiction de branche).

Ça c'est sûr!...

La prédiction de branche rend la logique plus lente, à cause de la commutation qui se produit dans votre code! C'est comme si vous allez dans une rue droite ou une rue avec beaucoup de tournants, c'est sûr que la ligne droite se fera plus vite! ...

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

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

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

Enfin, il est bon de savoir que nous avons deux types de prédictions de branche qui affecteront chacune 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 successives du code de branche conditionnelle.

Afin d'écrire efficacement votre code pour 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 descendez progressivement vers les moins courants. Les boucles ne nécessitent pas nécessairement un ordre spécial de code pour la prédiction de branche statique, car seule la condition de l'itérateur de boucle est normalement utilisée.

Cette question a déjà reçu d'excellentes réponses à plusieurs reprises. Je voudrais quand même attirer l'attention du groupe sur une autre analyse intéressante.

Récemment, cet exemple (modifié très légèrement) a également été utilisé comme moyen de montrer comment un morceau de code peut être profilé dans le programme lui-même sous Windows. En cours de route, l'auteur montre également comment utiliser les résultats pour déterminer où le code passe la plupart de son temps dans le cas trié et non trié. Enfin, l'article montre également comment utiliser une fonctionnalité peu connue de la couche d'abstraction matérielle (HAL) pour déterminer à quel point une mauvaise prédiction de branche se produit dans le cas non trié.

Le lien est ici: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

Comme ce qui a déjà été mentionné par d'autres, ce qui se cache derrière le mystère est Branch Predictor .

Je n'essaye pas d'ajouter quelque chose mais d'expliquer le concept d'une autre manière. Il y a une introduction concise sur le wiki qui contient du texte et un diagramme. J'aime bien l'explication ci-dessous qui utilise un diagramme pour élaborer intuitivement le prédicteur de branche.

Dans l'architecture informatique, un prédicteur de branche est un circuit numérique qui essaie de deviner dans quelle direction une branche (par exemple une structure si-alors-sinon) ira avant que cela ne soit sûr. Le prédicteur de branchement a pour but d'améliorer le flux dans le pipeline d'instructions. Les prédicteurs de branche jouent un rôle essentiel dans la réalisation de performances efficaces élevées dans de nombreuses architectures de microprocesseurs en pipeline modernes telles que x86.

La ramification bidirectionnelle est généralement implémentée avec une instruction de saut conditionnel. Un saut conditionnel peut être "non pris" et continuer l'exécution avec la première branche de code qui suit immédiatement après le saut conditionnel, ou il peut être "pris" et sauter à un endroit différent dans la mémoire du programme où se trouve la deuxième branche de code. stockée. On ne sait pas avec certitude si un saut conditionnel sera effectué ou non jusqu'à ce que la condition ait été calculée et que le saut conditionnel ait franchi l'étape d'exécution dans le pipeline d'instructions (voir fig. 1).

Sur la base du scénario décrit, j'ai écrit une démo d'animation pour montrer comment les instructions sont exécutées dans un pipeline dans différentes situations.

1. Sans le prédicteur de branche.

Sans prédiction de branchement, le processeur devrait attendre que l'instruction de saut conditionnel ait passé l'étape d'exécution avant que l'instruction suivante puisse entrer dans l'étape de récupération dans le pipeline.

L'exemple contient trois instructions et la première est une instruction de saut conditionnel. Les deux dernières instructions peuvent entrer dans le pipeline jusqu'à l'exécution de l'instruction de saut conditionnel.

Il faudra 9 cycles d'horloge pour terminer 3 instructions.

2. Utilisez Branch Predictor et ne faites pas de saut conditionnel. Supposons que le pronostic ne prenne pas le saut conditionnel.

Il faudra 7 cycles d'horloge pour terminer 3 instructions.

3. Utilisez Branch Predictor et faites un saut conditionnel. Supposons que le pronostic ne prenne pas le saut conditionnel.

Il faudra 9 cycles d'horloge pour terminer 3 instructions.

Le temps perdu en cas de mauvaise prédiction de branche est égal au nombre d'étapes dans le pipeline de l'étape de récupération à l'étape d'exécution. Les microprocesseurs modernes ont tendance à avoir des pipelines assez longs, de sorte que le délai de mauvaise prévision se situe entre 10 et 20 cycles d'horloge. Par conséquent, l'allongement d'un pipeline augmente le besoin d'un prédicteur de branche plus avancé.

Comme vous pouvez le voir, il semble que nous n'ayons aucune raison de ne pas utiliser Branch Predictor.

C'est une démo assez simple qui clarifie la partie très basique de Branch Predictor. Si ces gifs sont ennuyeux, n'hésitez pas à les supprimer de la réponse et les visiteurs peuvent également obtenir le code source de démonstration en direct de BranchPredictorDemo

Gain de prédiction de branche!

Il est important de comprendre qu'une mauvaise prédiction de branche ne ralentit pas les programmes. Le coût d'une prédiction manquée est comme si la prédiction de branche n'existait pas et que vous attendiez l'évaluation de l'expression pour décider du code à exécuter (plus d'explications 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 assembleur généré par le compilateur, des instructions de branchement conditionnel sont insérées.

Une instruction de branchement peut amener un ordinateur à commencer à exécuter une séquence d'instructions différente et ainsi s'écarter de son comportement par défaut d'exécution des instructions dans l'ordre (c'est-à-dire si l'expression est fausse, le programme saute le code du ifbloc) en fonction d'une condition, qui est l'évaluation de l'expression dans notre cas.

Cela étant dit, le compilateur essaie de prédire le résultat avant qu'il ne soit réellement évalué. Il récupérera les instructions du ifbloc, et si l'expression s'avère vraie, alors c'est merveilleux! Nous avons gagné du temps pour l'évaluer et progressé dans le code; sinon, nous exécutons le mauvais code, le pipeline est vidé et le bloc correct est exécuté.

Visualisation:

Disons que vous devez choisir l'itinéraire 1 ou l'itinéraire 2. En attendant que votre partenaire vérifie la carte, vous vous êtes arrêté à ## et avez attendu, ou vous pouvez simplement choisir l'itinéraire1 et si vous avez de la chance (l'itinéraire 1 est le bon itinéraire), alors super, vous n'avez pas eu à attendre que votre partenaire vérifie la carte (vous avez économisé le temps qu'il lui aurait fallu pour vérifier la carte), sinon vous reviendrez simplement en arrière.

Alors que le rinçage des pipelines est super rapide, prendre ce pari en vaut la peine de nos jours. Prédire des données triées ou des données qui changent lentement est toujours plus facile et meilleur que de prédire des changements rapides.

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

Sur ARM, aucune branche n'est nécessaire, car chaque instruction a un champ de condition de 4 bits, qui teste (à un coût nul) l'une des 16 conditions différentes qui peuvent survenir dans le registre d'état du processeur, et si la condition sur une instruction est false, l'instruction est ignorée. Cela élimine le besoin de branches courtes et il n'y aurait pas de prédiction de branche pour cet algorithme. Par conséquent, la version triée de cet algorithme s'exécuterait plus lentement que la version non triée sur ARM, en raison de la surcharge supplémentaire de tri.

La boucle interne de cet algorithme ressemblerait à ce qui suit dans le langage d'assemblage ARM:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

Mais cela fait en fait partie d'une image plus grande:

CMPLes opcodes mettent toujours à jour les bits d'état dans le registre d'état du processeur (PSR), car c'est leur objectif, mais la plupart des autres instructions ne touchent pas le PSR sauf si vous ajoutez un Ssuffixe facultatif à l'instruction, spécifiant que le PSR doit être mis à jour en fonction de la résultat de l'instruction. Tout comme le suffixe de condition 4 bits, être capable d'exécuter des instructions sans affecter le PSR est un mécanisme qui réduit le besoin de branches sur ARM, et facilite également la répartition hors service au niveau matériel , car après avoir effectué une opération X qui met à jour les bits d'état, par la suite (ou en parallèle), vous pouvez effectuer un tas d'autres travaux qui ne devraient explicitement pas affecter les bits d'état, puis vous pouvez tester l'état des bits d'état définis précédemment par X.

Le champ de test de condition et le champ facultatif "bit d'état défini" peuvent être combinés, par exemple:

• ADD R1, R2, R3fonctionne R1 = R2 + R3sans mettre à jour aucun bit d'état.
• ADDGE R1, R2, R3 effectue la même opération que si une instruction précédente qui a affecté les bits d'état a entraîné une condition supérieure à ou égale.
• ADDS R1, R2, R3effectue l'addition puis met à jour les N, Z, Cet Vdrapeaux dans le statut du processeur en fonction de registre si le résultat est négatif, zéro, Adoptée (pour l' addition non signé), ou Débordés (pour plus signé).
• ADDSGE R1, R2, R3effectue l'ajout uniquement si le GEtest est vrai, puis met à jour les bits d'état en fonction du résultat de l'addition.

La plupart des architectures de processeur n'ont pas cette capacité de spécifier si les bits d'état doivent être mis à jour pour une opération donnée, ce qui peut nécessiter l'écriture de code supplémentaire pour enregistrer et restaurer ultérieurement les bits d'état, ou peut nécessiter des branches supplémentaires, ou peut limiter la sortie du processeur de l'efficacité d'exécution des ordres: l'un des effets secondaires de la plupart des architectures de jeux d'instructions CPU mettant à jour de force les bits d'état après la plupart des instructions est qu'il est beaucoup plus difficile de déterminer quelles instructions peuvent être exécutées en parallèle sans interférer les unes avec les autres. La mise à jour des bits d'état a des effets secondaires, a donc un effet de linéarisation sur le code.La capacité d'ARM de mélanger et de faire correspondre les tests de condition sans branche sur n'importe quelle instruction avec la possibilité de mettre à jour ou de ne pas mettre à jour les bits d'état après qu'une instruction soit extrêmement puissante, pour les programmeurs et les compilateurs en langage assembleur, et produit un code très efficace.

Si vous vous êtes déjà demandé pourquoi ARM a connu un succès si phénoménal, l'efficacité brillante et l'interaction de ces deux mécanismes sont une grande partie de l'histoire, car ils sont l'une des plus grandes sources d'efficacité de l'architecture ARM. La brillance des concepteurs originaux de l'ARM ISA en 1983, Steve Furber et Roger (maintenant Sophie) Wilson, ne peut pas être surestimée.

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 toujours 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 d'erreurs de prédiction élevé.

• D'un autre côté, les prédictions de branchement complexes - basées sur des neurones ou des variantes de prédiction de branche à deux niveaux - offrent une meilleure précision de prédiction, mais elles consomment plus de puissance et la complexité augmente de façon exponentielle.

• De plus, dans les techniques de prédiction 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) où l'accent est mis sur la réalisation du taux de défaillance le plus bas possible, une faible consommation d'énergie et une faible complexité avec des ressources minimales.

Il existe en réalité trois types de branches différentes:

Branches conditionnelles de transfert - en fonction d'une condition d'exécution, le PC (compteur de programmes) est modifié pour pointer vers une adresse de transfert dans le flux d'instructions.

Branches conditionnelles arrière - le PC est modifié pour pointer vers l'arrière dans le flux d'instructions. La branche est basée sur une condition, telle que la ramification vers l'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 qui n'ont aucune condition spécifique. Par exemple, une instruction de saut inconditionnelle peut être codée en langage assembleur comme simplement "jmp", et le flux d'instructions doit être immédiatement dirigé vers l'emplacement cible pointé par l'instruction de saut, tandis qu'un saut conditionnel qui peut être codé comme "jmpne" redirigerait le flux d'instructions uniquement si le résultat d'une comparaison de deux valeurs dans une précédente instruction "comparer" montre 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" (dans 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 : 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 successives du code de branche conditionnelle.

Références:

• Prédicteur de branche

• Une démonstration de l'auto-profilage

• Examen des prévisions de succursales

• Prédiction de branche

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, de cette façon, vous bouclez uniquement sur les données pertinentes et ignorez le reste.
La prédiction de branche ne manquera qu'une seule fois.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

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

Les tableaux triés sont traités plus rapidement qu'un tableau non trié, en raison d'un phénomène appelé prédiction de branche.

Le prédicteur de branche est un circuit numérique (en architecture informatique) essayant de prédire dans quelle direction ira une branche, améliorant le flux dans le pipeline d'instructions. Le circuit / ordinateur prédit l'étape suivante et l'exécute.

Faire une mauvaise prédiction conduit à revenir à l'étape précédente et à exécuter une autre prédiction. En supposant que la prédiction est correcte, le code passera à l'étape suivante. Une mauvaise prédiction entraîne la répétition de la même étape, jusqu'à ce qu'une prédiction correcte se produise.

La réponse à votre question est très simple.

Dans un tableau non trié, l'ordinateur fait plusieurs prédictions, ce qui augmente le risque d'erreurs. Alors que, dans un tableau trié, l'ordinateur fait moins de prédictions, ce qui réduit le risque d'erreurs. Faire plus de prédictions demande plus de temps.

Tableau trié: route droite ____________________________________________________________________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Réseau non trié: route incurvée

______   ________
|     |__|

Prédiction de branche: deviner / prédire quelle route est droite et la suivre sans vérifier

___________________________________________ Straight road
 |_________________________________________|Longer road

Bien que les deux routes atteignent la même destination, la route droite est plus courte et l'autre plus longue. Si alors vous choisissez l'autre par erreur, il n'y a pas de retour en arrière, et vous perdrez donc du temps supplémentaire si vous choisissez la route la plus longue. C'est semblable à ce qui se passe dans l'ordinateur, et j'espère que cela vous a aidé à mieux comprendre.

Je veux également citer @Simon_Weaver dans les commentaires:

Il ne fait pas moins de prédictions - il fait moins de prédictions incorrectes. Il reste à prévoir à chaque fois dans la boucle ...

J'ai essayé le même code avec MATLAB 2011b avec mon MacBook Pro (Intel i7, 64 bits, 2,4 GHz) pour le code MATLAB suivant:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Les résultats pour le code MATLAB ci-dessus sont les suivants:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Les résultats du code C comme dans @GManNickG j'obtiennent:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Sur cette base, il semble que MATLAB soit presque 175 fois plus lent que l'implémentation C sans tri et 350 fois plus lent avec tri. En d'autres termes, l'effet (de la prédiction de branchement) est 1,46x pour l'implémentation MATLAB et 2,7x pour l'implémentation C.

L'hypothèse des autres réponses selon laquelle il faut trier les données n'est pas correcte.

Le code suivant ne trie pas l'intégralité du tableau, mais uniquement des segments de 200 éléments, et s'exécute ainsi le plus rapidement.

Le fait de trier uniquement les sections d'éléments k termine le prétraitement en temps linéaire O(n), plutôt qu'en O(n.log(n))temps nécessaire pour trier l'ensemble du tableau.

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

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

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

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

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

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

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Cela "prouve" également que cela n'a rien à voir avec un problème algorithmique tel que l'ordre de tri, et c'est en effet une prédiction de branche.

Réponse de Bjarne Stroustrup à cette question:

Cela ressemble à une question d'entrevue. Est-ce vrai? Comment saurais tu? C'est une mauvaise idée de répondre aux questions sur l'efficacité sans d'abord faire quelques mesures, il est donc important de savoir comment mesurer.

J'ai donc essayé avec un vecteur d'un million d'entiers et obtenu:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

J'ai couru ça plusieurs fois pour être sûr. Oui, le phénomène est réel. Mon code clé était:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Au moins, le phénomène est réel avec ce compilateur, cette bibliothèque standard et ces paramètres d'optimisation. Différentes implémentations peuvent donner et donnent des réponses différentes. En fait, quelqu'un a fait une étude plus systématique (une recherche rapide sur le Web le trouvera) et la plupart des implémentations montrent cet effet.

L'une des raisons est la prédiction de branche: l'opération clé dans l'algorithme de tri est “if(v[i] < pivot]) …”ou équivalente. Pour une séquence triée, ce test est toujours vrai alors que, pour une séquence aléatoire, la branche choisie varie de façon aléatoire.

Une autre raison est que lorsque le vecteur est déjà trié, nous n'avons jamais besoin de déplacer les éléments à leur position correcte. L'effet de ces petits détails est le facteur de cinq ou six que nous avons vu.

Quicksort (et le tri en général) est une étude complexe qui a attiré certains des plus grands esprits de l'informatique. Une bonne fonction de tri résulte à la fois du choix d'un bon algorithme et de l'attention portée aux performances matérielles dans sa mise en œuvre.

Si vous voulez écrire du code efficace, vous devez en savoir un peu sur l'architecture de la machine.

Cette question est enracinée dans les modèles de prédiction de branche sur les processeurs. Je recommanderais de lire ce document:

Augmentation du taux de récupération des instructions via la prédiction de branches multiples et un cache d'adresses de branche

Lorsque vous avez trié des éléments, IR ne pouvait pas être dérangé pour récupérer toutes les instructions du processeur, encore et encore, il les récupère du cache.

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 dans la plage [0, 255] et nous ne nous soucions que des valeurs> = 128. Cela signifie que nous pouvons facilement extraire un seul bit qui nous dira si nous voulons une valeur ou non: en décalant les données à droite 7 bits, nous nous retrouvons avec un bit 0 ou 1 bit, et nous voulons seulement ajouter la valeur lorsque nous avons un bit. 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 ajouterons la valeur quelque part qui nous importe peu. 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. C'est extrêmement plus rapide sur des données aléatoires que la version avec une instruction if réelle.

Mais dans 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 décalage de bits. Cela montre comment mon code s'installe et utilise la table de recherche (appelée sans ambiguïté lut pour "LookUp Table" dans le code). Voici le code C ++:

// Déclarez puis remplissez la table de recherche

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 n'était que de 256 octets, elle s'intègre donc bien dans un cache et tout était rapide. Cette technique ne fonctionnerait pas bien si les données étaient des valeurs 24 bits et nous n'en voulions que la moitié ... la table de recherche serait beaucoup trop grande pour être pratique. D'autre part, nous pouvons combiner les deux techniques présentées ci-dessus: d'abord décaler les bits, puis indexer une table de recherche. Pour une valeur de 24 bits que nous ne voulons que la demi-valeur supérieure, nous pourrions potentiellement déplacer les données vers la droite de 12 bits et se retrouver avec une valeur de 12 bits pour un index de table. Un index de table de 12 bits implique une table de 4096 valeurs, ce qui pourrait être pratique.

La technique d'indexation dans un tableau, au lieu d'utiliser une instruction if, peut être utilisée pour décider du pointeur à utiliser. J'ai vu une bibliothèque qui implémentait des arbres binaires et au lieu d'avoir deux pointeurs nommés (pLeft et pRight ou autre) avait un tableau de pointeurs de longueur 2 et utilisait 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;
this library would do something like:

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

c'est une bonne solution peut-être que cela fonctionnera