W szczególności, jeśli mam serię if... else ifinstrukcji i w jakiś sposób wiem z góry względne prawdopodobieństwo, że każde z nich oceni true, na ile różni się czas wykonania, aby je posortować według prawdopodobieństwa? Na przykład, czy wolę to:

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

do tego?:

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

Wydaje się oczywiste, że posortowana wersja byłaby szybsza, jednak ze względu na czytelność lub istnienie efektów ubocznych możemy chcieć zamówić je nieoptymalnie. Trudno też powiedzieć, jak dobrze CPU poradzi sobie z przewidywaniem gałęzi, dopóki nie uruchomisz kodu.

Tak więc, w trakcie eksperymentowania z tym, ostatecznie odpowiedziałem na własne pytanie dotyczące konkretnego przypadku, ale chciałbym również usłyszeć inne opinie / spostrzeżenia.

Ważne: w tym pytaniu założono, że ifmożna dowolnie zmienić kolejność instrukcji, nie wywierając żadnego innego wpływu na zachowanie programu. W mojej odpowiedzi trzy testy warunkowe wykluczają się wzajemnie i nie powodują żadnych skutków ubocznych. Z pewnością, jeśli stwierdzenia muszą być ocenione w określonej kolejności, aby osiągnąć pożądane zachowanie, kwestia wydajności jest dyskusyjna.

Zasadniczo większość, jeśli nie wszystkie procesory Intel zakładają, że gałęzie do przodu nie są brane za pierwszym razem, gdy je zobaczą. Zobacz pracę Godbolta .

Następnie gałąź przechodzi do pamięci podręcznej prognoz gałęzi, a przeszłe zachowanie służy do informowania o prognozie przyszłych gałęzi.

Tak więc w ciasnej pętli efekt nieprawidłowego uporządkowania będzie stosunkowo niewielki. Predyktor gałęzi dowie się, który zestaw rozgałęzień jest najprawdopodobniej, a jeśli masz nie trywialną ilość pracy w pętli, małe różnice nie będą się sumować.

W ogólnym kodzie większość kompilatorów domyślnie (bez innego powodu) zamawia wygenerowany kod maszynowy mniej więcej tak, jak zamówiono go w kodzie. Zatem jeśli instrukcje są gałęziami forward, gdy zawiodą.

Powinieneś więc uporządkować swoje gałęzie w kolejności malejącego prawdopodobieństwa uzyskania najlepszej prognozy gałęzi po „pierwszym spotkaniu”.

Znak mikrobenchowania, który wielokrotnie zapętla się ściśle w szeregu warunków i wykonuje trywialną pracę, będzie zdominowany przez drobne efekty liczenia instrukcji i tym podobne, a także w niewielkim stopniu pod względem względnych problemów z przewidywaniem gałęzi. W takim przypadku musisz się profilować , ponieważ podstawowe zasady nie będą wiarygodne.

Ponadto wektoryzacja i wiele innych optymalizacji mają zastosowanie do małych ciasnych pętli.

Tak więc w ogólnym kodzie umieść najbardziej prawdopodobny kod w ifbloku, a to spowoduje najmniejszą liczbę braków w prognozowaniu gałęzi bez pamięci podręcznej. W ciasnych pętlach postępuj zgodnie z ogólną zasadą, a jeśli chcesz dowiedzieć się więcej, nie masz innego wyboru, jak tylko profilować.

Oczywiście wszystko to wychodzi poza okno, jeśli niektóre testy są znacznie tańsze niż inne.

Wykonałem następujący test, aby wykonać na czas wykonanie dwóch różnych if... else ifbloków, jeden posortowany według prawdopodobieństwa, a 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 około 28% szybsza niż wersja nieposortowana. Według komentarza luk32 zmieniłem również kolejność dwóch testów, co robi zauważalną różnicę (22% vs 28%). Kod został uruchomiony w systemie Windows 7 na procesorze Intel Xeon E5-2697 v2. Jest to oczywiście bardzo specyficzne dla problemu i nie powinno być interpretowane jako rozstrzygająca odpowiedź.

Nie, nie powinieneś, chyba że naprawdę masz pewność, że dotyczy to systemu docelowego. Domyślnie przejść przez czytelność.

Bardzo wątpię w twoje wyniki. Trochę zmodyfikowałem twój przykład, aby łatwiej było wykonać cofanie. Ideone konsekwentnie pokazuje, że odwrotna kolejność jest szybsza, choć niewiele. Na niektórych biegach nawet to czasami się przewracało. Powiedziałbym, że wyniki nie są jednoznaczne. coliru nie zgłasza też żadnej różnicy. Mogę później sprawdzić procesor Exynos5422 na moim odroidu xu4.

Chodzi o to, że współczesne procesory mają predyktory gałęzi. Jest dużo logiki poświęconej pobieraniu zarówno danych, jak i instrukcji, a nowoczesne procesory x86 są dość inteligentne, jeśli chodzi o to. Niektóre cieńsze architektury, takie jak ARM lub GPU, mogą być na to podatne. Ale to naprawdę bardzo zależy zarówno od kompilatora, jak i systemu docelowego.

