Como funcionam as macros prováveis ​​/ improváveis ​​no kernel do Linux e qual é o benefício delas?

348

Eu estive pesquisando algumas partes do kernel do Linux e encontrei chamadas como esta:

if (unlikely(fd < 0))
{
    /* Do something */
}

ou

if (likely(!err))
{
    /* Do something */
}

Eu encontrei a definição deles:

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

Eu sei que eles são para otimização, mas como eles funcionam? E quanta redução de desempenho / tamanho pode ser esperada ao usá-los? E vale a pena o aborrecimento (e provavelmente a perda da portabilidade) pelo menos no código de gargalo (no espaço do usuário, é claro).

terminus
fonte
7
Isso realmente não é específico para o kernel do Linux ou sobre macros, mas uma otimização do compilador. Isso deve ser marcado novamente para refletir isso?
Cody Brocious
11
O artigo O que todo programador deve saber sobre memória (p. 57) contém uma explicação detalhada.
Torsten Marek
2
Veja tambémBOOST_LIKELY
Ruggero Turra
4
Relacionado: uma referência no uso de__builtin_expect em outra questão.
YSC
13
Não há problema de portabilidade. Você pode fazer trivialmente coisas como #define likely(x) (x)e #define unlikely(x) (x)em plataformas que não suportam esse tipo de dica.
David Schwartz

Respostas:

329

Eles sugerem que o compilador emita instruções que farão com que a predição de ramificação seja favorável ao lado "provável" de uma instrução de salto. Isso pode ser uma grande vitória, se a previsão estiver correta, significa que a instrução de salto é basicamente livre e levará zero ciclos. Por outro lado, se a previsão estiver incorreta, significa que o pipeline do processador precisa ser liberado e pode custar vários ciclos. Enquanto a previsão estiver correta na maioria das vezes, isso tenderá a ser bom para o desempenho.

Como todas essas otimizações de desempenho, você deve fazê-lo apenas após uma extensa criação de perfil para garantir que o código esteja realmente em um gargalo e, provavelmente, dada a natureza micro, que ele esteja sendo executado em um loop restrito. Geralmente os desenvolvedores do Linux são bem experientes, então eu imagino que eles teriam feito isso. Eles realmente não se importam muito com a portabilidade, pois só têm como alvo o gcc e têm uma ideia muito próxima do assembly que desejam que ele gere.

