Jak działa prawdopodobne / nieprawdopodobne makra w jądrze Linuksa i jakie są z nich korzyści?

Są to makra, które podpowiadają kompilatorowi, w którą stronę może pójść gałąź. Makra rozwijają się do konkretnych rozszerzeń GCC, jeśli są dostępne.

GCC wykorzystuje je do optymalizacji dla przewidywania gałęzi. Na przykład, jeśli masz coś takiego jak następujące

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

return x;

Wtedy można zrestrukturyzować ten kod, aby był bardziej podobny do:

if (!x) {
  return x;
}

dosomething();
return x;

Zaletą tego jest to, że gdy procesor pobiera gałąź za pierwszym razem, jest znaczny narzut, ponieważ mógł spekulatywnie ładować i wykonywać kod dalej. Gdy stwierdzi, że weźmie gałąź, musi ją unieważnić i zacząć od gałęzi docelowej.

Większość nowoczesnych procesorów ma teraz pewien rodzaj przewidywania gałęzi, ale to pomaga tylko wtedy, gdy już przechodziłeś przez gałąź wcześniej, a gałąź jest nadal w buforze przewidywania gałęzi.

Istnieje wiele innych strategii, które kompilator i procesor mogą wykorzystać w tych scenariuszach. Możesz więcej szczegółów na temat tego, jak branch predictors znajduje się w Wikipedii: http://en.wikipedia.org/wiki/Branch_predictor

Zdekompilujmy, 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;
}

Skompilować i dekompilować z GCC 4.8.2 x86_64 Linux:

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

Wyjście:

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 została niezmieniona: najpierw printf, a następnie puts i retq return.

Z __builtin_expect

Zastąp if (i) przez:

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 do __printf_chk) został przeniesiony do sam koniec funkcji, po puts i powrót do poprawy przewidywania gałęzi, jak wspomniano w innych odpowiedziach.

Więc jest to w zasadzie to samo co:

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 z -O0.

Ale powodzenia w pisaniu przykładu, który działa szybciej z __builtin_expect niż bez, procesory są naprawdę mądre w tamtych czasach . Moje naiwne próby są tutaj .

Powodują one, że kompilator emituje odpowiednie podpowiedzi gałęzi, gdzie sprzęt je obsługuje. Zwykle oznacza to tylko przesuwanie kilku bitów kodu instrukcji, więc rozmiar kodu nie ulegnie zmianie. Procesor zacznie pobierać instrukcje z przewidywanej lokalizacji, a następnie przepuści rurociąg i zacznie od nowa, jeśli okaże się to błędne po osiągnięciu gałęzi; w przypadku, gdy wskazówka jest poprawna, spowoduje to, że gałąź będzie znacznie szybsza - dokładnie ile szybciej będzie zależeć od tego, czy sprzętu; a to, jak bardzo wpłynie to na wydajność kodu, będzie zależeć od tego, jaka część czasu podpowiedzi jest poprawna.

Na przykład, na procesorze PowerPC niezakłócona gałąź może trwać 16 cykli, poprawnie wskazana 8 i niepoprawnie wskazana 24. W najskrytszych pętlach dobre Podpowiedzi mogą mieć ogromne znaczenie.

Przenośność nie jest problemem-prawdopodobnie definicja jest w nagłówku dla poszczególnych platform; można po prostu zdefiniować "prawdopodobne " i" mało prawdopodobne " do niczego dla platformy, które nie obsługują statycznych podpowiedzi do gałęzi.

long __builtin_expect(long EXP, long C);

Ten konstrukt mówi kompilatorowi, że wyrażenie EXP najprawdopodobniej będzie miał wartość C. zwracaną wartością jest EXP. _ _ _ _ expect {[5] } jest przeznaczony do użycia w warunkowym ekspresja. W prawie wszystkich przypadkach będzie on stosowany w kontekstu wyrażeń boolowskich. w takim przypadku jest to znacznie 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 tak jak w

if (likely(a > 1))

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

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

Nie ma powodu, aby tracić przenośność, używając ich.

Zawsze masz możliwość stworzenia prostego efektu zerowego "inline" lub makra, które pozwoli Ci kompilować na innych platformach z innymi kompilatorami.

Po prostu nie dostaniesz korzyści z optymalizacji, jeśli jesteś na innych platformach.

Zgodnie z komentarzem Cody , nie ma to nic wspólnego z Linuksem, ale jest podpowiedzią dla kompilatora. To, co się stanie, zależy od architektury i wersji kompilatora.

Ta szczególna Funkcja w Linuksie jest nieco niewłaściwie używana w sterownikach. Jak osgx wskazuje w semantyce hot atrybutu, każda hot lub cold funkcja wywołana w bloku może automatycznie wskazywać, że warunek jest prawdopodobny lub nie. Na przykład, dump_stack() jest oznaczone cold więc jest to redundant,

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

Przyszłe wersje gcc mogą selektywnie wbudować funkcję w oparciu o te wskazówki. Pojawiły się również sugestie, że nie jest to boolean, ale wynik jak w najprawdopodobniej itp. Ogólnie rzecz biorąc, powinno być preferowane użycie jakiegoś alternatywnego mechanizmu, takiego jak cold. Nie ma powodu, aby używać go w dowolnym miejscu, ale gorące ścieżki. To, co kompilator zrobi na jednej architekturze, może być zupełnie inne na innej.

W wielu wydaniach Linuksa można znaleźć kompilator.h W /usr / linux/, możesz go po prostu dołączyć do użytku. I jeszcze jedna opinia, raczej mało prawdopodobne () jest bardziej użyteczne niż prawdopodobne (), ponieważ

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

Może być również zoptymalizowany w wielu kompilatorach.

A przy okazji, jeśli chcesz obserwować zachowanie szczegółów kodu, możesz to zrobić po prostu w następujący sposób:

Test Gcc-C.c test objdump-D.o > obj.s

Następnie otwórz obj.s, Możesz znaleźć odpowiedź.

Są podpowiedziami dla kompilatora do generowania prefiksów podpowiedzi na gałęziach. Na x86/x64 zajmują one jeden bajt, więc otrzymasz co najwyżej jeden bajt wzrostu dla każdej gałęzi. Jeśli chodzi o wydajność, to całkowicie zależy od aplikacji - w większości przypadków predyktor gałęzi na procesorze będzie je ignorował, w dzisiejszych czasach.

Edit: zapomniałem o jednym miejscu, w którym naprawdę mogą pomóc. Może pozwolić kompilatorowi na zmianę kolejności wykresu przepływu sterowania w celu zmniejszenia liczby branych gałęzi na "prawdopodobną" ścieżkę. Może to spowodować wyraźną poprawę w pętlach, w których sprawdzasz wiele przypadków wyjścia.

Są to funkcje GCC, które programista podpowiada kompilatorowi jaki będzie najbardziej prawdopodobny warunek gałęzi w danym wyrażeniu. Pozwala to kompilatorowi na zbudowanie instrukcji odgałęzienia tak, aby najczęstszy przypadek wymagał jak najmniejszej liczby instrukcji do wykonania.

Sposób budowania instrukcji branch zależy od architektury procesora.