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

Oto fragment kodu C ++, który pokazuje niektóre bardzo dziwne zachowania. Z jakiegoś dziwnego powodu sortowanie danych w cudowny sposób przyspiesza prawie sześciokrotnie:

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

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

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

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

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

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

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

• Bez std::sort(data, data + arraySize);tego kod działa w 11,54 sekundy.
• Po posortowaniu danych kod działa w 1,93 sekundy.

Początkowo myślałem, że może to być anomalia dotycząca języka lub kompilatora, więc wypróbowałem Javę:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

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

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Z podobnym, ale mniej ekstremalnym rezultatem.

Najpierw pomyślałem, że sortowanie przenosi dane do pamięci podręcznej, ale potem pomyślałem, że to głupie, ponieważ tablica właśnie została wygenerowana.

• Co się dzieje?
• Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie nieposortowanej tablicy?

Kod sumuje niektóre niezależne warunki, więc kolejność nie powinna mieć znaczenia.

Jesteś ofiarą niepowodzenia prognozowania gałęzi .

Co to jest przewidywanie gałęzi?

Rozważ węzeł kolejowy:

_{Zdjęcie Mecanismo, za pośrednictwem Wikimedia Commons. Używany na licencji CC-By-SA 3.0 .}

Teraz, dla argumentu, załóżmy, że jest to już w 1800 roku - przed długą rozmową lub komunikacją radiową.

Jesteś operatorem skrzyżowania i słyszysz nadjeżdżający pociąg. Nie masz pojęcia, w którą stronę ma iść. Zatrzymujesz pociąg, aby zapytać kierowcę, który kierunek chce. A następnie odpowiednio ustawiłeś przełącznik.

Pociągi są ciężkie i mają dużą bezwładność. Więc zaczynają i zwalniają.

Czy jest lepszy sposób? Zgadnij, w którą stronę pójdzie pociąg!

• Jeśli dobrze zgadłeś, nadal trwa.
• Jeśli pomyliłeś się, kapitan zatrzyma się, cofnie i krzyknie na ciebie, aby przełączyć przełącznik. Następnie może ponownie uruchomić inną ścieżkę.

Jeśli dobrze zgadniesz za każdym razem , pociąg nigdy nie będzie musiał się zatrzymywać.
Jeśli zbyt często się mylicie , pociąg poświęci dużo czasu na zatrzymywanie się, tworzenie kopii zapasowych i restartowanie.

Rozważmy instrukcję if: na poziomie procesora jest to instrukcja rozgałęziona:

Jesteś procesorem i widzisz oddział. Nie masz pojęcia, w którą stronę pójdzie. Co robisz? Zatrzymujesz wykonywanie i czekasz, aż poprzednie instrukcje zostaną zakończone. Następnie idź właściwą ścieżką.

Nowoczesne procesory są skomplikowane i mają długie rurociągi. Dlatego trwają wiecznie, aby się „rozgrzać” i „zwolnić”.

Czy jest lepszy sposób? Zgadnij, w którą stronę pójdzie oddział!

• Jeśli dobrze zgadłeś, kontynuujesz wykonywanie.
• Jeśli pomyliłeś się, musisz przepłukać rurociąg i przetoczyć się z powrotem do gałęzi. Następnie możesz ponownie uruchomić inną ścieżkę.

Jeśli za każdym razem dobrze zgadniesz , egzekucja nigdy nie będzie musiała się kończyć.
Jeśli zbyt często się mylicie , spędzacie dużo czasu na zwlekaniu, wycofywaniu się i ponownym uruchamianiu.

To jest prognoza gałęzi. Przyznaję, że nie jest to najlepsza analogia, ponieważ pociąg może po prostu zasygnalizować kierunek flagą. Ale w komputerach procesor nie wie, w którą stronę pójdzie gałąź, do ostatniej chwili.

Jak więc strategicznie zgadnąć, aby zminimalizować liczbę przypadków, w których pociąg musi się wycofać i zejść inną drogą? Patrzysz na przeszłość! Jeśli pociąg jedzie w lewo w 99% przypadków, zgadujesz, że w lewo. Jeśli zmienia się, to na przemian zgadujesz. Jeśli pójdzie w jedną stronę co trzy razy, domyślacie się, że to samo ...

Innymi słowy, próbujesz zidentyfikować wzór i podążać za nim. Jest to mniej więcej sposób działania predyktorów gałęzi.

Większość aplikacji ma dobrze zachowujące się gałęzie. Tak więc nowoczesne predyktory branżowe zazwyczaj osiągają> 90% współczynników trafień. Ale w obliczu nieprzewidywalnych gałęzi bez rozpoznawalnych wzorców predyktory gałęzi są praktycznie bezużyteczne.

Dalsza lektura: Artykuł „Predyktor branży” na Wikipedii .

Jak wspomniano z góry, winowajcą jest to wyrażenie if:

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

Zauważ, że dane są równomiernie rozmieszczone między 0 a 255. Po posortowaniu danych, mniej więcej pierwsza połowa iteracji nie wejdzie w instrukcję if. Następnie wszyscy wprowadzą instrukcję if.

Jest to bardzo przyjazne dla predyktora gałęzi, ponieważ gałąź wielokrotnie podąża w tym samym kierunku wiele razy. Nawet prosty licznik nasycenia prawidłowo przewidzi gałąź, z wyjątkiem kilku iteracji po zmianie kierunku.

Szybka wizualizacja:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Jednak gdy dane są całkowicie losowe, predyktor gałęzi staje się bezużyteczny, ponieważ nie może przewidzieć losowych danych. Zatem prawdopodobnie wystąpi około 50% nieprzewidywalności (nie lepiej niż losowe zgadywanie).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Co więc można zrobić?

Jeśli kompilator nie jest w stanie zoptymalizować gałęzi do ruchu warunkowego, możesz spróbować kilku hacków, jeśli chcesz poświęcić czytelność wydajności.

Zastąpić:

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

z:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

To eliminuje gałąź i zastępuje ją niektórymi operacjami bitowymi.

_{(Zauważ, że ten hack nie jest ściśle równoważny z oryginalną instrukcją if. W tym przypadku dotyczy wszystkich wartości wejściowych data[].)}

Testy porównawcze: Core i7 920 @ 3,5 GHz

C ++ - Visual Studio 2010 - wydanie x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Obserwacje:

• Z odgałęzieniem: Istnieje ogromna różnica między posortowanymi i nieposortowanymi danymi.
• With Hack: Nie ma różnicy między posortowanymi i nieposortowanymi danymi.
• W przypadku C ++ włamanie jest odrobinę wolniejsze niż w przypadku gałęzi podczas sortowania danych.

Ogólna zasada polega na unikaniu rozgałęzień zależnych od danych w pętlach krytycznych (takich jak w tym przykładzie).

Aktualizacja:

• GCC 4.6.1 z -O3lub -ftree-vectorizena x64 jest w stanie wygenerować ruch warunkowy. Nie ma więc różnicy między posortowanymi i nieposortowanymi danymi - oba są szybkie.

  (Lub nieco szybciej: w przypadku już posortowanego przypadku cmovmoże być wolniejszy, szczególnie jeśli GCC umieści go na ścieżce krytycznej zamiast po prostu add, szczególnie na Intel przed Broadwell, gdzie cmovma 2 opóźnienia cyklu: flaga optymalizacji gcc -O3 powoduje, że kod jest wolniejszy niż -O2 )

• VC ++ 2010 nie jest w stanie wygenerować ruchów warunkowych dla tej gałęzi, nawet pod /Ox.

• Kompilator Intel C ++ (ICC) 11 robi coś cudownego. To węzłów dwie pętle , a tym samym podnoszenia nieprzewidywalne odgałęzienie do zewnętrznej pętli. Jest więc nie tylko odporny na nieprzewidziane zdarzenia, ale także dwa razy szybszy niż cokolwiek, co generują VC ++ i GCC! Innymi słowy, ICC skorzystało z pętli testowej, aby pokonać punkt odniesienia ...

• Jeśli podasz kompilatorowi Intela kod bez rozgałęzień, to po prostu wektoryzuje go ... i jest tak samo szybki jak w gałęzi (z wymianą pętli).

To pokazuje, że nawet dojrzałe współczesne kompilatory mogą się bardzo różnić w zakresie możliwości optymalizacji kodu ...

Prognozowanie gałęzi.

W przypadku posortowanej tablicy warunek data[c] >= 128jest najpierw falsedla pasma wartości, a następnie truedla wszystkich późniejszych wartości. Łatwo to przewidzieć. W przypadku nieposortowanej tablicy płacisz za koszty rozgałęzienia.

Powodem, dla którego wydajność drastycznie poprawia się podczas sortowania danych, jest usunięcie kary przewidywania gałęzi, jak pięknie wyjaśniono w odpowiedzi Mysticial .

Teraz, jeśli spojrzymy na kod

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

możemy stwierdzić, że znaczenie tej konkretnej if... else...gałęzi jest dodanie czegoś, gdy warunek jest spełniony. Ten typ oddziału można łatwo przekształcić w instrukcję warunkowego przeniesienia , która zostałaby skompilowana w instrukcję warunkowego przeniesienia: cmovlw x86systemie. Gałąź, a tym samym potencjalna kara za przewidywanie gałęzi, jest usuwana.

W Cten sposóbC++ , oświadczenie, które skompilować bezpośrednio (bez optymalizacji) w instrukcji warunkowej poruszać się x86, jest operatorem trójskładnikowych ... ? ... : .... Więc przepisujemy powyższą instrukcję na równoważną:

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

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

Na procesorze Intel Core i7 -2600K @ 3,4 GHz i Visual Studio 2010 w wersji testowej test porównawczy (format skopiowany z Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Wynik jest solidny w wielu testach. Dostajemy duże przyspieszenie, gdy wynik gałęzi jest nieprzewidywalny, ale cierpimy trochę, gdy jest przewidywalny. W rzeczywistości podczas korzystania z ruchu warunkowego wydajność jest taka sama, niezależnie od wzorca danych.

Przyjrzyjmy się teraz bliżej badając x86zespół, który generują. Dla uproszczenia używamy dwóch funkcjimax1 i max2.

max1używa gałęzi warunkowej if... else ...:

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

max2używa operatora trójskładnikowego ... ? ... : ...:

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

Na maszynie x86-64 GCC -Sgeneruje zestaw poniżej.

: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

max2zużywa znacznie mniej kodu ze względu na użycie instrukcji cmovge. Ale prawdziwym zyskiem jest to, że max2nie obejmuje skoków gałęzi,jmp , co miałoby znaczną karę wydajności, jeśli przewidywany wynik byłby niewłaściwy.

Dlaczego więc ruch warunkowy działa lepiej?

W typowym x86procesorze wykonanie instrukcji jest podzielone na kilka etapów. Z grubsza mamy inny sprzęt do obsługi różnych etapów. Nie musimy więc czekać na zakończenie jednej instrukcji, aby rozpocząć nową. Nazywa się to potokowaniem .

W przypadku rozgałęzienia następująca instrukcja jest określana przez poprzednią, więc nie możemy wykonywać potokowania. Musimy albo poczekać, albo przewidzieć.

W przypadku warunkowego ruchu instrukcja warunkowego wykonania wykonania jest podzielona na kilka etapów, ale wcześniejsze etapy, takie jak FetchiDecode nie zależą od wyniku poprzedniej instrukcji; tylko ostatnie etapy potrzebują rezultatu. Dlatego czekamy ułamek czasu wykonania jednej instrukcji. Właśnie dlatego wersja warunkowego przenoszenia jest wolniejsza niż gałąź, gdy przewidywanie jest łatwe.

Książka Computer Systems: A Programmer's Perspective, drugie wydanie , szczegółowo to wyjaśnia. Możesz zapoznać się z sekcją 3.6.6, aby uzyskać instrukcje dotyczące warunkowego przenoszenia , cały rozdział 4 dotyczący architektury procesora , a sekcję 5.11.2, aby uzyskać specjalne informacje na temat kar przewidujących rozgałęzienia i niedopuszczalności .

Czasami niektóre nowoczesne kompilatory mogą zoptymalizować nasz kod do złożenia z lepszą wydajnością, czasem niektóre kompilatory nie mogą (dany kod używa natywnego kompilatora Visual Studio). Znajomość różnicy w wydajności między oddziałem a ruchem warunkowym, gdy jest nieprzewidywalny, może pomóc nam pisać kod z lepszą wydajnością, gdy scenariusz staje się tak skomplikowany, że kompilator nie może ich automatycznie zoptymalizować.

Jeśli jesteś ciekawy jeszcze większej optymalizacji tego kodu, 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];
    }
}

Dzięki 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];
    }
}

Następnie możesz zobaczyć, że ifwarunek jest stały podczas wykonywania ipętli, więc możesz ifwyciągnąć:

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

Następnie zobaczysz, że pętla wewnętrzna może zostać zwinięta w jedno wyrażenie, przy założeniu, że zezwala na to model zmiennoprzecinkowy ( /fp:fastna przykład jest rzucany)

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

Ten jest 100 000 razy szybszy niż wcześniej.

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

Posortowane:

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

Nieposortowany:

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

Przechodząc do wyjścia produkowanego przez linię po linii cg_annotate, widzimy dla danej pętli:

Posortowane:

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

Nieposortowany:

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

To pozwala łatwo zidentyfikować problematyczną linię - w nieposortowanej wersji if (data[c] >= 128)linia powoduje 164.050,007 nieprzewidzianych rozgałęzień warunkowych ( Bcm) w modelu predykcyjnym rozgałęzienia cachegrinda, podczas gdy powoduje tylko 10,006 w posortowanej wersji.

