Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie niesortowanej tablicy?

/ align = "left" /

W przypadku posortowanej tablicy warunek data[c] >= 128 jest najpierw false Dla ciągu wartości, a następnie staje się true dla wszystkich późniejszych wartości. Łatwo to przewidzieć. Przy niesortowanej tablicy płacisz za koszty rozgałęzienia.

Powodem, dla którego wydajność drastycznie poprawia się, gdy dane są sortowane, jest to, że kara przewidywania gałęzi jest usuwana, jak pięknie wyjaśniono w Mysticial ' s answer.

Teraz, jeśli spojrzymy na kod

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

Możemy stwierdzić, że znaczeniem tej konkretnej gałęzi if... else... jest dodanie czegoś, gdy warunek jest spełniony. Ten typ gałęzi może być łatwo przekształcony w polecenie conditional move, które zostanie skompilowane do warunkowego Instrukcja move: cmovl, w systemie x86. Gałąź, a tym samym potencjalny oddział predykcji kary jest usuwany.

W C, a więc C++, instrukcja, która skompilowałaby się bezpośrednio (bez żadnej optymalizacji) do instrukcji warunkowego ruchu w x86, jest operatorem trójdzielnym ... ? ... : .... Tak więc przepisujemy powyższe stwierdzenie na równoważne:

sum += data[c] >=128 ? data[c] : 0;

Zachowując czytelność, możemy sprawdzić współczynnik przyspieszania.

Na Intel Core i7 -2600K @ 3,4 GHz i tryb Wydania Visual Studio 2010, benchmark to:

X86

X64

Wynik jest solidny w wielu testy. Bardzo przyspieszamy, gdy wynik gałęzi jest nieprzewidywalny, ale trochę cierpimy, gdy jest przewidywalny. W rzeczywistości przy użyciu ruchu warunkowego wydajność jest taka sama niezależnie od wzorca danych.

Przyjrzyjmy się teraz dokładniej badając x86 zgromadzenie, które generują. Dla uproszczenia używamy dwóch funkcji max1 i max2.

max1 używa gałęzi warunkowej if... else ...:

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

max2 używa operatora trójdzielnego ... ? ... : ...:

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

Na maszynie x86-64, GCC -S generuje poniższy zestaw.

: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 używa znacznie mniej kodu ze względu na użycie instrukcji cmovge. Ale prawdziwym zyskiem jest to, że max2 nie wiąże się ze skokami gałęzi, jmp, które mają znaczną karę wydajności, jeśli przewidywany wynik nie jest właściwy.

Więc dlaczego ruch warunkowy działa lepiej?

W typowym procesorze x86 wykonywanie instrukcji jest podzielone na kilka etapów. Z grubsza mamy inny sprzęt do radzenia sobie z różnymi etapami. Nie musimy więc czekać na ukończenie jednej instrukcji, aby rozpocząć nową. To się nazywa pipelining.

W przypadku gałęzi następująca instrukcja jest określona przez poprzednią, więc nie możemy wykonać pipeliningu. Musimy albo czekać, albo przewidywać.

W przypadku warunkowego przeniesienia Instrukcja wykonania warunkowego przeniesienia jest podzielona na kilka etapów, ale wcześniejsze etapy takie jak Fetch i Decode nie zależą od wyniku poprzedniej instrukcji; tylko ostatnie etapy wymagają wyniku. Tak więc czekamy ułamek czasu wykonania jednej instrukcji. To dlatego wersja warunkowego ruchu jest wolniejsza od gałęzi, gdy przewidywanie jest łatwe.

Książka Systemy Komputerowe. perspektywa programisty. wydanie II wyjaśnia to szczegółowo. Możesz sprawdzić sekcję 3.6.6 dla instrukcji warunkowego ruchu, cały rozdział 4 dla architektury procesora, oraz Sekcja 5.11.2 dla specjalnego traktowania dla przewidywania gałęzi i kar za błędy predykcyjne.

Czasami niektóre nowoczesne Kompilatory mogą zoptymalizować nasz kod do montażu z lepszą wydajnością, czasami niektóre Kompilatory nie mogą (Kod, o którym mowa, używa natywnego kompilatora Visual Studio). Znajomość różnicy wydajności między odgałęzieniem a ruchem warunkowym, gdy jest nieprzewidywalny, może pomóc nam napisać kod z lepszą wydajnością, gdy scenariusz staje się tak złożony, że kompilator nie może zoptymalizować ich automatycznie.

Jeśli jesteś ciekawy jeszcze więcej optymalizacji, które można wykonać w tym kodzie, rozważ to:

Zaczynając od oryginalnej pętli:

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

Przy wymianie pętli możemy bezpiecznie zmienić tę pętlę na:

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

Wtedy możesz zobaczyć, że if warunkowa jest stała przez cały czas wykonywania i pętli, więc możesz wyciągnąć if Na Zewnątrz:

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

Wtedy widzisz, że pętla wewnętrzna może być zwinięta w jedno wyrażenie, zakładając zmiennoprzecinkową model pozwala na to (/fp:fast jest wyrzucany, na przykład)

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

Bez wątpienia niektórzy z nas byliby zainteresowani sposobami identyfikacji kodu, który jest problematyczny dla predyktora gałęzi procesora. Narzędzie Valgrind cachegrind posiada symulator branch-predictor, włączony za pomocą znacznika --branch-sim=yes. Na przykładach w tym pytaniu, z liczbą zewnętrznych pętli zmniejszoną do 10000 i skompilowaną z g++, daje następujące wyniki:

Sortowane:

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

Niesortowane:

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

Wiercenie w dół do linii po linii wyjście wytworzone przez cg_annotate widzimy dla danej pętli:

Sortowane:

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

Niesortowane:

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

Pozwala to na łatwą identyfikację problematycznej linii - w wersji niesortowanej linia if (data[c] >= 128) powoduje 164 050 007 błędnie zdefiniowanych gałęzi warunkowych (Bcm) w modelu cachegrind branch-predictor, podczas gdy w wersji posortowanej powoduje tylko 10 006.

Alternatywnie, w Linuksie można użyć liczników wydajności podsystem do wykonania tego samego zadania, ale z natywną wydajnością przy użyciu liczników CPU.

perf stat ./sumtest_sorted

Sortowane:

 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

Niesortowane:

 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

