java - code - trier un tableau c++




Pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié? (14)

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.

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 de la CPU. L'outil Valgrind cachegrind dispose d'un simulateur de branche prédicteur, activé à l'aide de l' --branch-sim=yes . L'exécuter sur les exemples de cette question, avec le nombre de boucles externes réduit à 10 000 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 cg_annotate sortie ligne par ligne produite par cg_annotate nous 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 ligne if (data[c] >= 128) est à l'origine de 164 050 007 branches conditionnelles ( Bcm ) mal prédites sous le modèle prédicteur de branche de cachegrind, alors qu'elle ne provoque que 10 006 dans la version triée. .

Sous Linux, vous pouvez également utiliser le sous-système de compteurs de performance pour accomplir la même tâche, mais avec des performances natives à l'aide de compteurs de 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 effectuer une annotation de code source avec dissassembly.

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 tutoriel sur les performances pour plus de détails.


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();

les performances s’améliorent considérablement lorsque les données sont triées, c’est que la pénalité de prédiction de branche est supprimée, comme l’a expliqué joliment la réponse de .

Maintenant, si on regarde le code

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

nous pouvons trouver que la signification de ce if... else... particulier if... else... branche consiste à ajouter quelque chose lorsqu'une condition est remplie. Ce type de branche peut être facilement transformé en une instruction de mouvement conditionnel , qui serait compilée en une instruction de mouvement conditionnel: cmovl , dans un système x86 . La branche et donc la pénalité de prédiction de branche potentielle sont supprimées.

En C , donc en C++ , l'instruction qui compilerait directement (sans aucune optimisation) dans l'instruction de déplacement conditionnel de x86 , l'opérateur ternaire est-il ... ? ... : ... ... ? ... : ... 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 les processeurs Intel Core i7 -2600K à 3,4 GHz et Visual Studio 2010, le critère de référence est (format copié à partir de 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 quand il est prévisible. En fait, lorsque vous utilisez 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 l’assemblage x86 qu’ils génèrent. Pour simplifier, nous utilisons deux fonctions max1 et max2 .

max1 utilise la branche conditionnelle if... else ... :

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

max2 utilise l'opérateur ternaire ... ? ... : ... ... ? ... : ... :

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

Sur une machine x86-64, GCC -S génère l'assemblage 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

max2 utilise beaucoup moins de code en raison de l'utilisation de l'instruction cmovge . Mais le véritable max2 est que max2 n’implique pas de sauts de branche, jmp , ce qui entraînerait une pénalité significative en max2 performances si le résultat prédit n’est pas correct.

Alors, pourquoi un coup conditionnel fonctionne mieux?

Dans un processeur x86 typique, l'exécution d'une instruction est divisée en plusieurs étapes. En gros, nous avons différents matériels pour gérer différentes étapes. Il n’est donc pas nécessaire d’attendre la fin d’une instruction pour en commencer une nouvelle. Ceci s'appelle pipelining .

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

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 précédentes, telles que Fetch et Decode ne 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 avec déplacement conditionnel est plus lente que la branche lorsque la prédiction est facile.

Le livre Computer Systems: A Programmer's Point, 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 des pénalités de prédiction de branche et de prédiction erronée .

Parfois, certains compilateurs modernes peuvent optimiser notre code d'assemblage avec de meilleures performances, d'autres non (le code en question utilise le compilateur natif de Visual Studio). Connaître la différence de performance entre le mouvement de branche et le déplacement conditionnel lorsque imprévisible, 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.


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  \--------------------------------

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

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

Considérons un nœud ferroviaire:

de Mecanismo, via Wikimedia Commons. Utilisé sous la licence CC-By-SA 3.0 .

Maintenant, aux fins d’argumentation, supposons que cela remonte au XIXe siècle - avant les communications longue distance ou radio.

Vous êtes l'exploitant d'un carrefour et vous entendez un train arriver. Vous ne savez pas dans quel sens il est censé aller. Vous arrêtez le train pour demander au conducteur quelle direction il veut. Et ensuite, vous réglez le commutateur de manière appropriée.

Les trains sont lourds et ont beaucoup d'inertie. Donc, il faut une éternité pour démarrer et ralentir.

Y a-t-il un meilleur moyen? Vous devinez dans quelle direction va le train!

  • Si vous avez bien deviné, cela continue.
  • Si vous vous êtes trompé, le capitaine s’arrêtera, reculera et vous hurlera de tourner le bouton. Ensuite, il peut redémarrer l’autre chemin.

Si vous devinez bien à chaque fois , le train ne devra jamais s'arrêter.
Si vous vous trompez trop souvent , le train passera beaucoup de temps à s’arrêter, à sauvegarder et à redémarrer.

Prenons une instruction if: au niveau du processeur, il s’agit d’une instruction de branche:

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

Les processeurs modernes sont compliqués et ont de longs pipelines. Alors, il leur faut une éternité pour se "réchauffer" et "ralentir".

