Qual é a diferença entre chamadas prováveis ​​e improváveis ​​no Kernel?

11

Qual a diferença entre chamadas prováveis ​​e improváveis ​​no Kernel. Enquanto procurava na fonte do kernel, encontrei essas instruções.

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

Alguém poderia lançar alguma luz sobre isso?

Sen
fonte
Esta é realmente uma questão de programação, mais adequada para o Stack OVerflow .
Gilles 'SO- stop be evil'
stackoverflow.com/questions/109710/…
Ciro Santilli escreveu:

Respostas:

14

Eles são dicas do compilador para o GCC. Eles são usados ​​em condicionais para informar ao compilador se é provável que uma ramificação seja tomada ou não. Isso pode ajudar o compilador a definir o código de maneira ideal para o resultado mais frequente.

Eles são usados ​​assim:

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

Deve ser usado com muito cuidado (ou seja, com base nos resultados reais de criação de perfil de ramificação). Uma dica errada pode prejudicar o desempenho (obviamente).

Alguns exemplos de como o código pode ser otimizado são facilmente encontrados procurando GCC __builtin_expect. Esta postagem do blog otimiza o gcc: __builtin_expect, por exemplo, detalha uma desmontagem com ele.

O tipo de otimizações que pode ser feito é muito específico do processador. A idéia geral é que, frequentemente, os processadores executam o código mais rapidamente se não ramificam / saltam por todo o lugar. Quanto mais linear for, e quanto mais previsíveis forem as ramificações, mais rápido será executado. (Isso é especialmente verdadeiro para processadores com pipelines profundos, por exemplo.)

Portanto, o compilador emitirá o código de forma que a ramificação mais provável não envolva um salto, se é o que a CPU de destino prefere, por exemplo.

Esteira
fonte
O que se entende por unicórnios ? É um termo técnico ou apenas um preenchedor?
Sen
Tirei os unicórnios para evitar confusão.
19411 Mat
Poderia, por favor, elaborar o compilador e tentar otimizar o layout do código para o caso ? Eu gostaria de saber como isso acontece.
Sen
adicionou um pouco de informação sobre isso. não existe uma maneira geral de otimizar o código, tudo depende muito do processador.
19411 Mat
2

Vamos descompilar para ver o que o GCC 4.8 faz com ele

Sem esperar

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

Compile e descompile com o GCC 4.8.2 x86_64 Linux:

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

Resultado:

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

A ordem das instruções na memória permaneceu inalterada: primeiro o printfe depois putso retqretorno.

Com esperar

Agora substitua if (i)por:

if (__builtin_expect(i, 0))

e temos:

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>

O printf(compilado para __printf_chk) foi movido para o final da função, após putse o retorno para melhorar a previsão de ramificação, conforme mencionado por outras respostas.

Portanto, é basicamente o mesmo que:

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

Essa otimização não foi concluída -O0.

Mas boa sorte em escrever um exemplo que é mais rápido do __builtin_expectque sem, as CPUs são realmente inteligentes naqueles dias . Minhas tentativas ingênuas estão aqui .

C ++ 20 [[likely]]e[[unlikely]]

O C ++ 20 padronizou os recursos internos do C ++: /programming/51797959/how-to-use-c20s-likely-unlikely-attribute-in-if-else-statement Eles provavelmente (um trocadilho!) faça a mesma coisa.

Ciro Santilli adicionou uma nova foto
fonte