Może również wykonywać adnotację kodu źródłowego za pomocą disassassembly.

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

Właśnie przeczytałem to pytanie i odpowiedzi na nie i czuję, że brakuje odpowiedzi.

Powszechnym sposobem na wyeliminowanie przewidywania gałęzi, które okazało się szczególnie dobre w językach zarządzanych, jest wyszukiwanie tabeli zamiast używania gałęzi (chociaż nie testowałem tego w tym przypadku).

To podejście działa ogólnie, jeśli:

Jest to mała tabela, która prawdopodobnie będzie buforowana w procesorze i
1. prowadzisz rzeczy w dość ciasnej pętli i / lub procesor może wstępnie załadować dane.

Informacje ogólne i dlaczego

Z punktu widzenia procesora, twoja pamięć jest wolna. Aby zrekompensować różnicę w prędkości, kilka pamięci podręcznych jest wbudowanych w procesor (pamięć podręczna L1/L2). Więc wyobraź sobie, że robisz swoje ładne obliczenia i dowiedzieć się, że potrzebujesz kawałek pamięci. Procesor otrzyma operację "load" i ładuje kawałek pamięci do pamięci podręcznej-a następnie używa pamięci podręcznej do wykonywania pozostałych obliczeń. Ponieważ pamięć jest stosunkowo wolna, to "Ładowanie" spowolni twój program.

Podobnie jak przewidywanie gałęzi, zostało to zoptymalizowane w procesorach Pentium: procesor przewiduje, że musi załadować kawałek danych i próbuje załadować go do pamięci podręcznej, zanim operacja faktycznie trafi w pamięć podręczną. Jak już widzieliśmy, przewidywanie gałęzi czasami idzie okropnie źle - w najgorszym przypadku musisz wrócić i faktycznie poczekać na obciążenie pamięci, które zajmie wieczność (w innymi słowy: niepowodzenie przewidywania gałęzi jest złe, obciążenie pamięci po niepowodzeniu przewidywania gałęzi jest po prostu straszne!).

Na szczęście dla nas, jeśli wzór dostępu do pamięci jest przewidywalny, procesor załaduje go do szybkiej pamięci podręcznej i wszystko będzie dobrze.

Pierwszą rzeczą, którą musimy wiedzieć, jest to, co jest małe ? Podczas gdy mniejsze jest ogólnie lepsze, zasadą jest trzymanie się tabel wyszukiwania, które mają rozmiar

Konstruowanie tabeli

Więc doszliśmy do wniosku, że możemy stworzyć mały stolik. Następną rzeczą do zrobienia jest uzyskanie funkcji wyszukiwania w miejscu. Funkcje wyszukiwania są zwykle małymi funkcjami, które używają kilku podstawowych operacji typu integer (and, or, xor, shift, add, remove i być może multiply). Chcesz, aby Twój wkład został przetłumaczony przez funkcję wyszukiwania na jakiś "unikalny klucz" w tabeli, który następnie po prostu daje odpowiedź cała praca, którą chciałeś.

W tym przypadku: > = 128 oznacza, że możemy zachować wartość,

Języki zarządzane

Możesz się zastanawiać, dlaczego to działa dobrze w zarządzanych językach. W końcu języki zarządzane sprawdzają granice tablic za pomocą gałęzi, aby upewnić się, że nie nawalisz...

Było sporo pracy nad wyeliminowaniem tej gałęzi dla języków zarządzanych. Na przykład:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

W tym przypadku jest oczywiste dla kompilatora, że warunek graniczny nigdy nie zostanie spełniony. Przynajmniej kompilator Microsoft JIT (ale spodziewam się, że Java robi podobne rzeczy) zauważy to i usunie / align = "left" / To znaczy, że nie ma gałęzi. Podobnie będzie z innymi oczywistymi przypadkami.

Jeśli napotkasz problemy z wyszukiwaniem w językach zarządzanych, kluczem jest dodanie & 0x[something]FFF do funkcji wyszukiwania, aby sprawdzenie granic było przewidywalne - i obserwowanie, jak przebiega szybciej.

Wynik tej sprawy

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, 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();

Ponieważ dane są dystrybuowane pomiędzy 0 a 255, gdy tablica jest sortowana, około pierwszej połowy iteracji nie wprowadzi instrukcji if-(Instrukcja if jest dzielona poniżej).

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

Pytanie brzmi: co sprawia, że powyższa instrukcja nie jest wykonywana w pewnych przypadkach, jak w przypadku posortowanych danych? Nadchodzi "Branch predictor". Predyktor gałęzi jest obwodem cyfrowym, który próbuje odgadnąć, w którą stronę pójdzie gałąź (np. struktura if-then-else), zanim będzie to znane na pewno. Na celem branch predictor jest poprawa przepływu w potoku instrukcji. Branch predictors odgrywają kluczową rolę w osiąganiu wysokiej skuteczności!

Zróbmy kilka oznaczeń na ławce, aby lepiej to zrozumieć

Wydajność if-twierdzenie zależy od tego, czy jego stan ma przewidywalny wzór. Jeśli warunek jest zawsze prawdziwy lub zawsze fałszywy, logika przewidywania gałęzi w procesorze wychwyci wzór. Z drugiej strony, jeśli wzór jest nieprzewidywalny, twierdzenie if - będzie znacznie droższe.

Zmierzmy wydajność tej pętli z różnymi warunkami:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Oto timingi pętli z różnymi wzorcami true-false:

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

A " bad" true-false wzorzec może sprawić, że if-stwierdzenie będzie do sześciu razy wolniejsze niż " good" wzorzec! Oczywiście, który wzorzec jest dobry, a który zły zależy od dokładnych instrukcji generowanych przez kompilator i na konkretnym procesorze.

Więc nie ma wątpliwości co do wpływu przewidywania gałęzi na wydajność!

Jednym ze sposobów uniknięcia błędów przewidywania gałęzi jest zbudowanie tabeli wyszukiwania i indeksowanie jej za pomocą danych. Stefan de Bruijn mówił o tym w swojej odpowiedzi.

Ale w tym przypadku wiemy, że wartości są w zakresie [0, 255] i zależy nam tylko na wartościach >= 128. Oznacza to, że możemy łatwo wyodrębnić pojedynczy bit, który powie nam, czy chcemy wartości, czy nie: przesuwając dane do prawej 7 bitów, pozostajemy z bitem 0 LUB 1 bitem, a chcemy dodać wartość tylko wtedy, gdy mamy 1 bit. Nazwijmy to "decyzją".