Y a-t-il un meilleur moyen? Vous devinez dans quelle direction ira la branche!

  • Si vous avez bien deviné, vous continuez à exécuter.
  • Si vous avez mal compris, vous devez vider le pipeline et revenir à la succursale. Ensuite, vous pouvez redémarrer l'autre chemin.

Si vous devinez juste à chaque fois , l'exécution ne devra jamais s'arrêter.
Si vous vous trompez trop souvent , vous passez beaucoup de temps à ralentir, à revenir en arrière et à redémarrer.

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

Alors, comment pourriez-vous stratégiquement deviner pour minimiser le nombre de fois que le train doit reculer et emprunter l'autre voie? Vous regardez l'histoire passée! Si le train va à gauche 99% du temps, alors vous devinez à gauche. S'il alterne, vous alternez vos suppositions. Si cela se passe toutes les 3 fois, on devine la même chose ...

En d'autres termes, vous essayez d'identifier un motif 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 un taux de succès supérieur à 90%. Cependant, lorsqu'ils sont confrontés à des branches imprévisibles sans modèle reconnaissable, les prédicteurs de branche sont pratiquement inutiles.

Lectures complémentaires: Article "Prédicteur de branche" sur Wikipedia .

Comme indiqué ci-dessus, le coupable est cette déclaration 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, environ la première moitié des itérations ne sera pas saisie dans l'instruction if. Après cela, ils entreront tous dans la déclaration if.

Ceci est très favorable au prédicteur de branche car celle-ci va plusieurs fois dans la même direction. Même un simple compteur saturant permet de prédire correctement la branche, à l'exception des quelques itérations qui suivent son changement 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 de données aléatoires. Ainsi, il y aura probablement environ 50% de mauvaise prédiction. (pas mieux que de deviner au hasard)

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 ne parvient pas à optimiser la branche dans un mouvement conditionnel, vous pouvez essayer quelques astuces si vous êtes prêt à sacrifier la lisibilité pour la performance.

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 certaines opérations au niveau des bits.

(Notez que ce hack n’est pas strictement équivalent à l’instruction if initiale. Mais dans ce cas, il est valable pour toutes les valeurs d’entrée de data[] .)

Benchmarks: 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 branche: Il y a une énorme différence entre les données triées et non triées.
  • Avec le piratage: Il n'y a pas de différence entre les données triées et non triées.
  • Dans le cas de C ++, le hack est en réalité un peu plus lent qu'avec la branche lorsque les données sont triées.

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

Mettre à jour:

  • GCC 4.6.1 avec -O3 ou -ftree-vectorize sur x64 est capable de générer un déplacement conditionnel. Donc, il n'y a pas de différence entre les données triées et non triées - les deux sont rapides.

  • VC ++ 2010 ne peut pas générer de déplacements conditionnels pour cette branche, même sous /Ox .

  • Intel Compiler 11 fait quelque chose de miraculeux. Il échange les deux boucles , ce qui permet de lever la branche imprévisible vers la boucle externe. Ainsi, non seulement les erreurs de prédiction sont immunisées, mais également deux fois plus vite que tout ce que VC ++ et GCC peuvent générer! En d'autres termes, ICC a profité de la boucle de test pour faire échec à la référence ...

  • Si vous attribuez le code sans embranchement au compilateur Intel, il le vectorise tout simplement à droite ... et est aussi rapide que pour la branche (avec l'échange de boucle).

Cela montre que même des compilateurs modernes matures peuvent varier énormément dans leur capacité à optimiser le code ...


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.


Dans le cas trié, vous pouvez faire mieux que de vous fier à la 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. Donc, vous devriez 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 obscurcie

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 une valeur attendue de 191,5) :-)


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:


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

Le prédicteur de branche est un circuit numérique (dans l’architecture informatique) qui tente de prédire l’orientation d’une branche, améliorant ainsi le flux dans le pipeline d’instruction. Le circuit / ordinateur prédit l'étape suivante et l'exécute.

Faire une prédiction erronée conduit à revenir à l'étape précédente et à exécuter une autre prédiction. En supposant que la prédiction est correcte, le code continuera à 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 effectue plusieurs prédictions, ce qui augmente les risques d'erreur. Tandis que l'ordinateur trie moins de prédictions, ce qui réduit les risques d'erreur. Faire plus de prédiction nécessite plus de temps.

Tableau trié: Route droite

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Tableau non trié: Route courbée

______   ________
|     |__|

Prévision 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 vous choisissez l’autre par erreur, vous ne pouvez pas revenir en arrière et vous perdez du temps si vous choisissez la route la plus longue. Ceci est similaire à ce qui se passe sur l'ordinateur et j'espère que cela vous a aidé à mieux comprendre.

