Existe uma dica do compilador para o GCC forçar a previsão do branch a sempre seguir um determinado caminho?

118

Para as arquiteturas Intel, há uma maneira de instruir o compilador GCC a gerar código que sempre force a previsão de ramificação de uma maneira particular em meu código? O hardware Intel ainda suporta isso? E quanto a outros compiladores ou hardwares?

Eu usaria isso em código C ++, onde conheço o caso em que desejo executar mais rápido e não me importo com a lentidão quando o outro branch precisa ser executado, mesmo quando ele recentemente o fez.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

Como uma questão de acompanhamento para Evdzhan Mustafa, a dica pode apenas especificar uma dica para a primeira vez que o processador encontra a instrução, todas as previsões de ramificações subsequentes funcionando normalmente?

WilliamKF
fonte
também pode lançar uma exceção se algo se tornar anormal (que é independente do compilador)
Shep

Respostas:

9

A partir do C ++ 20, os atributos prováveis ​​e improváveis devem ser padronizados e já são suportados no g ++ 9 . Como discutido aqui , você pode escrever

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

por exemplo, no código a seguir o bloco else fica embutido graças ao [[unlikely]]no bloco if

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

link godbolt comparando a presença / ausência do atributo

pseyfert
fonte
Por que usar [[unlikely]]em ifvs [[likely]]no else?
WilliamKF
sem motivo, acabei nesta constelação depois de tentar descobrir onde o atributo precisa ir.
pseyfert
Muito legal. Uma pena que o método não seja aplicável a versões C ++ mais antigas.
Maxim Egorushkin
Link fantástico
Lewis Kelsey,
87

O GCC suporta a função __builtin_expect(long exp, long c)de fornecer esse tipo de recurso. Você pode verificar a documentação aqui .

Onde expestá a condição usada e cé o valor esperado. Por exemplo, no caso de você querer

if (__builtin_expect(normal, 1))

Por causa da sintaxe estranha, isso geralmente é usado definindo duas macros personalizadas como

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

apenas para facilitar a tarefa.

Pense nisso:

  1. isso não é padrão
  2. um preditor de ramificação de compilador / CPU é provavelmente mais habilidoso do que você para decidir essas coisas, então esta pode ser uma microotimização prematura
Jack
fonte
3
Existe um motivo para você mostrar uma macro e não uma constexprfunção?
Columbo
22
@Columbo: Não acho que uma constexprfunção possa substituir essa macro. Tem que estar ifdiretamente na declaração, eu acredito. A mesma razão assertnunca poderia ser uma constexprfunção.
Mooing Duck
1
@MooingDuck Eu concordo, embora haja mais razões para afirmar .
Shafik Yaghmour
7
@Columbo uma razão para usar uma macro seria porque este é um dos poucos lugares em C ou C ++ onde uma macro é semanticamente mais correta do que uma função. A função só parece funcionar por causa da otimização ( é uma otimização: constexprfala apenas sobre semântica de valor, não o inlining de assembly específico de implementação); a interpretação direta (sem inline) do código não tem sentido. Não há razão para usar uma função para isso.
Leushenko
2
@Leushenko Considere que em __builtin_expectsi é uma dica de otimização, então argumentar que um método que simplifica seu uso depende de otimização não é ... convincente. Além disso, não adicionei o constexprespecificador para fazê-lo funcionar em primeiro lugar, mas para fazê-lo funcionar em expressões constantes. E sim, existem razões para usar uma função. Por exemplo, eu não gostaria de poluir todo o meu namespace com um nome bonitinho como likely. Eu teria que usar LIKELY, por exemplo , para enfatizar que é uma macro e evitar colisões, mas isso é simplesmente feio.
Columbo
46

gcc has long __builtin_expect (long exp, long c) ( ênfase minha ):

Você pode usar __builtin_expect para fornecer ao compilador informações de previsão de ramificação. Em geral, você deve preferir usar feedback de perfil real para isso (-fprofile-arcs), já que os programadores são notoriamente ruins em prever como seus programas realmente funcionam . No entanto, existem aplicativos em que esses dados são difíceis de coletar.

O valor de retorno é o valor de exp, que deve ser uma expressão integral. A semântica do integrado é que se espera que exp == c. Por exemplo:

if (__builtin_expect (x, 0))
   foo ();