Używając wartości 0/1 bitu decyzji jako indeksu do tablicy, możemy tworzyć kod, który będzie równie szybki niezależnie od tego, czy dane są sortowane, czy nie. Nasz kod zawsze doda wartość, ale gdy bit decyzji będzie równy 0, dodamy wartość gdzieś, na czym nam nie zależy. Oto kod:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Ten kod marnuje połowę dodanych, ale nigdy nie ma awarii przewidywania gałęzi. Jest ogromnie szybszy na losowych danych niż wersja z rzeczywiste oświadczenie if.

Ale w moich testach, Jawna tabela wyszukiwania była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli wyszukiwania było nieco szybsze niż przesuwanie bitów. To pokazuje jak mój kod ustawia i używa tabeli lookup (niewyobrażalnie zwanej lut dla "tabeli LookUp" w kodzie). Oto kod C++:

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

W tym przypadku tabela wyszukiwania miała tylko 256 bajtów, więc ładnie mieści się w pamięci podręcznej i wszystko było szybkie. Ta technika nie działa dobrze, jeśli dane było 24-bitowe wartości i chcieliśmy tylko połowę z nich... tabela wyszukiwania byłaby zbyt duża, aby była praktyczna. Z drugiej strony, możemy połączyć dwie techniki pokazane powyżej: najpierw przesuń bity nad, a następnie indeks tabeli wyszukiwania. Dla wartości 24-bitowej, której chcemy tylko górną połowę, możemy potencjalnie przesunąć dane w prawo o 12 bitów i pozostawić 12-bitową wartość dla indeksu tabeli. 12-bitowy indeks tabel zakłada tabelę 4096 wartości, co może być praktyczne.

Technika indeksowanie do tablicy, zamiast używania instrukcji if, może być używane do decydowania, którego wskaźnika użyć. Widziałem bibliotekę, która zaimplementowała binarne drzewa, i zamiast mieć dwa nazwane wskaźniki (pLeft i pRight czy cokolwiek innego) miała tablicę wskaźników długości-2 i używała techniki" bit decyzji", aby zdecydować, który z nich należy wykonać. Na przykład zamiast:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

Ta biblioteka zrobiłaby coś takiego:

i = (x < node->value);
node = node->link[i];

Oto link do tego kodu: czerwone czarne drzewa, Eternally Confuzzled

W posortowanym przypadku możesz zrobić coś lepszego niż polegać na pomyślnym przewidywaniu gałęzi lub jakimkolwiek sztuczce porównawczej bez rozgałęzień: całkowicie usunąć gałąź.

Rzeczywiście, tablica jest podzielona w strefie ciągłej za pomocą data < 128, a druga za pomocą data >= 128. Powinieneś więc znaleźć punkt podziału za pomocą wyszukiwania dychotomicznego (używając porównań Lg(arraySize) = 15), a następnie wykonać prostą akumulacji z tego punktu.

Coś w rodzaju (niezaznaczone)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

Lub nieco więcej obfuscated

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Jeszcze szybsze podejście, które daje przybliżone rozwiązanie zarówno dla sortowanych, jak i niesortowanych to: sum= 3137536; (przy założeniu prawdziwie jednolitego rozkładu, 16384 próbek o wartości oczekiwanej 191.5) :-)

Powyższe zachowanie dzieje się z powodu przewidywania gałęzi.

Aby zrozumieć przewidywanie gałęzi należy najpierw zrozumieć instruction Pipeline :

Każda instrukcja jest podzielona na sekwencję kroków tak, że różne kroki mogą być wykonywane jednocześnie równolegle. Technika ta jest znana jako instruction pipeline i jest używana do zwiększenia przepustowości w nowoczesnych procesorach. Aby to lepiej zrozumieć zobacz ten przykład na Wikipedia.

Ogólnie rzecz biorąc, nowoczesne procesory mają dość długie potoki, ale dla ułatwienia rozważmy tylko te 4 kroki.

1. IF -- Fetch the instruction from memory
2. ID -- Decode the instruction
3. EX -- wykonaj instrukcję
4. WB -- Write back to CPU register

4-etap rurociągu ogólnie dla 2 instrukcji.

Wracając do powyższego pytania rozważmy następujące Instrukcja:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Bez przewidywania gałęzi, następowałoby:

Aby wykonaÄ ‡ instrukcjÄ ™ B lub instrukcjÄ ™ C, procesor bÄ ™ dzie musiaĹ 'poczekać, aĹź Instrukcja A nie dotrze do etapu EX w potoku, poniewaĹź decyzja o przejĹ" ciu do instrukcji B lub instrukcji C zaleĹźy od wyniku instrukcji A. Tak wiÄ ™ c potoki bÄ ™ dÄ ... wyglÄ ... daÄ ‡ tak.

gdy warunek if zwraca true:

gdy zwraca warunek if false:

W wyniku oczekiwania na wynik instrukcji A, suma cykli CPU spędzonych w powyższym przypadku (bez przewidywania gałęzi; zarówno dla true, jak i false) wynosi 7.

Czym jest przewidywanie gałęzi?

Branch predictor spróbuje odgadnąć, w którą stronę pójdzie gałąź (Struktura if-then-else), zanim będzie to znane na pewno. Nie będzie czekać na instrukcję A, aby dotrzeć do etapu Ex rurociągu, ale odgadnie decyzję i przejdzie do tej instrukcji (B lub C w przypadku naszego przykładu).

W przypadku poprawnego odgadnięcia, rurociąg wygląda mniej więcej tak:

Jeśli później zostanie wykryte, że odgadnięcie było błędne, to częściowo wykonane instrukcje są odrzucane i rurociąg zaczyna się od nowa z prawidłową gałęzią, powodując opóźnienie. Czas, który jest marnowany w przypadku błędnej interpretacji gałęzi, jest równy liczbie etapów w rurociągu od etapu fetch do etapu execute. Współczesne mikroprocesory mają zwykle dość długie rurociągi, więc opóźnienie błędu wynosi od 10 do 20 cykli zegara. Im dłuższy rurociąg, tym większe zapotrzebowanie na dobry predyktor gałęzi .

