Jak działają prawdopodobne / mało prawdopodobne makra w jądrze Linuksa i jakie są ich zalety?

348

Przekopałem się przez niektóre części jądra Linuxa i znalazłem takie wywołania:

if (unlikely(fd < 0))
{
    /* Do something */
}

lub

if (likely(!err))
{
    /* Do something */
}

Znalazłem ich definicję:

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

Wiem, że są do optymalizacji, ale jak działają? A o ile można zmniejszyć wydajność / rozmiar po ich użyciu? I czy warto się męczyć (i prawdopodobnie stracić przenośność) przynajmniej w kodzie wąskiego gardła (oczywiście w przestrzeni użytkownika).

stacja końcowa
źródło
7
To naprawdę nie jest specyficzne dla jądra Linuksa ani makr, ale jest to optymalizacja kompilatora. Czy należy to zmienić, aby to odzwierciedlić?
Cody Brocious,
11
Artykuł Co każdy programista powinien wiedzieć o pamięci (s. 57) zawiera szczegółowe wyjaśnienie.
Torsten Marek,
2
patrz takżeBOOST_LIKELY
Ruggero Turra,
4
Powiązane: test porównawczy dotyczący użycia__builtin_expect w innym pytaniu.
YSC
13
Nie ma problemu z przenośnością. Możesz w prosty sposób robić rzeczy takie jak #define likely(x) (x)i #define unlikely(x) (x)na platformach, które nie obsługują tego rodzaju wskazówek.
David Schwartz,

Odpowiedzi:

328

Są one wskazówką dla kompilatora, aby emitował instrukcje, które spowodują, że przewidywanie gałęzi faworyzuje „prawdopodobną” stronę instrukcji skoku. Może to być duża wygrana, jeśli prognoza jest poprawna, oznacza to, że instrukcja skoku jest zasadniczo darmowa i zajmie zero cykli. Z drugiej strony, jeśli prognoza jest błędna, oznacza to, że procesor procesora wymaga opróżnienia i może kosztować kilka cykli. Tak długo, jak prognoza jest poprawna przez większość czasu, będzie to dobre dla wydajności.

Podobnie jak wszystkie takie optymalizacje wydajności, powinieneś to zrobić tylko po obszernym profilowaniu, aby upewnić się, że kod rzeczywiście znajduje się w wąskim gardle, i prawdopodobnie biorąc pod uwagę mikro charakter, że jest uruchamiany w ciasnej pętli. Ogólnie programiści Linuksa są dość doświadczeni, więc wyobrażam sobie, że by to zrobili. Naprawdę nie przejmują się zbytnio przenośnością, ponieważ atakują tylko gcc i mają bardzo bliskie pojęcie o zestawie, który chcą wygenerować.

