Pytanie Dlaczego szybciej jest przetwarzać posortowaną tablicę niż nieposortowaną tablicę?


Oto fragment kodu C ++, który wydaje się bardzo osobliwy. Z jakiegoś dziwnego powodu, sortowanie danych w cudowny sposób czyni kod prawie sześć razy szybszym.

#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.
  • Przy posortowanych 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 to w Javie.

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 nieco podobnym, ale mniej ekstremalnym rezultatem.


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

  • Co się dzieje?
  • Dlaczego szybciej jest przetwarzać posortowaną tablicę niż nieposortowaną tablicę?
  • Kod podsumowuje kilka niezależnych terminów, a kolejność nie powinna mieć znaczenia.

21674
2018-06-27 13:51


pochodzenie


Tylko dla nagrania. W systemach Windows / VS2017 / i7-6700K 4GHz nie ma ŻADNEJ różnicy między dwiema wersjami. W obu przypadkach zajmuje to 0,6 s. Jeśli liczba powtórzeń w pętli zewnętrznej zostanie zwiększona 10-krotnie, czas wykonania zwiększy się 10-krotnie w obu przypadkach do 6 s. - mp31415
@ user194715: dowolny kompilator korzystający z cmov lub inną implementację bez branchless (jak auto-wektoryzacja z pcmpgtd) osiągnie wydajność, która nie jest zależna od danych dowolnego procesora. Ale jeśli jest rozgałęziony, będzie zależał od dowolnego procesora z nietypowym wykonaniem spekulacyjnym. (Nawet wysokowydajne, nieobsługiwane procesory używają przewidywania rozgałęzień, aby uniknąć pobierania / dekodowania baniek w pobranych gałęziach, kara za pomyłkę jest mniejsza). - Peter Cordes
Woops ... re: Meltdown and Spectre - KyleMit
@ KyleMit ma to coś wspólnego z obydwoma? Nie czytałem dużo na temat obu - mohitmun
@mohitmun, obie te luki bezpieczeństwa pasują do szerokiej kategorii luk zaklasyfikowanych jako Ataki "wtrysku docelowego gałęzi" - KyleMit


Odpowiedzi:


Jesteś ofiarą prognozowanie gałęzi zawieść.


Co to jest rozgałęzienie?

Zastanów się nad węzłem kolejowym:

Licensed Image Obraz autor: Mecanismo, za pośrednictwem Wikimedia Commons. Używany pod CC-By-SA 3.0 licencja.

Teraz ze względu na argument, przypuśćmy, że jest to z powrotem w 1800 roku - przed długim dystansie lub komunikacji radiowej.

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

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

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

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

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


Rozważmy instrukcję if: Na poziomie procesora jest to instrukcja rozgałęzienia:

image2

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

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

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

  • Jeśli dobrze zgadłeś, kontynuujesz wykonywanie.
  • Jeśli źle się domyślisz, musisz przepłukać rurociąg i wrócić do oddziału. Następnie możesz uruchomić ponownie drugą ścieżkę.

Jeśli zgadniesz za każdym razem, egzekucja nigdy nie będzie musiała się zatrzymać.
Jeśli źle się domyślasz, zbyt częstoSpędzasz dużo czasu na przeciągnięciu, cofnięciu i ponownym uruchomieniu.


To jest prognoza rozgałęzień. Przyznaję, że nie jest to najlepsza analogia, ponieważ pociąg mógłby sygnalizować kierunek flagą. Ale w komputerach procesor nie wie, w którym kierunku odejdzie gałąź do ostatniej chwili.

Jak więc strategicznie zgadnąć, aby zminimalizować liczbę razy, kiedy pociąg musi się cofnąć i zejść na drugą ścieżkę? Patrzysz na przeszłą historię! Jeśli pociąg odjeżdża w 99% czasu, to zgadujesz, że jest lewo. Jeśli będzie się wyświetlać naprzemiennie, to naprzemiennie zgadujesz. Jeśli pójdzie w jedną stronę co 3 razy, zgadniesz, że to samo ...

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

