[C++] Quel est l'effet de la commande si ... sinon si les déclarations par probabilité?



Answers

J'ai fait le test suivant pour chronométrer l'exécution de deux différents if ... else if blocs, l'un trié par ordre de probabilité, l'autre trié dans l'ordre inverse:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    long long sortedTime = 0;
    long long reverseTime = 0;

    for (int n = 0; n != 500; ++n)
    {
        //Generate a vector of 5000 random integers from 1 to 100
        random_device rnd_device;
        mt19937 rnd_engine(rnd_device());
        uniform_int_distribution<int> rnd_dist(1, 100);
        auto gen = std::bind(rnd_dist, rnd_engine);
        vector<int> rand_vec(5000);
        generate(begin(rand_vec), end(rand_vec), gen);

        volatile int nLow, nMid, nHigh;
        chrono::time_point<chrono::high_resolution_clock> start, end;

        //Sort the conditional statements in order of increasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 95) ++nHigh;               //Least likely branch
            else if (i < 20) ++nLow;
            else if (i >= 20 && i < 95) ++nMid; //Most likely branch
        }
        end = chrono::high_resolution_clock::now();
        reverseTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

        //Sort the conditional statements in order of decreasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 20 && i < 95) ++nMid;  //Most likely branch
            else if (i < 20) ++nLow;
            else if (i >= 95) ++nHigh;      //Least likely branch
        }
        end = chrono::high_resolution_clock::now();
        sortedTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

    }

    cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}

En utilisant MSVC2017 avec / O2, les résultats montrent que la version triée est systématiquement environ 28% plus rapide que la version non triée. Par le commentaire de Luk32, j'ai également changé l'ordre des deux tests, ce qui fait une différence notable (22% vs 28%). Le code a été exécuté sous Windows 7 sur un Intel Xeon E5-2697 v2. Ceci est, bien sûr, très spécifique au problème et ne doit pas être interprété comme une réponse concluante.

Question

Plus précisément, si j'ai une série de if ... else if déclarations, et je sais d'une manière ou d'une autre la probabilité relative que chaque déclaration va évaluer à true , combien de temps d'exécution fait-il pour les trier par ordre de probabilité? Par exemple, devrais-je préférer ceci:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

pour ça?:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

Il semble évident que la version triée serait plus rapide, mais pour la lisibilité ou l'existence d'effets secondaires, nous pourrions vouloir les ordonner de façon non optimale. Il est également difficile de dire à quel point le CPU va faire avec la prédiction de branche jusqu'à ce que vous exécutiez le code.

Donc, au cours de l'expérimentation avec cela, j'ai fini par répondre à ma propre question pour un cas spécifique, mais j'aimerais aussi entendre d'autres opinions / idées.

Important: cette question suppose que les instructions if peuvent être arbitrairement réorganisées sans avoir d'autres effets sur le comportement du programme. Dans ma réponse, les trois tests conditionnels s'excluent mutuellement et ne produisent aucun effet secondaire. Certes, si les déclarations doivent être évaluées dans un certain ordre pour atteindre un comportement souhaité, alors la question de l'efficacité est discutable.




Juste mes 5 cents. Il semble que l'effet de la commande si les instructions doivent dépendre de:

  1. Probabilité de chaque instruction if.

  2. Nombre d'itérations, de sorte que le prédicteur de branche puisse être activé.

  3. Indices de compilateur probables / improbables, c'est-à-dire disposition de code.

Pour explorer ces facteurs, j'ai comparé les fonctions suivantes:

ordered_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] < check_point) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] == check_point) // very unlikely
        s += 1;
}

reverse_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] == check_point) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] < check_point) // highly likely
        s += 3;
}

ordered_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (likely(data[i] < check_point)) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
}

reverse_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (likely(data[i] < check_point)) // highly likely
        s += 3;
}

Les données

Le tableau de données contient des nombres aléatoires compris entre 0 et 100:

const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];

static void data_init(int data_sz)
{
    int i;
        srand(0);
    for (i = 0; i < data_sz * 1024; i++)
        data[i] = rand() % RANGE_MAX;
}

Les resultats

