Um salto caro com o GCC 5.4.0

Eu tinha uma função que se parecia com isso (mostrando apenas a parte importante):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

Escrita assim, a função levou ~ 34ms na minha máquina. Depois de alterar a condição para multiplicação booleana (fazendo o código ficar assim):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

o tempo de execução diminuiu para ~ 19ms.

O compilador usado foi o GCC 5.4.0 com -O3 e depois de verificar o código asm gerado usando godbolt.org, descobri que o primeiro exemplo gera um salto, enquanto o segundo não. Decidi experimentar o GCC 6.2.0, que também gera uma instrução de salto ao usar o primeiro exemplo, mas o GCC 7 parece não gerar mais um.

Descobrir esta maneira de acelerar o código foi bastante horrível e levou algum tempo. Por que o compilador se comporta dessa maneira? É planejado e é algo que os programadores devem procurar? Existem mais coisas semelhantes a isso?

EDIT: link para godbolt https://godbolt.org/g/5lKPF3

O operador AND lógico ( &&) usa a avaliação de curto-circuito, o que significa que o segundo teste é feito apenas se a primeira comparação for avaliada como verdadeira. Isso geralmente é exatamente a semântica que você precisa. Por exemplo, considere o seguinte código:

if ((p != nullptr) && (p->first > 0))

Você deve garantir que o ponteiro não seja nulo antes de desmarcá-lo. Se essa não fosse uma avaliação de curto-circuito, você teria um comportamento indefinido porque estaria desreferenciando um ponteiro nulo.

Também é possível que a avaliação de curto-circuito produza um ganho de desempenho nos casos em que a avaliação das condições é um processo caro. Por exemplo:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

Se DoLengthyCheck1falhar, não há sentido em ligar DoLengthyCheck2.

No entanto, no binário resultante, uma operação de curto-circuito geralmente resulta em duas ramificações, pois essa é a maneira mais fácil para o compilador preservar essas semânticas. (É por isso que, do outro lado da moeda, a avaliação de curto-circuito às vezes pode inibir o potencial de otimização.) Você pode ver isso observando a parte relevante do código do objeto gerado para sua ifdeclaração pelo GCC 5.4:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

Você vê aqui as duas comparações ( cmpinstruções) aqui, cada uma seguida por um salto / ramificação condicional separada ( jaou pula se acima).

É uma regra geral que os galhos são lentos e, portanto, devem ser evitados em laços apertados. Isso aconteceu em praticamente todos os processadores x86, desde o humilde 8088 (cujos tempos de busca lentos e fila de pré-busca extremamente pequena [comparável a um cache de instruções], combinados com a absoluta falta de previsão de ramificação, significavam que ramificações feitas exigiam que o cache fosse despejado. ) para implementações modernas (cujos pipelines longos tornam as ramificações imprevisíveis igualmente caras). Observe a pequena advertência que eu coloquei lá. Os processadores modernos desde o Pentium Pro possuem mecanismos avançados de previsão de ramificações, projetados para minimizar o custo das ramificações. Se a direção da ramificação puder ser adequadamente prevista, o custo será mínimo. Na maioria das vezes, isso funciona bem, mas se você entrar em casos patológicos em que o preditor de ramo não está do seu lado,seu código pode ficar extremamente lento . Presumivelmente, é aqui que você está aqui, pois diz que sua matriz não está classificada.

Você diz que os benchmarks confirmaram que a substituição de &&um por *torna o código visivelmente mais rápido. A razão para isso é evidente quando comparamos a parte relevante do código do objeto:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