W kodzie OP, za pierwszym razem, gdy jest warunkowa, predyktor gałęzi nie ma żadnych informacji, które mogłyby bazować na predykcji, więc za pierwszym razem losowo wybierze następną instrukcję. Później w pętli for może oprzeć prognozę na historii. Dla tablicy posortowane w porządku rosnącym, istnieją trzy możliwości:

1. wszystkie elementy są mniejsze niż 128
2. wszystkie elementy są większe niż 128
3. niektóre początkowe elementy są mniejsze niż 128, a później stają się większe niż 128

Załóżmy, że predyktor zawsze przyjmie prawdziwą gałąź w pierwszym uruchomieniu.

Więc w pierwszym przypadku zawsze będzie brana prawdziwa gałąź, ponieważ historycznie wszystkie jej przewidywania są poprawne. W 2. przypadek, początkowo będzie przewidywać źle, ale po kilku iteracjach, będzie przewidywać poprawnie. W trzecim przypadku, będzie początkowo prawidłowo przewidzieć, aż elementy będą mniejsze niż 128. Po czym zawiedzie przez jakiś czas i poprawi się, gdy widzi awarię przewidywania gałęzi w historii.

We wszystkich tych przypadkach błąd będzie zbyt mniejszy i w rezultacie tylko kilka razy będzie musiał odrzucić częściowo wykonane instrukcje i zacząć od nowa z poprawnym gałąź, co skutkuje mniejszą liczbą cykli procesora.

Ale w przypadku losowej niesortowanej tablicy, PREDYKCJA będzie musiała odrzucić częściowo wykonane instrukcje i zacząć od początku z poprawną gałęzią przez większość czasu i spowodować więcej cykli procesora w porównaniu do posortowanej tablicy.

Oficjalna odpowiedź będzie z

1. Intel-unikanie kosztów błędnej interpretacji gałęzi
2. Intel-Branch and Loop Reorganization to Prevent Mispredicts
3. Prace Naukowe-branch prediction computer architecture
W 2007 roku, w ramach projektu "Computer architecture: a quantitative approach", w 2008 roku, w ramach projektu "Computer architecture: a quantitative approach".]}
4. artykuły w publikacjach naukowych: T. Y. Yeh, Y. N. Patt zrobił wiele z nich na gałęzi przewidywania.

Możesz również zobaczyć z tego uroczego diagramu Dlaczego predyktor gałęzi się myli.

Każdy element w oryginalnym kodzie jest losową wartością

data[c] = std::rand() % 256;

Więc predyktor zmieni strony jako cios std::rand().

Z drugiej strony, po posortowaniu, predyktor najpierw przejdzie do stanu silnie Nie wziętego, a gdy wartości zmienią się na wysoką wartość, predyktor w trzech przebiegach zmieni wszystkie droga z mocno nie podjęte do mocno podjęte.

W tej samej linijce (myślę, że nie zostało to podkreślone przez żadną odpowiedź) warto wspomnieć, że czasami (szczególnie w oprogramowaniu, w którym liczy się wydajność-jak w jądrze Linuksa) można znaleźć kilka instrukcji if, takich jak:

if (likely( everything_is_ok ))
{
    /* Do something */
}

Lub podobnie:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Zarówno likely() jak i unlikely() są w rzeczywistości makrami, które są zdefiniowane za pomocą czegoś takiego jak __builtin_expect GCC, aby pomóc kompilatorowi wstawić kod przewidywania, aby faworyzować warunek biorąc pod uwagę informacje dostarczone przez użytkownika. GCC obsługuje inne wbudowane programy, które mogą zmienić zachowanie uruchomionego programu lub emitować instrukcje niskiego poziomu, takie jak czyszczenie pamięci podręcznej itp. Zobacz tę dokumentację , która przechodzi przez dostępne wbudowane GCC.

Zazwyczaj tego rodzaju optymalizacje znajdują się głównie w aplikacjach w czasie rzeczywistym lub systemach wbudowanych, gdzie czas wykonania ma znaczenie i jest krytyczny. Na przykład, jeśli sprawdzasz jakiś warunek błędu, który występuje tylko 1/10000000 razy, to dlaczego nie poinformować o tym kompilatora? W ten sposób domyślnie przewidywanie gałęzi zakłada, że warunek jest fałszywy.

Często używane operacje logiczne w C++ wytwarzają wiele gałęzi w skompilowanym programie. Jeśli gałęzie te znajdują się wewnątrz pętli i są trudne do przewidzenia, mogą znacznie spowolnić wykonanie. Zmienne logiczne są przechowywane jako 8-bitowe liczby całkowite o wartości 0 dla false i 1 dla true.

Zmienne logiczne są overdeterminowane w tym sensie, że wszystkie operatory, które mają zmienne logiczne jako wejście, sprawdzają, czy wejścia mają inną wartość niż 0 lub 1, ale operatory, które mają wartości logiczne, ponieważ wyjście nie może wytworzyć innej wartości niż 0 lub 1. To sprawia, że operacje ze zmiennymi logicznymi jako danymi wejściowymi są mniej wydajne niż jest to konieczne. Rozważmy przykład:

bool a, b, c, d;
c = a && b;
d = a || b;

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Ten kod jest daleki od optymalnego. Gałęzie mogą trwać długo w przypadku błędnych interpretacji. Operacje logiczne mogą być znacznie bardziej wydajne, jeśli wiadomo z całą pewnością, że operandy nie mają innych wartości niż 0 i 1. Powodem, dla którego kompilator nie przyjmuje takiego założenia, jest to, że zmienne mogą mieć inne wartości, jeśli są niezinicjalizowane lub pochodzą z nieznanych źródeł. Powyższy kod można zoptymalizować, jeśli a i b zostały zainicjowane na prawidłowe wartości lub jeśli pochodzą one od operatorów wytwarzających Boolean output. Zoptymalizowany kod wygląda tak:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char jest używany zamiast bool w celu umożliwienia użycia operatorów bitowych (& i |) zamiast operatorów logicznych (&& i ||). Operatory bitowe są pojedynczymi instrukcjami, które zajmują tylko jeden cykl zegara. Operator OR (|) Działa nawet wtedy, gdy a i b mają inne wartości niż 0 lub 1. Operator AND (&) i operator EXCLUSIVE OR (^) mogą dawać niespójne wyniki, jeśli operandy mają inne wartości niż 0 i 1.