indica que não esperamos chamar foo, pois esperamos que x seja zero. Uma vez que você está limitado a expressões integrais para exp, você deve usar construções como

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

ao testar valores de ponteiro ou de ponto flutuante.

Conforme a documentação observa, você deve preferir usar feedback de perfil real e este artigo mostra um exemplo prático disso e como isso no caso deles, pelo menos, acaba sendo uma melhoria em relação ao uso __builtin_expect. Veja também Como usar otimizações guiadas por perfil no g ++? .

Também podemos encontrar um artigo para iniciantes no kernel do Linux sobre as macros kernal provável () e improvável () que usam este recurso:

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

Observe o !!usado na macro, podemos encontrar a explicação para isso em Por que usar !! (condição) em vez de (condição)? .

Só porque essa técnica é usada no kernel do Linux não significa que sempre faz sentido usá-la. Podemos ver a partir desta pergunta que respondi recentemente a diferença entre o desempenho da função ao passar parâmetro como constante de tempo de compilação ou variável que muitas técnicas de otimizações roladas à mão não funcionam no caso geral. Precisamos criar o perfil do código com cuidado para entender se uma técnica é eficaz. Muitas técnicas antigas podem nem mesmo ser relevantes para as otimizações de compiladores modernos.

Observe, embora os builtins não sejam portáteis, o clang também oferece suporte a __builtin_expect .

Além disso, em algumas arquiteturas, pode não fazer diferença .

Shafik Yaghmour
fonte
O que é bom o suficiente para o kernel Linux não é suficiente para C ++ 11.
Maxim Egorushkin
@MaximEgorushkin note, eu realmente não recomendo seu uso, na verdade a documentação do gcc que cito, que é minha primeira citação, nem mesmo usa essa técnica. Eu diria que o principal objetivo da minha resposta é considerar as alternativas cuidadosamente antes de seguir esse caminho.
Shafik Yaghmour
44

Não, não há. (Pelo menos em processadores x86 modernos.)

__builtin_expectmencionado em outras respostas influencia a maneira como o gcc organiza o código assembly. Ele não influencia diretamente o preditor de ramificação da CPU. Claro, haverá efeitos indiretos na previsão de ramificação causados ​​pela reordenação do código. Mas nos processadores x86 modernos não há nenhuma instrução que diga à CPU "assuma que este ramo foi / não foi usado".

Consulte esta pergunta para obter mais detalhes: Intel x86 0x2E / 0x3E Prefix Branch Prediction realmente usado?

Para ser claro, __builtin_expecte / ou o uso de -fprofile-arcs pode melhorar o desempenho do seu código, dando dicas ao preditor de branch por meio do layout do código (consulte Otimizações de desempenho do assembly x86-64 - Alinhamento e previsão de branch ) e também melhorando o comportamento do cache mantendo o código "improvável" longe do código "provável".

Artelius
fonte
9
Isso está incorreto. Em todas as versões modernas do x86, o algoritmo de predição padrão é prever que as ramificações para a frente não sejam obtidas e que as ramificações para trás, sim (consulte software.intel.com/en-us/articles/… ). Portanto, reorganizando seu código, você pode efetivamente dar uma dica para a CPU. Isso é exatamente o que o GCC faz quando você usa __builtin_expect.
Nemo
6
@Nemo, você leu além da primeira frase da minha resposta? Tudo o que você disse está coberto pela minha resposta ou nos links fornecidos. A pergunta feita se você pode "forçar a previsão do branch a sempre seguir um determinado caminho", para a qual a resposta é "não", e eu não achei que outras respostas fossem claras o suficiente sobre isso.
Artelius
4
OK, eu deveria ter lido com mais atenção. Parece-me que esta resposta é tecnicamente correta, mas inútil, visto que o questionador obviamente está procurando __builtin_expect. Portanto, este deve ser apenas um comentário. Mas não é falso, então removi meu voto negativo.
Nemo
IMO não é inútil; é um esclarecimento útil de como CPUs e compiladores realmente funcionam, o que pode ser relevante para a análise de desempenho com / sem essas opções. por exemplo, você geralmente não pode usar __builtin_expectpara criar trivialmente um caso de teste com o qual possa medir e perf statque terá uma taxa muito alta de erro de estimativa de branch. Afeta apenas o layout da filial . E, a propósito, a Intel desde Sandybridge ou pelo menos Haswell não usa previsão estática muito / nada; há sempre alguma previsão no BHT, seja um pseudônimo obsoleto ou não. xania.org/201602/bpu-part-two
Peter Cordes
24