Większość aplikacji ma dobrze ułożone gałęzie. Współczesne predykatory rozgałęzień zazwyczaj osiągają> 90% trafień. Ale w obliczu nieprzewidywalnych gałęzi bez rozpoznawalnych wzorów, prognozy oddziałów są praktycznie bezużyteczne.

Dalsze czytanie: Artykuł "Prognozy rozgałęzień" na Wikipedii.


Jak wynika z powyższego, winowajcą jest to stwierdzenie:

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

Zauważ, że dane są równomiernie rozłożone między 0 a 255. Gdy dane są posortowane, z grubsza pierwsza połowa iteracji nie zostanie wprowadzona w instrukcji if. Następnie wszyscy wprowadzą instrukcję if.

Jest to bardzo przyjazne dla predyktora oddziału, ponieważ gałąź kolejno wielokrotnie podąża w tym samym kierunku. Nawet prosty licznik nasycenia prawidłowo przewiduje 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że, gdy dane są całkowicie losowe, predyktor gałęzi staje się bezużyteczny, ponieważ nie jest w stanie przewidzieć danych losowych. W związku z tym prawdopodobnie wystąpi około 50% niezgodności. (Nie lepsze niż przypadkowe 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 w ruch warunkowy, możesz spróbować niektórych hacków, jeśli chcesz poświęcić czytelność dla wydajności.

Zastąpić:

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

z:

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

Eliminuje to gałąź i zastępuje ją niektórymi operacjami bitowymi.

(Zauważ, że ten hack nie jest dokładnie równoważny oryginalnemu wyrażeniu if, ale w tym przypadku jest ważny dla wszystkich wartości wejściowych data[].)

Benchmarki: Core i7 920 @ 3,5 GHz

C ++ - Visual Studio 2010 - wersja 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 Hackem: Nie ma różnicy pomiędzy posortowanymi i nieposortowanymi danymi.
  • W przypadku C ++, hack jest rzeczywiście odrobinę wolniejszy niż z odgałęzieniem, gdy dane są sortowane.

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


Aktualizacja:

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

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

  • Intel Compiler 11 robi coś cudownego. To zamienia dwie pętle, tym samym podnosząc nieprzewidywalną gałąź do zewnętrznej pętli. Więc nie tylko jest odporny na błędy, jest także dwa razy szybszy niż to, co VC ++ i GCC może wygenerować! Innymi słowy, ICC wykorzystało pętlę testową, aby pokonać test porównawczy ...

  • Jeśli dasz kompilatorowi Intel kod bezlistny, to po prostu wyprostuje go wektorowo ... i jest równie szybki jak z odgałęzieniem (z wymianą pętli).

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


28593
2018-06-27 13:56



@Mysticial Aby uniknąć zmiany hack, możesz napisać coś takiego int t=-((data[c]>=128)) aby wygenerować maskę. To też powinno być szybsze. Byłoby interesujące dowiedzieć się, czy kompilator jest wystarczająco inteligentny, aby wstawić warunkowy ruch, czy nie. - Mackie Messer
@phonetagger Zobacz następujące pytanie uzupełniające: stackoverflow.com/questions/11276291/... Kompilator Intela prawie całkowicie pozbył się zewnętrznej pętli. - Mysticial
@Novelocrat Tylko połowa z tego jest poprawna. Przesunięcie 1 do bitu znaku, gdy wynosi zero, to rzeczywiście UB. Dzieje się tak dlatego, że jest to sygnatura przekroczenia liczby całkowitej. Ale przesunięcie 1 na bit znaku to IB. Przesunięcie ujemne liczby całkowitej ze znakiem ujemnym 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. - Mysticial
@Mysticial Dzięki za link. Wygląda obiecująco. Pójdę chociaż. Ostatnia prośba. Przepraszam, ale proszę, nie przejmuj się, możesz mi powiedzieć, jak możesz to zrobić int t = (data[c] - 128) >> 31; sum += ~t & data[c];zastąpić oryginalny warunek if powyżej? - Unheilig
Gramatyka we mnie chce, bym pomyślał, że to powinno brzmieć: "... ofiara prognozy rozgałęzień zawodziure"raczej niż" ... ofiara prognozy rozgałęzień zawodzi ". - jdero


Prognozowanie gałęzi.

Z posortowaną tablicą, warunek data[c] >= 128 jest pierwszy false aby uzyskać smugę wartości, staje się true dla wszystkich późniejszych wartości. Łatwo to przewidzieć. W przypadku nieposortowanej tablicy płacisz za koszty rozgałęzienia.


3640
2018-06-27 13:54



Czy przewidywanie rozgałęzień działa lepiej na posortowanych tablicach vs. tablicach o różnych wzorach? Na przykład dla tablicy -> {10, 5, 20, 10, 40, 20, ...} następnym elementem w tablicy z wzorca jest 80. Czy ten rodzaj tablicy zostanie przyspieszony przez przewidywanie rozgałęzień w który następny element ma tutaj 80, jeśli wzór jest śledzony? Czy zwykle pomaga tylko w posortowanych tablicach? - Adam Freeman
Więc zasadniczo wszystko, czego konwencjonalnie nauczyłem się o big-O, jest poza zasięgiem? Lepiej ponieść koszty sortowania niż koszty rozgałęzienia? - Agrim Pathak
@AgrimPathak To zależy. Dla 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. Gdzie próg rentowności może być trudny do przewidzenia. Również, porównaj to, lokalizacja jest ważna. Big-O jest ważny, ale nie jest jedynym kryterium wydajności. - Daniel Fischer
Kiedy ma miejsce rozgałęzienie prognozy? Kiedy język będzie wiedział, że tablica jest sortowana? Zastanawiam się nad sytuacją macierzy, która wygląda jak: [1,2,3,4,5, ... 998,999,1 000, 3, 10001, 10002]? Czy to utrudni 3 wydłużenie czasu pracy? Czy będzie to tak długo jak niesortowana tablica? - Filip Bartuzi
@FilipBartuzi Branch przewidywanie odbywa się w procesorze, poniżej poziomu języka (ale język może oferować sposoby, aby powiedzieć kompilatorowi, co jest prawdopodobne, więc kompilator może emitować kod dostosowany do tego). W twoim przykładzie, kolejność 3 spowoduje błędność rozgałęzień (dla odpowiednich warunków, gdzie 3 daje inny wynik niż 1000), a zatem przetwarzanie tej macierzy zajmie prawdopodobnie kilka lub kilkanaście nanosekund dłużej niż posortowana tablica byłaby, prawie nigdy nie zauważalna. Ile czasu kosztuje wysoki odsetek błędów, jedna nieprawidłowość na 1000 to niewiele. - Daniel Fischer


Powodem, dla którego wydajność poprawia się drastycznie, gdy dane są posortowane, jest to, że kara przewidująca rozgałęzienie zostanie usunięta, co zostało wyjaśnione Mysticalodpowiedź.

Teraz, jeśli spojrzymy na kod

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

możemy znaleźć, że znaczenie tego szczególnego if... else... gałąź to dodać coś, gdy warunek jest spełniony. Ten rodzaj gałęzi można łatwo przekształcić w ruch warunkowy instrukcja, która zostanie skompilowana w warunkową instrukcję ruchu: cmovl, w x86 system. Oddział, a tym samym potencjalna kara za rozgałęzienie, zostaje usunięty.

W Cw ten sposób C++, instrukcja, która kompiluje się bezpośrednio (bez żadnej optymalizacji) w warunkowej instrukcji ruchu w x86, jest operatorem trójskładnikowym ... ? ... : .... Tak więc przepisujemy powyższe stwierdzenie na równoważny:

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

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

Na Intel Core i7-2600K @ 3,4 GHz i Visual Studio 2010 w trybie wydania, 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 świetne przyspieszenie, gdy wynik odgałęzienia jest nieprzewidywalny, ale cierpimy trochę, gdy jest przewidywalny. W rzeczywistości przy użyciu warunkowego ruchu wydajność jest taka sama, niezależnie od wzorca danych.

Teraz przyjrzyjmy się bliżej, badając x86 montaż, który generują. Dla uproszczenia używamy dwóch funkcji max1 i max2.

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

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

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

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

Na maszynie x86-64, GCC -S generuje poniższy zespół.

: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 max2 nie obejmuje skoków oddziałów, jmp, który miałby znaczną karę wykonania, jeśli przewidywany wynik nie jest właściwy.

Dlaczego więc ruch warunkowy działa lepiej?

W typowym x86 procesor, 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ą. To się nazywa pipelining.

W przypadku oddziału następująca instrukcja jest określona przez poprzednią, więc nie możemy wykonywać potoków. Musimy albo czekać, albo przewidzieć.

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

Książka Systemy komputerowe: Perspektywa programisty, druga edycja wyjaśnia to szczegółowo. Możesz sprawdzić sekcję 3.6.6 dla Instrukcje warunkowego przeniesienia, cały rozdział 4 dla Architektura procesoraoraz sekcja 5.11.2 w sprawie szczególnego traktowania Prognozy rozgałęzień i kary za popełnianie błędów.

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 w wydajności pomiędzy odgałęzieniem i warunkowym ruchem, gdy jest nieprzewidywalna, może pomóc nam w napisaniu kodu z lepszą wydajnością, gdy scenariusz stanie się tak skomplikowany, że kompilator nie będzie mógł zoptymalizować ich automatycznie.


2961
2018-06-28 02:14



Nie ma domyślnego poziomu optymalizacji, chyba że dodasz -O do linii poleceń GCC. (I nie możesz mieć najgorszego angielskiego niż mój;) - Yann Droneaud
Trudno mi uwierzyć, że kompilator może zoptymalizować operatora trójskładnikowego lepiej niż równoważne instrukcje if. Pokazałeś, że GCC optymalizuje operatora trójskładnikowego do warunkowego ruchu; ty nie mam pokazał, że nie robi dokładnie tego samego dla instrukcji if. W rzeczywistości, zgodnie z Mystical powyżej, GCC robi zoptymalizuj instrukcję if do warunkowego ruchu, co spowodowałoby, że ta odpowiedź byłaby całkowicie niepoprawna. - BlueRaja - Danny Pflughoeft
@WiSaGaN Kod nic nie demonstruje, ponieważ twoje dwa kawałki kodu kompilują się do tego samego kodu maszynowego. Bardzo ważne jest, aby ludzie nie wpadli na pomysł, że jakaś wypowiedź w twoim przykładzie różni się od miejscary w twoim przykładzie. To prawda, że ​​posiadasz podobieństwo w swoim ostatnim akapicie, ale to nie usuwa faktu, że reszta przykładu jest szkodliwa. - Justin L.
@WiSaGaN Mój downvote z pewnością przerodzi się w przegraną, jeśli zmienisz swoją odpowiedź, aby usunąć wprowadzające w błąd -O0 przykład i pokazać różnicę w zoptymalizowany asm na twoich dwóch testach. - Justin L.
@UpAndAdam W momencie testu VS2010 nie może zoptymalizować oryginalnego odgałęzienia do warunkowego przeniesienia, nawet jeśli określono wysoki poziom optymalizacji, podczas gdy gcc może. - WiSaGaN


Jeśli jesteś ciekawy, jakie jeszcze optymalizacje można wykonać dla 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 zamianie pętli możemy bezpiecznie zmienić tę pętlę na:

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

Wtedy możesz zobaczyć, że if warunkowe jest stałe w trakcie wykonywania i pętli, dzięki czemu można podnieść if na zewnątrz:

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

Następnie widzisz, że wewnętrzna pętla może zostać zwinięta do jednego pojedynczego wyrażenia, zakładając, że pozwala na to model zmiennoprzecinkowy (na przykład: / fp: fast)

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

Ta jest 100 000 razy szybsza niż wcześniej


2026
2017-07-03 02:25



Jeśli chcesz oszukać, równie dobrze możesz wykonać mnożenie poza pętlą i zrobić sumę * = 100000 po pętli. - Jyaif
@Michael - Wierzę, że ten przykład jest faktycznie przykładem inwentaryzacja pętlowa (LIH) optymalizacja, a NIE zamiana pętli. W tym przypadku cała wewnętrzna pętla jest niezależna od zewnętrznej pętli i dlatego może być wyciągnięta z zewnętrznej pętli, po czym wynik jest po prostu pomnożony przez sumę ponad i jednej jednostki = 1e5. Nie ma to żadnego wpływu na końcowy wynik, ale chciałem po prostu ustawić rekord, ponieważ jest to tak często odwiedzana strona. - Yair Altman
Chociaż nie w prostym duchu zamiany pętli, wewnętrzny if w tym momencie można przekształcić w: sum += (data[j] >= 128) ? data[j] * 100000 : 0; do którego kompilator może być zdolny cmovge lub odpowiednik. - Alex North-Keys
Zewnętrzna pętla ma sprawić, by czas zajęty przez wewnętrzną pętlę był wystarczająco duży, aby profilować. Dlaczego miałbyś zamieniać pętlę? Na końcu ta pętla i tak zostanie usunięta. - saurabheights
@saurabheights: Złe pytanie: dlaczego kompilator NIE miał zamiany pętli. Microbenchmarks jest trudne;) - Matthieu M.