~ nie może być używany do nie. Zamiast tego, można zrobić Boolean nie na zmiennej, która jest znana być 0 lub 1 przez XOR ' ing z 1:

bool a, b;
b = !a;

Można zoptymalizować do:

char a = 0, b;
b = a ^ 1;

a && b nie można zastąpić a & b, jeśli b jest wyrażeniem, którego nie należy oceniać, jeśli a jest false ( && nie będzie oceniać b, & will). Podobnie, a || b nie można zastąpić a | b, jeśli b jest wyrażeniem, którego nie należy oceniać, jeśli a jest true.

Używanie operatorów bitowych jest korzystniejsze, jeśli operandy są zmiennymi niż operandami są porównania:

bool a; double x, y, z;
a = x > y && z < 5.0;

Jest optymalne w większości przypadków (chyba że oczekujesz, że wyrażenie && wygeneruje wiele błędnych interpretacji gałęzi).

To na pewno!...

Przewidywanie gałęzi sprawia, że logika działa wolniej, z powodu przełączania, które dzieje się w Twoim kodzie! To tak, jakbyś jechał prostą ulicą lub ulicą z wieloma zakrętami, na pewno prosta zostanie wykonana szybciej!...

Jeśli tablica jest posortowana, Twój warunek jest false w pierwszym kroku: data[c] >= 128, wtedy staje się wartością true dla całej drogi do końca ulicy. W ten sposób szybciej dotrzesz do końca logiki. Na z drugiej strony, używając niesortowanej tablicy, potrzebujesz dużo obracania i przetwarzania, które na pewno spowolnią Twój kod...

Spójrz na obrazek, który dla Ciebie stworzyłem poniżej. Która ulica skończy się szybciej?

Tak programowo, przewidywanie gałęzi powoduje, że proces jest wolniejszy...

Również na koniec, dobrze jest wiedzieć, że mamy dwa rodzaje prognoz gałęzi, które każdy z nich będzie miał inny wpływ na Twój kod:

1. Static

2. Dynamic

Statyczne przewidywanie gałęzi jest używane przez mikroprocesor po raz pierwszy napotkana jest gałąź warunkowa, a dynamiczne przewidywanie gałęzi jest używany do kolejnych egzekucji warunkowego kodu gałęzi.

Aby skutecznie napisać swój kod, aby skorzystać z tych Zasady, pisząc If-else lub switch należy sprawdzić najbardziej sprawy wspólne najpierw i praca stopniowo do najmniej pospolitych. Pętle niekoniecznie wymagają specjalnego zamówienia kodu dla statyczne przewidywanie gałęzi, jako tylko warunek iteratora pętli jest zwykle używany.

Na to pytanie już wiele razy udzielono doskonałej odpowiedzi. Chciałbym jednak zwrócić uwagę grupy na jeszcze jedną ciekawą analizę.

Ostatnio ten przykład (bardzo nieznacznie zmodyfikowany) został również użyty jako sposób na zademonstrowanie, w jaki sposób fragment kodu może być profilowany w samym programie w systemie Windows. Po drodze autor pokazuje również, jak wykorzystać wyniki do określenia, gdzie kod spędza większość czasu zarówno w przypadku posortowanym , jak i niesortowanym. Wreszcie kawałek pokazuje również, jak użyć mało znanej funkcji Hal (Hardware Abstraction Layer), aby określić, ile błędnych interpretacji gałęzi dzieje się w niesortowanej sprawie.

Link jest tutaj: demonstracja Autoprofilowania

Jak już wspominali inni, za tajemnicą kryje się branch Predictor .

Nie staram się coś dodać, ale wyjaśnić pojęcie w inny sposób. Na wiki jest zwięzłe wprowadzenie, które zawiera tekst i diagram. Podoba mi się wyjaśnienie poniżej, które wykorzystuje diagram do opracowania predyktora gałęzi intuicyjnie.

W architekturze komputera predyktorem gałęzi jest obwód cyfrowy, który próbuje odgadnąć, w którą stronę oddział (np. struktura if-then-else) przejdzie zanim będzie to znane na pewno. Na celem predyktora gałęzi jest poprawa przepływu w rurociąg instrukcji. Branch predictors odgrywają kluczową rolę w osiągnięcie wysokiej wydajności w wielu nowoczesnych rurociągach architektury mikroprocesorów, takich jak x86.

Rozgałęzianie dwukierunkowe jest zwykle realizowane za pomocą skoku warunkowego Instrukcja. Warunkowego skoku można albo "nie wykonać" i kontynuować wykonanie z pierwszym gałąź kodu, która następuje natychmiast po warunkowym skoku, lub można go "zabrać" i przejść do inne miejsce w pamięci programu, gdzie druga gałąź kodu jest przechowywany. Nie wiadomo na pewno, czy skok warunkowy będzie podjęte lub nie podjęte, dopóki warunek nie zostanie obliczony i skok warunkowy przeszedł etap wykonania w instrukcji rurociąg (patrz rys. 1).

Na podstawie opisanego scenariusza I napisali demo animacji, aby pokazać, jak instrukcje są wykonywane w potoku w różnych sytuacjach.

1. bez predyktora gałęzi.

Bez odgałęzień procesor musiałby poczekać do warunkowa Instrukcja skoku przeszła etap wykonania przed Następna instrukcja może wejść do etapu pobierania w potoku.

Przykład zawiera trzy instrukcje, a pierwsza jest instrukcją warunkowego skoku. Dwie ostatnie instrukcje mogą wejść do potoku dopóki nie zostanie wykonana Instrukcja warunkowego skoku.

Wykonanie 3 Instrukcji zajmie 9 cykli zegara.

1. użyj Branch Predictor i nie wykonuj warunkowego skoku. Załóżmy, że przewidywanie jest a nie biorąc skok warunkowy.

Wykonanie 3 Instrukcji zajmie 7 cykli zegara.

1. użycie Branch Predictor i wykonać skok warunkowy. Załóżmy, że przewidywanie jest a nie biorąc skok warunkowy.

Wykonanie 3 Instrukcji zajmie 9 cykli zegara.

Czas, który jest marnowany w przypadku błędnej interpretacji gałęzi jest równy liczba etapów w rurociągu od etapu pobierania do wykonać etap. Współczesne mikroprocesory mają zazwyczaj dość długie rurociągów tak, że opóźnienie błędnej interpretacji jest między 10 a 20 Zegar cykle. W rezultacie wydłużenie rurociągu zwiększa potrzebę bardziej zaawansowany predyktor gałęzi.