Alternatywnie w systemie Linux można skorzystać z podsystemu liczników wydajności, aby wykonać to samo zadanie, ale z wydajnością natywną przy użyciu liczników procesora.

perf stat ./sumtest_sorted

Posortowane:

 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

Nieposortowany:

 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 także wykonywać adnotacje do kodu źródłowego z dezasemblacją.

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

Zobacz samouczek wydajności, aby uzyskać więcej informacji.

Właśnie przeczytałem to pytanie i jego odpowiedzi 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 tabel zamiast korzystania z gałęzi (chociaż nie testowałem tego w tym przypadku).

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

1. jest to mały stolik i prawdopodobnie będzie buforowany w procesorze, i
2. działasz w dość ciasnej pętli i / lub procesor może wstępnie załadować dane.

Tło i dlaczego

Z perspektywy procesora pamięć jest wolna. Aby zrekompensować różnicę prędkości, w twoim procesorze wbudowanych jest kilka pamięci podręcznych (pamięć podręczna L1 / L2). Wyobraź sobie, że wykonujesz swoje miłe obliczenia i zorientuj się, że potrzebujesz pamięci. Procesor otrzyma operację „ładowania” i ładuje pamięć do pamięci podręcznej - a następnie wykorzystuje pamięć podręczną do wykonania 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ć to do pamięci podręcznej, zanim operacja rzeczywiście trafi do pamięci podręcznej. Jak już widzieliśmy, przewidywanie rozgałęzień czasami idzie strasznie źle - w najgorszym przypadku musisz cofnąć się i faktycznie czekać na obciążenie pamięci, które potrwa wieczność ( innymi słowy: niepoprawne przewidywanie rozgałęzienia jest złe, pamięć obciążenie po niepowodzeniu przewidywania gałęzi jest po prostu okropne! ).

Na szczęście dla nas, jeśli wzorzec 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, ogólną zasadą jest trzymanie się tablic odnośników o rozmiarze <= 4096 bajtów. Jako górny limit: jeśli twoja tabela odnośników jest większa niż 64 KB, prawdopodobnie warto ją ponownie rozważyć.

Konstruowanie stołu

Odkryliśmy więc, że możemy stworzyć mały stolik. Następnie należy uruchomić funkcję wyszukiwania. Funkcje wyszukiwania są zwykle małymi funkcjami, które wykorzystują kilka podstawowych operacji na liczbach całkowitych (i, lub xor, shift, dodawanie, usuwanie i być może mnożenie). Chcesz, aby twoje dane wejściowe zostały przetłumaczone przez funkcję wyszukiwania na jakiś „unikalny klucz” w twojej tabeli, który następnie po prostu daje odpowiedź na całą pracę, którą chciałeś wykonać.

W tym przypadku:> = 128 oznacza, że ​​możemy zachować wartość, <128 oznacza, że ​​się go pozbyliśmy. Najłatwiejszym sposobem na to jest użycie „AND”: jeśli je zachowamy, my AND to z 7FFFFFFF; jeśli chcemy się go pozbyć, my ORAZ 0. 0. Zauważ też, że 128 to potęga 2 - więc możemy iść do przodu i zrobić tabelę liczb całkowitych 32768/128 i wypełnić ją jednym zerem i dużą liczbą 7FFFFFFFF's.

Zarządzane języki

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

Cóż, niezupełnie ... :-)

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 takim przypadku dla kompilatora oczywiste jest, że warunek brzegowy nigdy nie zostanie osiągnięty. Przynajmniej kompilator Microsoft JIT (ale spodziewam się, że Java robi podobne rzeczy) zauważy to i całkowicie usunie zaznaczenie. WOW, to oznacza brak oddziału. Podobnie będzie zajmować się innymi oczywistymi przypadkami.

Jeśli napotkasz problemy z przeglądaniem w zarządzanych językach - kluczem jest dodanie & 0x[something]FFFdo funkcji wyszukiwania, aby umożliwić przewidywalne sprawdzenie granicy - i obserwowanie, jak przebiega szybciej.

Wynik tego przypadku

// 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ą rozdzielane między 0 a 255 podczas sortowania tablicy, mniej więcej w pierwszej połowie iteracji nie pojawi się if-statement ( ifinstrukcja jest udostępniana poniżej).

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

Pytanie brzmi: co powoduje, że powyższe stwierdzenie nie jest wykonywane w niektórych przypadkach, jak w przypadku danych posortowanych? Oto „predyktor gałęzi”. Predyktor gałęzi to obwód cyfrowy, który próbuje odgadnąć, w którą stronę if-then-elsepójdzie gałąź (np. Struktura), zanim zostanie to z całą pewnością znane. Celem predyktora rozgałęzienia jest poprawa przepływu w potoku instrukcji. Predyktory branżowe odgrywają kluczową rolę w osiągnięciu wysokiej wydajności!

Zróbmy trochę benchmarkingu, aby lepiej to zrozumieć

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

Zmierzmy wydajność tej pętli w różnych warunkach:

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

Oto czasy pętli z różnymi wzorcami prawda-fałsz:

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

„ Zły ” wzór prawda-fałsz może stworzyćif będzie sześć razy wolniejsze niż „ dobry ” wzór! Oczywiście, który wzorzec jest dobry, a który zły, zależy od dokładnych instrukcji generowanych przez kompilator i od konkretnego procesora.

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

Jednym ze sposobów uniknięcia błędów prognozowania gałęzi jest zbudowanie tabeli odnośników i zindeksowanie jej przy użyciu danych. Stefan de Bruijn omówił to w swojej odpowiedzi.

Ale w tym przypadku wiemy, że wartości mieszczą się w zakresie [0, 255] i dbamy tylko o wartości> = 128. Oznacza to, że możemy łatwo wyodrębnić pojedynczy bit, który powie nam, czy chcemy wartość, czy nie: poprzez przesunięcie dane w prawych 7 bitach, mamy 0 bitów lub 1 bitów i chcemy dodać wartość tylko wtedy, gdy mamy 1 bit. Nazwijmy ten bit „bitem decyzyjnym”.

Używając wartości 0/1 bitu decyzyjnego jako indeksu w tablicy, możemy stworzyć kod, który będzie równie szybki, niezależnie od tego, czy dane zostaną posortowane, czy nie. Nasz kod zawsze doda wartość, ale gdy bit decyzyjny ma wartość 0, dodamy wartość w miejscu, w którym nas nie obchodzi. 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ę wartości dodanych, ale nigdy nie występuje błąd przewidywania gałęzi. Jest losowo szybszy w przypadku danych losowych niż wersja z rzeczywistą instrukcją if.