Bez wątpienia niektórzy z nas byliby zainteresowani sposobami identyfikacji kodu, który jest problematyczny dla predyktora gałęziowego procesora. Narzędzie Valgrind cachegrind ma symulator predykcji gałęzi, włączony przy użyciu --branch-sim=yes flaga. Uruchamia go na przykładach w tym pytaniu, z liczbą pętli zewnętrznych zmniejszonych do 10000 i skompilowanych przy pomocy 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%   )

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

Wiercenie w dół na linii produkowanej 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];
           .      .  .   .          }
           .      .  .   .      }

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

Pozwala to łatwo zidentyfikować problematyczną linię - w niesortowanej wersji if (data[c] >= 128) linia powoduje 164 050,007 nieprzewidzianych gałęzi warunkowych (Bcm) pod modelem predyktora gałęzi cachegrind, podczas gdy powoduje tylko 10 006 w posortowanej wersji.


Alternatywnie w systemie Linux można użyć podsystemu liczników wydajności, aby wykonać to samo zadanie, ale z wydajnością natywną za pomocą 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

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 również tworzyć adnotacje kodu źródłowego przy demassemble.

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

Widzieć samouczek dotyczący wydajności po więcej szczegółów.


1690
2017-10-12 05:53



To jest przerażające, na liście nieposortowanej powinno być 50% szansy na trafienie. Jakoś prognozy oddziału ma tylko 25% wskaźnika miss, jak może on lepiej niż 50% miss? - TallBrianL
@ tall.b.lo: 25% wszystkich gałęzi - są dwa gałęzie w pętli, jeden dla data[c] >= 128 (który ma 50% wskaźnika miss, jak sugerujesz) i jeden dla warunku pętli c < arraySize który ma współczynnik utraty 0%. - caf


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