A maneira correta de definir macros prováveis ​​/ improváveis ​​em C ++ 11 é a seguinte:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Este método é compatível com todas as versões C ++, ao contrário [[likely]], mas depende de uma extensão não padrão __builtin_expect.


Quando essas macros são definidas desta forma:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Isso pode mudar o significado das ifinstruções e quebrar o código. Considere o seguinte código:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

E sua saída:

if(a) is true
if(LIKELY(a)) is false

Como você pode ver, a definição de PROVÁVEL usar !!como um elenco para boolquebrar a semântica de if.

O ponto aqui não é isso operator int()e operator bool()deve estar relacionado. O que é uma boa prática.

Em vez disso, usar em !!(x)vez de static_cast<bool>(x)perde o contexto para as conversões contextuais do C ++ 11 .

Maxim Egorushkin
fonte
Observe que as conversões contextuais vieram por meio de um defeito em 2012 e mesmo no final de 2014 ainda havia divergência de implementação. Na verdade, parece que o caso ao qual vinculei ainda não funciona para o gcc.
Shafik Yaghmour
@ShafikYaghmour Essa é uma observação interessante com relação à conversão contextual envolvida switch, obrigado. A conversão contextual envolvida aqui é partucluar para o tipo boole os cinco contextos específicos listados lá , que não incluem o switchcontexto.
Maxim Egorushkin
Isso afeta apenas C ++, certo? Portanto, não há razão para mudar os projetos C existentes para usar(_Bool)(condition) , porque C não tem sobrecarga de operador.
Peter Cordes
2
Em seu exemplo, você usou apenas (condition), não !!(condition). Ambos estão truedepois de mudar isso (testado com g ++ 7.1). Você pode construir um exemplo que realmente demonstre o problema do qual está falando quando usa !!para booleanizar?
Peter Cordes
3
Como Peter Cordes apontou, você diz "Quando essas macros [são] definidas desta maneira:" e, em seguida, mostra uma macro usando '!!', "pode ​​alterar o significado das instruções if e quebrar o código. Considere o seguinte código:" ... e então você mostra o código que não usa '!!' de todo - que sabia ser quebrado antes mesmo do C ++ 11. Altere a resposta para mostrar um exemplo em que a macro fornecida (usando !!) dá errado.
Carlo Wood
18

Como todas as outras respostas sugeriram adequadamente, você pode usar __builtin_expectpara dar ao compilador uma dica sobre como organizar o código do assembly. Como os documentos oficiais apontam, na maioria dos casos, o montador embutido em seu cérebro não será tão bom quanto o criado pela equipe do GCC. É sempre melhor usar dados de perfil reais para otimizar seu código, em vez de adivinhar.

Ao longo de linhas semelhantes, mas ainda não mencionadas, é uma maneira específica do GCC para forçar o compilador a gerar código em um caminho "frio". Isso envolve o uso dos atributos noinlinee cold, que fazem exatamente o que parecem que fazem. Esses atributos só podem ser aplicados a funções, mas com C ++ 11, você pode declarar funções lambda embutidas e esses dois atributos também podem ser aplicados a funções lambda.

Embora isso ainda se enquadre na categoria geral de micro-otimização e, portanto, o conselho padrão se aplica - teste, não adivinhe -, sinto que é mais útil do que geralmente __builtin_expect. Quase nenhuma geração do processador x86 usa dicas de previsão de ramificação ( referência ), então a única coisa que você poderá afetar de qualquer maneira é a ordem do código de montagem. Como você sabe o que é código de manipulação de erros ou "caso extremo", pode usar esta anotação para garantir que o compilador nunca irá prever um branch para ele e irá vinculá-lo fora do código "quente" ao otimizar o tamanho.

Uso de amostra:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    
}

Melhor ainda, o GCC irá ignorar isso automaticamente em favor do feedback do perfil quando estiver disponível (por exemplo, ao compilar com -fprofile-use).

Veja a documentação oficial aqui: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