Ale w moich testach jawna tabela odnośników była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli odnośników było nieco szybsze niż przesuwanie bitów. To pokazuje, jak mój kod konfiguruje się i korzysta z tabeli odnośników (niewyobrażalnie nazywanej lutw tabeli „LookUp Table”). 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 tablica przeglądowa 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łaby dobrze, gdyby dane były 24-bitowymi wartościami, a chcieliśmy tylko połowy z nich ... tabela przeglądowa byłaby o wiele za duża, aby była praktyczna. Z drugiej strony możemy połączyć dwie techniki pokazane powyżej: najpierw przesuń bity, a następnie zindeksuj tabelę wyszukiwania. W przypadku 24-bitowej wartości, której potrzebujemy tylko górnej połowy, możemy potencjalnie przesunąć dane w prawo o 12 bitów i pozostawić 12-bitową wartość dla indeksu tabeli. 12-bitowy indeks tabeli implikuje tabelę 4096 wartości, co może być praktyczne.

Technika indeksowania do tablicy zamiast użycia ifinstrukcji może być użyta do podjęcia decyzji, którego wskaźnika użyć. Widziałem bibliotekę, w której zaimplementowano drzewa binarne, i zamiast dwóch nazwanych wskaźników ( pLefti tak dalej pRight) posiadał tablicę wskaźników o długości 2 i użyłem techniki „bitu decyzyjnego”, aby zdecydować, który wybrać. 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: Red Black Trees , Eternally Confuzzled

W posortowanym przypadku możesz zrobić coś lepszego niż poleganie na udanej prognozie gałęzi lub jakiejkolwiek sztuczce porównania bez gałęzi: całkowicie usuń gałąź.

Rzeczywiście, tablica jest podzielona na strefy ciągłe z data < 128i inną z data >= 128. Więc powinieneś znaleźć punkt podziału z wyszukiwaniem dychotomicznym (używającLg(arraySize) = 15 porównań), a następnie dokonać prostej akumulacji od tego punktu.

Coś jak (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 bardziej zaciemnione

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 szybszym podejściem, które daje przybliżone rozwiązanie zarówno dla posortowanych, jak i nieposortowanych, jest: sum= 3137536;(zakładając naprawdę jednolity rozkład, 16384 próbek o oczekiwanej wartości 191,5) :-)

Powyższe zachowanie występuje z powodu przewidywania gałęzi.

Aby zrozumieć przewidywanie gałęzi, należy najpierw zrozumieć potok instrukcji :

Każda instrukcja jest podzielona na sekwencję kroków, aby różne kroki mogły być wykonywane równolegle równolegle. Ta technika jest znana jako potok instrukcji i służy do zwiększenia przepustowości w nowoczesnych procesorach. Aby to lepiej zrozumieć, zobacz ten przykład na Wikipedii .

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

1. IF - pobierz instrukcję z pamięci
2. ID - Dekoduj instrukcję
3. EX - Wykonaj instrukcję
4. WB - Zapis do rejestru procesora

4-etapowy rurociąg ogólnie dla 2 instrukcji.

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

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

Bez przewidywania gałęzi wystąpiłyby:

Aby wykonać instrukcję B lub instrukcję C, procesor będzie musiał poczekać, aż instrukcja A nie dojdzie 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 potok będzie tak wyglądać.

kiedy, jeśli warunek zwraca wartość true:

Kiedy jeśli warunek zwraca false:

W wyniku oczekiwania na wynik instrukcji A łączna liczba cykli procesora spędzonych w powyższym przypadku (bez przewidywania gałęzi; zarówno dla prawdy, jak i fałszu) wynosi 7.

Czym jest prognoza gałęzi?

Narzędzie prognozy rozgałęzień spróbuje odgadnąć, w którą stronę pójdzie gałąź (struktura „jeśli-to-inaczej”), zanim będzie to pewne. Nie będzie czekać, aż instrukcja A osiągnie etap EX potoku, ale zgadnie decyzję i przejdzie do tej instrukcji (B lub C w przypadku naszego przykładu).

W przypadku prawidłowego odgadnięcia potok wygląda mniej więcej tak:

Jeśli później zostanie wykryte, że zgadnięcie było błędne, wówczas częściowo wykonane instrukcje są odrzucane, a potok zaczyna od nowa z prawidłową gałęzią, co powoduje opóźnienie. Czas marnowany w przypadku nieprzewidzianego rozgałęzienia jest równy liczbie etapów w potoku od etapu pobierania do etapu wykonywania. Współczesne mikroprocesory mają zwykle dość długie rurociągi, tak że opóźnienie w nieprzewidywalności wynosi od 10 do 20 cykli zegara. Im dłuższy rurociąg, tym większa potrzeba dobrego predyktora gałęzi .

W kodzie OP, po raz pierwszy, gdy warunkowy, predyktor gałęzi nie ma żadnych informacji umożliwiających przewidywanie, więc za pierwszym razem losowo wybierze następną instrukcję. Później w pętli for może opierać prognozy na historii. Dla tablicy posortowanej w porządku rosnącym istnieją trzy możliwości:

1. Wszystkie elementy mają mniej niż 128
2. Wszystkie elementy są większe niż 128
3. Niektóre nowe elementy początkowe są mniejsze niż 128, a później stają się większe niż 128

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

Tak więc w pierwszym przypadku zawsze przyjmie on prawdziwą gałąź, ponieważ historycznie wszystkie jej przewidywania są poprawne. W drugim przypadku początkowo będzie to przewidywać źle, ale po kilku iteracjach będzie poprawnie przewidywać. W trzecim przypadku będzie początkowo poprawnie przewidywał, aż elementy będą mniejsze niż 128. Po tym czasie zawiedzie przez pewien czas i poprawi się, gdy zobaczy awarię przewidywania gałęzi w historii.

We wszystkich tych przypadkach liczba awarii będzie zbyt mała, w wyniku czego tylko kilka razy będzie trzeba odrzucić częściowo wykonane instrukcje i zacząć od nowa z prawidłową gałęzią, co spowoduje mniej cykli procesora.

Ale w przypadku losowej nieposortowanej tablicy przewidywanie będzie musiało odrzucić częściowo wykonane instrukcje i zacząć od nowa z prawidłową gałęzią przez większość czasu i spowodować więcej cykli procesora w porównaniu do sortowanej tablicy.

Oficjalna odpowiedź pochodzi od

1. Intel - unikanie kosztów niedyspozycji branżowych
2. Intel - Reorganizacja oddziału i pętli w celu zapobiegania niepowodzeniom
3. Artykuły naukowe - architektura komputerów z prognozami branżowymi
4. Książki: JL Hennessy, DA Patterson: Architektura komputerów: podejście ilościowe
5. Artykuły w publikacjach naukowych: TY Yeh, YN Patt zrobił wiele z nich na temat prognoz branżowych.