Les résultats suivants sont pour Intel i5 @ 3,2 GHz et G ++ 6.3.0. Le premier argument est le check_point (c'est-à-dire la probabilité en %% pour l'instruction if très probable), le second argument est data_sz (c'est-à-dire le nombre d'itérations).

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/75/4                    4326 ns       4325 ns     162613
ordered_ifs/75/8                   18242 ns      18242 ns      37931
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612
reversed_ifs/50/4                   5342 ns       5341 ns     126800
reversed_ifs/50/8                  26050 ns      26050 ns      26894
reversed_ifs/75/4                   3616 ns       3616 ns     193130
reversed_ifs/75/8                  15697 ns      15696 ns      44618
reversed_ifs/100/4                  3738 ns       3738 ns     188087
reversed_ifs/100/8                  7476 ns       7476 ns      93752
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/75/4         3165 ns       3165 ns     218492
ordered_ifs_with_hints/75/8        13785 ns      13785 ns      50574
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205
reversed_ifs_with_hints/50/4        6573 ns       6572 ns     105629
reversed_ifs_with_hints/50/8       27351 ns      27351 ns      25568
reversed_ifs_with_hints/75/4        3537 ns       3537 ns     197470
reversed_ifs_with_hints/75/8       16130 ns      16130 ns      43279
reversed_ifs_with_hints/100/4       3737 ns       3737 ns     187583
reversed_ifs_with_hints/100/8       7446 ns       7446 ns      93782

Une analyse

1. La commande est importante

Pour les itérations 4K et (presque) 100% de probabilité de déclaration très appréciée, la différence est énorme: 223%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
reversed_ifs/100/4                  3738 ns       3738 ns     188087

Pour les itérations 4K et la probabilité de 50% d'une déclaration fortement appréciée, la différence est d'environ 14%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
reversed_ifs/50/4                   5342 ns       5341 ns     126800

2. Le nombre d'itérations est important

La différence entre les itérations 4K et 8K pour (presque) 100% de probabilité d'une déclaration fortement appréciée est environ deux fois (comme prévu):

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612

Mais la différence entre les itérations 4K et 8K pour une probabilité de 50% de déclaration fortement aimée est 5,5 fois:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852

Pourquoi est-ce? En raison des échecs de prédiction de branche. Voici les échecs de branche pour chaque cas mentionné ci-dessus:

ordered_ifs/100/4    0.01% of branch-misses
ordered_ifs/100/8    0.01% of branch-misses
ordered_ifs/50/4     3.18% of branch-misses
ordered_ifs/50/8     15.22% of branch-misses

Donc, sur mon i5, le prédicteur de branchement échoue de manière spectaculaire pour les branches moins importantes et les grands ensembles de données.

3. Conseils Aide un peu

Pour les itérations 4K, les résultats sont un peu moins bons pour une probabilité de 50% et un peu meilleurs pour une probabilité proche de 100%:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687

Mais pour les itérations 8K les résultats sont toujours un peu meilleurs:

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/100/8                   3381 ns       3381 ns     207612
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205

Donc, les conseils aident aussi, mais juste un tout petit peu.

La conclusion générale est: toujours comparer le code, parce que les résultats peuvent surprendre.

J'espère que cela pourra aider.




Si vous connaissez déjà la probabilité relative de l'instruction if-else, il serait préférable, à des fins de performance, d'utiliser la méthode triée, car elle ne vérifie qu'une seule condition (la vraie).

De manière non triée, le compilateur vérifiera toutes les conditions inutilement et prendra du temps.




J'ai décidé de relancer le test sur ma propre machine en utilisant le code Lik32. Je devais le changer en raison de mes fenêtres ou compilateur pensée haute résolution est de 1ms, en utilisant

mingw32-g ++ .exe -O3 -Wall -std = c ++ 11 -fexceptions -g

vector<int> rand_vec(10000000);

GCC a fait la même transformation sur les deux codes originaux.

Notez que seules les deux premières conditions sont testées car la troisième doit toujours être vraie, GCC est une sorte de Sherlock ici.

Sens inverse

.L233:
        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L219
.L293:
        mov     edx, DWORD PTR [rsp+104]
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
.L217:
        add     rax, 4
        cmp     r14, rax
        je      .L292
.L219:
        mov     edx, DWORD PTR [rax]
        cmp     edx, 94
        jg      .L293 // >= 95
        cmp     edx, 19
        jg      .L218 // >= 20
        mov     edx, DWORD PTR [rsp+96]
        add     rax, 4
        add     edx, 1 // < 20 Sherlock
        mov     DWORD PTR [rsp+96], edx
        cmp     r14, rax
        jne     .L219
.L292:
        call    std::chrono::_V2::system_clock::now()

.L218: // further down
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
        jmp     .L217

And sorted

        mov     DWORD PTR [rsp+104], 0
        mov     DWORD PTR [rsp+100], 0
        mov     DWORD PTR [rsp+96], 0
        call    std::chrono::_V2::system_clock::now()
        mov     rbp, rax
        mov     rax, QWORD PTR [rsp+8]
        jmp     .L226
.L296:
        mov     edx, DWORD PTR [rsp+100]
        add     edx, 1
        mov     DWORD PTR [rsp+100], edx
.L224:
        add     rax, 4
        cmp     r14, rax
        je      .L295
