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


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 pour autant 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ébut, je pensais que cela pourrait être juste une anomalie du langage ou du 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 le cache, mais j'ai alors pensé à quel point c'était stupide parce que 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ésume certains termes indépendants, et l'ordre ne devrait pas avoir d'importance.

21647
2018-06-27 13:51


origine


Réponses:


Vous êtes une victime de prédiction de branchement échouer.


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

Considérons une jonction de chemin de fer:

Licensed Image Image par Mecanismo, via Wikimedia Commons. Utilisé sous la CC-By-SA 3.0 Licence.

Maintenant, pour le bien de l'argumentation, supposons que ce soit dans les années 1800 - avant la communication longue distance ou radio.

Vous êtes l'opérateur d'une jonction et vous entendez un train venir. Vous n'avez aucune idée de la façon dont il est censé aller. Vous arrêtez le train pour demander au conducteur la direction qu'il veut. Et puis vous réglez l'interrupteur de manière appropriée.

Les trains sont lourds et ont beaucoup d'inertie. Donc, ils prennent 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 deviné juste, ça continue.
  • Si vous avez mal deviné, le capitaine s'arrête, recule, et vous crie dessus pour retourner l'interrupteur. Ensuite, il peut redémarrer l'autre chemin.

Si vous devinez juste à chaque fois, le train n'aura jamais à s'arrêter.
Si vous devinez mal 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:

image2

Vous êtes un processeur et vous voyez une branche. Vous n'avez aucune idée de quel chemin il ira. 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. Donc, ils prennent une éternité pour "réchauffer" et "ralentir".

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

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

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


C'est la prédiction de branche. J'avoue que ce n'est pas la meilleure analogie puisque le train pourrait simplement signaler 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 pouvez-vous stratégiquement deviner pour minimiser le nombre de fois que le train doit sauvegarder et descendre l'autre voie? Vous regardez l'histoire passée! Si le train part à gauche 99% du temps, alors vous devinez à gauche. Si elle alterne, alors vous alternez vos suppositions. Si ça se passe d'une façon toutes les 3 fois, vous devinez 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> 90% de taux de succès. Mais face à des branches imprévisibles sans motifs reconnaissables, les prédicteurs de branche sont pratiquement inutiles.

En lire plus: Article "prédicteur de branche" sur Wikipedia.


Comme indiqué ci-dessus, le coupable est cette if-déclaration:

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, la première moitié des itérations n'entrera pas dans l'instruction if. Après cela, ils entreront tous dans la déclaration if.

Ceci est très amical au prédicteur de branche puisque la branche va consécutivement dans la même direction plusieurs fois. Même un compteur de saturation simple prédisera correctement la branche à l'exception des quelques itérations après qu'elle change 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 inutilisable car il ne peut pas prédire les 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 qu'est ce qui peut être fait?

Si le compilateur n'est pas capable d'optimiser la branche dans un mouvement conditionnel, vous pouvez essayer certains 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];

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

(Notez que ce hack n'est pas strictement équivalent à l'if-statement d'origine, mais dans ce cas, il est valable 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 piratage 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 dérivation dépendante 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 mouvement conditionnel. Il n'y a donc aucune différence entre les données triées et non triées - les deux sont rapides.

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

  • Intel Compiler 11 fait quelque chose de miraculeux. Il échange les deux boucles, hissant ainsi la branche imprévisible à la boucle extérieure. Donc, non seulement il est immunisé contre les erreurs, mais il est aussi 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 vaincre le benchmark ...

  • Si vous donnez au compilateur Intel le code sans branches, 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 peuvent varier énormément dans leur capacité à optimiser le code ...


28564
2018-06-27 13:56



Prédiction de branche.

Avec un tableau trié, la condition data[c] >= 128 est premier false pour une série de valeurs, devient alors true pour toutes les valeurs ultérieures. C'est facile à prévoir. Avec un tableau non trié, vous payez pour le coût de branchement.


3635
2018-06-27 13:54



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 branchement est supprimée, comme expliqué magnifiquement dans MysticLa réponse

Maintenant, si nous regardons le code

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

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

Dans C, Ainsi C++, l'instruction, qui compilerait directement (sans aucune optimisation) dans l'instruction de mouvement conditionnel x86, est l'opérateur ternaire ... ? ... : .... Donc, nous réécrivons la déclaration ci-dessus en un équivalent:

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 Visual Studio 2010 Release Mode, le benchmark 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 c'est prévisible. En fait, lorsque vous utilisez un mouvement conditionnel, la performance est la même quel que soit le modèle de données.

Maintenant, regardons de plus près en enquêtant sur le x86 l'assemblage 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 gain réel est que max2 n'implique pas de saut de branche, jmp, qui aurait une pénalité de performance significative si le résultat prévu n'est pas correct.

Alors pourquoi un déménagement conditionnel fonctionne-t-il mieux?

Dans un typique x86 processeur, 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. Nous n'avons donc pas besoin d'attendre une instruction pour en finir une nouvelle. C'est appelé 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 soit attendre ou prédire.

Dans un cas de mouvement conditionnel, l'instruction de mouvement conditionnelle d'exécution est divisée en plusieurs étapes, mais les étapes précédentes Fetch et Decode ne dépend 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 du mouvement conditionnel est plus lente que la branche lorsque la prédiction est facile.

Le livre Les systèmes informatiques: une perspective de programmeur, deuxième édition explique cela en détail. Vous pouvez vérifier la section 3.6.6 pour Instructions de mouvement conditionnel, chapitre entier 4 pour Architecture du processeur, et la section 5.11.2 pour un traitement spécial Prédiction de branchement et pénalités de malédiction.

Parfois, certains compilateurs modernes peuvent optimiser notre code pour l'assemblage avec de meilleures performances, parfois certains compilateurs ne peuvent pas (le code en question utilise le compilateur natif de Visual Studio). Connaître la différence de performance entre une branche et un mouvement conditionnel quand elle est 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.


2958
2018-06-28 02:14



Si vous êtes curieux de connaître encore plus d'optimisations pour ce code, considérez ceci:

À partir de la boucle d'origine:

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

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

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

Ensuite, vous pouvez voir que le if conditionnelle est constante tout au long de l'exécution de la i boucle, de sorte que vous pouvez hisser le if en dehors:

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

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

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

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


2024
2017-07-03 02:25



Il ne fait aucun doute que certains d'entre nous seraient intéressés par les moyens d'identifier le code qui est problématique pour le prédicteur de branche du processeur. L'outil Valgrind cachegrind a un simulateur de prédiction de branche, activé en utilisant le --branch-sim=yes drapeau. En cours d'exécution sur les exemples de cette question, avec le nombre de boucles externes réduit à 10000 et compilé avec g++, donne ces résultats:

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%   )