Na tym uroczym diagramie możesz także zobaczyć, dlaczego predyktor gałęzi jest zdezorientowany.

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

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

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

Z drugiej strony, po posortowaniu, predyktor najpierw przejdzie w stan silnie nieprzyjęty, a gdy wartości zmienią się na wysoką, predyktor w trzech biegnie przez całą zmianę od całkowicie nieprzyjętej do silnie pobranej.

W tym samym wierszu (myślę, że żadna odpowiedź tego nie podkreśliła) warto wspomnieć, że czasami (szczególnie w oprogramowaniu, w którym wydajność ma znaczenie - jak w jądrze Linuksa), można znaleźć następujące instrukcje, takie jak:

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

lub podobnie:

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

Zarówno likely()i unlikely()są w rzeczywistości makr, które są zdefiniowane za pomocą coś jak GCC __builtin_expectpomóc kompilator wstawianie kodu predykcji faworyzować podejmowania Stan techniczny pod uwagę informacje dostarczone przez użytkownika. GCC obsługuje inne wbudowane funkcje, które mogą zmieniać zachowanie działającego programu lub emitować instrukcje niskiego poziomu, takie jak czyszczenie pamięci podręcznej itp. Zobacz dokumentację zawierającą dostępne wbudowane funkcje GCC.

Zazwyczaj tego rodzaju optymalizacje występują głównie w aplikacjach czasu rzeczywistego lub systemach wbudowanych, w których czas wykonania ma znaczenie i jest krytyczny. Na przykład, jeśli sprawdzasz, czy występuje jakiś błąd, który zdarza się 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 ++ tworzą wiele gałęzi w skompilowanym programie. Jeśli te gałęzie znajdują się w pętli i trudno je przewidzieć, mogą znacznie spowolnić wykonywanie. Zmienne boolowskie są przechowywane jako 8-bitowe liczby całkowite o wartościach 0for falsei 1for true.

Zmienne boolowskie są nadmiernie określone w tym sensie, że wszystkie operatory, które mają zmienne boolowskie jako dane wejściowe, sprawdzają, czy dane wejściowe mają inną wartość niż 0lub 1, ale operatory, które mają dane wyjściowe boolean , nie mogą generować innych wartości niż 0lub 1. To sprawia, że ​​operacje na zmiennych logicznych jako danych wejściowych są mniej wydajne niż to konieczne. Rozważ przykład:

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

Zwykle jest to realizowane przez kompilator w następujący sposó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. Oddziały mogą trwać długo w przypadku nieprzewidzianych zdarzeń. Operacje boolowskie można uczynić znacznie wydajniejszymi, jeśli wiadomo z całą pewnością, że operandy nie mają innych wartości niż 0i 1. Powodem, dla którego kompilator nie przyjmuje takiego założenia, jest to, że zmienne mogą mieć inne wartości, jeśli są niezainicjowane lub pochodzą z nieznanych źródeł. Powyższy kod można zoptymalizować jeśli ai bzostał zainicjowany do prawidłowych wartości lub jeśli pochodzą one od podmiotów, które produkują wyjście Boolean. Zoptymalizowany kod wygląda następująco:

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

charjest używany zamiast bool, aby umożliwić użycie operatorów bitowych ( &i |) zamiast operatorów boolowskich ( &&i ||). Operatory bitowe są pojedynczymi instrukcjami, które biorą tylko jeden cykl zegara. Operator OR ( |) działa nawet jeśli ai bmieć inne wartości niż 0lub 1. Operator AND ( &) i operator EXCLUSIVE OR ( ^) mogą dawać niespójne wyniki, jeśli operandy mają inne wartości niż 0i 1.

~nie można użyć do NIE. Zamiast tego możesz utworzyć wartość logiczną NIE dla zmiennej, która jest znana, 0lub 1poprzez XOR'owanie jej za pomocą 1:

bool a, b;
b = !a;

można zoptymalizować w celu:

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

a && bnie można zastąpić a & bif bjest wyrażeniem, którego nie należy oceniać, jeśli ajest false( &&nie będzie b, &będzie). Podobnie a || bnie może być zastąpiony a | bjeśli bto wyrażenie, które nie powinny być oceniane, czy ajest true.

Używanie operatorów bitowych jest bardziej korzystne, jeśli operandy są zmienne, niż jeśli operandy są porównaniami:

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

jest optymalna w większości przypadków (chyba że spodziewane jest, że &&wyrażenie wygeneruje wiele nieprzewidywalnych oddziałów).

Na pewno!...

Prognozowanie gałęzi spowalnia logikę z powodu przełączania, które ma miejsce w kodzie! To tak, jakbyś wybierał prostą ulicę lub ulicę z wieloma zakrętami, na pewno prosta będzie szybsza! ...

Jeśli tablica jest posortowana, warunek jest fałszywy na pierwszym etapie: data[c] >= 128 :, a następnie staje się prawdziwą wartością dla całej drogi do końca ulicy. W ten sposób szybciej dochodzisz do końca logiki. Z drugiej strony, używając nieposortowanej tablicy, potrzebujesz dużo obracania i przetwarzania, które z pewnością spowolnią działanie twojego kodu ...

Spójrz na zdjęcie, które dla ciebie stworzyłem poniżej. Która ulica zostanie ukończona szybciej?

Więc programowo, przewidywanie gałęzi powoduje spowolnienie procesu ...

Na koniec warto wiedzieć, że mamy dwa rodzaje przewidywania gałęzi, z których każdy będzie miał inny wpływ na kod:

1. Statyczny

2. Dynamiczny

Statyczne przewidywanie rozgałęzień jest używane przez mikroprocesor przy pierwszym napotkaniu rozgałęzienia warunkowego, a dynamiczne przewidywanie rozgałęzienia jest wykorzystywane do następnej realizacji kodu gałęzi warunkowego.

Aby skutecznie napisać kod, aby skorzystać z tych reguł, pisząc instrukcje „ if-else” lub „ zmień” , najpierw sprawdź najczęstsze przypadki i postępuj stopniowo aż do najmniej powszechnych. Pętle niekoniecznie wymagają specjalnego porządkowania kodu w celu przewidywania gałęzi statycznych, ponieważ zwykle stosowany jest tylko warunek iteratora pętli.

Odpowiedź na to pytanie była już wielokrotnie doskonała. Nadal chciałbym zwrócić uwagę grupy na kolejną interesującą analizę.

Ostatnio ten przykład (bardzo nieznacznie zmodyfikowany) został również użyty jako sposób na zademonstrowanie, jak kawałek kodu można profilować w samym programie w systemie Windows. Po drodze autor pokazuje również, jak wykorzystać wyniki, aby określić, gdzie kod spędza większość czasu zarówno w przypadku posortowanym, jak i nieposortowanym. Na koniec utwór pokazuje także, jak używać mało znanej funkcji warstwy HAL (Hardware Abstraction Layer), aby określić, jak często nieprzewidywalne są rozgałęzienia w nieposortowanym przypadku.