1800 INFORMACJI
źródło
3
Te makra były najczęściej używane do sprawdzania błędów. Ponieważ błąd pozostawia mniej prawdopodobne niż normalne działanie. Kilka osób dokonuje profilowania lub obliczeń, aby zdecydować o najczęściej używanym liściu ...
gavenkoa
51
Jeśli chodzi o fragment "[...]that it is being run in a tight loop", wiele procesorów ma predyktor gałęzi , dlatego użycie tych makr pomaga tylko przy pierwszym uruchomieniu kodu lub gdy tablica historii zostanie nadpisana przez inną gałąź z tym samym indeksem w tabeli rozgałęzień. W ciasnej pętli i przy założeniu, że gałąź idzie w jedną stronę przez większość czasu, predyktor gałęzi prawdopodobnie szybko zacznie zgadywać prawidłową gałąź. - twój przyjaciel w pedanterii.
Ross Rogers
8
@RossRogers: Tak naprawdę dzieje się tak, że kompilator porządkuje gałęzie, więc częstym przypadkiem nie jest brane. Jest to szybsze, nawet jeśli działa przewidywanie gałęzi. Wykonane gałęzie są problematyczne przy pobieraniu instrukcji i dekodowaniu, nawet jeśli są doskonale przewidziane. Niektóre procesory statycznie przewidują gałęzie, których nie ma w tabeli historii, zwykle zakładając, że nie są brane dla gałęzi forward. Procesory Intel nie działają w ten sposób: nie próbują sprawdzić, czy pozycja tabeli predyktorów jest dla tej gałęzi, po prostu z niej korzystają. Gorąca gałąź i zimna gałąź mogą być aliasami tego samego wpisu ...
Peter Cordes
12
Ta odpowiedź jest w większości nieaktualna, ponieważ głównym twierdzeniem jest to, że pomaga przewidywać odgałęzienia, a jak wskazuje @PeterCordes, w większości nowoczesnych urządzeń nie ma niejawnej ani jawnej prognozy rozgałęzień statycznych. W rzeczywistości podpowiedź jest wykorzystywana przez kompilator do optymalizacji kodu, bez względu na to, czy wymaga to statycznych wskazówek dotyczących gałęzi, czy innego rodzaju optymalizacji. W przypadku większości architektur obecnie liczy się „jakakolwiek inna optymalizacja”, np. Połączenie ciągłych ścieżek, lepsze planowanie gorącej ścieżki, minimalizacja wielkości wolnej ścieżki, wektoryzacja tylko oczekiwanej ścieżki itp.
BeeOnRope
3
@BeeOnRope ze względu na wstępne pobieranie pamięci podręcznej i rozmiar słowa, nadal jest zaleta uruchamiania programu liniowo. Następna lokalizacja w pamięci zostanie już pobrana, a w pamięci podręcznej cel docelowy oddziału może, a może nie. Dzięki 64-bitowemu procesorowi przechwytujesz co najmniej 64 bity na raz. W zależności od przeplotu DRAM, może to być 2x 3x lub więcej bitów, które zostaną przechwycone.
Bryce
88

Dekompilujmy, aby zobaczyć, co robi z nim GCC 4.8

Bez __builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        printf("%d\n", i);
    puts("a");
    return 0;
}

Kompiluj i dekompiluj za pomocą GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Wynik:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

Kolejność instrukcji w pamięci nie uległa zmianie: najpierw printfa potem putsi retqpowrót.

Z __builtin_expect

Teraz zamień na if (i):

if (__builtin_expect(i, 0))

i otrzymujemy:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

printf(Skompilowany __printf_chk) przeniesiono do końca funkcji po putsi powrotu w celu poprawy przewidywania rozgałęzienia, jak wspomniano w innych odpowiedzi.

Jest to w zasadzie to samo co:

int main() {
    int i = !time(NULL);
    if (i)
        goto printf;
puts:
    puts("a");
    return 0;
printf:
    printf("%d\n", i);
    goto puts;
}

Ta optymalizacja nie została wykonana -O0.

Ale powodzenia w pisaniu przykładu, który działa szybciej __builtin_expectniż bez niego, procesory są naprawdę inteligentne . Moje naiwne próby są tutaj .

C ++ 20 [[likely]]i[[unlikely]]

C ++ 20 ustandaryzował te wbudowane C ++: Jak używać prawdopodobnego / nieprawdopodobnego atrybutu C ++ 20 w instrukcji if-else Prawdopodobnie (gra słów!) Zrobi to samo.

Ciro Santilli
źródło
71

Są to makra, które dają kompilatorowi wskazówki, w którą stronę może iść gałąź. Makra rozwijają się do rozszerzeń specyficznych dla GCC, jeśli są dostępne.

GCC wykorzystuje je do optymalizacji pod kątem przewidywania gałęzi. Na przykład, jeśli masz coś takiego:

if (unlikely(x)) {
  dosomething();
}

return x;

Następnie może zrestrukturyzować ten kod, aby był bardziej podobny do:

if (!x) {
  return x;
}

dosomething();
return x;

Zaletą tego jest to, że gdy procesor bierze gałąź po raz pierwszy, występuje znaczny narzut, ponieważ może spekulacyjnie ładować i wykonywać kod dalej. Kiedy stwierdzi, że zajmie gałąź, musi to unieważnić i rozpocząć od celu docelowego gałęzi.

Większość współczesnych procesorów ma teraz jakieś przewidywanie gałęzi, ale to pomaga tylko wtedy, gdy przejrzałeś już gałąź, a gałąź nadal znajduje się w pamięci podręcznej prognoz gałęzi.

Istnieje wiele innych strategii, które kompilator i procesor mogą wykorzystać w tych scenariuszach. Więcej informacji na temat działania predyktorów branżowych można znaleźć na Wikipedii: http://en.wikipedia.org/wiki/Branch_predictor