Jak widzisz, wygląda na to, że nie mamy powodu, aby nie używać Branch Predictor.

Jest to dość proste demo, które wyjaśnia bardzo podstawową część Branch Predictor. Jeśli te gify są irytujące, prosimy o usunięcie ich z odpowiedzi, a odwiedzający mogą również uzyskać kod źródłowy demo na żywo z BranchPredictorDemo

Branch-prediction gain!

Ważne jest, aby zrozumieć, że błędna interpretacja gałęzi nie spowalnia programów. Koszt pominiętej prognozy jest tak, jakby przewidywanie gałęzi nie istniało i czekałeś na ocenę wyrażenia, aby zdecydować, jaki kod uruchomić (dalsze wyjaśnienie w następnym akapicie).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Gdy jest if-else \ switch polecenie, wyrażenie musi być obliczone w celu określenia, który blok ma zostać wykonany. W kodzie montażowym generowane przez kompilator, wstawiane są instrukcje warunkowe branch.

Instrukcja gałęzi może spowodować, że komputer zacznie wykonywać inną sekwencję instrukcji, a tym samym odbiegać od domyślnego zachowania instrukcji w kolejności (tzn. jeśli wyrażenie jest fałszywe, program pomija kod bloku if) w zależności od pewnego warunku, jakim jest ewaluacja wyrażenia w naszym przypadku.

To powiedziawszy, kompilator stara się przewidzieć wynik zanim zostanie ona faktycznie oceniona. Pobierze instrukcje z bloku if, a jeśli wyrażenie okaże się prawdziwe, to wspaniale! Zyskaliśmy czas potrzebny na jego ocenę i zrobiliśmy postępy w kodzie; jeśli nie, to uruchamiamy niewłaściwy kod, rurociąg jest wypłukiwany, a właściwy blok jest uruchamiany.

Wizualizacja:

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

NA ARM nie jest potrzebna gałąź, ponieważ każda instrukcja ma 4-bitowe pole warunkowe, które testuje (przy zerowym koszcie) dowolny z 16 różnych warunków , które mogą pojawić się w rejestrze statusu procesora, a jeśli warunek Na instrukcji jest fałszywy, instrukcja jest pomijana. Eliminuje to potrzebę krótkich gałęzi, a algorytm ten nie będzie przewidywał trafień gałęzi. dlatego posortowana wersja tego algorytmu będzie działać wolniej niż wersja niesortowana na ramieniu, ze względu na dodatkowe koszty sortowania.

Pętla wewnętrzna dla tego algorytmu wyglądałaby mniej więcej tak jak w języku Arm assembly:

MOV R0, #0   // R0 = sum = 0
MOV R1, #0   // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop  // Inner loop branch label
    LDRB R3, [R2, R1]   // R3 = data[c]
    CMP R3, #128        // compare R3 to 128
    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1      // c++
    CMP R1, #arraySize  // compare c to arraySize
    BLT inner_loop      // Branch to inner_loop if c < arraySize

Ale To jest w rzeczywistości część większego obrazu:

CMP opcody zawsze aktualizują bity stanu w rejestrze stanu procesora (PSR), ponieważ taki jest ich cel, ale większość innych instrukcji nie dotyka PSR, chyba że dodasz opcjonalny przyrostek S do Instrukcja określająca, że PSR powinien być aktualizowany na podstawie wyniku instrukcji. podobnie jak 4-bitowy przyrostek warunkowy, możliwość wykonywania instrukcji bez wpływu na PSR jest mechanizmem, który zmniejsza zapotrzebowanie na gałęzie na ARM, a także ułatwia wysyłkę poza zamówienie na poziomie sprzętowym, ponieważ po wykonaniu jakiejś operacji X, która aktualizuje bity stanu, Następnie (lub równolegle) można wykonać kilka innych prac, które wyraźnie nie powinny wpływać na działanie systemu. (lub być dotknięte) bitami stanu, następnie możesz przetestować stan bitów stanu ustawionych wcześniej przez X.

Pole condition testing i opcjonalne pole "set status bit" można połączyć, na przykład:

• ADD R1, R2, R3 wykonuje R1 = R2 + R3 bez aktualizacji bitów statusu.
• ADDGE R1, R2, R3 wykonuje tę samą operację tylko wtedy, gdy poprzednia instrukcja, która miała wpływ na bity stanu, spowodowała warunek większy lub równy.
• ADDS R1, R2, R3 wykonuje dodawanie, a następnie aktualizuje N, Z, C i znaczniki V w rejestrze statusu procesora na podstawie tego, czy wynik był ujemny, zerowy, przenoszony (dla niepodpisanego dodania), czy przepełniony (dla podpisanego dodania).
• ADDSGE R1, R2, R3 wykonuje dodanie tylko wtedy, gdy test GE jest prawdziwy, a następnie aktualizuje bity stanu na podstawie wyniku dodania.

Większość architektur procesorów nie ma takiej możliwości określenia, czy bity stanu powinny być aktualizowane dla działanie, które może wymagać napisania dodatkowego kodu w celu zapisania i późniejszego przywrócenia bitów stanu, lub może wymagać dodatkowych gałęzi, lub może ograniczyć wydajność wykonania poza zamówieniem procesora: jednym z efektów ubocznych większości architektur zestawów instrukcji CPU wymuszające aktualizowanie bitów stanu po większości instrukcji jest to, że znacznie trudniej jest rozdzielić, które instrukcje mogą być uruchamiane równolegle bez ingerencji między sobą. Aktualizacja bitów statusu ma skutki uboczne, dlatego ma wpływ linearyzacji na kod. zdolność ARM do mieszania i dopasowywania bezgałęziowego testowania stanu na dowolnej instrukcji z opcją aktualizacji lub nie aktualizacji bitów stanu po dowolnej instrukcji jest niezwykle potężna, zarówno dla programistów języka asemblera, jak i kompilatorów, i tworzy bardzo wydajny kod.