1800 INFORMAÇÃO
fonte
3
Essas macros foram usadas principalmente para verificação de erros. Porque o erro deixa menos provavelmente que a operação normal. Algumas pessoas fazem de perfil ou cálculo para decidir folha mais utilizado ...
gavenkoa
51
Com relação ao fragmento "[...]that it is being run in a tight loop", muitas CPUs possuem um preditor de ramificação , portanto, o uso dessas macros ajuda apenas na primeira execução do código ou quando a tabela de histórico é substituída por uma ramificação diferente com o mesmo índice na tabela de ramificação. Em um loop restrito, e supondo que uma ramificação seja uma maneira na maioria das vezes, o preditor de ramificação provavelmente começará a adivinhar a ramificação correta muito rapidamente. - seu amigo de pediatria.
Ross Rogers
8
@RossRogers: O que realmente acontece é que o compilador organiza as ramificações, de modo que o caso comum é o que não foi adotado. Isso é mais rápido, mesmo quando a previsão de ramificação funciona. As ramificações obtidas são problemáticas para a busca e decodificação de instruções, mesmo quando são previstas perfeitamente. Algumas CPUs prevêem estaticamente ramificações que não estão em sua tabela de histórico, geralmente assumindo que não são usadas para ramificações avançadas. Os processadores Intel não funcionam dessa maneira: eles não tentam verificar se a entrada da tabela preditora é para esse ramo, eles apenas o utilizam de qualquer maneira. Um ramo quente e uma força filial frio aliás a mesma entrada ...
Peter Cordes
12
Essa resposta é principalmente obsoleta, pois a principal reivindicação é que ela ajuda na previsão de ramificação e, como aponta @PeterCordes, na maioria dos hardwares modernos não há previsão de ramificação estática implícita ou explícita. De fato, a dica é usada pelo compilador para otimizar o código, isso envolve dicas de ramificação estática ou qualquer outro tipo de otimização. Para a maioria das arquiteturas hoje em dia, é a "qualquer outra otimização" que importa, por exemplo, tornar os caminhos ativos contíguos, agendar melhor o caminho ativo, minimizar o tamanho do caminho lento, vetorizar apenas o caminho esperado, etc.
BeeOnRope
3
@BeeOnRope devido à pré-busca em cache e ao tamanho da palavra, ainda há uma vantagem em executar um programa linearmente. O próximo local de memória já será buscado e no cache, o destino da ramificação, talvez ou não. Com uma CPU de 64 bits, você pega pelo menos 64 bits por vez. Dependendo da intercalação DRAM, pode ser 2x 3x 3x ou mais bits capturados.
18717 Bryce
88

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

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

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 __builtin_expect

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 main() {
    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 seja mais rápido do __builtin_expectque sem, as CPUs são realmente inteligentes atualmente . Minhas tentativas ingênuas estão aqui .

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

O C ++ 20 padronizou os recursos internos do C ++: Como usar o atributo provável / improvável do C ++ 20 na instrução if-else Eles provavelmente (um trocadilho!) Farão a mesma coisa.

Ciro Santilli adicionou uma nova foto
fonte
71

Essas são macros que dão dicas ao compilador sobre o caminho a ser seguido por uma ramificação. As macros se expandem para extensões específicas do GCC, se estiverem disponíveis.

O GCC usa esses recursos para otimizar a previsão de ramificação. Por exemplo, se você tiver algo parecido com o seguinte

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

return x;

Em seguida, ele pode reestruturar esse código para algo mais ou menos como:

if (!x) {
  return x;
}

dosomething();
return x;

O benefício disso é que, quando o processador entra em uma ramificação pela primeira vez, há uma sobrecarga significativa, porque pode estar carregando e executando especulativamente o código mais adiante. Quando determina que a ramificação será executada, ela deve ser invalidada e iniciada no destino da ramificação.

Os processadores mais modernos agora têm algum tipo de previsão de ramificação, mas isso só ajuda quando você já passou pela ramificação antes, e a ramificação ainda está no cache de previsão de ramificação.

Existem várias outras estratégias que o compilador e o processador podem usar nesses cenários. Você pode encontrar mais detalhes sobre como os preditores de agência funcionam na Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

dvorak
fonte
3
Além disso, afeta a pegada do icache - mantendo trechos improváveis ​​de código fora do caminho ativo.
fche 3/03/2015
2
Mais precisamente, ele pode fazê-lo com gotos sem repetir o return x: stackoverflow.com/a/31133787/895245
Ciro Santilli
7

Eles fazem com que o compilador emita as dicas de ramificação apropriadas onde o hardware as suporta. Isso geralmente significa apenas girar alguns bits no opcode da instrução, para que o tamanho do código não seja alterado. A CPU começará a buscar instruções no local previsto e liberará o pipeline e reiniciará se isso estiver errado quando a ramificação for alcançada; no caso em que a dica estiver correta, isso tornará a ramificação muito mais rápida - precisamente quanto mais rapidamente dependerá do hardware; e quanto isso afeta o desempenho do código dependerá de qual proporção de tempo a dica está correta.

Por exemplo, em uma CPU do PowerPC, uma ramificação não sugerida pode levar 16 ciclos, uma incorreta com 8 e outra incorretamente com 24. Nos loops mais internos, uma boa sugestão pode fazer uma enorme diferença.

Portabilidade não é realmente um problema - presumivelmente a definição está em um cabeçalho por plataforma; você pode simplesmente definir "provável" e "improvável" para plataformas que não suportam dicas de ramificação estática.

sombra da Lua
fonte
3
Para o registro, o x86 ocupa espaço adicional para dicas de ramificação. Você precisa ter um prefixo de um byte nas ramificações para especificar a dica apropriada. Concordou que sugerir é uma coisa boa (TM), no entanto.
Cody Brocious
2
Dang CISC CPUs e suas instruções de comprimento variável;)
moonshadow
3
Dang RISC CPUs - Fique longe de minhas instruções 15-byte;)
Cody Brocious
7
@CodyBrocious: a dica de ramo foi introduzida com o P4, mas foi abandonada junto com o P4. Todas as outras CPUs x86 simplesmente ignoram esses prefixos (porque os prefixos são sempre ignorados em contextos em que não fazem sentido). Essas macros não fazem com que o gcc realmente emita prefixos de dicas de ramificação no x86. Eles ajudam você a fazer com que o gcc distribua sua função com menos ramificações obtidas no caminho rápido.
Peter Cordes
5
long __builtin_expect(long EXP, long C);

