Przygotowałem poniższy test do czasu wykonania dwóch różnych if...else if bloki, jeden posortowany w kolejności prawdopodobieństwa, drugi posortowany w odwrotnej kolejności:

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

Używając MSVC2017 z /O2, wyniki pokazują, że posortowana wersja jest konsekwentnie o 28% szybsza niż niesortowana wersja. Zgodnie z komentarzem luk32, zmieniłem również kolejność dwóch testów, co robi zauważalną różnicę(22% vs 28%). Kod został uruchomiony pod Windows 7 na procesorze Intel Xeon E5-2697 v2. To jest, oczywiście bardzo specyficzny problem i nie powinien być interpretowany jako rozstrzygająca odpowiedź.

Nie, Nie powinieneś, chyba że jesteś naprawdę pewien, że system docelowy ma wpływ. domyślnie przejdź przez czytelność.

Wątpię w Twoje wyniki. trochę zmodyfikowałem twój przykład, więc odwrócenie wykonania jest łatwiejsze. Ideone dość konsekwentnie pokazuje, że odwrotna kolejność jest szybsza, choć niewiele. Na niektórych biegach nawet to od czasu do czasu przewrócił. Powiedziałbym, że wyniki są niejednoznaczne. Coliru też nie ma realnej różnicy. Mogę sprawdzić Exynos5422 Procesor na moim odroid xu4 później.

Rzecz w tym, że nowoczesne procesory mają predyktory gałęzi. Istnieje dużo-dużo logiki poświęconej wstępnemu pobieraniu zarówno danych, jak i instrukcji, a nowoczesne procesory x86 są raczej inteligentne, jeśli chodzi o to. Niektóre smuklejsze architektury, takie jak ramiona lub GPU mogą być na to narażone. Jest on jednak w dużej mierze zależny zarówno od kompilatora, jak i systemu docelowego.

Powiedziałbym, że optymalizacja uporządkowania gałęzi jest dość krucha i efemeryczna. Robić to tylko jako niektórzy naprawdę etap dostrajania.

Kod:

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

using namespace std;

int main()
{
    //Generate a vector of 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;

    //Count the number of values in each of three different ranges
    //Run the test a few times
    for (int n = 0; n != 10; ++n) {

        //Run the test again, but now sort the conditional statements in reverse-order of likelyhood
        {
          nLow = nMid = nHigh = 0;
          auto 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
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Reverse-sorted: \t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }

        {
          //Sort the conditional statements in order of likelyhood
          nLow = nMid = nHigh = 0;
          auto 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
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Sorted:\t\t\t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }
        cout << endl;
    }
}

Tylko moje 5 centów. Wydaje się, że efekt uporządkowania jeśli wypowiedzi powinny zależeć od:

1. Prawdopodobieństwo każdego twierdzenia if.

2. Liczba iteracji, więc branch predictor może zacząć działać.

3. Prawdopodobne / nieprawdopodobne podpowiedzi kompilatora, czyli układ kodu.

Aby zbadać te czynniki, porównałem następujące funkcje:

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

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

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

Dane

Tablica danych zawiera liczby losowe z zakresu od 0 do 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;
}

Wyniki

Poniższe wyniki dotyczą Intel i5@3,2 GHz i G++ 6.3.0. Pierwszym argumentem jest check_point (tzn. Prawdopodobieństwo w %% dla wyrażenia wysoce prawdopodobne if), drugim argumentem jest data_sz (tj. liczba iteracji).

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

Analiza

1. Zamówienie Ma Znaczenie

Dla iteracji 4K i (prawie) 100% prawdopodobieństwa bardzo lubianego stwierdzenia różnica jest ogromna 223%:

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

Dla iteracji 4K i 50% prawdopodobieństwa bardzo lubianego stwierdzenia różnica wynosi około 14%:

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

2. Liczba iteracji ma znaczenie

Różnica między iteracjami 4K i 8K dla (prawie) 100% prawdopodobieństwa bardzo lubianego stwierdzenia jest około dwa razy (zgodnie z oczekiwaniami):

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

Ale różnica między iteracjami 4K i 8K dla 50% prawdopodobieństwa bardzo lubianego stwierdzenia jest 5,5 razy:

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

Dlaczego tak jest? Bo branch predictor pudłuje. Oto Branch misses dla każdego wyżej wymienionego przypadku:

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

Więc na moim i5 branch predictor zawodzi spektakularnie dla niezbyt prawdopodobnych gałęzi i dużych zbiorów danych.

3. Podpowiedzi trochę pomagają

W przypadku iteracji 4K wyniki są nieco gorzej dla 50% prawdopodobieństwa i nieco lepiej dla blisko 100% prawdopodobieństwa:

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