Link jest tutaj: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

Jak już wspomnieli inni, tajemnicą jest Predyktor gałęzi .

Nie próbuję niczego dodawać, ale wyjaśniam koncepcję w inny sposób. Na wiki znajduje się zwięzłe wprowadzenie, które zawiera tekst i schemat. Podobają mi się poniższe wyjaśnienia, które wykorzystują diagram do intuicyjnego opracowania Predictor gałęzi.

W architekturze komputerowej predyktor gałęzi to obwód cyfrowy, który próbuje zgadnąć, w którą stronę pójdzie gałąź (np. Struktura „jeśli-to-inaczej”), zanim zostanie to z całą pewnością znane. Celem predyktora rozgałęzienia jest poprawa przepływu w potoku instrukcji. Predyktory odgrywają kluczową rolę w osiągnięciu wysokiej wydajności w wielu nowoczesnych architekturach mikroprocesorowych, takich jak x86.

Dwukierunkowe rozgałęzienie jest zwykle realizowane za pomocą instrukcji skoku warunkowego. Skok warunkowy można albo „nie wykonać” i kontynuować wykonywanie z pierwszą gałęzią kodu, która następuje bezpośrednio po skoku warunkowym, albo można go „wykonać” i przeskoczyć w inne miejsce w pamięci programu, w którym znajduje się druga gałąź przechowywane. Nie wiadomo na pewno, czy skok warunkowy zostanie wykonany, czy nie, dopóki warunek ten nie zostanie obliczony, a skok warunkowy przejdzie etap wykonania w potoku instrukcji (patrz rys. 1).

W oparciu o opisany scenariusz napisałem demo animacji, aby pokazać, w jaki sposób instrukcje są wykonywane w potoku w różnych sytuacjach.

1. Bez predyktora gałęzi.

Bez przewidywania gałęzi procesor musiałby poczekać, aż instrukcja skoku warunkowego przejdzie etap wykonania, zanim następna instrukcja będzie mogła wejść w etap pobierania w potoku.

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

Wykonanie 3 instrukcji zajmie 9 cykli zegara.

2. Użyj Predictor gałęzi i nie wykonuj skoku warunkowego. Załóżmy, że przewidywanie nie wykonuje skoku warunkowego.

Wykonanie 3 instrukcji zajmie 7 cykli zegara.

3. Użyj Predictor gałęzi i wykonaj skok warunkowy. Załóżmy, że przewidywanie nie wykonuje skoku warunkowego.

Wykonanie 3 instrukcji zajmie 9 cykli zegara.

Czas marnowany w przypadku nieprzewidzianego rozgałęzienia jest równy liczbie etapów w potoku od etapu pobierania do etapu wykonywania. Współczesne mikroprocesory mają zwykle dość długie rurociągi, tak że opóźnienie w nieprzewidywalności wynosi od 10 do 20 cykli zegara. W rezultacie wydłużenie potoku zwiększa potrzebę bardziej zaawansowanego predyktora gałęzi.

Jak widać, wydaje się, że nie mamy powodu, aby nie używać programu Predictor gałęzi.

Jest to dość proste demo, które wyjaśnia bardzo podstawową część programu Predictor oddziału. Jeśli te gify są denerwujące, możesz je usunąć z odpowiedzi, a odwiedzający mogą również uzyskać kod źródłowy demonstracji na żywo z BranchPredictorDemo

Przewidywanie gałęzi!

Ważne jest, aby zrozumieć, że nieprzewidywalność gałęzi nie spowalnia programów. Koszt pominiętej prognozy jest taki, jakby przewidywanie gałęzi nie istniało, a użytkownik czekał na ocenę wyrażenia, aby zdecydować, który kod ma zostać uruchomiony (dalsze wyjaśnienia w następnym akapicie).

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

Ilekroć występuje instrukcja if-else\ switch, wyrażenie musi zostać ocenione w celu ustalenia, który blok powinien zostać wykonany. W kodzie zestawu generowanym przez kompilator wstawiane są instrukcje gałęzi warunkowych .

Instrukcja rozgałęzienia może spowodować, że komputer zacznie wykonywać inną sekwencję instrukcji, a tym samym odbiega od domyślnego zachowania wykonywania instrukcji w kolejności (tj. Jeśli wyrażenie jest fałszywe, program pomija kod ifbloku) w zależności od pewnego warunku, którym jest ocena wyrażenia w naszym przypadku.

To powiedziawszy, kompilator próbuje przewidzieć wynik przed jego faktyczną oceną. Pobierze instrukcje z ifbloku, a jeśli wyrażenie okaże się prawdziwe, to cudownie! Zyskaliśmy czas, aby go ocenić i poczynić postępy w kodzie; jeśli nie, to uruchamiamy zły kod, rurociąg jest opróżniany i uruchamiany jest poprawny blok.

Wyobrażanie sobie:

Powiedzmy, że musisz wybrać trasę 1 lub trasę 2. Oczekiwanie na partnera, aby sprawdził mapę, zatrzymałeś się na ## i czekałeś, lub możesz po prostu wybrać trasę 1 i jeśli masz szczęście (trasa 1 jest prawidłową trasą), świetnie, że nie musiałeś czekać na sprawdzenie mapy przez partnera (zaoszczędziłeś czas, który zajęłoby mu sprawdzenie mapy), w przeciwnym razie po prostu zawrócisz.

Podczas gdy przepłukiwanie rurociągów jest super szybkie, w dzisiejszych czasach warto podjąć ten hazard. Przewidywanie posortowanych danych lub danych, które zmieniają się powoli, jest zawsze łatwiejsze i lepsze niż przewidywanie szybkich zmian.

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

W przypadku ARM nie jest wymagana gałąź, ponieważ każda instrukcja ma 4-bitowe pole warunku, które testuje (przy zerowym koszcie) dowolny z 16 różnych warunków, które mogą wystąpić w rejestrze statusu procesora, a jeśli warunek instrukcji jest false, instrukcja jest pomijana. Eliminuje to potrzebę krótkich gałęzi i nie byłoby trafienia prognozy gałęzi dla tego algorytmu. Dlatego posortowana wersja tego algorytmu działałaby wolniej niż nieposortowana wersja na ARM, z powodu dodatkowego obciążenia związanego z sortowaniem.

Wewnętrzna pętla dla tego algorytmu wyglądałaby mniej więcej tak jak w języku asemblera ARM:

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 tak naprawdę jest to część większego obrazu:

CMPopcodes 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 Ssufiks do instrukcji, określając, że PSR powinien być aktualizowany na podstawie wynik instrukcji. Podobnie jak 4-bitowy sufiks warunku, możliwość wykonywania instrukcji bez wpływu na PSR jest mechanizmem, który zmniejsza potrzebę rozgałęzień ARM, a także ułatwia wysyłanie poza kolejnością na poziomie sprzętowym , ponieważ po wykonaniu niektórych operacji X aktualizuje bity statusu, następnie (lub równolegle) możesz wykonać szereg innych prac, które wyraźnie nie powinny wpływać na bity statusu, a następnie możesz przetestować stan bitów statusu ustawiony wcześniej przez X.

Pole testowania warunków i opcjonalne pole „ustaw bit stanu” można połączyć, na przykład:

• ADD R1, R2, R3wykonuje R1 = R2 + R3bez aktualizacji bitów statusu.
• ADDGE R1, R2, R3 wykonuje tę samą operację tylko wtedy, gdy poprzednia instrukcja, która wpłynęła na bity statusu, spowodowała warunek Większy lub Równy.
• ADDS R1, R2, R3Wykonuje dodawanie i aktualizuje N, Z, Coraz Vflagi w stanie procesora Rejestru podstawie tego, czy wynik był ujemny, zerowy, Przygotowane (dla unsigned dodatkowo) lub przepełnienie (dla podpisana dodatkowo).
• ADDSGE R1, R2, R3wykonuje dodawanie tylko wtedy, gdy GEtest jest prawdziwy, a następnie aktualizuje bity statusu na podstawie wyniku dodawania.

Większość architektur procesorów nie ma tej możliwości określania, czy bity statusu powinny być aktualizowane dla danej operacji, co może wymagać napisania dodatkowego kodu w celu zapisania i późniejszego przywrócenia bitów statusu, lub może wymagać dodatkowych rozgałęzień, lub może ograniczyć wydajność procesora wydajności wykonywania zleceń: jednym z efektów ubocznych większości architektur zestawów instrukcji CPU wymuszających aktualizację bitów statusu po większości instrukcji jest to, że znacznie trudniej jest rozdzielić, które instrukcje mogą być uruchamiane równolegle, nie zakłócając się nawzajem. Aktualizacja bitów stanu ma skutki uboczne, a zatem ma wpływ na linearyzację kodu.Zdolność ARM do mieszania i dopasowywania testów stanu bez rozgałęzień dla dowolnej instrukcji z opcją aktualizacji lub nie aktualizowania bitów statusu po każdej instrukcji jest niezwykle potężna, zarówno dla programistów i kompilatorów w języku asemblera, jak i wytwarza bardzo wydajny kod.

Jeśli kiedykolwiek zastanawiałeś się, dlaczego ARM odniósł tak fenomenalny sukces, genialna skuteczność i współdziałanie tych dwóch mechanizmów stanowią dużą część historii, ponieważ są jednym z największych źródeł wydajności architektury ARM. Blasku oryginalnych projektantów ARM ISA z 1983 roku, Steve'a Furbera i Rogera (obecnie Sophie) Wilsona, nie można przecenić.

Chodzi o przewidywanie gałęzi. Co to jest?

• Predyktor gałęzi jest jedną ze starożytnych technik poprawiających wydajność, która wciąż znajduje zastosowanie w nowoczesnych architekturach. Podczas gdy proste techniki prognozowania zapewniają szybkie wyszukiwanie i efektywność energetyczną, cierpią z powodu wysokiego wskaźnika nieprzewidywalności.

• Z drugiej strony, złożone przewidywania gałęzi - albo neuronowe, albo warianty dwupoziomowego przewidywania gałęzi - zapewniają lepszą dokładność przewidywania, ale zużywają więcej mocy, a złożoność rośnie wykładniczo.

• Ponadto w przypadku złożonych technik przewidywania czas przewidziany na rozgałęzienia sam w sobie jest bardzo wysoki - od 2 do 5 cykli - co jest porównywalne z czasem wykonania rzeczywistych rozgałęzień.

• Prognozowanie rozgałęzień jest zasadniczo problemem optymalizacji (minimalizacji), w którym nacisk kładziony jest na osiągnięcie najniższego możliwego wskaźnika pominięć, niskiego zużycia energii i niskiej złożoności przy minimalnych zasobach.

Naprawdę istnieją trzy różne rodzaje gałęzi:

Przekazywanie gałęzi warunkowych - w zależności od warunku działania komputer PC (licznik programu) jest zmieniany tak, aby wskazywał adres w strumieniu instrukcji.

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

Bezwarunkowe gałęzie - obejmuje to skoki, wywołania procedur i powroty, które nie mają określonego warunku. Na przykład bezwarunkowa instrukcja skoku może zostać zakodowana w języku asemblera jako po prostu „jmp”, a strumień instrukcji musi natychmiast zostać skierowany do miejsca docelowego wskazanego przez instrukcję skoku, podczas gdy skok warunkowy może być zakodowany jako „jmpne” przekieruje strumień instrukcji tylko wtedy, gdy wynik porównania dwóch wartości z poprzednich instrukcji „porównaj” wykaże, że wartości nie są równe. (Schemat adresowania segmentowego stosowany w architekturze x86 zwiększa złożoność, ponieważ skoki mogą być „bliskie” (w obrębie segmentu) lub „dalekie” (poza segmentem). Każdy typ ma inny wpływ na algorytmy przewidywania gałęzi.)

Przewidywanie rozgałęzień statycznych / dynamicznych : mikroprocesor stosuje przewidywanie rozgałęzień statycznych przy pierwszym napotkaniu rozgałęzienia warunkowego, a przewidywanie rozgałęzienia dynamicznego jest wykorzystywane do następnej realizacji kodu gałęzi warunkowej.

Bibliografia:

• Predyktor gałęzi

• Demonstracja samoprofilu

• Przegląd prognoz branżowych

• Prognozy branżowe

Oprócz tego, że przewidywanie gałęzi może cię spowolnić, posortowana tablica ma jeszcze jedną zaletę:

Możesz mieć warunek zatrzymania zamiast tylko sprawdzania wartości, w ten sposób zapętlasz tylko odpowiednie dane i ignorujesz resztę.
Prognozy dotyczące gałęzi zostaną pominięte 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];               
 }

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

Predyktor rozgałęzienia to obwód cyfrowy (w architekturze komputerowej), który próbuje przewidzieć, w którą stronę pójdzie rozgałęzienie, poprawiając przepływ w potoku instrukcji. Obwód / komputer przewiduje następny krok i wykonuje go.

Dokonanie błędnej prognozy prowadzi do powrotu do poprzedniego kroku i wykonania z inną prognozą. Zakładając, że prognoza jest poprawna, kod przejdzie do następnego kroku. Niepoprawne przewidywanie powoduje powtarzanie tego samego kroku, dopóki nie nastąpi prawidłowe przewidywanie.

Odpowiedź na twoje pytanie jest bardzo prosta.

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

Sorted Array: Straight Road ____________________________________________________________________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TTTTTTTTTTTTTTTTTTTTTTTTTTTT