Cody Gray
fonte
2
Os prefixos de dicas de previsão de ramificação são ignorados porque não são necessários; você pode obter exatamente o mesmo efeito apenas reordenando seu código. (O algoritmo de previsão de desvio padrão é adivinhar que os desvios anteriores são obtidos e os desvios posteriores não.) Portanto, você pode, de fato, dar uma dica à CPU, e é isso que __builtin_expectfaz. Não é inútil. Você está certo ao dizer que o coldatributo também é útil, mas você subestima a utilidade de, __builtin_expecteu acho.
Nemo
CPUs modernas da Intel não usam previsão de branch estático. O algoritmo que você descreve, @Nemo, em que as ramificações anteriores são previstas tomadas e as ramificações diretas são previstas como não realizadas, foi usado em processadores anteriores e até o Pentium M ou mais, mas os designs modernos basicamente adivinham aleatoriamente, indexando em suas ramificações tabelas onde ele esperaria encontrar informações sobre aquele branch e usando qualquer informação que estivesse lá (mesmo que possa ser essencialmente lixo). Portanto, as dicas de previsão de ramificação seriam teoricamente úteis, mas talvez não na prática, razão pela qual a Intel as removeu.
Cody Gray
Para ser claro, a implementação da previsão de ramificação é extremamente complicada e as restrições de espaço nos comentários me forçaram a simplificar muito. Esta seria realmente uma resposta completa por si só. Ainda pode haver vestígios de previsão de branch estático em microarquiteturas modernas, como Haswell, mas não é tão simples como costumava ser.
Cody Gray
Você tem uma referência para "CPUs modernas da Intel não usam previsão de branch estático"? O próprio artigo da Intel ( software.intel.com/en-us/articles/… ) diz o contrário ... Mas isso é de 2011
Nemo
Não tenho uma referência oficial, @Nemo. A Intel é extremamente discreta sobre os algoritmos de previsão de ramos usados ​​em seus chips, tratando-os como segredos comerciais. A maior parte do que é conhecido foi descoberto por testes empíricos. Como sempre, os materiais de Agner Fog são os melhores recursos, mas até ele diz: "O preditor de ramificação parece ter sido redesenhado no Haswell, mas muito pouco se sabe sobre sua construção." Não me lembro onde vi pela primeira vez os benchmarks demonstrando que BP estático não era mais usado, infelizmente.
Cody Gray
5

__builtin_expect pode ser usado para dizer ao compilador para que lado você espera que um branch vá. Isso pode influenciar como o código é gerado. Os processadores típicos executam o código sequencialmente com mais rapidez. Então, se você escrever

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

o compilador irá gerar código como

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

Se sua dica estiver correta, isso executará o código sem quaisquer ramificações realmente executadas. Ele será executado mais rápido do que a sequência normal, onde cada instrução if ramificará em torno do código condicional e executará três ramificações.

Os processadores x86 mais novos têm instruções para ramificações que se espera que sejam obtidas ou para ramificações que se espera que não sejam usadas (há um prefixo de instrução; não tenho certeza sobre os detalhes). Não tenho certeza se o processador usa isso. Não é muito útil, porque a previsão de ramificação resolverá isso muito bem. Portanto, não acho que você possa realmente influenciar a previsão do branch .

gnasher729
fonte
2

Com relação ao OP, não, não há como no GCC dizer ao processador para sempre assumir que o branch foi ou não tomado. O que você tem é __builtin_expect, que faz o que os outros dizem que faz. Além disso, acho que você não quer dizer ao processador se o ramo é levado ou não sempre . Os processadores de hoje, como a arquitetura Intel, podem reconhecer padrões bastante complexos e se adaptar com eficácia.

No entanto, há momentos em que você deseja assumir o controle se, por padrão, uma ramificação é prevista ou não: Quando você souber, o código será chamado de "frio" com relação às estatísticas de ramificação.

Um exemplo concreto: código de gerenciamento de exceção. Por definição, o código de gerenciamento acontecerá excepcionalmente, mas talvez quando ocorrer o desempenho máximo seja desejado (pode haver um erro crítico para ser eliminado o mais rápido possível), portanto, você pode querer controlar a previsão padrão.

Outro exemplo: você pode classificar sua entrada e pular para o código que trata o resultado de sua classificação. Se houver muitas classificações, o processador pode coletar estatísticas, mas perdê-las porque a mesma classificação não ocorre em tempo suficiente e os recursos de previsão são dedicados ao código recentemente chamado. Gostaria que houvesse um primitivo para dizer ao processador "por favor, não dedique recursos de previsão a este código" da maneira que às vezes você pode dizer "não coloque isso em cache".

TheCppZoo
fonte