Ale dla iteracji 8K wyniki są zawsze nieco lepsze:

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

Więc, podpowiedzi również pomagają, ale tylko trochę.

Ogólny wniosek brzmi: zawsze porównuj Kod, ponieważ wyniki mogą zaskoczyć.

Bazując na innych odpowiedziach tutaj, wygląda na to, że jedyną prawdziwą odpowiedzią jest: to zależy . Zależy od co najmniej następujących (choć niekoniecznie w tej kolejności ważności):

• względne prawdopodobieństwo każdej gałęzi.To jest pierwotne pytanie, które zostało zadane. Na podstawie istniejących odpowiedzi wydaje się, że istnieją pewne warunki, w których zamawianie według prawdopodobieństwa pomaga, ale wydaje się, że nie zawsze tak jest. Jeśli względne prawdopodobieństwa są nie bardzo się różnią, to jest mało prawdopodobne, aby cokolwiek zmienić, w jakiej kolejności są. Jednak, jeśli pierwszy warunek dzieje 99.999% czasu i następny jest ułamek tego, co pozostało, to zakładam, że umieszczenie najbardziej prawdopodobne jeden pierwszy będzie korzystne pod względem czasu.
• Koszt obliczenia warunku prawda / fałsz dla każdej gałęzi. Jeśli czas testowania warunków jest naprawdę wysoki dla jednej gałęzi w porównaniu z inną, to prawdopodobnie będzie to miało znaczący wpływ na czas i wydajność. Na przykład rozważmy warunek, który zajmuje 1 jednostkę czasu do obliczenia (np. sprawdzanie stanu zmiennej logicznej) w porównaniu z innym warunkiem, który zajmuje dziesiątki, setki, tysiące, a nawet miliony jednostek czasu do obliczenia (np. sprawdzanie zawartości pliku na dysku lub wykonanie złożonego zapytania SQL przeciwko dużej bazie danych). Zakładając, że kod sprawdza warunki w kolejności za każdym razem, szybsze warunki powinny być prawdopodobnie pierwsze (chyba, że są one uzależnione od innych warunków niepowodzenie pierwszy).
• kompilator/Interpreter Niektóre Kompilatory (lub interpretery) mogą zawierać optymalizacje jednego rodzaju, które mogą mieć wpływ na wydajność (a niektóre z nich są obecne tylko wtedy, gdy wybrane są pewne opcje podczas kompilacji i/lub wykonywania). Więc jeśli nie porównujesz dwóch kompilacji i wykonań identycznego kodu na tym samym systemie, używając dokładnie tego samego kompilatora, gdzie jedyną różnicą jest kolejność gałęzi, o których mowa, będziesz musiał dać trochę swobody dla odmian kompilatora.
• System Operacyjny / Sprzęt Jak wspomniano przez luk32 i Yakk, różne procesory mają swoje własne optymalizacje (podobnie jak systemy operacyjne). Więc benchmarki są ponownie podatne na zmiany tutaj.
• częstotliwość wykonywania bloku kodu Jeśli blok zawierający gałęzie jest rzadko dostępny( np. tylko raz podczas uruchamiania), to prawdopodobnie nie ma znaczenia co każ położyć gałęzie. Z drugiej strony, jeśli twój kod uderza w ten blok kodu podczas krytycznej części kodu, kolejność może mieć duże znaczenie (w zależności od benchmarków).

Jedynym sposobem, aby wiedzieć na pewno, jest porównanie konkretnego przypadku, najlepiej na systemie identycznym (lub bardzo podobnym do) zamierzonego systemu, na którym kod będzie w końcu uruchomiony. Jeśli ma działać na zestawie różnych systemów z różnym sprzętem, systemem operacyjnym itp., następnie dobrym pomysłem jest porównanie wielu odmian, aby zobaczyć, która jest najlepsza. Dobrym pomysłem może być nawet skompilowanie kodu z jednym zamówieniem na jednym typie systemu, a innym zamówieniem na innym typie systemu.

Moja osobista zasada (w większości przypadków, w przypadku braku benchmarka) to zamawianie na podstawie:

1. warunki, które opierają się na wyniku wcześniejszych warunków,
2. koszt obliczenia warunku, to
3. względne prawdopodobieństwo każdego branch.

Sposób, w jaki zwykle widzę to rozwiązane dla kodu o wysokiej wydajności, polega na utrzymywaniu kolejności, która jest najbardziej czytelna, ale dostarczaniu podpowiedzi kompilatorowi. Oto przykład z jądra Linuksa :

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

Tutaj zakłada się, że Kontrola dostępu przejdzie i że w res nie zostanie zwrócony żaden błąd. Próba zmiany kolejności którejkolwiek z tych klauzul if po prostu zmyli kod, ale makra likely() i unlikely() rzeczywiście pomagają czytelność, wskazując, co jest normalnym przypadkiem i co jest wyjątek.