dvorak
źródło
3
Wpływa to również na ślad icache - utrzymując mało prawdopodobne fragmenty kodu z dala od gorącej ścieżki.
fche
2
Dokładniej, można to zrobić za pomocą gotos bez powtarzania return x: stackoverflow.com/a/31133787/895245
Ciro Santilli 30 冠状 病 六四 事件 法轮功
7

Powodują, że kompilator emituje odpowiednie wskazówki gałęzi, tam gdzie sprzęt je obsługuje. Zwykle oznacza to po prostu pomieszanie kilku bitów w opodzie instrukcji, więc rozmiar kodu się nie zmieni. Procesor zacznie pobierać instrukcje z przewidywanej lokalizacji, opróżni rurociąg i zacznie od nowa, jeśli okaże się, że nie jest to prawidłowe po osiągnięciu gałęzi; w przypadku, gdy podpowiedź jest poprawna, spowoduje to, że gałąź będzie znacznie szybsza - dokładnie o ile szybciej będzie zależeć od sprzętu; a to, jak bardzo wpłynie to na wydajność kodu, będzie zależeć od tego, jaka część wskazania czasu jest poprawna.

Na przykład na procesorze PowerPC niezauważona gałąź może zająć 16 cykli, prawidłowo wskazana 8 i nieprawidłowo wskazana 24. W najbardziej wewnętrznych pętlach dobre podpowiedzi mogą mieć ogromną różnicę.

Przenośność nie jest tak naprawdę problemem - przypuszczalnie definicja znajduje się w nagłówku na platformę; możesz po prostu zdefiniować „prawdopodobne” i „mało prawdopodobne” na niczym dla platform, które nie obsługują statycznych wskazówek dotyczących gałęzi.

księżycowy cień
źródło
3
Dla przypomnienia x86 zajmuje dodatkowe miejsce na podpowiedzi gałęzi. Musisz mieć jednobajtowy prefiks na gałęziach, aby określić odpowiednią wskazówkę. Zgodził się jednak, że podpowiedzi są dobrą rzeczą (TM).
Cody Brocious,
2
Dang CISC CPU i ich instrukcje o zmiennej długości;)
moonshadow
3
Dang CPU RISC - Trzymaj się z dala od moich 15-bajtowych instrukcji;)
Cody Brocious,
7
@CodyBrocious: podpowiedzi do gałęzi zostały wprowadzone w P4, ale zostały porzucone wraz z P4. Wszystkie pozostałe procesory x86 po prostu ignorują te prefiksy (ponieważ prefiksy są zawsze ignorowane w kontekstach, w których są bez znaczenia). Te makra nie powodują, że gcc faktycznie emituje prefiksy gałęzi na x86. Pomagają ci przekonać gcc do ułożenia twojej funkcji za pomocą mniejszej liczby odgałęzień na szybkiej ścieżce.
Peter Cordes
5
long __builtin_expect(long EXP, long C);

Ta konstrukcja mówi kompilatorowi, że wyrażenie EXP najprawdopodobniej będzie miało wartość C. Zwracana wartość to EXP. __builtin_expect jest przeznaczony do użycia w wyrażeniu warunkowym. W prawie wszystkich przypadkach będzie on używany w kontekście wyrażeń boolowskich, w którym to przypadku wygodniej jest zdefiniować dwa makra pomocnicze:

#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)

Te makra mogą być następnie używane jak w

if (likely(a > 1))

Odniesienie: https://www.akkadia.org/drepper/cpumemory.pdf

