Jaka jest różnica między prawdopodobnymi i mało prawdopodobnymi wywołaniami w jądrze?

11

Jakie są prawdopodobne i mało prawdopodobne wywołania w jądrze. Podczas przeszukiwania źródła jądra znalazłem te instrukcje.

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

Czy ktoś mógłby rzucić na to trochę światła?

Sen
źródło
To jest naprawdę pytanie programistyczne, lepiej dostosowane do Stack OVerflow .
Gilles 'SO - przestań być zły'
stackoverflow.com/questions/109710/…
Ciro Santilli 30 病毒 审查 六四 事件 法轮功

Odpowiedzi:

14

Są to wskazówki kompilatora dla GCC. Są one używane w warunkach warunkowych do informowania kompilatora, czy gałąź może zostać podjęta, czy nie. Może pomóc kompilatorowi w ustawieniu kodu w sposób optymalny dla najczęstszych rezultatów.

Są one używane w następujący sposób:

if (likely(some_condition)) {
  // the compiler will try and make the code layout optimal for the case
  // where some_condition is true, i.e. where this block is run
  most_likely_action();
} else {
  // this block is less frequently used
  corner_case();
}

Należy go używać z dużą ostrożnością (tj. W oparciu o rzeczywiste wyniki profilowania gałęzi). Niewłaściwa wskazówka może obniżyć wydajność (oczywiście).

Niektóre przykłady optymalizacji kodu można łatwo znaleźć, wyszukując GCC __builtin_expect. Ten post na blogu : optymalizacja gcc: __builtin_expect, na przykład, szczegółowo opisuje demontaż z nim.

Optymalizacje, które można wykonać, są bardzo specyficzne dla procesora. Ogólna idea polega na tym, że często procesory będą uruchamiały kod szybciej, jeśli nie rozgałęzią się / nie przeskoczą całego miejsca. Im bardziej jest liniowy i im bardziej przewidywalne są gałęzie, tym szybciej będzie działać. (Dotyczy to zwłaszcza procesorów z głębokimi rurociągami).

Tak więc kompilator wyśle ​​kod w taki sposób, że najbardziej prawdopodobna gałąź nie będzie wymagała przeskoku, jeśli na przykład woli to docelowy procesor.

Mata
źródło
Co oznaczają jednorożce ? Czy to termin techniczny czy tylko wypełniacz?
Sen
Usunąłem jednorożce, aby uniknąć zamieszania.
Mat.
Czy możesz opracować kompilator, który spróbuje zoptymalizować układ kodu dla przypadku ? Chciałbym wiedzieć, jak to robi.
Sen
dodał trochę informacji na ten temat. nie ma ogólnego sposobu optymalizacji kodu, wszystko zależy od procesora.
Mat.
2

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

Bez oczekiwania

#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 oczekiwaniem

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 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 ++: /programming/51797959/how-to-use-c20s-likely-unlikely-attribute-in-if-else-statement Prawdopodobnie ( kalambur!) zrób to samo.

Ciro Santilli
źródło