Kiedy nie musisz rozgałęziać, możesz uniknąć kosztów czasu płukania rurociągu, co w przeciwnym razie byłoby krótkimi rozgałęzieniami, i możesz uniknąć złożoności projektu wiele form spekulacyjnej ewaluacji. Wpływ na wydajność początkowych naiwnych imlementacji łagodzenia wielu niedawno odkrytych luk w zabezpieczeniach procesora (Spectre itp.) pokazuje, jak bardzo wydajność nowoczesnych procesorów zależy od skomplikowanej logiki oceny spekulacyjnej. Z krótkim rurociągiem i radykalnie zmniejszoną potrzebą rozgałęziania, ARM po prostu nie musi polegać na spekulacyjnej ocenie tak bardzo, jak procesory CISC. (Oczywiście wysokiej klasy implementacje ARM do zawiera ocenę spekulacyjną, ale jest to mniejsza część historii wydajności.)

Jeśli kiedykolwiek zastanawiałeś się, dlaczego ARM odniósł tak fenomenalny sukces, genialna skuteczność i wzajemne oddziaływanie tych dwóch mechanizmów (w połączeniu z innym mechanizmem, który pozwala "przesuwać baryłkę" w lewo lub w prawo jeden z dwóch argumentów dowolnego operatora arytmetycznego lub offsetowego operatora dostępu do pamięci bez dodatkowych kosztów) są dużą częścią historii, ponieważ są jednymi z największych źródeł dostępu do pamięci. wydajność architektury ARM. Błyskotliwość oryginalnych projektantów ARM ISA z 1983 roku, Steve Furber i Roger (obecnie Sophie) Wilson, nie może być przeceniana.

Poza tym, że przewidywanie gałęzi może cię spowolnić, posortowana tablica ma jeszcze jedną zaletę:

Możesz mieć warunek stop zamiast tylko sprawdzania wartości, w ten sposób tylko zapętlasz odpowiednie dane, a resztę zignorujesz.
Przewidywanie gałęzi będzie chybione tylko raz.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

Chodzi o przewidywanie gałęzi. O co chodzi?

• Branch predictor jest jedną z starożytnych technik poprawy wydajności, która nadal znajduje znaczenie w nowoczesnych architekturach. Podczas gdy proste techniki przewidywania zapewniają szybkie wyszukiwanie i wydajność energetyczną, cierpią z powodu wysokiego wskaźnika błędów.

• Z drugiej strony złożone przewidywania gałęzi-oparte na neuronach lub warianty dwupoziomowego przewidywania gałęzi –zapewniają lepszą dokładność przewidywania, ale zużywają więcej mocy i złożoność wzrasta wykładniczo.

• Oprócz tego, w złożonych technikach przewidywania czas potrzebny na przewidzenie gałęzi jest bardzo wysoki –od 2 do 5 cykli –co jest porównywalne do czasu wykonania rzeczywistych gałęzi.

• Przewidywanie gałęzi jest zasadniczo problemem optymalizacji (minimalizacji), w którym nacisk kładzie się na osiągnięcie możliwie najniższej miss rate, niskiego zużycia energii i niskiej złożoności z minimalne zasoby.

Istnieją naprawdę trzy rodzaje gałęzi:

Forward conditional branches - W oparciu o warunek run-time, komputer (licznik programów) jest zmieniany tak, aby wskazywał adres forward w strumieniu instrukcji.

Backward conditional branches - komputer jest zmieniany tak, aby wskazywał wstecz w strumieniu instrukcji. Gałąź opiera się na pewnych warunkach, takich jak rozgałęzienie do tyłu do początku pętli programu, gdy test na końcu pętli stwierdza, że pętla powinna zostać wykonana ponownie.

Unconditional branches - dotyczy to skoków, wywołań procedur i zwrotów, które nie mają określonego warunku. Na przykład, bezwarunkowa Instrukcja skoku może być zakodowana w języku asemblera jako po prostu "jmp", a strumień instrukcji musi być natychmiast skierowany do miejsca docelowego wskazanego przez instrukcję skoku, podczas gdy skok warunkowy, który może być zakodowany jako "jmpne", przekierowywałby strumień instrukcji tylko wtedy, gdy wynik porównania dwóch wartości w poprzedniej instrukcji "Porównaj" pokazuje, że wartości nie są równe. (Schemat adresowania segmentowanego używany przez architekturę x86 dodaje dodatkowej złożoności, ponieważ skoki mogą być "blisko" (w obrębie segmentu) lub" daleko " (poza segmentem). Każdy typ ma inny wpływ na algorytmy predykcji gałęzi.)

Static / dynamic Branch Prediction: static branch prediction jest używany przez mikroprocesor jako pierwszy czas napotkania gałęzi warunkowej, a dynamiczne przewidywanie gałęzi jest używane do kolejnych egzekucji kodu gałęzi warunkowej.

Bibliografia:

• Branch predictor

• demonstracja Autoprofilowania

• Przegląd Prognoz Branżowych

• Branch Prediction (Using wayback machine)

Posortowane tablice są przetwarzane szybciej niż niesortowane tablice, ze względu na zjawisko zwane prognozowaniem gałęzi.

Branch predictor jest cyfrowym obwodem (w architekturze komputera) próbującym przewidzieć, w którą stronę pójdzie gałąź, poprawiając przepływ w potoku instrukcji. Układ / komputer przewiduje następny krok i wykonuje go.

Wykonanie błędnej prognozy prowadzi do powrotu do poprzedniego kroku i wykonania kolejnej prognozy. Zakładając, że przewidywanie jest poprawne, kod będzie kontynuowany do następnego kroku. Błędne przewidywanie powoduje powtarzanie tego samego kroku, dopóki nie nastąpi prawidłowe przewidywanie.

W nieposortowanej tablicy komputer dokonuje wielu prognoz, co prowadzi do zwiększonej szansy na błędy. Natomiast w posortowanej tablicy komputer wykonuje mniej prognoz, zmniejszając ryzyko wystąpienia błędów. Tworzenie większej liczby prognoz wymaga więcej czasu.

Sortowana Tablica: Prosta Droga

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

Unsorted Array: Curved Road

______   ________
|     |__|

Przewidywanie gałęzi: zgadywanie / przewidywanie, która droga jest prosta i podążanie za nią bez sprawdzania

___________________________________________ Straight road
 |_________________________________________|Longer road