Ashish Maurya
źródło
1
Jak zapytano w komentarzu do innej odpowiedzi - jaki jest powód podwójnej inwersji w makrach (tj. Dlaczego warto używać __builtin_expect(!!(expr),0)zamiast po prostu __builtin_expect((expr),0)?
Michael Firth,
1
@MichaelFirth „podwójna inwersja” !!jest równoważna rzutowaniu czegoś na bool. Niektórzy lubią pisać w ten sposób.
Ben XO,
2

(komentarz ogólny - inne odpowiedzi obejmują szczegóły)

Nie ma powodu, abyś tracił przenośność, korzystając z nich.

Zawsze masz opcję utworzenia prostego „inline” lub makra z zerowym efektem, który pozwoli ci na kompilację na innych platformach z innymi kompilatorami.

Po prostu nie uzyskasz korzyści z optymalizacji, jeśli korzystasz z innych platform.

Andrew Edgecombe
źródło
1
Nie używasz przenośności - platformy, które ich nie obsługują, po prostu je definiują, aby rozwinąć je do pustych ciągów.
sharptooth 30.09.11
2
Myślę, że wasza dwójka faktycznie się ze sobą zgadza - to tylko mylące sformułowanie. (Wygląda na to, komentarz Andrew mówi „możesz ich używać bez utraty przenośności”, ale ostry myśli, że powiedział „nie używaj ich, ponieważ nie są przenośne” i sprzeciwił się.)
Miral
2

Zgodnie z komentarzem Cody , nie ma to nic wspólnego z Linuksem, ale jest wskazówką dla kompilatora. To, co się stanie, będzie zależeć od architektury i wersji kompilatora.

Ta szczególna funkcja w Linuksie jest nieco niewłaściwie używana w sterownikach. Jak osgx punktów w semantyce gorącej atrybutu , każdy hotlub coldfunkcja wywołana w bloku może automatycznie wskazywać, że warunek jest prawdopodobne, czy nie. Na przykład dump_stack()jest oznaczony, coldwięc jest zbędny,

 if(unlikely(err)) {
     printk("Driver error found. %d\n", err);
     dump_stack();
 }

Przyszłe wersje gccmogą selektywnie wstawiać funkcję na podstawie tych wskazówek. Pojawiły się również sugestie, że tak nie jest boolean, ale wynik jak w najbardziej prawdopodobnym itp. Zasadniczo należy preferować stosowanie alternatywnego mechanizmu, takiego jak cold. Nie ma powodu, aby używać go w dowolnym miejscu poza gorącymi ścieżkami. To, co kompilator zrobi dla jednej architektury, może być zupełnie inne dla innej.

bezgłośny hałas
źródło
2

W wielu wersjach systemu Linux można znaleźć plik compier.h w katalogu / usr / linux /, można go dołączyć do użycia w prosty sposób. I inna opinia, mało prawdopodobne () jest bardziej przydatne niż prawdopodobne (), ponieważ

if ( likely( ... ) ) {
     doSomething();
}

można go również zoptymalizować w wielu kompilatorach.

Nawiasem mówiąc, jeśli chcesz obserwować szczegółowe zachowanie kodu, możesz po prostu wykonać następujące czynności:

gcc -c test.c objdump -d test.o> obj.s

Następnie otwórz obj.s, znajdziesz odpowiedź.

Finaldie
źródło
1

Są one wskazówkami dla kompilatora do generowania prefiksów wskazówek dla gałęzi. W systemach x86 / x64 zajmują jeden bajt, więc możesz uzyskać najwyżej jednobajtowy wzrost dla każdej gałęzi. Jeśli chodzi o wydajność, zależy to całkowicie od aplikacji - w większości przypadków predyktor gałęzi procesora je teraz zignoruje.

Edycja: Zapomniałem o jednym miejscu, w którym naprawdę mogą pomóc. Może to pozwolić kompilatorowi na zmianę kolejności wykresu sterowania w celu zmniejszenia liczby rozgałęzień wykonanych dla „prawdopodobnej” ścieżki. Może to mieć wyraźną poprawę w pętlach, w których sprawdzasz wiele przypadków wyjścia.

Cody Brocious
źródło
10
gcc nigdy nie generuje wskazówek dotyczących gałęzi x86 - przynajmniej wszystkie procesory Intel i tak je zignorują. Spróbuje jednak ograniczyć rozmiar kodu w mało prawdopodobnych regionach, unikając wstawiania i rozwijania pętli.
Alex dziwne
1

Są to funkcje GCC dla programisty, które dają kompilatorowi podpowiedź na temat najbardziej prawdopodobnego warunku rozgałęzienia w danym wyrażeniu. Umożliwia to kompilatorowi zbudowanie instrukcji rozgałęzienia, dzięki czemu najczęstszy przypadek wymaga wykonania najmniejszej liczby instrukcji.

Sposób budowania instrukcji rozgałęzienia zależy od architektury procesora.

dcgibbons
źródło