Popularnym sposobem na wyeliminowanie przewidywania rozgałęzień, które według mnie działa szczególnie dobrze w zarządzanych językach, jest wyszukiwanie w tabeli zamiast używania oddziału (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 zostanie zbuforowany w procesorze
  2. Prowadzisz rzeczy w dość ciasnej pętli i / lub procesor może wstępnie załadować dane

Tło i dlaczego

Pfew, więc co to do cholery ma znaczyć?

Z perspektywy procesora Twoja pamięć jest wolna. Aby zrekompensować różnicę w prędkości, wbudowują one kilka pamięci podręcznych procesora (pamięć podręczna L1 / L2), które to kompensują. Wyobraź sobie, że wykonujesz swoje ładne obliczenia i odkryjesz, że potrzebujesz kawałka pamięci. Procesor otrzyma operację "ładowania" i załaduje ją do pamięci podręcznej - a następnie za pomocą pamięci podręcznej wykona pozostałe obliczenia. Ponieważ pamięć jest stosunkowo powolna, to "obciążenie" spowolni twój program.

Podobnie jak w przypadku przewidywania gałęzi, został on zoptymalizowany w procesorach Pentium: procesor przewiduje, że musi załadować dane i próbuje załadować je do pamięci podręcznej, zanim operacja rzeczywiście dotrze do pamięci podręcznej. Jak już widzieliśmy, prognozy rozgałęzień czasami idą okropnie źle - w najgorszym przypadku trzeba wrócić i faktycznie poczekać na załadowanie pamięci, co zajmie na zawsze (innymi słowy: niepoprawne prognozowanie gałęzi jest złe, obciążenie pamięci po niepowodzeniu 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 swojej szybkiej pamięci podręcznej i wszystko będzie dobrze.

Pierwszą rzeczą, którą musimy wiedzieć, jest to, co jest mały? O ile mniejsza jest ogólnie lepsza, zasadą jest trzymanie się tabel wyszukiwania o rozmiarze <= 4096 bajtów. Jako górny limit: jeśli Twoja tablica wyszukiwania jest większa niż 64K, warto ją ponownie rozważyć.

Konstruowanie stołu

Zrozumieliśmy, że możemy stworzyć mały stolik. Następną rzeczą do zrobienia jest uzyskanie funkcji wyszukiwania w miejscu. Funkcje wyszukiwania są zwykle małymi funkcjami, które używają kilku podstawowych operacji na liczbach całkowitych (i, lub, xor, shift, add, remove, a może multiply). Chcesz, aby twoje dane wejściowe zostały przetłumaczone przez funkcję wyszukiwania na jakiś "unikalny klucz" w twoim stole, który po prostu daje ci odpowiedź na całą pracę, jaką chcesz wykonać.

W tym przypadku:> = 128 oznacza, że ​​możemy zachować wartość, <128 oznacza, że ​​się go pozbędziemy. Najłatwiej to zrobić, używając "ORAZ": jeśli zachowamy to, my I to z 7FFFFFFF; jeśli chcemy się go pozbyć, my I to z 0. Zauważmy również, że 128 to potęga 2 - możemy więc zrobić tablicę 32768/128 liczb całkowitych i wypełnić ją jednym zerem i wieloma 7FFFFFFFF.

Zarządzane języki

Można się zastanawiać, dlaczego to działa dobrze w zarządzanych językach. Mimo wszystko, zarządzane języki sprawdzają granice tablic z odgałęzieniem, aby upewnić się, że nie zepsujesz ...

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

Trochę pracowało nad wyeliminowaniem tej gałęzi dla zarządzanych języków. 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 JIT firmy Microsoft (ale oczekuję, że Java robi podobne rzeczy) zauważy to i całkowicie usunie test. WOW - oznacza to brak rozgałęzienia. Podobnie będzie z innymi oczywistymi przypadkami.

Jeśli masz kłopoty z wyszukiwaniem w zarządzanych językach - kluczem jest dodanie & 0x[something]FFFdo funkcji wyszukiwania, aby sprawdzić granice przewidywalne - i obserwuj, jak działa szybciej.

Wynik tego przypadku

// 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.Next(256);

//To keep the spirit of the code in-tact 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();

1160
2018-04-24 06:26



Chcesz ominąć prognozę branży, dlaczego? To jest optymalizacja. - Dustin Oprea
Ponieważ żadna gałąź nie jest lepsza niż oddział :-) W wielu sytuacjach jest to po prostu o wiele szybsze ... Jeśli optymalizujesz, zdecydowanie warto spróbować. Używają go również trochę w np. graphics.stanford.edu/~seander/bithacks.html - atlaste
Ogólnie tabele wyszukiwania mogą być szybkie, ale czy przeprowadziłeś testy dla tego konkretnego warunku? W twoim kodzie nadal będzie istniała gałąź, dopiero teraz zostanie przeniesiona do części generującej tabelę wyszukiwania. Nadal nie osiągniesz doskonałości - Zain Rizvi
@ Zain, jeśli naprawdę chcesz wiedzieć ... Tak: 15 sekund w oddziale i 10 w mojej wersji. Bez względu na to, jest to przydatna technika, aby wiedzieć, czy tak. - atlaste
Dlaczego nie sum += lookup[data[j]] gdzie lookup jest tablicą zawierającą 256 wpisów, z których pierwsze to zero, a ostatnie są równe indeksowi? - Kris Vandermotten


Ponieważ dane są rozdzielane między 0 a 255, gdy tablica jest sortowana, pierwsza połowa iteracji nie zostanie wprowadzona if-zacisku ( if oświadczenie jest udostępniane poniżej).

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

Pytanie brzmi: co sprawia, że ​​powyższe stwierdzenie nie jest wykonywane w niektórych przypadkach, jak w przypadku posortowanych danych? Nadchodzi "predykator gałęzi". Predykator gałęzi to obwód cyfrowy, który próbuje odgadnąć, w jaki sposób gałąź (np if-then-else struktura), zanim to zostanie na pewno poznane. Celem predyktora gałęzi jest poprawienie przepływu w potoku instrukcji. Prognozy rozgałęzień odgrywają kluczową rolę w osiąganiu wysokiej wydajności!

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

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

Zmierzmy wydajność tej pętli przy 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"Wzorzec true-false może spowodować if-wymagają do sześciu razy wolniej niż "dobry" wzór! Oczywiście, który wzór jest dobry, a który zły, zależy od dokładnych instrukcji generowanych przez kompilator i konkretny procesor.

Nie ma więc wątpliwości co do wpływu prognozy rozgałęzień na wydajność!


1035
2018-02-15 07:24



Nie pokazuje się taktów "losowego" wzorca TF. - Mooing Duck
@MooingDuck Bo to nie ma znaczenia - ta wartość może być dowolna, ale nadal będzie w granicach tych progów. Dlaczego pokazywać losową wartość, gdy już znasz granice? Chociaż zgadzam się, że można pokazać jeden ze względu na kompletność i "tylko dla do cholery". - cst1992
@ cst1992: W tej chwili jego najwolniejszy timing to TTFFTTFFTTFF, który, jak się wydaje, mojemu ludzkiemu oku, jest całkiem przewidywalny. Losowe jest z natury nieprzewidywalne, więc jest całkowicie możliwe, że będzie wolniejsze, a więc poza przedstawionymi tutaj granicami. OTOH, może się zdarzyć, że TTFFTTFF doskonale trafi w patologiczną sprawę. Nie mogę powiedzieć, ponieważ nie pokazywał czasu losowego. - Mooing Duck
@MooingDuck Dla ludzkiego oka "TTFFTTFFTTFF" jest przewidywalną sekwencją, ale to, o czym tu mówimy, to zachowanie predyktora gałęzi wbudowanego w procesor. Predykator gałęzi nie jest rozpoznawaniem wzorca poziomu AI; to jest bardzo proste. Kiedy po prostu zmieniasz gałęzie, nie przewidujesz 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ąc razy. Oddział na końcu pętli wraca do początku pętli 999 razy, a po raz tysięczny robi coś innego. Bardzo prosty predyktor gałęzi działa dobrze, zwykle. - steveha
@steveha: Myślę, że przyjmujesz założenia dotyczące działania prognostycznego odgałęzienia procesora i nie zgadzam się z tą metodologią. Nie wiem, jak zaawansowany jest ten predykktor oddziału, ale wydaje mi się, że jest o wiele bardziej zaawansowany niż ty. Prawdopodobnie masz rację, ale pomiary na pewno będą dobre. - Mooing Duck


Jednym ze sposobów uniknięcia błędów przewidywania rozgałęzień 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 przedziale [0, 255] i zależy nam tylko na wartościach = = 128. Oznacza to, że możemy łatwo wyodrębnić pojedynczy bit, który powie nam, czy chcemy wartości, czy nie: poprzez zmianę dane na prawo 7 bitów, pozostawiamy 0 lub 1 bit, a my chcemy tylko dodać wartość, gdy mamy 1 bit. Nazwijmy ten bit "bitem decyzji".

Używając wartości 0/1 bitu decyzyjnego jako indeksu do tablicy, możemy stworzyć kod, który będzie równie szybki, czy dane są posortowane, czy nie. Nasz kod zawsze doda wartość, ale gdy bit decyzyjny ma wartość 0, dodamy wartość tam, gdzie nas nie interesuje. 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 traci połowę wartości dodanej, ale nigdy nie ma niepowodzenia przewidywania rozgałęzienia. Jest niesamowicie szybszy w przypadku danych losowych niż wersja z rzeczywistą instrukcją if.

Ale w moich testach tabela bezpośredniego wyszukiwania była nieco szybsza niż ta, prawdopodobnie dlatego, że indeksowanie do tabeli odnośników było nieco szybsze niż zmiana bitów. Pokazuje to, w jaki sposób mój kod ustawia i używa tabeli odnośników (niewyobrażalnie nazwany lut dla "tabeli LookUp" w kodzie). Oto kod C ++:

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

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

W tym przypadku tabela odnośników miała tylko 256 bajtów, więc dobrze pasuje do pamięci podręcznej i wszystko było szybkie. Ta technika nie działałaby dobrze, gdyby dane były wartościami 24-bitowymi i chcieliśmy tylko połowę z nich ... tabela odnośników 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 zindeksuj tabelę odnośników. W przypadku 24-bitowej wartości, którą chcemy uzyskać tylko w górnej połowie, możemy potencjalnie przesunąć dane o 12 bitów i pozostawić 12-bitową wartość dla indeksu tabeli. 12-bitowy indeks tabeli oznacza tabelę o wartości 4096, co może być praktyczne.

EDYCJA: Jedna rzecz, o której zapomniałem wstawić.

Technika indeksowania w tablicy, zamiast korzystania z if instrukcja, może być używana do decydowania, 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ł długą tablicę wskaźników i użył techniki "bitów decyzyjnych", aby zdecydować, który z nich zastosować. Na przykład zamiast:

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

ta biblioteka może zrobić coś takiego:

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

Oto link do tego kodu: Czerwone Czarne Drzewa, Eternally Confuzzled


963
2017-07-22 08:29



Możesz też po prostu użyć bit bezpośrednio i pomnożyć (data[c]>>7 - który jest tu również omawiany); Celowo opuściłem to rozwiązanie, ale oczywiście masz rację. Tylko mała uwaga: Regułą dla tabel odnośników jest to, że jeśli mieści się w 4KB (z powodu buforowania), będzie działać - najlepiej uczynić tabelę tak małą, jak to tylko możliwe. Dla języków zarządzanych popchnęłbym to do 64 KB, dla języków niskopoziomowych, takich jak C ++ i C, prawdopodobnie ponownie rozważyłbym (to tylko moje doświadczenie). Od typeof(int) = 4, Próbowałbym trzymać się maksymalnie 10 bitów. - atlaste
Myślę, że indeksowanie z wartością 0/1 będzie prawdopodobnie szybsze niż liczba całkowita, ale myślę, że jeśli wydajność jest naprawdę krytyczna, powinieneś ją profilować. Zgadzam się, że małe tabele przeglądowe są niezbędne, aby uniknąć presji na cache, ale wyraźnie, jeśli masz większą pamięć podręczną, możesz wydostać się z większej tabeli odnośników, więc 4KB jest bardziej regułą niż twardą regułą. Myślę, że miałeś na myśli sizeof(int) == 4? Tak będzie w przypadku wersji 32-bitowej. Mój dwuletni telefon komórkowy ma pamięć podręczną LK 32KB, więc nawet tabela wyszukiwania 4K może działać, zwłaszcza jeśli wartości wyszukiwania były bajtami zamiast int. - steveha
Prawdopodobnie brakuje mi czegoś, ale w twoim j jest równa 0 lub 1, dlaczego nie pomnożysz swojej wartości przez j przed dodaniem, zamiast korzystania z indeksowania tablicowego (być może należy pomnożyć przez 1-j zamiast j) - Richard Tingle
@steveha Mnożenie powinno być szybsze, próbowałem tego szukać w książkach Intela, ale nie mogłem go znaleźć ... tak czy inaczej, benchmarking daje mi ten wynik tutaj. - atlaste
@steveha P.S .: Inna możliwa odpowiedź byłaby int c = data[j]; sum += c & -(c >> 7); który nie wymaga żadnych multiplikacji. - atlaste