Powiedziałbym, że optymalizacja kolejności gałęzi jest dość delikatna i efemeryczna. Zrób to tylko jako naprawdę dopracowany krok.

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 zamówienia, jeśli instrukcje powinny zależeć od:

1. Prawdopodobieństwo każdej instrukcji if.

2. Liczba iteracji, aby predyktor gałęzi mógł się uruchomić.

3. Prawdopodobne / mało prawdopodobne wskazówki kompilatora, tj. Układ kodu.

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

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

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

dane

Tablica danych zawiera liczby losowe 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ą procesorów Intel i5 @ 3,2 GHz i G ++ 6.3.0. Pierwszy argument to punkt kontrolny (tzn. Prawdopodobieństwo w %% dla wysoce prawdopodobnej instrukcji if), drugi argument to 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

W przypadku iteracji 4K i (prawie) 100% prawdopodobieństwa bardzo podobającego się 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

W przypadku iteracji 4K i 50% prawdopodobieństwa bardzo podobającego się 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 lubianej wypowiedzi 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 zdania 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 Z powodu brakujących predyktorów gałęzi. Oto brakujące rozgałęzienia dla każdego wymienionego wyżej 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

Tak więc na moim i5 predyktor gałęzi zawodzi spektakularnie w przypadku mało prawdopodobnych gałęzi i dużych zestawów danych.

3. Wskazówki Pomóż trochę

W przypadku iteracji 4K wyniki są nieco gorsze dla prawdopodobieństwa 50% i nieco lepsze dla prawdopodobieństwa bliskiego 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

Ale w przypadku 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

Wskazówki też pomagają, ale tylko trochę.

Ogólny wniosek jest następujący: zawsze testuj kod, ponieważ wyniki mogą zaskoczyć.

Mam nadzieję, że to pomaga.

Na podstawie niektórych innych odpowiedzi tutaj wydaje się, że jedyną prawdziwą odpowiedzią jest: to zależy . Zależy to przynajmniej od następujących (choć niekoniecznie w tej kolejności):

• Względne prawdopodobieństwo każdej gałęzi. To jest pierwotne pytanie, które zostało zadane. W oparciu o istniejące odpowiedzi wydaje się, że istnieją pewne warunki, w których uporządkowanie według prawdopodobieństwa pomaga, ale nie zawsze tak jest. Jeśli względne prawdopodobieństwa nie różnią się bardzo, to nie jest prawdopodobne, aby miało jakiekolwiek znaczenie w jakiej kolejności są. Jednak jeśli pierwszy warunek zdarzy się w 99,999% przypadków, a następny to ułamek tego, co pozostało, zakładamy, że umieszczenie najbardziej prawdopodobnego na pierwszym miejscu byłoby korzystne pod względem czasu.
• Koszt obliczenia warunku prawda / fałsz dla każdego oddziału. Jeśli koszt czasowy testowania warunków jest naprawdę wysoki dla jednej gałęzi w stosunku do drugiej, może to mieć znaczący wpływ na czas i wydajność. Rozważmy na przykład warunek, który wymaga 1 jednostki czasu do obliczenia (np. Sprawdzenie stanu zmiennej logicznej) w porównaniu z innym warunkiem, który wymaga dziesiątek, setek, tysięcy, a nawet milionów jednostek czasu (np. Sprawdzenie zawartości plik na dysku lub wykonywanie złożonego zapytania SQL na 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 zależą od innych warunków, które zawiodą jako pierwsze).
• Kompilator / interpreter Niektóre kompilatory (lub interpretatory) mogą zawierać optymalizacje innego rodzaju, które mogą wpływać na wydajność (a niektóre z nich są obecne tylko wtedy, gdy pewne opcje zostaną wybrane podczas kompilacji i / lub wykonania). Więc jeśli nie przeprowadzasz testów porównawczych dwóch kompilacji i wykonań identycznego kodu w tym samym systemie, używając dokładnie tego samego kompilatora, a jedyną różnicą jest kolejność gałęzi, o których mowa, będziesz musiał dać trochę swobody w zakresie wariantów kompilatora.
• System operacyjny / sprzęt Jak wspomniano w luk32 i Yakk, różne procesory mają własne optymalizacje (podobnie jak systemy operacyjne). Dlatego testy porównawcze znów są podatne na zmiany.
• Częstotliwość wykonywania bloku kodu Jeśli dostęp do bloku zawierającego rozgałęzienia jest rzadki (np. Tylko raz podczas uruchamiania), to prawdopodobnie nie ma większego znaczenia, w jakiej kolejności należy umieścić rozgałęzienia. Z drugiej strony, jeśli twój kod wbija się w ten blok kodu podczas krytycznej części kodu, wówczas zamawianie może mieć duże znaczenie (w zależności od testów porównawczych).