É um pouco contra-intuitivo que isso possa ser mais rápido, pois há mais instruções aqui, mas é assim que a otimização funciona às vezes. Você vê as mesmas comparações ( cmp) sendo feitas aqui, mas agora, cada uma é precedida por um xore seguida por um setbe. O XOR é apenas um truque padrão para limpar um registro. A setbeé uma instrução x86 que define um pouco com base no valor de um sinalizador e é frequentemente usada para implementar código sem ramificação. Aqui, setbeé o inverso de ja. Ele define seu registro de destino como 1 se a comparação for menor ou igual (desde que o registro tenha sido pré-zerado, será 0 caso contrário), enquanto jaramificado se a comparação estiver acima. Uma vez que esses dois valores foram obtidos no r15ber14bregistradores, eles são multiplicados juntos usando imul. Tradicionalmente, a multiplicação era uma operação relativamente lenta, mas é extremamente rápida nos processadores modernos, e isso será especialmente rápido, porque está multiplicando apenas dois valores de tamanho de byte.

Você poderia facilmente substituir a multiplicação pelo operador AND bit a bit ( &), que não faz avaliação de curto-circuito. Isso torna o código muito mais claro e é um padrão que os compiladores geralmente reconhecem. Mas quando você faz isso com seu código e o compila com o GCC 5.4, ele continua emitindo o primeiro ramo:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Não há nenhuma razão técnica para que ele tenha emitido o código dessa maneira, mas por alguma razão, suas heurísticas internas estão dizendo que isso é mais rápido. Ele iria provavelmente ser mais rápido se o preditor ramo estava do seu lado, mas ele provavelmente vai ser mais lento se previsão de desvios falhar mais vezes do que ele consegue.

Gerações mais recentes do compilador (e outros compiladores, como Clang) conhecem essa regra e às vezes a usam para gerar o mesmo código que você procuraria otimizando manualmente. Eu vejo regularmente Clang traduzir &&expressões para o mesmo código que seria emitido se eu tivesse usado &. A seguir, é apresentada a saída relevante do GCC 6.2 com seu código usando o &&operador normal :

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

Note como isso é inteligente ! Ele está usando condições assinadas ( jge setle) em oposição a condições não assinadas ( jae setbe), mas isso não é importante. Você pode ver que ele ainda faz a comparação e ramificação para a primeira condição, como na versão mais antiga, e usa a mesma setCCinstrução para gerar código sem ramificação para a segunda condição, mas ficou muito mais eficiente na maneira como faz o incremento . Em vez de fazer uma segunda comparação redundante para definir os sinalizadores para uma sbboperação, ele usa o conhecimento que r14dserá 1 ou 0 para simplesmente adicionar esse valor incondicionalmente nontopOverlap. Se r14dfor 0, a adição será no-op; caso contrário, ele adiciona 1, exatamente como deveria.

Na verdade, o GCC 6.2 produz um código mais eficiente quando você usa o &&operador em curto-circuito que o &operador bit a bit :

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

O ramo e o conjunto condicional ainda estão lá, mas agora ele volta para a maneira menos inteligente de incrementar nontopOverlap. Esta é uma lição importante sobre por que você deve tomar cuidado ao tentar enganar seu compilador!

Mas se você puder provar com parâmetros de referência que o código de ramificação é realmente mais lento, poderá ser útil tentar enganar seu compilador. Você só precisa fazer isso com uma inspeção cuidadosa da desmontagem - e estar preparado para reavaliar suas decisões quando atualizar para uma versão posterior do compilador. Por exemplo, o código que você possui pode ser reescrito como:

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

Não há nenhuma ifdeclaração aqui, e a grande maioria dos compiladores nunca pensará em emitir código de ramificação para isso. O GCC não é exceção; todas as versões geram algo semelhante ao seguinte:

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

Se você acompanha os exemplos anteriores, isso deve parecer muito familiar para você. Ambas as comparações são feitas sem ramificação, os resultados intermediários são andeditados juntos e, em seguida, esse resultado (que será 0 ou 1) é addeditado nontopOverlap. Se você deseja código sem ramificação, isso praticamente garantirá que você o obtenha.

