Jak fungují pravděpodobná/nepravděpodobná makra v linuxovém jádře a jaký je jejich přínos?

Jsou nápovědou kompilátoru, aby vyslal instrukce, které způsobí, že predikce větvení upřednostní "pravděpodobnou" stranu instrukce skoku. To může být velká výhra, pokud je předpověď správná, znamená to, že instrukce skoku je v podstatě zdarma a bude trvat nula cyklů. Na druhou stranu, pokud je předpověď špatná, znamená to, že je potřeba propláchnout potrubí procesoru a to může stát několik cyklů. Dokud je předpověď po většinu času správná, bude to pro výkon dobré.

Stejně jako všechny takové optimalizace výkonu byste to měli provést pouze po rozsáhlém profilování, abyste zajistili, že kód je skutečně v úzkém hrdle, a pravděpodobně vzhledem k mikropovaze, že je provozován v těsné smyčce. Obecně jsou vývojáři Linuxu dost zkušení, takže bych si představoval, že by to udělali. O přenositelnost se ve skutečnosti příliš nestarají, protože se zaměřují pouze na gcc a mají velmi blízkou představu o sestavě, kterou chtějí generovat.

Pojďme provést dekompilaci, abychom viděli, co s tím GCC 4.8 dělá

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

Kompilace a dekompilace pomocí GCC 4.8.2 x86_64 Linux:

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

Výstup:

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

Pořadí instrukcí v paměti bylo nezměněno:nejprve printf a poté puts a retq návrat.

S __builtin_expect

Nyní nahraďte if (i) s:

if (__builtin_expect(i, 0))

a dostaneme:

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 (zkompilováno do __printf_chk ) byl přesunut na úplný konec funkce, za puts a návrat ke zlepšení predikce větvení, jak je zmíněno v jiných odpovědích.

Takže je to v podstatě stejné jako:

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

Tato optimalizace nebyla provedena s -O0 .

Ale hodně štěstí při psaní příkladu, který běží rychleji s __builtin_expect CPU jsou dnes opravdu chytré. Moje naivní pokusy jsou tady.

C++20 [[likely]] a [[unlikely]]

C++20 standardizovalo tyto vestavěné prvky C++:Jak použít atribut pravděpodobné/nepravděpodobné C++20 v příkazu if-else Pravděpodobně (slovní hříčka!) udělají totéž.

Jedná se o makra, která dávají kompilátoru rady, jakým směrem se může větev vydat. Makra se rozšiřují na konkrétní rozšíření GCC, pokud jsou k dispozici.

GCC je používá k optimalizaci pro predikci větví. Například, pokud máte něco jako následující

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

return x;

Pak může tento kód restrukturalizovat tak, aby byl něco podobného:

if (!x) {
  return x;
}

dosomething();
return x;

Výhodou toho je, že když procesor poprvé provede větev, vzniká značná režie, protože mohl spekulativně načítat a spouštět kód dále dopředu. Když se rozhodne, že bude mít větev, musí ji zrušit a začít u cíle větve.

Většina moderních procesorů má nyní nějaký druh predikce větvení, ale to pomáhá pouze tehdy, když jste větev prošli dříve a větev je stále v mezipaměti predikce větví.

Existuje řada dalších strategií, které může kompilátor a procesor v těchto scénářích použít. Další podrobnosti o tom, jak fungují prediktory větví, najdete na Wikipedii:http://en.wikipedia.org/wiki/Branch_predictor