Jedynym sposobem, aby wiedzieć na pewno, jest przeprowadzenie testu porównawczego konkretnego przypadku, najlepiej w systemie identycznym (lub bardzo podobnym) do zamierzonego systemu, w którym kod w końcu zostanie uruchomiony. Jeśli ma on działać na zestawie różnych systemów z różnym sprzętem, systemem operacyjnym itp., Dobrym pomysłem jest przetestowanie wielu odmian, aby sprawdzić, który jest najlepszy. Dobrym pomysłem może być kompilacja kodu z jednym zamówieniem na jednym typie systemu, a drugim na innym typie systemu.

Moją osobistą zasadą (w większości przypadków, w przypadku braku testu porównawczego) jest zamawianie na podstawie:

1. Warunki, które opierają się na wynikach wcześniejszych warunków,
2. Zatem koszt obliczenia warunku
3. Względne prawdopodobieństwo każdej gałęzi.

Sposób, w jaki zwykle postrzegam to rozwiązanie w przypadku kodu o wysokiej wydajności, polega na utrzymywaniu kolejności, która jest najbardziej czytelna, ale zapewnia kompilatorowi wskazówki. Oto jeden 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 nie zostanie zwrócony żaden błąd res. Próba zmiany kolejności któregokolwiek z tych klauzul if spowoduje po prostu zamieszanie w kodzie, ale makra likely()i unlikely()faktycznie pomagają w czytelności, wskazując, co jest normalnym przypadkiem i jaki jest wyjątek.

Implementacja tych makr w systemie Linux wykorzystuje funkcje specyficzne dla GCC . Wygląda na to, że kompilator clang i Intel C obsługuje tę samą składnię, ale MSVC nie ma takiej funkcji .

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

Teoretycznie najbardziej prawdopodobny warunek powinien sprawić, że kontrola skoczy jak najmniej.

Zazwyczaj najbardziej prawdopodobnym warunkiem powinien być pierwszy:

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

Najpopularniejsze asmy oparte są na gałęziach warunkowych, które podskakują, gdy warunek jest spełniony . Ten kod C zostanie prawdopodobnie przetłumaczony na taki pseudo asm:

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

Wynika to z tego, że skoki powodują, że procesor anuluje potok wykonania i zatrzymuje się, ponieważ zmienił się licznik programu (dla architektur obsługujących potoki, które są naprawdę powszechne). Potem chodzi o kompilator, który może, ale nie musi, zastosować wyrafinowane optymalizacje dotyczące statystycznie najprawdopodobniej warunku, aby uzyskać kontrolę, wykonać mniej skoków.

Postanowiłem ponownie uruchomić test na własnym komputerze, używając kodu Lik32. Musiałem to zmienić, ponieważ moje okna lub kompilator uważają, że wysoka rozdzielczość to 1ms

mingw32-g ++. exe -O3 -Wall -std = c ++ 11 -wyrażenia -g

vector<int> rand_vec(10000000);

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

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

Odwrócić

.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

To niewiele nam mówi, poza tym, że ostatni przypadek nie wymaga przewidywania oddziału.

Teraz wypróbowałem wszystkie 6 kombinacji if, pierwsze 2 są oryginalną odwrotnością i posortowane. high is> = 95, low is <20, mid is 20-94 with 10000000 iterations.

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.

Dlaczego więc kolejność jest wysoka, niska, med, a następnie szybsza (nieznacznie)

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 oddziały zostaną przepowiedziane, zabrane, zabrane i pozostały przy

6% + (0,94 *) 20% nieprzewidywalnych.

„Posortowane”

          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

Oddziały będą przewidywane z nie zabranych, nie zabranych i Sherlocka.

25% + (0,75 *) 24% nieprzewidywalnych

Dajemy 18-23% różnicy (zmierzona różnica ~ 9%), ale musimy obliczyć cykle zamiast błędnego przewidywania%.

Załóżmy, że 17 cykli za niepoprawną karę na moim procesorze Nehalem i że każda kontrola zajmuje 1 cykl na wydanie (instrukcje 4-5), a pętla zajmuje również jeden cykl. Zależności danych to liczniki i zmienne pętlowe, ale gdy błędne prognozy staną się na przeszkodzie, nie powinno to wpłynąć na czas.

W przypadku „odwrotności” otrzymujemy czasy (powinna to być formuła stosowana w architekturze komputerowej: 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 „posortowane”

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

Zatem oczywiste z PO nie jest oczywiste.

Dzięki tym testom inne testy z bardziej skomplikowanym kodem lub większą liczbą zależności danych na pewno będą się różnić, dlatego zmierz swoją sprawę.

Zmiana kolejności testu zmieniła wyniki, ale mogło to wynikać z różnych wyrównań początku pętli, które najlepiej powinny być wyrównane 16 bajtów na wszystkich nowszych procesorach Intela, ale tak nie jest.

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

Jeśli pracujesz nad częścią kodu krytyczną pod względem wydajności, z pewnością użyj logicznej kolejności, optymalizacji kierowanej profilem i innych technik, ale w przypadku kodu ogólnego uważam, że jest to raczej wybór stylistyczny.

Jeśli znasz już względne prawdopodobieństwo instrukcji if-else, dla celów wydajności lepiej posortować sposób, ponieważ sprawdzi on tylko jeden warunek (prawdziwy).

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