Mise à jour: après ce que @Simon_Weaver a dit, je souhaite ajouter un fait supplémentaire ... "il ne fait pas moins de prédictions - il fait moins de prédictions incorrectes. Il doit encore prédire à chaque fois dans la boucle."


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];               
 }

Cette question a déjà été répondue à maintes reprises. J'aimerais néanmoins attirer l'attention du groupe sur une autre analyse intéressante.

Récemment, cet exemple (très légèrement modifié) a également été utilisé pour montrer comment un morceau de code peut être profilé dans le programme lui-même sous Windows. En cours de route, l'auteur explique également comment utiliser les résultats pour déterminer où le code passe le plus clair de son temps, à la fois dans le cas trié et non trié. Enfin, l'article montre également comment utiliser une fonction peu connue de la couche d'abstraction matérielle (HAL) pour déterminer l'ampleur des erreurs de prédiction de branche 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, derrière ce mystère se cache Branch Predictor .

Je n'essaie 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 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 le sens d'une branche (par exemple une structure if-then-else) avant que cela ne soit connu avec certitude. L'objectif du prédicteur de branche est 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 effectives élevées dans de nombreuses architectures de microprocesseurs pipelined modernes telles que x86.

Le branchement dans les deux sens est généralement implémenté avec une instruction de saut conditionnel. Un saut conditionnel peut être "non pris" et poursuivre l'exécution avec la première branche de code qui suit immédiatement le saut conditionnel, ou il peut être "pris" et passer à un autre emplacement de la mémoire programme où la seconde branche de code est stockée. On ne sait pas avec certitude si un saut conditionnel sera exécuté ou non tant que la condition n'aura pas été calculée et que le saut conditionnel n'aura pas franchi l'étape d'exécution du pipeline d'instructions (voir la figure 1).

Sur la base du scénario décrit, j'ai écrit une démonstration 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 branche, le processeur devrait attendre que l'instruction de saut conditionnel ait franchi l'étape d'exécution avant que l'instruction suivante puisse entrer dans l'étape d'extraction dans le pipeline.

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

Il faudra 9 cycles d'horloge pour que 3 instructions soient complétées.

  1. Utilisez Branch Predictor et ne faites pas de saut conditionnel. Supposons que le pronostic ne prend pas le saut conditionnel.

Il faudra 7 cycles d'horloge pour que 3 instructions soient complétées.

  1. Utilisez le prédicteur de branche et faites un saut conditionnel. Supposons que le pronostic ne prend pas le saut conditionnel.

Il faudra 9 cycles d'horloge pour que 3 instructions soient complétées.

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. En conséquence, le fait de prolonger un pipeline augmente le besoin d'un prédicteur de succursale plus avancé.

Comme vous pouvez le constater, 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 gênants, n'hésitez pas à les supprimer de la réponse et les visiteurs peuvent également obtenir la démo de git


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

Les variables booléennes sont surdéterminées en ce sens que tous les opérateurs ayant des variables booléennes en tant qu'entrée vérifient si les entrées ont une autre valeur que 0ou 1, mais les opérateurs ayant des booléens en sortie ne peuvent produire aucune autre valeur que 0ou 1. Cela rend les opérations avec les 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 branches peuvent prendre beaucoup de temps en cas de prédictions erronées. Les opérations booléennes peuvent être beaucoup plus efficaces si l’on sait avec certitude que les opérandes n’ont pas d’autre valeur que 0et 1. La raison pour laquelle le compilateur ne fait pas cette hypothèse est que les variables peuvent avoir d'autres valeurs si elles ne sont pas initialisées ou si elles proviennent de sources inconnues. Le code ci-dessus peut être optimisé si aet bont été initialisés avec des valeurs valides ou s'ils proviennent d'opérateurs produisant une 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 l'utilisation des opérateurs au niveau des bits ( &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 cycle d'horloge. L'opérateur OR ( |) fonctionne même si aet ba d'autres valeurs que 0ou 1. Les opérateurs AND ( &) et EXCLUSIVE OR ( ^) peuvent donner des résultats incohérents si les opérandes ont des valeurs autres que 0et 1.

~ne peut pas être utilisé pour NOT. Au lieu de cela, vous pouvez créer un booléen NON sur une variable connue 0ou 1en effectuant une commande 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 & bsi best une expression qui ne devrait pas être évaluée si aest false( &&ne sera pas évalué b, &sera). De même, a || bne peut pas être remplacé par a | bsi best une expression qui ne devrait pas être évaluée si aest 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 prédictions erronées de la part d'une branche).


Sur ARM, aucune branche n’est nécessaire, car chaque instruction possède un champ de condition de 4 bits, qui est testé à un coût nul. Cela élimine le besoin de branches courtes et la prédiction de branche ne serait pas touchée. Par conséquent, la version triée s'exécuterait plus lentement que la version non triée sur ARM, en raison de la charge de travail supplémentaire liée au tri. La boucle interne ressemblerait à quelque chose comme ceci:

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




branch-prediction