Essa construção informa ao compilador que a expressão EXP provavelmente terá o valor C. O valor de retorno é EXP. __builtin_expect deve ser usado em uma expressão condicional. Em quase todos os casos, será usado no contexto de expressões booleanas; nesse caso, é muito mais conveniente definir duas macros auxiliares:

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

Essas macros podem então ser usadas como em

if (likely(a > 1))

Referência: https://www.akkadia.org/drepper/cpumemory.pdf

Ashish Maurya
fonte
11
Como foi perguntado em um comentário para outra resposta - o que é a razão para a dupla inversão nas macros (ou seja, por que usar __builtin_expect(!!(expr),0)em vez de apenas __builtin_expect((expr),0)?
Michael Firth
11
@ MichaelFirth "inversão dupla" !!é equivalente a converter algo para a bool. Algumas pessoas gostam de escrever dessa maneira.
Ben XO
2

(comentário geral - outras respostas cobrem os detalhes)

Não há motivo para perder a portabilidade usando-os.

Você sempre tem a opção de criar uma macro "inline" ou efeito nulo simples que permita compilar em outras plataformas com outros compiladores.

Você simplesmente não terá o benefício da otimização se estiver em outras plataformas.

Andrew Edgecombe
fonte
11
Você não usa portabilidade - as plataformas que não os suportam apenas as definem para expandir para cadeias vazias.
Sharptooth 30/09/11
2
Eu acho que vocês dois estão realmente concordando um com o outro - é apenas uma expressão confusa. (A partir da aparência dele, o comentário de Andrew está dizendo "você pode usá-los sem perder a portabilidade", mas sharptooth pensou que ele disse "não usá-los como eles são não portátil" e objetou.)
Miral
2

De acordo com o comentário de Cody , isso não tem nada a ver com o Linux, mas é uma dica para o compilador. O que acontece dependerá da arquitetura e da versão do compilador.

Esse recurso específico no Linux é um pouco mal utilizado nos drivers. Como o osgx aponta na semântica do atributo hot , qualquer função hotou coldfunção chamada em um bloco pode sugerir automaticamente que a condição é provável ou não. Por exemplo, dump_stack()está marcado, coldentão isso é redundante,

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

Versões futuras de gccpodem seletivamente alinhar uma função com base nessas dicas. Também houve sugestões de que não boolean, mas uma pontuação como a mais provável etc. Geralmente, deve ser preferido usar algum mecanismo alternativo como cold. Não há razão para usá-lo em qualquer lugar, exceto em caminhos quentes. O que um compilador fará em uma arquitetura pode ser completamente diferente em outra.

ruído artless
fonte
2

Em muitas versões do linux, você pode encontrar complier.h em / usr / linux /, incluindo-o para uso simples. E outra opinião, improvável () é mais útil do que provável (), porque

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

Ele também pode ser otimizado em muitos compiladores.

A propósito, se você quiser observar o comportamento detalhado do código, faça o seguinte:

gcc -c test.c objdump -d test.o> obj.s

Em seguida, abra obj.s, você pode encontrar a resposta.

Finaldie
fonte
1

Eles são dicas para o compilador para gerar os prefixos de dicas nas ramificações. No x86 / x64, eles ocupam um byte, então você terá no máximo um aumento de um byte para cada ramificação. Quanto ao desempenho, depende inteiramente do aplicativo - na maioria dos casos, o preditor de ramificação do processador os ignorará atualmente.

Edit: Esqueceu-se de um lugar que eles realmente podem realmente ajudar. Ele pode permitir que o compilador reordene o gráfico de fluxo de controle para reduzir o número de ramificações realizadas para o caminho 'provável'. Isso pode ter uma melhoria acentuada nos loops onde você está verificando vários casos de saída.

Cody Brocious
fonte
10
O gcc nunca gera dicas de ramificação x86 - pelo menos todas as CPUs Intel as ignorariam de qualquer maneira. Ele tentará limitar o tamanho do código em regiões improváveis, evitando inlining e loop desenrolando.
alex estranha
1

Essas são funções do GCC para o programador dar uma dica ao compilador sobre qual será a condição de ramificação mais provável em uma determinada expressão. Isso permite que o compilador construa as instruções de ramificação para que o caso mais comum leve o menor número de instruções para executar.

Como as instruções de ramificação são construídas depende da arquitetura do processador.

dcgibbons
fonte