Implementacja Linuksa tych makr wykorzystuje specyficzne cechy GCC . Wydaje się, że kompilator Clang i Intel C obsługuje tę samą składnię, ale MSVC nie ma takiej funkcji .

Zależy również od kompilatora i platformy, dla której kompilujesz.

Teoretycznie, najbardziej prawdopodobny warunek powinien sprawić, że skok kontrolny będzie jak najmniejszy.

Zazwyczaj najbardziej prawdopodobny warunek powinien być pierwszy:

if (most_likely) {
     // most likely instructions
} else …

Najpopularniejsze ASM są oparte na gałęziach warunkowych, które przeskakują, gdy warunek jest true. Że kod C zostanie prawdopodobnie przetłumaczony na takie pseudo asm:

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…

Dzieje się tak, ponieważ skoki powodują, że procesor anuluje rurociąg wykonawczy i przeciągnij, ponieważ licznik Programu się zmienił(dla architektur, które obsługują potoki, które są naprawdę powszechne). Wtedy chodzi o kompilator, który może, ale nie musi, zastosować kilka wyrafinowanych optymalizacji o statystycznie najprawdopodobniej warunek, aby uzyskać kontrolę wykonaj mniej skoków.

Postanowiłem ponownie uruchomić test na własnej maszynie używając kodu Lik32. Musiałem ją zmienić, ponieważ mój windows lub kompilator myślał, że wysoka rozdzielczość to 1ms, używając

Mingw32-g++.exe-O3-Wall-std=c++11-Fex-g

vector<int> rand_vec(10000000);

GCC dokonało tej samej transformacji na obu oryginalnych kodach.

Zauważ, że tylko dwa pierwsze warunki są testowane jako trzeci musi być zawsze prawdziwy, GCC jest tu rodzajem Sherlocka.

Rewers

.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

Więc to nam nie mówi dużo z wyjątkiem tego, że ostatnia sprawa nie potrzebuje oddziału.

Teraz próbowałem wszystkich 6 kombinacji if, top 2 są oryginalne odwrotne i posortowane. high is > = 95, low is

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.

Więc dlaczego kolejność jest wysoka, niska, med wtedy szybciej (marginalnie)

Ponieważ najbardziej nieprzewidywalny jest ostatni i dlatego nigdy nie jest uruchamiany przez predyktor gałęzi.

          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.

Więc gałęzie będą przewidywane wzięte, wzięte i reszta z

6%+(0.94*)20% błędy.

"sortowane"

          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

Gałęzie będą przewidywane z nie wziętymi, nie wziętymi i Sherlockiem.

25%+(0.75*)24% mispredicts

Daje różnicę 18-23% (zmierzona różnica wynosi ~9%), ale musimy obliczyć cykle zamiast błędnie interpretować %.

Załóżmy, że 17 cykli źle odczytuje karę na moim procesorze Nehalem i że każde sprawdzenie zajmuje 1 cykl do wydania (4-5 instrukcji), a pętla również trwa jeden cykl. Dane zależności To liczniki i zmienne pętli, ale gdy błędy zostaną usunięte, nie powinno to wpływać na czas.

Więc dla "odwrotnej", otrzymujemy timingi (to powinien być wzór używany w architekturze komputera: podejście ilościowe 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

I to samo dla "sortowane"

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% mierzone(blisko mierzone!?!).

Z tymi testami, innymi testami przy bardziej skomplikowanym kodzie lub większej liczbie zależności danych z pewnością będą inne, więc zmierz swój przypadek.

Zmiana kolejności testu zmieniła wyniki, ale może to być spowodowane różnymi wyrównaniami początku pętli, które powinny być idealnie wyrównane 16 bajtów na wszystkich nowszych procesorach Intela, ale nie jest w tym przypadku.

Ustaw je w dowolnej logicznej kolejności. Oczywiście, gałąź może być wolniejsza, ale rozgałęzianie nie powinno być większością pracy wykonywanej przez komputer.

Jeśli pracujesz nad krytyczną dla wydajności częścią kodu, to z pewnością użyj logicznego porządku, optymalizacji ukierunkowanej na profil i innych technik, ale dla ogólnego kodu, myślę, że to naprawdę bardziej stylistyczny wybór.

Jeśli znasz już względne prawdopodobieństwo polecenia if-else, to dla celów wydajności lepiej byłoby użyć sortowanego sposobu, ponieważ sprawdzi on tylko jeden warunek (prawdziwy).

W niesortowany sposób kompilator niepotrzebnie sprawdzi wszystkie warunki i zajmie trochę czasu.