.L226:
        mov     edx, DWORD PTR [rax]
        lea     ecx, [rdx-20]
        cmp     ecx, 74
        jbe     .L296
        cmp     edx, 19
        jle     .L297
        mov     edx, DWORD PTR [rsp+104]
        add     rax, 4
        add     edx, 1
        mov     DWORD PTR [rsp+104], edx
        cmp     r14, rax
        jne     .L226
.L295:
        call    std::chrono::_V2::system_clock::now()

.L297: // further down
        mov     edx, DWORD PTR [rsp+96]
        add     edx, 1
        mov     DWORD PTR [rsp+96], edx
        jmp     .L224

Donc, cela ne nous dit pas grand chose sauf que le dernier cas n'a pas besoin d'une branche prédire.

Maintenant, j'ai essayé toutes les 6 combinaisons de l'if, les 2 premiers sont l'inverse d'origine et triés. élevé est> = 95, faible est <20, milieu est 20-94 avec 10000000 itérations chacun.

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 44000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 46000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 43000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 48000000ns
high, mid, low: 44000000ns
low, mid, high: 44000000ns
mid, high, low: 45000000ns
low, high, mid: 45000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 47000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 46000000ns
low, high, mid: 44000000ns

high, low, mid: 43000000ns
mid, low, high: 46000000ns
high, mid, low: 45000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

high, low, mid: 42000000ns
mid, low, high: 46000000ns
high, mid, low: 44000000ns
low, mid, high: 45000000ns
mid, high, low: 45000000ns
low, high, mid: 44000000ns

1900020, 7498968, 601012

Process returned 0 (0x0)   execution time : 2.899 s
Press any key to continue.

So why is the order high, low, med then faster (marginally)

Because the most unpredictable is last and therefore is never run through a branch predictor.

          if (i >= 95) ++nHigh;               // most predictable with 94% taken
          else if (i < 20) ++nLow; // (94-19)/94% taken ~80% taken
          else if (i >= 20 && i < 95) ++nMid; // never taken as this is the remainder of the outfalls.

So the branches will be predicted taken, taken and remainder with

6%+(0.94*)20% mispredicts.

"Sorted"

          if (i >= 20 && i < 95) ++nMid;  // 75% not taken
          else if (i < 20) ++nLow;        // 19/25 76% not taken
          else if (i >= 95) ++nHigh;      //Least likely branch

The branches will be predicted with not taken, not taken and Sherlock.

25%+(0.75*)24% mispredicts

Giving 18-23% difference (measured difference of ~9%) but we need to calculate cycles instead of mispredicting %.

Let's assume 17 cycles mispredict penalty on my Nehalem CPU and that each check takes 1 cycle to issue (4-5 instructions) and the loop takes one cycle too. The data dependencies are the counters and the loop variables, but once the mispredicts are out of the way it shouldn't influence the timing.

So for "reverse", we get the timings (this should be the formula used in Computer Architecture: A Quantitative Approach IIRC).

mispredict*penalty+count+loop
0.06*17+1+1+    (=3.02)
(propability)*(first check+mispredict*penalty+count+loop)
(0.19)*(1+0.20*17+1+1)+  (= 0.19*6.4=1.22)
(propability)*(first check+second check+count+loop)
(0.75)*(1+1+1+1) (=3)
= 7.24 cycles per iteration

and the same for "sorted"

0.25*17+1+1+ (=6.25)
(1-0.75)*(1+0.24*17+1+1)+ (=.25*7.08=1.77)
(1-0.75-0.19)*(1+1+1+1)  (= 0.06*4=0.24)
= 8.26

(8.26-7.24)/8.26 = 13.8% vs. ~9% measured (close to the measured!?!).

So the obvious of the OP is not obvious.

With these tests, other tests with more complicated code or more data dependencies will certainly be different so measure your case.

Changing the order of the test changed the results but that could be because of different alignments of the loop start which should ideally be 16 bytes aligned on all newer Intel CPUs but isn't in this case.




La façon dont j'ai l'habitude de voir cela résolu pour le code haute performance est de garder l'ordre le plus lisible, mais en fournissant des indications au compilateur. Voici un exemple du noyau Linux :

if (likely(access_ok(VERIFY_READ, from, n))) {
    kasan_check_write(to, n);
    res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
    memset(to + (n - res), 0, res);

Ici, l'hypothèse est que la vérification d'accès passera, et qu'aucune erreur n'est renvoyée dans res . Essayer de réorganiser l'une ou l'autre de ces clauses if ne ferait que compliquer le code, mais les macros likely() et unlikely() aident réellement à la lisibilité en indiquant quel est le cas normal et quelle est l'exception.

L'implémentation Linux de ces macros utilise des fonctionnalités spécifiques de GCC . Il semble que clang et le compilateur Intel C supportent la même syntaxe, mais MSVC n'a pas cette fonctionnalité .






Links