Unsorted Array: Curved Road

______   ________
|     |__|

Przewidywanie rozgałęzień: Zgadywanie / przewidywanie, która droga jest prosta i podążanie 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 przez pomyłkę wybierzesz inną, nie będzie już zawracania, a więc wybierzesz dłuższą drogę. Jest to podobne do tego, co dzieje się na komputerze i mam nadzieję, że pomogło ci to lepiej zrozumieć.

Chcę też zacytować @Simon_Weaver z komentarzy:

Nie czyni mniej prognoz - czyni mniej niepoprawnych prognoz. Nadal musi przewidywać za każdym razem przez pętlę ...

Próbowałem tego samego kodu z MATLAB 2011b z moim MacBookiem Pro (Intel i7, 64-bitowy, 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 otrzymuję:

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

Na tej podstawie wygląda, że ​​MATLAB jest prawie 175 razy wolniejszy niż implementacja C bez sortowania i 350 razy wolniej z sortowaniem. Innymi słowy, efekt (przewidywania gałęzi) wynosi 1,46x dla implementacji MATLAB i 2,7x dla implementacji C.

Założenie innych odpowiedzi, że należy posortować dane, jest nieprawidłowe.

Poniższy kod nie sortuje całej tablicy, a jedynie 200-elementowe segmenty, dzięki czemu działa najszybciej.

Sortowanie tylko sekcji k-elementowych kończy przetwarzanie wstępne w czasie liniowym O(n), a nie O(n.log(n))czas potrzebny na sortowanie 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 jakimkolwiek zagadnieniem algorytmicznym, takim jak kolejność sortowania, i rzeczywiście jest to przewidywanie gałęzi.

Odpowiedź Bjarne'a Stroustrupa na to pytanie:

To brzmi jak pytanie do wywiadu. Czy to prawda? Skąd mógłbyś wiedzieć? Odpowiadanie na pytania dotyczące wydajności bez uprzedniego wykonania niektórych pomiarów jest złym pomysłem, dlatego ważne jest, aby wiedzieć, jak mierzyć.

Próbowałem więc z wektorem miliona liczb całkowitych i otrzymałem:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

Sprawdziłem to kilka razy, aby się upewnić. Tak, zjawisko jest prawdziwe. Mój kod klucza to:

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 ten fenomen jest prawdziwy w przypadku tego kompilatora, biblioteki standardowej i ustawień optymalizatora. Różne implementacje mogą i dają różne odpowiedzi. W rzeczywistości ktoś przeprowadził bardziej systematyczne badanie (znajdzie je szybkie wyszukiwanie w Internecie) i większość implementacji wykazuje ten efekt.

Jednym z powodów jest przewidywanie gałęzi: kluczowa operacja w algorytmie sortowania jest “if(v[i] < pivot]) …”równoważna. W przypadku posortowanej sekwencji ten test jest zawsze prawdziwy, natomiast w przypadku sekwencji losowej wybrana gałąź zmienia się losowo.

Innym powodem jest to, że kiedy wektor jest już posortowany, nigdy nie musimy przesuwać elementów do ich prawidłowej pozycji. Efekt tych drobnych szczegółów to współczynnik pięciu lub sześciu, które widzieliśmy.

Quicksort (i sortowanie ogólnie) to złożone badanie, które przyciągnęło jedne z największych umysłów informatyki. Dobra funkcja sortowania jest wynikiem zarówno wyboru dobrego algorytmu, jak i zwrócenia uwagi na wydajność sprzętu w jego implementacji.

Jeśli chcesz napisać wydajny kod, musisz wiedzieć trochę o architekturze maszyny.

To pytanie jest zakorzenione w modelach przewidywania rozgałęzień na procesorach. Polecam przeczytać ten artykuł:

Zwiększanie szybkości pobierania instrukcji poprzez przewidywanie wielu oddziałów i pamięć podręczną adresów oddziałów

Kiedy masz posortowane elementy, IR nie może mieć problemu z pobraniem wszystkich instrukcji procesora, raz po raz, pobiera je z pamięci podręcznej.

Jednym ze sposobów uniknięcia błędów prognozowania gałęzi jest zbudowanie tabeli odnośników i zindeksowanie jej przy użyciu danych. Stefan de Bruijn omówił to w swojej odpowiedzi.

Ale w tym przypadku wiemy, że wartości mieszczą się w zakresie [0, 255] i dbamy tylko o wartości> = 128. Oznacza to, że możemy łatwo wyodrębnić pojedynczy bit, który powie nam, czy chcemy wartość, czy nie: poprzez przesunięcie dane w prawych 7 bitach, mamy 0 bitów lub 1 bitów i chcemy dodać wartość tylko wtedy, gdy mamy 1 bit. Nazwijmy ten bit „bitem decyzyjnym”.

Używając wartości 0/1 bitu decyzyjnego jako indeksu w tablicy, możemy stworzyć kod, który będzie równie szybki, niezależnie od tego, czy dane zostaną posortowane, czy nie. Nasz kod zawsze doda wartość, ale gdy bit decyzyjny ma wartość 0, dodamy wartość w miejscu, w którym nas nie obchodzi. 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ę wartości dodanych, ale nigdy nie występuje błąd przewidywania gałęzi. Jest losowo szybszy w przypadku danych losowych niż wersja z rzeczywistą instrukcją if.

Ale w moich testach jawna tabela odnośników była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli odnośników było nieco szybsze niż przesuwanie bitów. To pokazuje, jak mój kod konfiguruje i korzysta z tabeli odnośników (niewyobrażalnie nazwanej lut dla „LookUp Table” w kodzie). Oto kod C ++:

// Zadeklaruj, a następnie wypełnij tabelę odnośników

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 tablica przeglądowa 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łaby dobrze, gdyby dane były 24-bitowymi wartościami, a chcieliśmy tylko połowy z nich ... tabela przeglądowa byłaby o wiele za duża, aby była praktyczna. Z drugiej strony możemy połączyć dwie techniki pokazane powyżej: najpierw przesuń bity, a następnie zindeksuj tabelę wyszukiwania. W przypadku 24-bitowej wartości, której potrzebujemy tylko górnej połowy, możemy potencjalnie przesunąć dane w prawo o 12 bitów i pozostawić 12-bitową wartość dla indeksu tabeli. 12-bitowy indeks tabeli implikuje tabelę 4096 wartości, co może być praktyczne.

Technika indeksowania do tablicy zamiast użycia instrukcji if może być użyta do podjęcia decyzji, którego wskaźnika użyć. Widziałem bibliotekę, która zaimplementowała drzewa binarne i zamiast dwóch nazwanych wskaźników (pLeft i pRight lub cokolwiek innego) miała tablicę wskaźników o długości 2 i zastosowała technikę „bitu decyzyjnego”, aby zdecydować, który wybrać. 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];

to dobre rozwiązanie, może zadziała