Pergunta sobre linux, likely-unlikely, linux-kernel, gcc – Como as macros prováveis ​​/ improváveis ​​no kernel do Linux funcionam e qual é o benefício delas?

295

Eu estive procurando por algumas partes do kernel Linux e encontrei chamadas assim:

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 quanto a diminuição de desempenho / tamanho pode ser esperada de usá-los? E vale a pena o incômodo (e provavelmente a perda da portabilidade) pelo menos no código do gargalo (no espaço do usuário, é claro).

De acordo comFAQ do kernelnewbies (e a última fonte do kernel 3.11), as definições das macros são um pouco diferentes agora: #define likely (x) __builtin_expect (!! (x), 1) #define improvável (x) __builtin_expect (!! (x), 0) I acho que isso adiciona um pouco mais à confusão! :) Eu não tenho a necessidade de double NOT (<code> !! </ code>). Mandeep Sandhu
Relacionado:uma referência sobre o uso de__builtin_expect em outra pergunta. YSC
Isso realmente não é específico para o kernel do Linux ou sobre macros, mas uma otimização do compilador. Isso deve ser retagged para refletir isso? Cody Brocious
Veja tambémBOOST_LIKELY Ruggero Turra

Sua resposta

10   a resposta
1

amificações. Em 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, isso depende inteiramente do aplicativo - na maioria dos casos, o preditor de ramificação no processador os ignorará nos dias de hoje.

Edit: Esqueceu sobre um lugar que eles 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 tomadas para o caminho 'provável'. Isso pode ter uma melhoria acentuada nos loops em que você está verificando vários casos de saída.

O gcc nunca gera dicas sobre o branch x86 - pelo menos todos os processadores da Intel os ignorariam de qualquer maneira. Ele tentará limitar o tamanho do código em regiões improváveis, evitando o inlining e o loop unrolling. alex strange
2

você pode encontrar o complier.h em / usr / linux /, você pode incluí-lo para uso simples. E outra opinião, improvável () é mais útil do que provável (), porque

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

pode ser otimizado também em muitos compiladores.

E, a propósito, se você quiser observar o comportamento detalhado do código, você pode simplesmente fazer o seguinte:

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

Então, abra obj.s, você pode encontrar a resposta.

60

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

Saída:

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 de instrução na memória foi inalterada: primeiroprintf e depoisputs e aretq Retorna.

Com__builtin_expect

Agora substituaif (i) com:

if (__builtin_expect(i, 0))

e nós 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>

oprintf (compilado para__printf_chk) foi movido para o final da função, apósputs e o retorno para melhorar a predição de ramos como mencionado por outras respostas.

Então é 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 feita com-O0.

Mas boa sorte em escrever um exemplo que corre mais rápido com__builtin_expect do que semCPUs são realmente inteligentes naqueles dias. Minhas tentativas ingênuasestão aqui.

6

priadas onde o hardware as suporta. Isso geralmente significa apenas girar alguns bits no opcode da instrução, portanto, o tamanho do código não será alterado. A CPU começará a buscar instruções do local previsto, liberará o pipeline e recomeçará, caso isso aconteça quando a filial for atingida; no caso em que a sugestão estiver correta, isso tornará o branch muito mais rápido - precisamente quanto mais rápido dependerá do hardware; e o quanto isso afeta o desempenho do código dependerá de qual proporção da dica de tempo está correta.

Por exemplo, em uma CPU PowerPC, um ramo não-hu- mano pode levar 16 ciclos, um sugerido corretamente 8 e um sugerido incorretamente 24. Em loops mais internos, boas sugestões podem 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 nada para plataformas que não suportam dicas de ramificação estática.

Para o registro, o x86 ocupa espaço adicional para sugestões de ramificações. Você precisa ter um prefixo de um byte nas ramificações para especificar a dica apropriada. Concordou que insinuar é uma coisa boa (TM), embora. Cody Brocious
@CodyBrocious: a sugestão de ramificação foi introduzida com P4, mas foi abandonada junto com P4. Todas as outras CPUs x86 simplesmente ignoram esses prefixos (porque os prefixos são sempre ignorados em contextos em que não têm sentido). Essas macrosnão faça faça com que o gcc realmente emita prefixos de dica de ramificação no x86. Eles ajudam você a fazer com que o gcc defina sua função com menos ramificações tomadas no caminho rápido. Peter Cordes
Dang CISC CPUs e suas instruções de comprimento variável;) moonshadow
CPUs Dang RISC - Fique longe das minhas instruções de 15 bytes;) Cody Brocious
2

Cody, isso não tem nada a ver com o Linux, mas é uma dica para o compilador. O que acontece depende da versão da arquitetura e do compilador.

Esse recurso específico no Linux é um pouco mal usado em drivers. Comoosgx aponta emsemântica do atributo hot, qualquerhot oucold A função chamada em um bloco pode sugerir automaticamente que a condição é provável ou não. Por exemplo,dump_stack() é marcadocold então isso é redundante,

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

