22 Pytanie: Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie niesortowanej tablicy?

pytanie utworzone w Tue, Jun 4, 2019 12:00 AM

Oto fragment kodu C ++, który pokazuje bardzo specyficzne zachowanie. Z jakiegoś dziwnego powodu sortowanie danych w cudowny sposób powoduje, że kod jest prawie sześć razy szybszy:

 
#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); kod działa w 11,54 sekundy.
  • Po posortowaniu danych kod działa w 1,93 sekundy.

Początkowo myślałem, że to może być tylko anomalia języka lub kompilatora, więc wypróbowałem ją w języku Java:

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


Moją pierwszą myślą było to, że sortowanie przenosi dane do pamięci podręcznej, ale potem pomyślałem, jak głupie było to, że tablica została właśnie wygenerowana.

  • Co się dzieje?
  • Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie niesortowanej tablicy? Kod podsumowuje kilka niezależnych terminów, więc kolejność nie powinna mieć znaczenia.
23151
  1. Tylko dla rekordu. W systemie Windows /VS2017 /i7-6700K 4GHz nie ma różnicy między dwiema wersjami. Zajmuje 0,6 s dla obu przypadków. Jeśli liczba iteracji w pętli zewnętrznej zwiększy się 10 razy, czas wykonania zwiększa się 10 razy w porównaniu do 6 w obu przypadkach.
    2017-11-15 20: 45: 37Z
  2. @ user194715: każdy kompilator, który używa cmov lub innej implementacji bez rozgałęzień (np. auto-wektoryzacja z pcmpgtd) będzie miał wydajność, która nie zależy od danych od żadnego procesora. Ale jeśli jest rozgałęziony, będzie zależny od sortowania od dowolnego procesora z nietypowym wykonaniem spekulacyjnym. (Nawet wysokowydajne jednostki centralne korzystają z przewidywania gałęzi, aby uniknąć pobierania /dekodowania bąbelków na pobranych gałęziach; kara za brak jest mniejsza).
    2017-12-26 07: 14: 57Z
  3. @ KyleMit czy ma to coś wspólnego z obydwoma? Nie czytałem dużo o obu
    2018-01-10 06: 26: 02Z
  4. @ mohitmun, obie te luki w zabezpieczeniach pasują do szerokiej kategorii luk klasyfikowanych jako ataki„ docelowej gałęzi ”
    2018-01-10 14: 26: 37Z
  5. 22 odpowiedzi                              22                         

    Jesteś ofiarą przewidywania gałęzi nie powiodło się.


    Co to jest przewidywanie gałęzi?

    Rozważ węzeł kolejowy:

    Obraz autorstwa Mecanismo, poprzez Wikimedia Commons. Używane w ramach licencji CC-By-SA 3.0 .

    Dla dobra argumentu załóżmy, że ma to miejsce w XIX wieku - przed komunikacją na odległość lub drogą radiową.

    Jesteś operatorem skrzyżowania i słyszysz nadchodzący pociąg. Nie masz pojęcia, w którą stronę ma iść. Zatrzymujesz pociąg, by zapytać kierowcę, w jakim kierunku chcą. A potem odpowiednio ustawisz przełącznik.

    Pociągi są ciężkie i mają dużą bezwładność. Więc trwają wiecznie, aby uruchomić i zwolnić.

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

    • Jeśli zgadłeś, to nadal trwa.
    • Jeśli się pomyliłeś, kapitan zatrzyma się, cofnie i krzyczy na ciebie, żebyś przełączył przełącznik. Następnie może zrestartować inną ścieżkę.

    Jeśli zgadnieszza każdym razem , pociąg nigdy nie będzie musiał się zatrzymywać.
    Jeśli zgadujesz, że zbyt często się mylisz , pociąg będzie spędzał dużo czasu zatrzymując się, wykonując kopie zapasowe i uruchamiając ponownie.


    Zastanów się nad instrukcją if: na poziomie procesora jest to instrukcja rozgałęzienia:

    Zrzut ekranu skompilowanego kodu zawierającego instrukcję if

    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ą ukończone. Następnie kontynuujesz właściwą ścieżkę.

    Nowoczesne procesory są skomplikowane i mają długie potoki. Więc trwają wiecznie „rozgrzewka” i „spowolnienie”.

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

    • Jeśli zgadłeś, kontynuujesz wykonywanie.
    • Jeśli się pomyliłeś, musisz opróżnić rurociąg i wrócić do oddziału. Następnie możesz zrestartować inną ścieżkę.

    Jeśli odgadniesz za każdym razem , wykonanie nigdy nie będzie musiało się kończyć.
    Jeśli zgadujesz, że zbyt często się mylisz , spędzasz dużo czasu przeciągając się, wycofując i restartując.


    To jest przewidywanie gałęzi. Przyznaję, że nie jest to najlepsza analogia, ponieważ pociąg mógłby po prostu sygnalizować kierunek flagą. Ale w komputerach procesor nie wie, w którym kierunku oddział pójdzie do ostatniej chwili.

    Jak więc zgadłbyś strategicznie, aby zminimalizować liczbę razy, kiedy pociąg musi się cofnąć i zejść na drugą ścieżkę? Patrzysz na przeszłą historię! Jeśli pociąg odjedzie w 99% przypadków, zgadniesz, że odjechałeś. Jeśli się zmienia, to na przemian zgadujesz. Jeśli co trzy razy idzie w jedną stronę, zgadnij to samo ...

    Innymi słowy, próbujesz zidentyfikować wzór i podążać za nim. Jest to mniej więcej tak, jak działają predyktory gałęzi.

    Większość aplikacji ma dobrze zachowane gałęzie. Współczesne predyktory oddziałów zazwyczaj osiągają współczynniki trafień> 90%. Ale w obliczu nieprzewidywalnych gałęzi bez rozpoznawalnych wzorców predyktory gałęzi są praktycznie bezużyteczne.

    Dalsza lektura: Artykuł „Predyktor gałęzi” na Wikipedii .


    Jak wskazano powyżej, winowajcą jest to, jeśli instrukcja:

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

    Zauważ, że dane są równomiernie rozłożone między 0 a 255. Gdy dane są sortowane, mniej więcej pierwsza połowa iteracji nie wejdzie w instrukcję if. Potem wszystkie wejdą do instrukcji if.

    Jest to bardzo przyjazne dla predyktora rozgałęzienia, ponieważ gałąź kolejno idzie w tym samym kierunku wiele razy. Nawet prosty licznik nasycenia poprawnie przewidzi gałąź, z wyjątkiem kilku iteracji po przełączeniu 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 jest bezużyteczny, ponieważ nie może przewidzieć losowych danych. Tak więc prawdopodobnie będzie około 50% błędnych przewidywań (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)
    

    Więc co można zrobić?

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

    Zastąp:

     
    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. Ale w tym przypadku jest poprawny dla wszystkich wartości wejściowych data[].)

    Testy porównawcze: Core i7 920 przy 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 oddziałem: istnieje ogromna różnica między posortowanymi i nieposortowanymi danymi.
    • Z Hackiem: nie ma różnicy między posortowanymi i nieposortowanymi danymi.
    • W przypadku C ++ hack jest w rzeczywistości trochę wolniejszy niż w przypadku gałęzi, gdy dane są sortowane.

    Ogólną zasadą jest unikanie zależnych od danych rozgałęzień w krytycznych pętlach (takich jak w tym przykładzie).


    Aktualizacja :

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

    • VC ++ 2010 nie jest w stanie generować ruchów warunkowych dla tej gałęzi nawet poniżej /Ox.

    • Kompilator Intel C ++ (ICC) 11 robi coś cudownego. To zamienia obie pętle , tym samym podnosząc nieprzewidywalną gałąź do zewnętrznej pętli, więc nie tylko jest odporna na błędy, ale także dwa razy szybciej niż cokolwiek VC ++ i GCC mogą generować! Innymi słowy, ICC skorzystało z pętli testowej, aby pokonać benchmark ...

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

    To pokazuje, że nawet dojrzałe nowoczesne kompilatory mogą się bardzo różnić pod względem możliwości optymalizacji kodu ...

        
    30295
    2019-05-27 12: 42: 11Z
    1. @ Mysticial Aby uniknąć zmiany położenia hacku, możesz napisać coś takiego jak int t=-((data[c]>=128)), aby wygenerować maskę. To też powinno być szybsze. Interesujące byłoby wiedzieć, czy kompilator jest na tyle sprytny, aby wstawić ruch warunkowy czy nie.
      2012-06-27 16: 47: 51Z
    2. @ phonetagger Spójrz na to pytanie uzupełniające: stackoverflow.com/questions/11276291/… Kompilator Intela był całkiem blisko całkowitego pozbycia się zewnętrznej pętli.
      2012-07-10 17: 08: 39Z
    3. @ Novelocrat Tylko połowa z nich jest poprawna. Przesunięcie 1 do bitu znakowego, gdy wynosi zero, jest rzeczywiście UB. To dlatego, że jest to przepełnienie z całkowitą liczbą znaków. Ale przesunięcie 1 z bitu znaku to IB. Przesunięcie w prawo ujemnej liczby całkowitej to IB. Możesz przejść do argumentu, że C /C ++ nie wymaga, aby górny bit był wskaźnikiem znaku. Ale szczegóły implementacji to IB.
      2013-08-18 21: 04: 38Z
    4. @ Mysticial Bardzo dziękuję za link. Wygląda obiecująco. Pójdę przez to. Ostatnia prośba. Przepraszam, ale proszę, nie przejmuj się, czy mógłbyś mi powiedzieć, jak możesz to zrobić int t = (data[c] - 128) >> 31; sum += ~t & data[c];, aby zastąpić oryginalny, jeśli warunek powyżej?
      2014-03-08 20: 05: 22Z
    5. Gramatyka we mnie chce, żebym pomyślał, że to powinno brzmieć "... ofiara przewidywania rozgałęzień zawodzi ure ", a nie tylko ".. . ofiara przewidywania rozgałęzienia nie działa. ”
      2015-06-27 11: 35: 58Z

    Przewidywanie gałęzi.

    Przy posortowanej tablicy warunek data[c] >= 128 jest pierwszym false dla pasma wartości, a następnie staje się true dla wszystkich późniejszych wartości. To łatwe do przewidzenia. Z niesortowaną tablicą płacisz za koszt rozgałęzienia.

        
    3907
    2016-08-05 07: 53: 10Z
    1. Czy przewidywanie gałęzi działa lepiej na posortowanych tablicach niż tablice z różnymi wzorami? Na przykład dla tablicy - > {10, 5, 20, 10, 40, 20, ...} następny element tablicy z wzorca to 80. Czy ten rodzaj tablicy zostanie przyspieszony przez przewidywanie rozgałęzień, w którym następnym elementem jest 80, jeśli wzór jest przestrzegany? Czy też zwykle pomaga tylko w posortowanych tablicach?
      2014-09-23 18: 58: 12Z
    2. Więc w zasadzie wszystko, czego zwykle nauczyłem się o big-O, jest poza oknem? Lepiej ponieść koszt sortowania niż koszt rozgałęzienia?
      2014-10-30 07: 51: 58Z
    3. @ AgrimPathak To zależy. W przypadku niezbyt dużego wejścia algorytm o większej złożoności jest szybszy niż algorytm o mniejszej złożoności, gdy stałe są mniejsze dla algorytmu o większej złożoności. Whepunkt progu rentowności może być trudny do przewidzenia. Ponadto porównaj to lokalność jest ważna. Big-O jest ważne, ale nie jest jedynym kryterium wydajności.
      2014-10-30 10: 14: 12Z
    4. Kiedy ma miejsce przewidywanie gałęzi? Kiedy język będzie wiedział, że tablica jest posortowana? Mam na myśli sytuację tablicy, która wygląda jak: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? czy ta niejasna 3 zwiększy czas działania? Czy będzie tak długo jak niesortowana tablica?
      2014-11-09 13: 37: 18Z
    5. @ FilipBartuzi Przewidywanie rozgałęzień odbywa się w procesorze, poniżej poziomu języka (ale język może zaoferować kompilatorowi to, co jest prawdopodobne, więc kompilator może emitować odpowiedni kod do tego). W twoim przykładzie nietypowy 3 doprowadzi do błędnej prognozy gałęzi (dla odpowiednich warunków, gdzie 3 daje inny wynik niż 1000), a zatem przetwarzanie tej tablicy prawdopodobnie zajmie kilka tuzinów lub stu nanosekund dłużej niż posortowana tablica prawie nigdy nie będzie widoczna. To, co kosztuje czas, to wysoka liczba błędnych przewidywań, jedno nieporozumienie na 1000 to niewiele.
      2014-11-09 13: 49: 37Z

    Powodem, dla którego wydajność znacznie wzrasta, gdy dane są sortowane, jest to, że kara przewidywania rozgałęzień jest usuwana, jak to pięknie wyjaśniono w Odpowiedź mistrza .

    Teraz, jeśli spojrzymy na kod

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

    możemy stwierdzić, że znaczenie tej konkretnej gałęzi if... else... polega na dodaniu czegoś, gdy warunek jest spełniony. Ten rodzaj oddziału można łatwo przekształcić w instrukcję warunkowego ruchu , która zostanie skompilowana w instrukcję warunkowego przeniesienia: cmovl w systemie x86. Oddział i tym samym potencjalna kara przewidywania rozgałęzień jest usuwana.

    W C, a więc C++, instrukcja, która kompiluje się bezpośrednio (bez jakiejkolwiek optymalizacji) do instrukcji warunkowego ruchu w x86, jest operatorem trójskładnikowym ... ? ... : .... 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 Intelu Core i7 -2600K @ 3,4 GHz i Visual Studio 2010 Release Mode , benchmark to (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. Otrzymujemy duże przyspieszenie, gdy wynik rozgałęzienia jest nieprzewidywalny, ale cierpimy trochę, gdy jest przewidywalny. W rzeczywistości, gdy używasz warunkowego ruchu, wydajność jest taka sama niezależnie od wzorca danych.

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

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

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

    max2 używa operatora trójskładnikowego ... ? ... : ...:

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

    Na maszynie x86-64 GCC -S generuje 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
    

    max2 używa znacznie mniej kodu ze względu na użycie instrukcji cmovge. Ale prawdziwym zyskiem jest to, że max2 nie obejmuje skoków w oddziałach, jmp, co miałoby znaczną karę za wydajność, gdyby przewidywany wynik nie był właściwy.

    Dlaczego więc ruch warunkowy działa lepiej?

    W typowym procesorze x86 wykonanie instrukcji jest podzielone na kilka etapów. Ogólnie rzecz biorąc, mamy inny sprzęt do obsługi różnych etapów. Więc nie musimy czekać na jedną instrukcję, aby zakończyć, aby rozpocząć nową. Nazywa się to potokowaniem .

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

    W przypadku warunkowego przeniesienia instrukcja warunkowego przeniesienia wykonania 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ą rezultatu. Tak więc mya ułamek czasu wykonania jednej instrukcji. Dlatego wersja warunkowego przenoszenia jest wolniejsza niż gałąź, gdy przewidywanie jest łatwe.

    Książka Systemy komputerowe: perspektywa programisty, druga edycja wyjaśnia to szczegółowo. Możesz sprawdzić Sekcja 3.6.6 dla Warunkowych instrukcji przenoszenia , całego Rozdziału 4 dla Architektury procesorów oraz Rozdziału 5.11.2 dla specjalnego traktowania Prognozowania i Misprediction Oddziału Kary .

    Czasami niektóre nowoczesne kompilatory mogą zoptymalizować nasz kod do montażu z lepszą wydajnością, czasami niektóre kompilatory nie mogą (dany kod używa natywnego kompilatora Visual Studio). Znajomość różnicy wydajności między gałęzią a ruchem warunkowym, gdy jest nieprzewidywalna, może pomóc nam w napisaniu kodu o lepszej wydajności, gdy scenariusz stanie się tak skomplikowany, że kompilator nie będzie mógł ich zoptymalizować automatycznie.

        
    3144
    2019-05-27 12: 50: 22Z
    1. Nie ma domyślnego poziomu optymalizacji, chyba że dodasz -O do linii poleceń GCC. (I nie możesz mieć najgorszego angielskiego niż mój;)
      2012-06-28 14: 04: 45Z
    2. Trudno mi uwierzyć, że kompilator może zoptymalizować operatora trójskładnikowego lepiej niż odpowiadający mu if-statement. Pokazałeś, że GCC optymalizuje operatora trójskładnikowego do warunkowego ruchu; nie pokazał, że nie robi dokładnie tego samego dla instrukcji if. W rzeczywistości, zgodnie z powyższym Mystical, GCC optymalizuje instrukcję if do warunkowego ruchu, co uczyniłoby tę odpowiedź całkowicie niepoprawną.
      2012-06-30 15: 29: 23Z
    3. @ WiSaGaN Kod nie pokazuje niczego, ponieważ twoje dwa fragmenty kodu kompilują się do tego samego kodu maszynowego. Bardzo ważne jest, aby ludzie nie wpadli na pomysł, że instrukcja if w twoim przykładzie jest inna niż w twoim przykładzie. To prawda, że ​​jesteś w posiadaniu podobieństwa w ostatnim akapicie, ale to nie usuwa faktu, że reszta przykładu jest szkodliwa.
      2012-10-11 03: 12: 02Z
    4. @ WiSaGaN Mój downvote na pewno zamieniłby się w komentarz, jeśli zmodyfikowałeś swoją odpowiedź, aby usunąć mylący przykład -O0 i pokazać różnicę w zoptymalizowanym asm na twoich dwóch testach.
      2012-10-11 04: 13: 03Z
    5. @ UpAndAdam W momencie testu VS2010 nie może zoptymalizować oryginalnej gałęzi do warunkowego ruchu, nawet przy określaniu wysokiego poziomu optymalizacji, podczas gdy gcc może.
      2013-09-14 15: 18: 02Z

    Jeśli jesteś zainteresowany jeszcze większą optymalizacją tego kodu, rozważ to:

    Począwszy 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];
        }
    }
    

    Wtedy możesz zobaczyć, że warunkowe if jest stałe podczas wykonywania pętli i, więc możesz wyciągnąć if:

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

    Wtedy widzisz, że wewnętrzna pętla może zostać zwinięta w jedno pojedyncze wyrażenie, zakładając, że model zmiennoprzecinkowy na to pozwala (na przykład /fp:fast 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.

        
    2159
    2019-05-27 12: 51: 33Z
    1. Jeśli chcesz oszukać, równie dobrze możesz wziąć mnożenie poza pętlę i zrobić sumę * = 100000 po pętli.
      2012-10-11 01: 48: 01Z
    2. @ Michael - Uważam, że ten przykład jest w rzeczywistości przykładem optymalizacja niezmienności pętli (LIH), a NIE pętla wymiany . W tym przypadku cała wewnętrzna pętla jest niezależna od zewnętrznej pętli i dlatego może zostać podniesiona z zewnętrznej pętli, po czym wynik jest mnożony przez suma ponad i jednej jednostki = 1e5. Nie ma to znaczenia dla wyniku końcowego, ale chciałem po prostu ustawić rekord, ponieważ jest to strona często odwiedzana.
      2013-03-04 12: 59: 11Z
    3. Chociaż nie w prostym duchu zamiany pętli, wewnętrzny if w tym momencie może zostać przekonwertowany na: sum += (data[j] >= 128) ? data[j] * 100000 : 0;, który kompilator może być w stanie zredukować do cmovge lub równoważnego.
      2013-05-15 11: 57: 16Z
    4. Zewnętrzna pętla ma zrobić wystarczająco dużo czasu, aby wewnętrzna pętla mogła zostać profilowana. Dlaczego więc miałbyś zamieniać się w pętlę. Na końcu ta pętla zostanie usunięta mimo wszystko.
      2016-06-22 15: 45: 19Z
    5. @ saurabheights: Błędne pytanie: dlaczego kompilator NIE miałby pętli zamiany. Microbenchmarks jest trudny;)
      2016-12-29 13: 58: 53Z

    Bez wątpienia niektórzy z nas byliby zainteresowani sposobami identyfikowania kodu, który jest problematyczny dla predyktora gałęziowego procesora. Narzędzie Valgrind cachegrind ma symulator predyktora gałęzi, włączony za pomocą flagi --branch-sim=yes. Uruchamianie go z przykładami w tym pytaniu, z liczbą zewnętrznych pętli zmniejszonych do 10000 i skompilowanych 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%   )
    

    Nieautoryzowane :

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

    W dół do wyjścia liniowego produkowanego 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];
               .      .  .   .          }
               .      .  .   .      }
    

    Nieautoryzowane :

     
              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 łatwo zidentyfikować problematyczną linię - w wersji nieposortowanej linia if (data[c] >= 128) powoduje 164,050,007 błędnych przewidywanych rozgałęzień warunkowych (Bcm) w modelu predyktorów rozgałęzień cachegrind, podczas gdy w wersji posortowanej powoduje tylko 10,006.


    Alternatywnie, w Linuksie możesz użyć podsystemu liczników wydajności, aby wykonać to samo zadanie, ale z natywną wydajnością przy użyciu liczników procesora.

     
    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
    

    Nieautoryzowane :

     
     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ć adnotacje do kodu źródłowego z demontażem.

     
    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.

        
    1800
    2012-10-18 19: 20: 21Z
    1. To jest przerażające, na nieposortowanej liście powinno być 50% szans na trafienie addu. W pewnym sensie przewidywanie rozgałęzień ma tylko 25% szansy na pominięcie, jak to zrobić lepiej niż 50% braków?
      2013-12-09 04: 00: 09Z
    2. @ tall.b.lo: 25% to wszystkie gałęzie - w pętli są dwie gałęzie, jedna dla data[c] >= 128 (która ma 50% szansy na utratę, jak sugerujesz) i jeden na stan pętli c < arraySize, który ma ~ 0% współczynnik pominięcia.
      2013-12-09 04: 29: 25Z

    Właśnie przeczytałem o tym pytaniu i jego odpowiedziach i czuję, że brakuje odpowiedzi.

    Typowym sposobem wyeliminowania predykcji gałęzi, która okazała się szczególnie skuteczna w językach zarządzanych, jest wyszukiwanie tabeli zamiast użycia gałęzi (chociaż w tym przypadku nie testowałem tego).

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

    1. to mała tabela i prawdopodobnie będzie buforowana w procesorze i
    2. uruchamiasz rzeczy w dość zwartej pętli i /lub procesor może wstępnie załadować dane.

    Backgroui dlaczego

    Z perspektywy procesora pamięć jest wolna. Aby zrekompensować różnicę prędkości, w pamięci procesora wbudowanych jest kilka pamięci podręcznych (pamięć podręczna L1 /L2). Więc wyobraź sobie, że robisz miłe obliczenia i dowiadujesz się, że potrzebujesz kawałka pamięci. Procesor pobierze operację „load” i załaduje fragment pamięci do pamięci podręcznej - a następnie użyje pamięci podręcznej 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ć go 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 wrócić i rzeczywiście poczekać na obciążenie pamięci, które potrwa wiecznie ( innymi słowy: niepowodzenie przewidywania rozgałęzienia jest złe , ładowanie pamięci po niepowodzeniu przewidywania rozgałęzień jest po prostu okropne! ).

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

    Pierwszą rzeczą, którą musimy wiedzieć, to co jest małe ? Chociaż mniejsze jest ogólnie lepsze, podstawową zasadą jest trzymanie się tablic przeglądowych o rozmiarze

    Konstruowanie tabeli

    Zorientowaliśmy się, że możemy stworzyć mały stolik. Następną rzeczą do zrobienia jest wprowadzenie funkcji wyszukiwania. Funkcje wyszukiwania są zwykle małymi funkcjami, które używają kilku podstawowych operacji na liczbach całkowitych (i, lub, xor, przesuwają, dodają, usuwają i być może mnożą). Chcesz, aby twoje wejście zostało przetłumaczone przez funkcję wyszukiwania na jakiś „unikalny klucz” w twojej tabeli, który następnie daje ci odpowiedź na wszystkie zadania, które chciałeś wykonać.

    W tym przypadku: > = 128 oznacza, że ​​możemy zachować wartość, < 128 oznacza, że ​​się go pozbywamy. Najłatwiej to zrobić za pomocą „AND”: jeśli go zachowamy, to I ORAZ z 7FFFFFFF; jeśli chcemy się go pozbyć, to I ORAZ 0. Zauważmy również, że 128 jest potęgą 2 - więc możemy iść dalej i stworzyć tabelę z 32768/128 liczbami całkowitymi i wypełnić ją jednym zerem i wieloma 7FFFFFFFF.

    Zarządzane języki

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

    Cóż, nie dokładnie ... :-)

    Trochę pracy poświęcono wyeliminowaniu 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 dla kompilatora jest oczywiste, że warunek brzegowy nigdy nie zostanie trafiony. Przynajmniej kompilator Microsoft JIT (ale spodziewam się, że Java robi podobne rzeczy) zauważy to i całkowicie usunie sprawdzanie. WOW, co oznacza brak oddziału. Podobnie zajmie się 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 granicy było przewidywalne - i obserwuj, jak przyspiesza.

    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();
    
        
    1259
    2019-01-16 04: 47: 21Z
    1. Chcesz pominąć predyktor gałęzi, dlaczego? To optymalizacja.
      2013-04-24 17: 50: 33Z
    2. Ponieważ żadna gałąź nie jest lepsza niż gałąź :-) W wielu sytuacjach jest to po prostu dużo szybsze ... jeśli optymalizujesz, na pewno warto próbować. Używają go również trochę na f.ex. graphics.stanford.edu/~seander/bithacks.html
      2013-04-24 21: 57: 13Z
    3. W ogólnych tabelach wyszukiwania mogą być szybkie, ale czy przeprowadziłeś testy dla tego konkretnego warunku? Nadal będziesz mieć warunek rozgałęzienia w swoim kodzie, dopiero teraz zostanie przeniesiony do części generowania tabeli wyszukiwania. Nadal nie udałoby ci się uzyskać poprawy perfekcji
      2013-12-19 21: 45: 03Z
    4. @ Zain, jeśli naprawdę chcesz wiedzieć ... Tak: 15 sekund z odgałęzieniem i 10 z moją wersją. Niezależnie od tego, jest to przydatna technika do poznania obu sposobów.
      2013-12-20 18: 57: 29Z
    5. Dlaczego nie sum += lookup[data[j]], gdzie lookup to tablica z 256 wpisami, z których pierwsze są zerowe, a ostatnie równe indeksowi?
      2014-03-12 12: 17: 49Z

    Ponieważ dane są rozłożone między 0 a 255, gdy tablica jest posortowana, wokół pierwszej połowy iteracji nie pojawi się opis 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 niektórych przypadkach, jak w przypadku posortowanych danych? Nadchodzi „predyktor gałęzi”. Predyktor rozgałęzienia jest obwodem cyfrowym, który próbuje odgadnąć, w jaki sposób pójdzie gałąź (np. Struktura if-then-else), zanim będzie to znane na pewno. Zadaniem predyktora gałęzi jest poprawa przepływu w potoku instrukcji. Predyktory gałęzi odgrywają kluczową rolę w osiąganiu wysokiej wydajności!

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

    Wydajność opisu if 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, opis if będzie znacznie droższy.

    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 fałszywymi wzorcami:

     
    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
    

    Wzorzec „ zły ” typu „prawda-fałsz” może spowodować, że wynik if będzie sześciokrotnie wolniejszy niż wzór „ dobry ”! Oczywiście, który wzór jest dobry, a który zły, zależy od dokładnych instrukcji generowanych przez kompilator i określony procesor.

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

        
    1129
    2019-02-27 10: 58: 32Z
    1. Nie wyświetlasz czasów „losowego” wzoru TF.
      2013-02-23 02: 31: 21Z
    2. @ MooingDuck Bo to nie zrobi różnicy - ta wartość może być dowolna, ale nadal będzie w granicach tych progów. Po co więc pokazywać losową wartość, gdy już znasz limity? Chociaż zgadzam się, że możesz pokazać jeden ze względu na kompletność i „po prostu do cholery”.
      2016-03-28 12: 58: 51Z
    3. @ cst1992: W tej chwili jego najwolniejszym czasem jest TTFFTTFFTTFF, co moim ludzkiemu oku wydaje się dość przewidywalne. Losowo jest z natury nieprzewidywalny, więc jest całkowicie możliwe, że będzie wolniej, a więc poza zakresem przedstawionym tutaj. OTOH, może być tak, że TTFFTTFF doskonale trafia w patologiczny przypadek. Nie mogę powiedzieć, ponieważ nie pokazywał czasu losowo.
      2016-03-28 18: 27: 16Z
    4. @ MooingDuck Dla ludzkiego oka, "TTFFTTFFTTFF" jest przewidywalną sekwencją, ale mówimy tutaj o zachowaniu predyktora gałęzi wbudowanego w CPU. Predyktor gałęzi nie jest rozpoznawany przez wzorzec AI; to jest bardzo proste. Kiedy po prostu zmieniasz gałęzie, nie przewiduje to dobrze. W większości kodów gałęzie działają prawie tak samo przez cały czas; rozważ pętlę, która wykonuje się tysiące razy. Gałąź na końcu pętli wraca do początku pętli 999 razy, a po raz tysięczny robi coś innego. Zwykle bardzo prosty predyktor gałęzi działa.
      2016-07-20 21: 07: 37Z
    5. @ steveha: Myślę, że robisz założenia o tym, jak działa predyktor gałęzi procesora i nie zgadzam się z tą metodologią. Nie wiem, jak zaawansowany jest ten predyktor gałęzi, ale wydaje mi się, że jest znacznie bardziej zaawansowany niż ty. Prawdopodobnie masz rację, ale pomiary na pewno będą dobre.
      2016-07-20 21: 10: 18Z

    Jednym ze sposobów uniknięcia błędów przewidywania gałęzi jest zbudowanie tabeli odnośników i indeksowanie 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 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ść lub nie: przesuwając dane w prawo na 7 bitów, pozostaje nam bit 0 lub 1 bit, a 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 utworzyć 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 decyzji ma wartość 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ę dodatków, ale nigdy nie ma błędu przewidywania rozgałęzienia. Jest znacznie szybszy na danych losowych niż wersja z rzeczywistą instrukcją if.

    Ale w moich testach jawna tabela przeglądowa była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli przeglądowej było nieco szybsze niż przerzucanie bitów. Pokazuje to, w jaki sposób mój kod jest konfigurowany i korzysta z tabeli odnośników (nieodmiennie nazwanej lut dla „LookUp Table” 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 przeglądowa miała tylko 256 bajtów, więc ładnie pasuje do pamięci podręcznej i wszystko było szybkie. Ta technika nie zadziałałaby dobrze, gdyby dane były wartościami 24-bitowymi i chcieliśmy tylko połowy z nich ... tablica przeglądowa byłaby zbyt duża, aby była praktyczna. Z drugiej strony możemy połączyć dwie techniki pokazane powyżej: najpierw przesuń bity, a następnie indeksuj tabelę odnośników. Aby wartość 24-bitowa wymagała tylko wartości górnej połowy, moglibyśmy przesunąć prawo do danych o 12 bitów i pozostawić wartość 12-bitową dla indeksu tabeli. 12-bitowy indeks tabeli implikuje tabelę 4096 wartości, co może być praktyczne.

    Technika indeksowania do tablicy, zamiast używania instrukcji if, może być użyta do decydowania, którego wskaźnika użyć. Widziałem bibliotekę, która zaimplementowała drzewa binarne i zamiast mieć dwa nazwane wskaźniki (pLeft i pRight lub cokolwiek), miała tablicę wskaźników o długości 2 i wykorzystała technikę „bitów decyzyjnych”, aby zdecydować, którą z nich 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: Czerwone czarne drzewa , Wiecznie zaskoczony

        
    1051
    2019-05-27 13: 08: 32Z
    1. Prawo, możesz także użyć bitu bezpośrednio i pomnożyć (data[c]>>7 - który jest również tutaj omawiany); Celowo zostawiłem to rozwiązanie, ale oczywiście masz rację. Mała uwaga: podstawową zasadą dla tabel przeglądowych jest to, że jeśli pasuje do 4 KB (z powodu buforowania), będzie działać - najlepiej uczynić tabelę możliwie najmniejszą. W przypadku języków zarządzanych naciskam na 64 KB, w przypadku języków niskiego poziomu, takich jak C ++ i C, prawdopodobnie ponownie rozważę (to tylko moje doświadczenie). Od typeof(int) = 4 starałbym się trzymać maksymalnie 10 bitów.
      2013-07-29 12: 05: 24Z
    2. Myślę, że indeksowanie z wartością 0/1 będzie prawdopodobnie szybsze niż liczba całkowita pomnożona, ale myślę, że jeśli wydajność jest naprawdę krytyczna, powinieneś ją profilować. Zgadzam się, że małe tablice przeglądowe są niezbędne, aby uniknąć presji na pamięć podręczną, ale oczywiście, jeśli masz większą pamięć podręczną, możesz uciec z większą tablicą przeglądową, więc 4 KB jest bardziej regułą niż twardą regułą. Myślę, że miałeś na myśli sizeof(int) == 4? To byłoby prawdziwe dla 32-bitowych. Mój dwuletni telefon komórkowy ma pamięć podręczną L1 o pojemności 32 KB, więc nawet tabela przeglądowa 4K może działać, zwłaszcza jeśli wartości wyszukiwania byłyby bajtem zamiast int.
      2013-07-29 22: 02: 13Z
    3. Prawdopodobnie brakuje mi czegoś, ale w j równa się 0 lub 1 metodzie, dlaczego po prostu nie pomnożysz swojej wartości przez j, zanim ją dodasz, zamiast używać indeksowania tablicy (prawdopodobnie należy pomnożyć przez 1-j zamiast j)
      2014-03-04 15: 38: 24Z
    4. @ steveha Mnożenie powinno być szybsze, próbowałem znaleźć go w książkach Intela, ale nie mogłem go znaleźć ... tak czy inaczej, testowanie porównawcze również daje mi taki wynik tutaj.
      2014-03-18 08: 45: 05Z
    5. @ steveha P.S .: Inną możliwą odpowiedzią byłaby int c = data[j]; sum += c & -(c >> 7);, która w ogóle nie wymaga mnożenia.
      2014-03-18 08: 52: 11Z

    W posortowanym przypadku możesz zrobić coś więcej niż polegać na skutecznym przewidywaniu rozgałęzień lub jakiejkolwiek bezgałęziowej sztuczce porównania: całkowicie usunąć gałąź.

    Rzeczywiście, tablica jest podzielona na strefy przyległe z data < 128, a druga z data >= 128. Więc powinieneś znaleźć punkt podziału przy wyszukiwaniu dychotomicznym (przy użyciu Lg(arraySize) = 15 porównań), a następnie wykonaj proste akumulacja od tego momentu.

    Coś takiego (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 zaciemniony

     
    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 posortowanych, jak i nieposortowanych, to: sum= 3137536; (zakładając prawdziwie jednolitą dystrybucję, 16384 próbek o oczekiwanej wartości 191,5) : -)

        
    950
    2019-05-11 11: 31: 12Z
    1. sum= 3137536 - sprytny. To oczywiście nie jest sedno pytania. Pytanie wyraźnie dotyczy wyjaśnienia zaskakujących cech wydajności. Jestem skłonny powiedzieć, że dodanie std::partition zamiast std::sort jest cenne. Chociaż rzeczywiste pytanie rozciąga się na coś więcej niż tylko syntetyczny benchmark.
      2013-07-24 16: 31: 30Z
    2. @ DeadMG: w rzeczywistości nie jest to standardowe wyszukiwanie dychotomiczne dla danego klucza, ale wyszukiwanie indeksu partycjonowania; wymaga pojedynczego porównania dla każdej iteracji. Ale nie polegaj na tym kodzie, nie sprawdziłem tego. Jeśli jesteś zainteresowany gwarantowaną poprawną implementacją, daj mi znać.
      2013-07-24 20: 37: 31Z

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

    Aby zrozumieć prognozę branżową, musisz najpierw zrozumieć Pipeline instrukcji :

    Każda instrukcja jest podzielona na sekwencję kroków, dzięki czemu różne kroki mogą 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 lepiej to zrozumieć, przeczytaj ten przykład na Wikipedii .

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

    1. IF - Pobierz instrukcję z pamięci   
    2. ID - Zdekoduj instrukcję   
    3. EX - Wykonaj instrukcję   
    4. WB - Napisz z powrotem do rejestru CPU

    ogólnie 4-etapowy potok dla 2 instrukcji. 4-etapowy potok ogólnie

    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 następujące zdarzenia:

    Aby wykonać instrukcję B lub instrukcję C, procesor będzie musiał poczekać, aż instrukcja A nie osiągnie etapu EX w potoku, ponieważ decyzja o przejściu do instrukcji B lub C zależy od wyniku instrukcji A. Tak więc potok będzie wyglądał tak.

    kiedy warunek zwraca wartość true: wprowadź opis obrazu tutaj>> </p>

<p><strong> <em> Kiedy warunek zwraca false: </em> </strong>
<img src = predyktora gałęzi .

    W kodzie OP, po raz pierwszy, gdy warunkowy, predyktor rozgałęzienia nie ma żadnych informacji do oparcia predykcji, więc po raz pierwszy losowo wybierze następną instrukcję. Później w pętli for może opierać prognozę na historii. Dla tablicy posortowanej 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 nowe elementy są mniejsze niż 128, a później stają się większe niż 128

    Załóżmy, że predyktor zawsze przyjmie prawdziwą gałąź podczas pierwszego uruchomienia.

    Tak więc w pierwszym przypadku zawsze przyjmie prawdziwą gałąź, ponieważ historycznie wszystkie jej przewidywania są poprawne. W drugim przypadku początkowo będzie przewidywać błędne, ale po kilku iteracjach będzie przewidywać poprawnie. W trzecim przypadku będzie początkowo poprawnie przewidywać, aż elementy będą mniejsze niż 128. Po pewnym czasie zakończy się niepowodzeniem i poprawi się, gdy zobaczy błąd przewidywania gałęzi w historii.

    We wszystkich tych przypadkach liczba błędów będzie zbyt mała iw rezultacie tylko kilka razy będzie musiał 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 początku z poprawną gałęzią przez większość czasu i skutkować większą liczbą cykli procesora w porównaniu z posortowaną tablicą.

        
    774
    2018-04-10 20: 13: 26Z
    1. w jaki sposób są wykonywane dwie instrukcje? czy odbywa się to za pomocą oddzielnych rdzeni procesorów lub czy instrukcja potoku jest zintegrowana w jednym rdzeniu procesora?
      2017-10-11 14: 49: 42Z
    2. @ M.kazemAkhgary To wszystko jest wewnątrz jednego logicznego rdzenia. Jeśli jesteś zainteresowany, jest to ładnie opisane na przykład w Podręczniku programisty Intela
      2017-11-03 07: 45: 12Z

    Oficjalna odpowiedź pochodzi z

    1. Intel - unikanie kosztów oddziału
    2. Intel - Reorganizacja oddziałów i pętli zapobiegać rozpowszechnianiu informacji
    3. Artykuły naukowe - architektura komputerowa przewidywania gałęzi
    4. Książki: J.L. Hennessy, D.A. Patterson: Architektura komputera: podejście ilościowe
    5. Artykuły w publikacjach naukowych: T.Y. Tak, Y.N. Patt zrobił wiele z nich na podstawie przewidywań branżowych.

    Możesz również zobaczyć z tego uroczego diagram , dlaczego predyktor gałęzi jest zdezorientowany.

    678

    2017-01-31 11: 39: 33Z

    W tej samej linii (myślę, że nie została podświetlona żadną odpowiedzią) dobrze jest wspomnieć, że czasami (szczególnie w oprogramowaniu, w którym liczy się wydajność - jak w jądrze Linuksa), można znaleźć pewne stwierdzenia, takie jak:  

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

    lub podobnie:

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

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

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

        
    645
    2016-10-28 10: 28: 11Z

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

    Zmienne boolowskie są naddeterminowane w tym sensie, że wszystkie operatory, które mają zmienne boolowskie, sprawdzają, czy dane wejściowe mają jakąkolwiek inną wartość niż 0 lub 1, ale operatory, które mają Booleany jako dane wyjściowe, nie mogą wygenerować żadnej innej wartości niż 0 lub 1. To sprawia, że ​​operacje ze zmiennymi boolowskimi są mniej wydajne niż to konieczne. Rozważmy przykład:

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

    Zazwyczaj 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ą zająć dużo czasu w przypadku nieprawidłowości. Operacje boolowskie 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 zakłada 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 a i b zostały zainicjowane do poprawnych wartości lub pochodzą od operatorów, które produkują wyjście boolowskie. Zoptymalizowany kod wygląda następująco:

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

    char jest używany zamiast bool, aby umożliwić użycie operatorów bitowych (& i |) zamiast operatorów boolowskich (&& i ||). Operatory bitowe to pojedyncze instrukcje, które wykonują 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ą dać niespójne wyniki, jeśli operandy mają inne wartości niż 0 i 1.

    ~ nie może być używany dla NIE. Zamiast tego możesz uczynić Boolean NIE na zmiennej, o której wiadomo, że jest 0 lub 1 przez XOR 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 wynosi false (&& wiNie oceniamy b, & woli). 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 wynosi true.

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

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

    jest optymalny w większości przypadków (chyba że oczekuje się, że wyrażenie && wygeneruje wiele nieprawidłowości w rozgałęzieniach).

        
    614
    2019-05-30 16: 34: 26Z

    To na pewno! ...

    Przewidywanie gałęzi powoduje, że logika działa wolniej z powodu przełączania w kodzie! To tak, jakbyś jechał prostą ulicą lub ulicą z wieloma zakrętami, na pewno prosta będzie szybsza! ...

    Jeśli tablica jest posortowana, twój warunek jest fałszywy w pierwszym kroku: data[c] >= 128, a następnie staje się prawdziwą wartością dla całej drogi do końca ulicy. W ten sposób szybciej dojdziesz do końca logiki. Z drugiej strony, używając niesortowanej tablicy, potrzebujesz dużo toczenia i przetwarzania, które na pewno spowodują, że twój kod będzie działał wolniej ...

    Spójrz na obraz, który dla Ciebie stworzyłem poniżej. Która ulica zostanie ukończona szybciej?

    289

    2018-05-03 06: 35: 51Z

    To pytanie zostało już wielokrotnie udzielone. Nadal chciałbym zwrócić uwagę grupy na kolejną ciekawą analizę.

    Ostatnio ten przykład (zmodyfikowany bardzo nieznacznie) został również wykorzystany jako sposób na zademonstrowanie, jak 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 posortowanym, jak i nieposortowana skrzynka. Wreszcie, artykuł pokazuje również, jak użyć mało znanej funkcji HAL (Hardware Abstraction Layer), aby określić, jak wiele nieprawidłowości rozgałęzień ma miejsce w nieposortowanym przypadku.

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

        
    266
    2017-01-17 18: 02: 31Z
    1. To jest bardzo interesujący artykuł (właściwie przeczytałem to wszystko), ale jak to odpowiedzieć na pytanie?
      2018-03-16 12: 47: 19Z
    2. @ PeterMortensen Trochę mnie przeraża twoje pytanie. Na przykład tutaj znajduje się jedna odpowiednia linia z tego utworu: When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. Autor próbuje omówić profilowanie w kontekście kodu zamieszczonego tutaj iw trakcie próby wyjaśnienia, dlaczego posortowana sprawa jest o wiele szybsza.
      2018-03-16 15: 37: 16Z

    Jak już wspominali inni, za tą tajemnicą kryje się Predyktor gałęzi .

    Nie próbuję niczego dodawać, ale wyjaśniam pojęcie w inny sposób. Na wiki znajduje się zwięzłe wprowadzenie, które zawiera tekst i diagram. Podoba mi się poniższe wyjaśnienie, które wykorzystuje diagram do intuicyjnego opracowania Predyktora gałęzi.

      

    W architekturze komputera predyktorem gałęzi jest a   układ cyfrowy, który próbuje odgadnąć, w którą stronę oddział (np   struktura if-then-else) pójdzie zanim będzie to znane na pewno. The   Celem predyktora gałęzi jest poprawa przepływu w   potok instrukcji. Predyktory gałęzi odgrywają kluczową rolę   osiągnięcie wysokiej wydajności w wielu nowoczesnych urządzeniach   architektury mikroprocesorowe, takie jak x86.

         

    Dwukierunkowe rozgałęzianie jest zwykle realizowane za pomocą skoku warunkowego   instrukcja. Skok warunkowy może zostać „nie wzięty” i kontynuować   wykonanie z pierwszą gałęzią kodu, która następuje natychmiast   po skoku warunkowym lub może być „wzięty” i wskoczyć na   inne miejsce w pamięci programu, w którym znajduje się druga gałąź kodu   przechowywane. Nie wiadomo na pewno, czy nastąpi skok warunkowy   podjęte lub nieodebrane, dopóki warunek nie zostanie obliczony i   skok warunkowy przeszedł etap wykonania w instrukcji   potok (patrz rys. 1).

     rysunek 1

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

    1. Bez predyktora oddziału.
      

    Bez przewidywania rozgałęzienia procesor musiałby poczekać do   instrukcja skoku warunkowego przeszła etap wykonania przed   następna instrukcja może wprowadzić 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.

     bez predyktora gałęzi

    Potrzeba 9 cykli zegara, aby wykonać 3 instrukcje.

    1. Użyj predyktora gałęzi i nie skacz warunkowo. Załóżmy, że przewidywane nie wykonuje skoku warunkowego.

     wprowadź opis obrazu tutaj>> </a> </p>

<p> Potrzeba 7 cykli zegara, aby wykonać 3 instrukcje. </p>

<ol start =

  6. Użyj predyktora gałęzi i wykonaj skok warunkowy. Załóżmy, że przewidywane nie wykonuje skoku warunkowego.
  7.  wprowadź opis obrazu tutaj>> </a> </p>

<p> Potrzeba 9 cykli zegara, aby wykonać 3 instrukcje. </p>

<blockquote>
  <p> Czas, który marnuje się w przypadku błędnego przewidywania gałęzi, jest równy
  liczba etapów rurociągu od etapu pobierania do
  wykonać etap. Nowoczesne mikroprocesory mają dość długi czas
  rurociągi, tak aby opóźnienie błędnej prognozy wynosiło od 10 do 20 zegara
  cykle. W efekcie tworzenie rurociągu wydłuża czas oczekiwania
  bardziej zaawansowany predyktor gałęzi. </p>
</blockquote>

<p> Jak widzisz, wydaje się, że nie mamy powodu, aby nie używać narzędzia Predyktor gałęzi. </p>

<p> To dość proste demo, które wyjaśnia bardzo podstawową część narzędzia Predyktor gałęzi. Jeśli te gify są denerwujące, prosimy o usunięcie ich z odpowiedzi, a odwiedzający mogą również pobrać demo z <a href= BranchPredictorDemo

        

    183
    2019-06-04 16: 20: 33Z

    Zwiększ przewidywanie rozgałęzień!

    Ważne jest zrozumienie tej nieprawidłowości w branżynie spowalnia programów. Koszt nieudanej prognozy jest taki, jak gdyby nie istniało przewidywanie gałęzi 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
    }
    

    Ilekroć jest instrukcja if-else switch, wyrażenie musi zostać ocenione, aby określić, który blok powinien zostać wykonany. W kodzie zespołu wygenerowanym przez kompilator wstawiane są warunkowe instrukcje gałąź .

    Instrukcja rozgałęzienia może spowodować, że komputer rozpocznie wykonywanie innej sekwencji instrukcji, a tym samym odbiegnie 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 niektórych warunek, który jest oceną wyrażenia w naszym przypadku.

    Powiedziawszy to, kompilator próbuje przewidzieć wynik przed jego faktyczną oceną. Będzie pobierać instrukcje z bloku if i jeśli wyrażenie okaże się prawdziwe, to cudownie! Uzyskaliśmy czas potrzebny na jego ocenę i dokonaliśmy postępu w kodzie; jeśli nie, uruchomimy niewłaściwy kod, potok zostanie opróżniony, a poprawny blok zostanie uruchomiony.

    Wizualizacja:

    Powiedzmy, że musisz wybrać trasę 1 lub trasę 2. Oczekiwanie na partnera do sprawdzenia mapy, zatrzymałeś się na ## i czekałeś, albo możesz po prostu wybrać trasę 1 i jeśli miałeś szczęście (trasa 1 jest prawidłowa trasa), więc świetnie, że nie musisz czekać na partnera, aby sprawdzić mapę (zaoszczędziłaś czas, jaki zajęłoby mu sprawdzenie mapy), w przeciwnym razie po prostu zawrócisz.

    Podczas gdy spłukiwanie rurociągów jest bardzo szybkie, obecnie podejmowanie tego ryzyka jest tego warte. Przewidywanie posortowanych danych lub danych, które zmieniają się powoli, jest zawsze łatwiejsze i lepsze niż przewidywanie szybkich zmian.

     
     O      Route 1  /-------------------------------
    /|\             /
     |  ---------##/
    / \            \
                    \
            Route 2  \--------------------------------
    
        
    172
    2018-03-16 12: 30: 45Z

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

    • Predyktor gałęzi jest jedną ze starożytnych technik zwiększania wydajności, która wciąż znajduje zastosowanie w nowoczesnych architekturach. Podczas gdy proste techniki predykcji zapewniają szybkie wyszukiwanie i efektywność energetyczną, cierpią na wysoki współczynnik nieprawidłowości.

    • Z drugiej strony, złożone prognozy rozgałęzień - oparte na neuronach lub warianty dwupoziomowej predykcji gałęzi - zapewniają lepszą dokładność przewidywania, ale zużywają więcej mocy i złożoności zwiększają się wykładniczo.

    • Oprócz tego, w złożonych technikach prognozowania czas przewidziany na rozgałęzienia jest sam w sobie bardzo wysoki - od 2 do 5 cykli - co jest porównywalne z czasem wykonania rzeczywistych gałęzi.

    • Przewidywanie gałęzi jest w istocie problemem optymalizacji (minimalizacji), w którym nacisk kładzie się na osiągnięcie najniższej możliwej szybkości pomijania, niskiego zużycia energii i niskiej złożoności przy minimalnych zasobach.

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

    Przekaż oddziały warunkowe - na podstawie warunku uruchomienia komputer (licznik programów) zostanie zmieniony tak, aby wskazywał na adres w strumieniu instrukcji.

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

    Oddziały bezwarunkowe - obejmują skoki, wywołania procedur i zwroty, 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 lokalizacji docelowej wskazywanej przez instrukcję skoku, podczas gdy skok warunkowy, który może być zakodowany jako „jmpne” przekierowuje strumień instrukcji tylko wtedy, gdy wynik porównania dwóch wartości w poprzednich instrukcjach „porównaj” pokazuje, że wartości nie są równe. (Schemat segmentowanego adresowania używany przez architekturę x86 dodaje dodatkową złożoność, ponieważ skoki mogą być „bliskie” (w obrębie segmentu) lub „daleko” (poza segmentem). Każdy typ ma inny wpływ na algorytmy predykcji gałęzi.)

    Statyczne /dynamiczne przewidywanie gałęzi : predykcja gałęzi statycznej jest używana przez mikroprocesor przy pierwszym napotkaniu warunkowej gałęzi, a dynamiczne przewidywanie gałęzi jest używane do kolejnych wykonań warunkuostatni kod oddziału.

    Referencje:

    116
    2018-03-16 10: 57: 23Z

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

    Możesz mieć warunek zatrzymania, a nie tylko sprawdzać wartość, w ten sposób zapętlasz tylko odpowiednie dane i ignorujesz resztę.
    Przewidywanie gałęzi zniknie 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];               
     }
    
        
    110
    2019-03-05 09: 58: 40Z
    1. Prawo, ale koszt ustawienia sortowania tablicy to O (N log N), więc wczesne łamanie nie pomaga, jeśli jedynym powodem sortowania tablicy jest w stanie wcześnie się złamać. Jeśli jednak masz inne powody do wstępnego sortowania tablicy, to tak, to jest cenne.
      2018-11-06 12: 28: 29Z
    2. @ LukeHutchison dobra obserwacja; proszę zobaczyć moją odpowiedź poniżej, aby zapoznać się z innym podejściem.
      2019-02-27 11: 47: 22Z
    3. Zależy od tego, ile razy posortujesz dane w porównaniu z tym, ile razy je zapętlisz. Sortowanie w tym przykładzie jest tylko przykładem, nie musi być tuż przed pętlą
      2019-02-27 12: 23: 22Z
    4. Tak, to jest dokładnie to, co zrobiłem w moim pierwszym komentarzu :-) Mówisz: "Przewidywanie gałęzi będzie tylko raz." Ale nie liczysz predykcji rozgałęzienia O (N log N) wewnątrz algorytmu sortowania, który jest faktycznie większy niż błąd prognozowania rozgałęzienia O (N) w nieposortowanym przypadku. Więc trzeba by użyć całych posortowanych danych O (log N) razy, aby się złamać (prawdopodobnie w rzeczywistości bliżej O (10 log N), w zależności od algorytmu sortowania, np. Quicksort, z powodu chybień pamięci podręcznej - mergesort jest bardziej spójny z pamięcią podręczną, więc musisz złamać progi bliżej O (2 log N).)
      2019-02-28 12: 28: 14Z
    5. Jedną znaczącą optymalizacją byłoby jednak zrobienie tylko "pół szybkiego sortowania", sortowanie tylko elementów mniejszych niż docelowa wartość przestawna 127 (zakładając, że wszystko mniej niż lub równy czop jest sortowany po czopie). Po dotarciu do osi przestaw elementy przed osią obrotu. Zostanie to uruchomione w czasie rozruchu O (N), a nie O (N log N), chociaż nadal będzie wiele błędów przewidywania rozgałęzień, prawdopodobnie rzędu O (5 N) w oparciu o liczby, które podałem wcześniej, ponieważ to pół szybkiego sortowania.
      2019-02-28 12: 34: 48Z

    W ARM nie jest potrzebna gałąź, ponieważ każda instrukcja ma 4-bitowe pole warunku, które jest testowane przy zerowym koszcie. Eliminuje to potrzebę krótkich gałęzi i nie byłoby trafienia przewidywania gałęzi. Dlatego posortowana wersja będzie działać wolniej niż nieposortowana wersja na ARM, ze względu na dodatkowy koszt sortowania. Wewnętrzna pętla wyglądałaby następująco:

     
    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
    
        
    106
    2018-05-14 14: 01: 18Z
    1. Czy mówisz, że każda instrukcja może być condi? Zatem wiele instrukcji z przyrostkiem GE może być wykonywanych sekwencyjnie, bez zmiany wartości między R3?
      2018-05-14 14: 04: 03Z
    2. Tak, poprawnie, każda instrukcja może być uzależniona od ARM, przynajmniej w zestawach instrukcji 32 i 64 bitowych. Istnieje poświęcone 4-bitowe pole warunku. Możesz mieć kilka instrukcji w jednym rzędzie z tym samym warunkiem, ale w pewnym momencie, jeśli prawdopodobieństwo, że warunek jest fałszywy, jest bez znaczenia, bardziej efektywne jest dodanie gałęzi.
      2018-05-15 17: 06: 42Z
    3. Inną innowacją w ARM jest dodanie sufiksu instrukcji S, również opcjonalnego w (prawie) wszystkich instrukcjach, które w przypadku jego braku uniemożliwiają zmianę instrukcji stanu przez bity (z wyjątkiem instrukcji CMP, której zadaniem jest ustawianie bitów statusu, więc nie potrzebuje on przyrostka S). Pozwala to uniknąć instrukcji CMP w wielu przypadkach, o ile porównanie jest zerowe lub podobne (np. SUBS R0, R0, # 1 ustawi bit Z (Zero), gdy R0 osiągnie zero). Warunki i przyrostek S powodują zerowy narzut. To całkiem piękny ISA.
      2018-05-15 17: 06: 54Z
    4. Nie dodawanie sufiksu S pozwala mieć kilka instrukcji warunkowych w rzędzie bez obawy, że jeden z nich może zmienić bity stanu, które w przeciwnym razie mogłyby mieć efekt uboczny pomijanie pozostałych instrukcji warunkowych.
      2018-05-15 17: 08: 22Z

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

    Predyktor gałęzi jest układem cyfrowym (w architekturze komputerowej) próbującym przewidzieć, w jaki sposób pójdzie gałąź, poprawiając przepływ w potoku instrukcji. Układ /komputer przewiduje następny krok i wykonuje go.

    Błędne przewidywanie prowadzi do powrotu do poprzedniego kroku i wykonania z inną prognozą. Zakładając, że przewidywanie jest poprawne, kod przejdzie do następnego kroku. Błędne przewidywanie powoduje powtórzenie tego samego kroku, aż do uzyskania prawidłowej prognozy.

    Odpowiedź na twoje pytanie jest bardzo prosta.

    W niesortowanej tablicy komputer wykonuje wiele prognoz, co prowadzi do zwiększonej szansy na błędy. Podczas gdy w posortowanej tablicy komputer wykonuje mniej prognoz, zmniejszając ryzyko błędów. Tworzenie kolejnych prognoz wymaga więcej czasu.

    Posortowana macierz: prosta droga     ____________________________________________________________________________________     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -     TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTMTTTTTTTTTTTTTTTTTT górę

    Unsorted Array: Curved Road

     
    ______   ________
    |     |__|
    

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

     
    ___________________________________________ Straight road
     |_________________________________________|Longer road
    

    Chociaż obie drogi osiągają ten sam cel, prosta droga jest krótsza, a druga jest dłuższa. Jeśli następnie przez pomyłkę wybierzesz drugą, nie ma już odwrotu, więc jeśli wybierzesz dłuższą drogę, stracisz trochę czasu. Jest to podobne do tego, co dzieje się na komputerze i mam nadzieję, że pomogło ci to lepiej zrozumieć.


    Chcę też cytować @Simon_Weaver z komentarzy:

      

    Nie ma mniej przewidywań - powoduje mniej błędnych prognoz. Nadal musi przewidzieć za każdym razem w pętli ...

        
    96
    2019-05-27 12: 47: 18Z
    1. "W prostych słowach" - uważam, że twoje wyjaśnienia są mniej proste niż inne z pociągami i znacznie mniej dokładne niż jakiekolwiek inne odpowiedzi, Nie jestem początkującym. Jestem bardzo ciekawa, dlaczego jest tak wiele głosów, może jeden z przyszłych awanturników może mi powiedzieć?
      2018-07-04 13: 54: 21Z
    2. @ Sinatr to prawdopodobnienaprawdę opierając się na opinii, sam uznałem, że jest wystarczająco dobry, aby go nadać, to nie jest tak dokładne, jak inne przykłady, to jest cały punkt: rozdawanie odpowiedzi (ponieważ wszyscy zgadzamy się, że chodzi tu o przewidywanie oddziałów) bez konieczności czytania czytelników wyjaśnienia techniczne, tak jak inni (bardzo dobrze). I myślę, że zrobił to wystarczająco dobrze.
      2018-07-09 12: 45: 50Z
    3. Nie ma mniej przewidywań - powoduje mniej błędnych prognoz. Nadal musi przewidzieć za każdym razem w pętli.
      2018-07-16 01: 28: 03Z
    4. Och, masz rację, mój zły, dziękuję @Simon_Weaver, poprawię to za jakiś czas, czy może niektóre z twoich poprawek i zatwierdzę to , z góry dzięki ...
      2018-07-16 05: 52: 47Z

    Założenie przez inne odpowiedzi, które trzeba posortować, nie jest poprawne.

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

    Sortowanie tylko sekcji k-elementu kończy wstępne przetwarzanie w czasie liniowym, a nie n.log(n).

     
    #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 nic wspólnego z jakimkolwiek problemem algorytmicznym, takim jak porządek sortowania, i rzeczywiście jest przewidywaniem gałęzi.

        
    17
    2019-02-28 15: 24: 59Z
    1. Naprawdę nie widzę, jak to wszystko dowodzi? Jedyną rzeczą, którą pokazałeś, jest to, że „nie robienie całej pracy sortowania całej tablicy zajmuje mniej czasu niż sortowanie całej tablicy”. Twoje twierdzenie, że to „działa również najszybciej”, jest bardzo zależne od architektury. Zobacz moją odpowiedź na temat tego, jak to działa na ARM. PS możesz przyspieszyć swój kod na architekturach innych niż ARM, umieszczając sumę wewnątrz pętli blokowej 200 elementów, sortując w odwrotnej kolejności, a następnie używając sugestii Yochai Timmera, że ​​złamanie nastąpi po uzyskaniu wartości spoza zakresu. W ten sposób każde 200-elementowe sumowanie bloków może zostać zakończone wcześniej.
      2019-02-28 12: 18: 29Z
    2. @ LukeHutchison Dowód dotyczy OP, a nie dobrze poinformowanego autora takiego jak ty. W OP eliminuje to hipotezę, że sortowanie ma coś wspólnego z szybszym przetwarzaniem (patrz tytuł pytania). „Uruchamia się najszybciej” w sensie algorytmicznym w architekturze ogólnego przeznaczenia - ARM to szczególny przypadek. Sugestia Yochai Timmera to piddly optymalizacja, która nie jest algorytmiczna w sensie big-O. Co więcej, ogólnie rzecz biorąc, ludzie robiliby coś zarówno w prawdziwych, jak i fałszywych przypadkach, więc hack Yochai nie miałby zastosowania i prawdopodobnie coś ważniejszego niż sumowanie.
      2019-02-28 15: 21: 15Z
źródło umieszczone tutaj