Exploration de la production ligne par ligne produite par cg_annotate on voit 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 if (data[c] >= 128) ligne provoque 164.050.007 branches conditionnelles mal prà © dits (Bcm) sous le modèle de prédicteur de branche de cachegrind, alors qu'il ne provoque que 10 006 dans la version triée.


Alternativement, sous Linux, vous pouvez utiliser le sous-système des compteurs de performance pour accomplir la même tâche, mais avec des performances natives en utilisant des 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 faire l'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 de performance pour plus de détails.


1687
2017-10-12 05:53



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

Une manière courante d'éliminer la prédiction de branchement 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é 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 serrée et / ou le processeur peut pré-charger les données

Contexte et pourquoi

Pfew, alors qu'est-ce que ça veut dire?

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

Comme la prédiction de branchement, ceci a été optimisé dans les processeurs Pentium: le processeur prédit qu'il a besoin de charger une donnée et essaie de la charger dans le cache avant que l'opération n'atteigne le cache. Comme nous l'avons déjà vu, la prédiction de branchement est parfois terriblement mauvaise - dans le pire des cas, il faut revenir en arrière et attendre en fait un chargement de mémoire, ce qui prendra une éternité (en d'autres termes: la prédiction de branchement échouée est mauvaise, une charge de mémoire après l'échec d'une prédiction de branche est juste horrible!).

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

La première chose que nous devons savoir est ce qui est petit? Tandis que plus petit est généralement meilleur, une règle de base est de s'en tenir à des tables de recherche qui sont <= 4096 octets de taille. En tant que 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 pouvions créer une petite table. La prochaine chose à faire est d'obtenir une fonction de recherche en place. Les fonctions de recherche sont généralement de petites fonctions qui utilisent quelques opérations entières de base (et, ou, xor, shift, add, remove et éventuellement 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 simplement la réponse de tout le travail que vous vouliez faire.

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

Langues gérées

Vous pourriez vous demander 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 s'assurer que vous ne vous trompez pas ...

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 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 la vérification tout à fait. 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 - la clé est d'ajouter un & 0x[something]FFFà votre fonction de recherche pour rendre le contrôle des limites prévisible - et le regarder aller plus vite.

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

1158
2018-04-24 06:26



Comme les données sont réparties entre 0 et 255 lorsque le tableau est trié, autour de la première moitié des itérations ne sera pas entrer dans le if-statement (le if déclaration 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 une branche (par exemple un if-then-else structure) ira avant que cela soit connu à coup 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 la réalisation d'une performance efficace élevée!

Faisons un bench bench pour mieux le comprendre

La performance d'un if-statement dépend si son état a un modèle prévisible. Si la condition est toujours vraie ou toujours fausse, la logique de prédiction de branchement dans le processeur ramassera le motif. D'un autre côté, si le modèle est imprévisible, le ifL'état sera beaucoup plus cher.

Mesurons la performance 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

UNE "mal"Modèle vrai-faux peut faire un if-statement jusqu'à six fois plus lent qu'un "bien" modèle! Bien sûr, quel modèle est bon et qui est mauvais dépend des instructions exactes générées par le compilateur et sur le processeur spécifique.

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


1033
2018-02-15 07:24