Chociaż obie drogi docierają do tego samego celu, prosta droga jest krótsza, a druga dłuższa. Jeśli następnie wybierzesz drugą przez pomyłkę, nie ma odwrotu, a więc stracisz trochę czasu, jeśli wybierzesz dłuższą drogę. Jest to podobne do tego, co dzieje się w komputerze i mam nadzieję, że to pomogło zrozum lepiej.

Również chcę przytoczyć @ Simon_Weaver Z komentarzy:

Nie tworzy mniej prognoz - tworzy mniej błędnych prognoz. Nadal musi przewidywać za każdym razem przez pętlę...

Próbowałem tego samego kodu z MATLAB 2011B z moim MacBook Pro (Intel i7, 64 bit, 2.4 GHz) dla następującego kodu MATLAB:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Wyniki dla powyższego kodu MATLAB są następujące:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Wyniki kodu C jak w @ GManNickG dostaję:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Na tej podstawie wygląda na to, że MATLAB jest prawie 175 razy wolniejszy od implementacji C bez sortowania i 350 razy wolniejszy od sortowania. Innymi słowy, efekt (przewidywania gałęzi) jest 1.46 x dla implementacji MATLAB i 2.7 x dla implementacji C.

Założenie przez inne odpowiedzi, że trzeba sortować dane, nie jest poprawne.

Poniższy kod nie sortuje całej tablicy, a jedynie jej 200-elementowe segmenty i tym samym uruchamia się najszybciej.

Sortowanie tylko sekcji k-elementowych kończy wstępne przetwarzanie w czasie liniowym, O(n), zamiast O(n.log(n)) czasu potrzebnego do sortowania całej tablicy.

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

To również "dowodzi", że nie ma to nic wspólnego z żadną kwestią algorytmiczną, taką jak kolejność sortowania, i rzeczywiście jest / align = "left" /

odpowiedź Bjarne Stroustrupa na to pytanie:

Więc próbowałem z wektorem miliona liczb całkowitych i dostałem:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label
         << duration_cast<microseconds>(t1 — t0).count()
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Przynajmniej zjawisko jest prawdziwe z tym kompilatorem, biblioteką standardową i ustawieniami optymalizatora. Różne implementacje mogą i dają różne odpowiedzi. W rzeczywistości ktoś zrobił bardziej systematyczne badanie (szybkie wyszukiwanie w Internecie go znajdzie) i większość implementacji pokazuje ten efekt.

Jednym z powodów jest przewidywanie gałęzi: kluczowa operacja w algorytmie sortowania to “if(v[i] < pivot]) …” lub równoważna. Dla uporządkowanej sekwencji test jest zawsze prawdziwy, podczas gdy dla losowej sekwencji wybrana gałąź zmienia się losowo.

Inny powód jest to, że gdy wektor jest już posortowany, nigdy nie musimy przesuwać elementów do ich właściwej pozycji. Efekt tych małych szczegółów jest czynnikiem pięciu lub sześciu, które widzieliśmy.

Jeśli chcesz napisać efektywny kod, to musisz dowiedzieć się trochę o architekturze maszyn.

To pytanie jest zakorzenione w modelach przewidywania gałęzi na procesorach. Polecam przeczytać ten artykuł:

Zwiększenie szybkości pobierania Instrukcji poprzez przewidywanie wielu gałęzi i bufor adresów gałęzi

Po posortowaniu elementów, IR nie może być kłopotliwy, aby pobrać wszystkie instrukcje procesora, raz za razem. Pobiera je z pamięci podręcznej.

Jednym ze sposobów uniknięcia błędów przewidywania gałęzi jest zbudowanie tabeli wyszukiwania i indeksowanie jej za pomocą danych. Stefan de Bruijn mówił o tym w swojej odpowiedzi.

Ale w tym przypadku wiemy, że wartości są w zakresie [0, 255] i zależy nam tylko na wartościach >= 128. Oznacza to, że możemy łatwo wyodrębnić pojedynczy bit, który powie nam, czy chcemy wartości, czy nie: przesuwając dane do prawej 7 bitów, pozostajemy z bitem 0 LUB 1 bitem, a chcemy dodać wartość tylko wtedy, gdy mamy 1 bit. Let ' s nazwij to "decyzją".

Używając wartości 0/1 bitu decyzji jako indeksu do tablicy, możemy tworzyć kod, który będzie równie szybki niezależnie od tego, czy dane są sortowane, czy nie. Nasz kod zawsze doda wartość, ale gdy bit decyzji będzie równy 0, dodamy wartość gdzieś, na czym nam nie zależy. Oto kod:

// Test

clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Ten kod marnuje połowę dodanych, ale nigdy nie ma awarii przewidywania gałęzi. Jest ogromnie szybszy na losowych danych niż wersja z rzeczywistą instrukcją if.

Ale w moich testach, Jawna tabela wyszukiwania była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli wyszukiwania było nieco szybsze niż przesuwanie bitów. To pokazuje jak mój kod ustawia i używa tabeli lookup (niewyobrażalnie zwanej lut dla "tabeli LookUp" w kodzie). Oto kod C++:

/ / Zadeklaruj, a następnie wypełnij tabelę lookup

int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

W tym przypadku tabela wyszukiwania miała tylko 256 bajtów, więc ładnie mieści się w pamięci podręcznej i wszystko było szybkie. Ta technika nie sprawdziłaby się dobrze, gdyby dane były wartościami 24-bitowymi i chcieliśmy tylko połowę z nich... tabela wyszukiwania byłaby zbyt duża, aby była praktyczna. Z drugiej strony, możemy połączyć dwie techniki pokazane powyżej: najpierw przesuń bity nad, a następnie indeks tabeli wyszukiwania. Dla wartości 24-bitowej, której chcemy tylko górną połowę, możemy potencjalnie przesunąć dane w prawo o 12 bitów i pozostawić 12-bitową wartość dla indeksu tabeli. 12-bitowy indeks tabeli oznacza tabelę 4096 wartości, które mogą być praktyczne.

Technika indeksowania do tablicy, zamiast używania instrukcji if, może być używana do decydowania, którego wskaźnika użyć. Widziałem bibliotekę, która zaimplementowała binarne drzewa i zamiast mieć dwa nazwane wskaźniki (pLeft i peright lub cokolwiek innego) miała tablicę wskaźników długości-2 i używała techniki" bit decyzji", aby zdecydować, który z nich podążać. Na przykład zamiast:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

i = (x < node->value);
node = node->link[i];