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

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

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

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.

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

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.

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

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

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.

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

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.

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.