O GCC 7 ficou ainda mais inteligente. Agora, ele gera código praticamente idêntico (exceto algumas pequenas reorganizações de instruções) para o truque acima como o código original. Portanto, a resposta para sua pergunta "Por que o compilador se comporta dessa maneira?" , é provavelmente porque eles não são perfeitos! Eles tentam usar heurísticas para gerar o código mais ideal possível, mas nem sempre tomam as melhores decisões. Mas pelo menos eles podem ficar mais espertos com o tempo!

Uma maneira de analisar essa situação é que o código de ramificação tem o melhor desempenho de melhor caso . Se a previsão da ramificação for bem-sucedida, pular operações desnecessárias resultará em um tempo de execução um pouco mais rápido. No entanto, o código sem ramificação tem o melhor desempenho de pior caso . Se a previsão da ramificação falhar, a execução de algumas instruções adicionais necessárias para evitar uma ramificação será definitivamente mais rápida do que uma ramificação incorreta. Até os compiladores mais inteligentes e inteligentes terão dificuldade em fazer essa escolha.

E para a sua pergunta sobre se isso é algo que os programadores precisam observar, a resposta é quase certamente não, exceto em certos loops que você está tentando acelerar por meio de micro-otimizações. Então, você se senta com a desmontagem e encontra maneiras de ajustá-la. E, como eu disse antes, esteja preparado para revisar essas decisões ao atualizar para uma versão mais recente do compilador, porque ele pode fazer algo estúpido com seu código complicado ou pode ter alterado suas heurísticas de otimização o suficiente para que você possa voltar para usar seu código original. Comente cuidadosamente!

Uma coisa importante a se notar é que

(curr[i] < 479) && (l[i + shift] < 479)

e

(curr[i] < 479) * (l[i + shift] < 479)

não são semanticamente equivalentes! Em particular, se você já teve a situação em que:

• 0 <= ie i < curr.size()são verdadeiras
• curr[i] < 479 é falso
• i + shift < 0ou i + shift >= l.size()é verdade

a expressão (curr[i] < 479) && (l[i + shift] < 479)é garantida como um valor booleano bem definido. Por exemplo, isso não causa uma falha de segmentação.

No entanto, nessas circunstâncias, a expressão (curr[i] < 479) * (l[i + shift] < 479)é comportamento indefinido ; isso é permitido para causar uma falha de segmentação.

Isso significa que, para o trecho de código original, por exemplo, o compilador não pode simplesmente escrever um loop que realiza comparações e executa uma andoperação, a menos que o compilador também possa provar que l[i + shift]nunca causará um segfault em uma situação que não é necessário.

Em resumo, o trecho de código original oferece menos oportunidades de otimização do que o último. (é claro, se o compilador reconhece ou não a oportunidade é uma questão totalmente diferente)

Você pode corrigir a versão original fazendo

bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
    // ...

O &&operador implementa a avaliação de curto-circuito. Isso significa que o segundo operando é avaliado apenas se o primeiro avaliar true. Isso certamente resulta em um salto nesse caso.

Você pode criar um pequeno exemplo para mostrar isso:

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

A saída do assembler pode ser encontrada aqui .

Você pode ver o código gerado primeiro chama f(x), depois verifica a saída e pula para a avaliação de g(x)quando isso ocorreu true. Caso contrário, sai da função.

O uso da multiplicação "booleana" força a avaliação de ambos os operandos todas as vezes e, portanto, não precisa de um salto.

Dependendo dos dados, o salto pode causar uma desaceleração porque perturba o pipeline da CPU e outras coisas, como a execução especulativa. Normalmente, a previsão de ramificação ajuda, mas se seus dados são aleatórios, não há muito que possa ser previsto.

Isso pode ocorrer porque, quando você está usando o operador lógico, &&o compilador precisa verificar duas condições para que a instrução if seja bem-sucedida. No entanto, no segundo caso, como você está implicitamente convertendo um valor int em um bool, o compilador faz algumas suposições com base nos tipos e valores que estão sendo passados, juntamente com (possivelmente) uma condição de salto único. Também é possível que o compilador otimize completamente os jmps com mudanças de bits.