Versões futuras degcc pode seletivamente inline uma função com base nessas dicas. Houve também sugestões de que não éboolean, mas uma pontuação como emprovavelmenteGeralmente, deve ser preferível usar algum mecanismo alternativo comocold. Não há razão para usá-lo em qualquer lugar, a não ser caminhos quentes. O que um compilador fará em uma arquitetura pode ser completamente diferente em outra.

277

e a predição do ramo favoreça o 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 errada, significa que o pipeline do processador precisa ser liberado e pode custar vários ciclos. Desde que a previsão esteja correta na maior parte do tempo, isso tenderá a ser bom para o desempenho.

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

@ Peter Cordes - Eu entendo o aliasing da tabela de ramificação, é por isso que eu escrevithe history table is overwritten by a different branch with the same index into the branching table.  Eu estava apenas apontando a coisa do laço apertado. Se você executar o loop repetidamente, o custo inicial é trivial e o preditor da ramificação assume o controle, a menos que você obtenha a predição da ramificação passando pelo salto / chamadas dentro do "loop fechado". Dizendo o compilador para favorecer um ramo é uma micro-otimização em loops apertados executar muitas muitas vezes. Tudo muito pedante, para ter certeza :-) Ross Rogers
@RossRogers: Meu ponto principal foi que estabelecer o caminho rápido com ramificações principalmente não tomadas é bom, e é uma vitória mesmo depois que os preditores de ramificação se aquecerem (por exemplo, em um loop apertado). Peter Cordes
Absolutamente, existem todos os tipos de razões relacionadas ao pipeline pelas quais o código linear é o preferido e eles não têm nada a ver com ocorrências de ramificação estáticas embutidas na instrução. As CPUs modernas geralmente as ignoram, de modo que toda a lógica dada nesta resposta é obsoleta. @Bryce BeeOnRope
Esta resposta é na maior parte obsoleta desde que a reivindicação principal é que ajuda a predição da filial, e como @PeterCordes indica, na maioria de hardware moderno não há predição estática implícita ou explícita da ramificação. Na verdade, a dica é usada pelo compilador para otimizar o código, seja envolvendo dicas estáticas de ramificação ou qualquer outro tipo de otimização. Para a maioria das arquiteturas de hoje, é a "qualquer outra otimização" que importa, por exemplo, tornando os caminhos quentes contíguos, agendando melhor o caminho quente, minimizando o tamanho do caminho lento, vetorizando apenas o caminho esperado, etc, etc. BeeOnRope
2

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

Você sempre tem a opção de criar um simples efeito nulo "inline" ou macro que permitirá que você compile em outras plataformas com outros compiladores.

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

Você não usa portabilidade - as plataformas que não as suportam apenas as definem para expandir para strings vazias. sharptooth
Eu acho que vocês dois estão realmente concordando um com o outro - é apenas uma frase confusa. (Pelo que parece, o comentário de Andrew está dizendo "você pode usá-los sem perder a portabilidade", mas o pensamento de que ele disse "não os use como eles não são portáteis" e se opôs.) Miral
66

m ramo pode ir. As macros se expandem para extensões específicas do GCC, se estiverem disponíveis.

O GCC usa isso para otimizar a previsão de filial. Por exemplo, se você tem algo como o seguinte

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

return x;

Então pode reestruturar este código para ser algo mais parecido com:

if (!x) {
  return x;
}

dosomething();
return x;

O benefício disso é que, quando o processador pega uma ramificação pela primeira vez, há uma sobrecarga significativa, porque ela pode ter carregado e executado especulativamente o código mais à frente. Quando ele determina a ramificação, ele precisa invalidar isso e iniciar no destino da ramificação.

A maioria dos processadores modernos agora tem 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.

Há 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 ramificação funcionam na Wikipedia:http://en.wikipedia.org/wiki/Branch_predictor

Além disso, impacta a pegada de icache - mantendo rastros improváveis ​​de código fora do caminho quente. fche
Mais precisamente, pode fazê-lo comgotos sem repetir oreturn x: stackoverflow.com/a/31133787/895245 Ciro Santilli 新疆改造中心996ICU六四事件
5
long __builtin_expect(long EXP, long C);

e terá o valor C. O valor de retorno é EXP.__builtin_expect destina-se a ser usado em uma expressão condicional. Em quase todos os casos, ele será usado no contexto de expressões booleanas, caso em que é muito mais conveniente definir duas macros auxiliares:

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

Essas macros podem ser usadas como em

if (likely(a > 1))

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

Como foi perguntado em um comentário para outra resposta - qual é 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
1

sobre qual a condição de ramificação mais provável em uma determinada expressão. Isso permite que o compilador construa as instruções da ramificação para que o caso mais comum receba o menor número de instruções a serem executadas.

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

Perguntas relacionadas