resolvidos - preencher matriz java




Por que é mais rápido processar uma matriz classificada do que uma matriz não classificada? (14)

Aqui está uma parte do código C ++ que parece muito peculiar. Por algum motivo estranho, classificar os dados milagrosamente torna o código quase seis vezes mais rápido.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Sem std::sort(data, data + arraySize); , o código é executado em 11,54 segundos.
  • Com os dados classificados, o código é executado em 1,93 segundos.

Inicialmente, pensei que isso pudesse ser apenas uma anomalia na linguagem ou no compilador. Então eu tentei em Java.

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Com um resultado um pouco semelhante, mas menos extremo.

Meu primeiro pensamento foi que a classificação traz os dados para o cache, mas depois pensei em como isso é bobo, porque o array acabou de ser gerado.

  • O que está acontecendo?
  • Por que é mais rápido processar uma matriz classificada do que uma matriz não classificada?
  • O código está resumindo alguns termos independentes e a ordem não deve importar.

A razão pela qual o desempenho melhora drasticamente quando os dados são classificados é que a penalidade de predição do ramo é removida, como explicado lindamente na resposta do .

Agora, se olharmos para o código

if (data[c] >= 128)
    sum += data[c];

podemos descobrir que o significado dessa ramificação particular if... else... é adicionar algo quando uma condição é satisfeita. Esse tipo de ramificação pode ser facilmente transformado em uma instrução de movimento condicional , que seria compilada em uma instrução de movimento condicional: cmovl , em um sistema x86 . O ramo e, portanto, a penalidade de predição de ramificação em potencial é removida.

Em C , assim C++ , a instrução, que compilaria diretamente (sem qualquer otimização) na instrução de movimentação condicional em x86 , é o operador ternário ... ? ... : ... ... ? ... : ... Então, reescrevemos a declaração acima em uma equivalente:

sum += data[c] >=128 ? data[c] : 0;

Mantendo a legibilidade, podemos verificar o fator de aceleração.

Em um Intel Core i7 -2600K @ 3.4 GHz e no Visual Studio 2010 Release Mode, o benchmark é (formato copiado de Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

O resultado é robusto em vários testes. Temos uma grande aceleração quando o resultado da ramificação é imprevisível, mas sofremos um pouco quando é previsível. De fato, ao usar um movimento condicional, o desempenho é o mesmo, independentemente do padrão de dados.

Agora, vamos examinar mais de perto, investigando o assembly x86 que eles geram. Por simplicidade, usamos duas funções max1 e max2 .

max1 usa o ramo condicional if... else ... :

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 usa o operador ternário ... ? ... : ... ... ? ... : ... :

int max2(int a, int b) {
    return a > b ? a : b;
}

Em uma máquina x86-64, o GCC -S gera o conjunto abaixo.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 usa muito menos código devido ao uso da instrução cmovge . Mas o ganho real é que max2 não envolve saltos de ramificação, jmp , o que teria uma penalidade de desempenho significativa se o resultado previsto não estivesse correto.

Então, por que um movimento condicional tem melhor desempenho?

Em um processador x86 típico, a execução de uma instrução é dividida em vários estágios. Grosso modo, temos hardware diferente para lidar com diferentes etapas. Portanto, não temos que esperar que uma instrução termine para iniciar uma nova. Isso é chamado de pipelining .

Em um caso de filial, a instrução a seguir é determinada pela anterior, portanto, não podemos fazer pipelining. Temos que esperar ou prever.

Em um caso de movimento condicional, a instrução de movimento condicional de execução é dividida em vários estágios, mas os estágios anteriores, como Fetch e Decode , não dependem do resultado da instrução anterior; somente os últimos estágios precisam do resultado. Assim, esperamos uma fração do tempo de execução de uma instrução. É por isso que a versão de movimento condicional é mais lenta que o ramo quando a previsão é fácil.

O livro Computer Systems: A Programmer's Perspective, segunda edição explica isso em detalhes. Você pode verificar a Seção 3.6.6 para instruções de movimento condicional , todo o capítulo 4 para arquitetura de processador e a Seção 5.11.2 para um tratamento especial para penalidades de predição e de erro de ramificação .

Às vezes, alguns compiladores modernos podem otimizar nosso código para montagem com melhor desempenho, às vezes alguns compiladores não podem (o código em questão está usando o compilador nativo do Visual Studio). Conhecer a diferença de desempenho entre movimento de ramificação e condicional quando imprevisível pode nos ajudar a escrever código com melhor desempenho quando o cenário fica tão complexo que o compilador não pode otimizá-lo automaticamente.


Acabei de ler esta pergunta e suas respostas, e sinto que falta uma resposta.

Uma maneira comum de eliminar a predição de ramificação que eu encontrei para trabalhar particularmente bem em linguagens gerenciadas é uma pesquisa de tabela em vez de usar uma ramificação (embora eu não tenha testado neste caso).

Esta abordagem funciona em geral se:

  1. É uma pequena mesa e é provável que seja armazenada em cache no processador
  2. Você está executando as coisas em um loop muito apertado e / ou o processador pode pré-carregar os dados

Antecedentes e porque

Pfew, então o que diabos isso quer dizer?

Do ponto de vista do processador, sua memória é lenta. Para compensar a diferença de velocidade, eles criam alguns caches em seu processador (cache L1 / L2) que compensam isso. Então imagine que você está fazendo seus bons cálculos e descubra que precisa de um pedaço de memória. O processador obterá sua operação de 'carga' e carregará a parte da memória no cache - e, em seguida, usará o cache para fazer o restante dos cálculos. Como a memória é relativamente lenta, essa 'carga' irá desacelerar seu programa.

Como a previsão de ramificação, isso foi otimizado nos processadores Pentium: o processador prevê que precisa carregar um pedaço de dados e tenta carregá-lo no cache antes que a operação atinja o cache. Como já vimos, a predição de ramificação às vezes dá muito errado - no pior cenário você precisa voltar e realmente aguardar uma carga de memória, o que levará uma eternidade ( em outras palavras: a predição de ramificação falho é ruim, uma memória carregar depois de uma falha de previsão de filial é simplesmente horrível! ).

Felizmente para nós, se o padrão de acesso à memória for previsível, o processador irá carregá-lo em seu cache rápido e tudo estará bem.

A primeira coisa que precisamos saber é o que é pequeno ? Enquanto menor geralmente é melhor, uma regra é ficar com tabelas de pesquisa que são de tamanho <= 4096 bytes. Como limite superior: se sua tabela de consulta for maior que 64 K, provavelmente vale a pena reconsiderar.

Construindo uma mesa

Então descobrimos que podemos criar uma pequena mesa. A próxima coisa a fazer é obter uma função de pesquisa no local. As funções de pesquisa são geralmente pequenas funções que usam um par de operações inteiras básicas (e, ou, xor, shift, add, remove e talvez multiplique). Você quer que sua entrada seja traduzida pela função de pesquisa para algum tipo de 'chave única' em sua tabela, que simplesmente lhe dá a resposta de todo o trabalho que você queria que ela fizesse.

Neste caso:> = 128 significa que podemos manter o valor, <128 significa que nos livramos dele. A maneira mais fácil de fazer isso é usando um 'AND': se continuarmos, nós AND it with 7FFFFFFF; se quisermos nos livrar disso, nós AND com 0. Observe também que 128 é uma potência de 2 - então podemos ir adiante e fazer uma tabela de 32768/128 inteiros e preenchê-la com um zero e muitos 7FFFFFFFF.

Idiomas gerenciados

Você pode se perguntar por que isso funciona bem em idiomas gerenciados. Afinal, os idiomas gerenciados verificam os limites dos arrays com um branch para garantir que você não atrapalhe ...

Bem, não exatamente ... :-)

Houve algum trabalho na eliminação dessa ramificação para idiomas gerenciados. Por exemplo:

for (int i=0; i<array.Length; ++i)
   // Use array[i]

Nesse caso, é óbvio para o compilador que a condição de limite nunca será atingida. Pelo menos o compilador Microsoft JIT (mas espero que o Java faça coisas semelhantes) irá notar isso e remover a verificação completamente. WOW - isso significa que não há ramo. Da mesma forma, lidará com outros casos óbvios.

Se você tiver problemas com pesquisas em idiomas gerenciados - a chave é adicionar um & 0x[something]FFF com o & 0x[something]FFF à sua função de pesquisa para tornar a verificação de limite previsível - e vê-lo ir mais rápido.

O resultado deste caso

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();

Se você está curioso sobre ainda mais otimizações que podem ser feitas para este código, considere isto:

Começando com o loop original:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Com o intercâmbio de loops, podemos alterar este loop com segurança para:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Então, você pode ver que a condicional if é constante durante a execução do loop i , assim você pode içar o if out:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Então, você vê que o loop interno pode ser recolhido em uma única expressão, assumindo que o modelo de ponto flutuante permite (/ fp: fast é lançado, por exemplo)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Aquele é 100.000x mais rápido que antes


Ganho de previsão de ramificação!

É importante entender que a má interpretação das agências não diminui a velocidade dos programas. O custo de uma previsão perdida é como se a predição da ramificação não existisse e você esperasse pela avaliação da expressão para decidir qual código executar (mais explicações no próximo parágrafo).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Sempre que há um if-else\ switchdeclaração, a expressão tem de ser avaliado para determinar qual bloco deve ser executado. No código de montagem gerado pelo compilador, instruções de branch condicional são inseridas.

Uma instrução de ramificação pode fazer com que um computador comece a executar uma sequência de instruções diferente e assim desviar do comportamento padrão de executar instruções em ordem (ou seja, se a expressão for falsa, o programa ignora o código do ifbloco) dependendo de alguma condição, que é a avaliação de expressão no nosso caso.

Dito isto, o compilador tenta prever o resultado antes de ele ser realmente avaliado. Ele irá buscar instruções do ifbloco, e se a expressão se mostrar verdadeira, então maravilhoso! Ganhamos o tempo necessário para avaliá-lo e fizemos progresso no código; se não, então estamos executando o código errado, o pipeline é liberado e o bloco correto é executado.

Visualização:

Digamos que você precise escolher a rota 1 ou a rota 2. Esperando pelo seu parceiro para verificar o mapa, você parou na ## e esperou, ou você pode escolher a rota1 e se tiver sorte (a rota 1 é a rota correta), então ótimo você não ter que esperar pelo seu parceiro para verificar o mapa (você salvou o tempo que teria levado para verificar o mapa), caso contrário, você só vai voltar atrás.

Embora o fluxo de dutos seja super rápido, hoje vale a pena aproveitar essa aposta. A previsão de dados classificados ou de dados que mudam lentamente é sempre mais fácil e melhor do que prever mudanças rápidas.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

Você é uma vítima da falha na previsão de ramificação .

O que é a previsão de ramificação?

Considere um entroncamento ferroviário:

de Mecanismo, via Wikimedia Commons. Usado sob a licença CC-By-SA 3.0 .

Agora, por uma questão de argumento, suponha que isso esteja de volta nos anos de 1800 - antes de longa distância ou de comunicação por rádio.

Você é o operador de um entroncamento e ouve um trem chegando. Você não tem ideia do caminho que deve seguir. Você pára o trem para perguntar ao motorista qual direção eles querem. E então você ajusta o switch apropriadamente.

Os trens são pesados ​​e têm muita inércia. Então eles levam uma eternidade para começar e desacelerar.

Existe uma maneira melhor? Você adivinha para qual direção o trem irá!

  • Se você adivinhou certo, continua.
  • Se você adivinhou errado, o capitão irá parar, recuar e gritar para você ligar o interruptor. Então, ele pode reiniciar o outro caminho.

Se você acertar todas as vezes , o trem nunca terá que parar.
Se você errar com muita frequência , o trem passará muito tempo parando, fazendo backup e reiniciando.

Considere uma declaração if: No nível do processador, é uma instrução de ramificação:

Você é um processador e vê um ramo. Você não tem idéia do caminho que vai seguir. O que você faz? Você interrompe a execução e aguarda até que as instruções anteriores sejam concluídas. Então você continua no caminho correto.

Os processadores modernos são complicados e possuem longos pipelines. Então eles levam uma eternidade para "aquecer" e "desacelerar".

Existe uma maneira melhor? Você adivinha qual direção o ramo irá!

  • Se você adivinhou certo, você continua executando.
  • Se você adivinhou errado, precisará liberar o pipeline e voltar ao ramo. Então você pode reiniciar o outro caminho.

Se você acertar todas as vezes , a execução nunca terá que parar.
Se você errar com muita frequência , você gasta muito tempo atrasando, retrocedendo e reiniciando.

Esta é a previsão de ramos. Admito que não é a melhor analogia, já que o trem poderia apenas sinalizar a direção com uma bandeira. Mas nos computadores, o processador não sabe em que direção um ramo vai até o último momento.

Então, como você acharia estrategicamente minimizar o número de vezes que o trem deve recuar e descer pelo outro caminho? Você olha para o passado! Se o trem for para a esquerda 99% do tempo, então você adivinhou à esquerda. Se alterna, você alterna suas suposições. Se for para um lado a cada 3 vezes, você adivinha o mesmo ...

Em outras palavras, você tenta identificar um padrão e segui-lo. Isso é mais ou menos como os preditores de ramos funcionam.

A maioria dos aplicativos tem ramificações bem comportadas. Portanto, os preditores modernos das agências geralmente atingem taxas de acerto> 90%. Mas quando confrontados com ramos imprevisíveis sem padrões reconhecíveis, os preditores das agências são praticamente inúteis.

Leitura adicional: artigo "Preditor de filiais" na Wikipedia .

Como sugerido acima, o culpado é esta afirmação:

if (data[c] >= 128)
    sum += data[c];

Observe que os dados são distribuídos uniformemente entre 0 e 255. Quando os dados são classificados, aproximadamente a primeira metade das iterações não entrará na instrução if. Depois disso, todos eles entrarão na declaração if.

Isso é muito amigável para o preditor da ramificação, já que a ramificação vai consecutivamente na mesma direção várias vezes. Mesmo um simples contador de saturação irá predizer corretamente o ramo, exceto pelas poucas iterações após ele mudar de direção.

Visualização rápida:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

No entanto, quando os dados são completamente aleatórios, o preditor da ramificação é inutilizado porque não pode prever dados aleatórios. Assim, provavelmente haverá cerca de 50% de erros de interpretação. (não melhor que adivinhação aleatória)

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

Então, o que pode ser feito?

Se o compilador não é capaz de otimizar o ramo em um movimento condicional, você pode tentar alguns hacks se você estiver disposto a sacrificar a legibilidade para o desempenho.

Substituir:

if (data[c] >= 128)
    sum += data[c];

com:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Isso elimina a ramificação e a substitui por algumas operações bit a bit.

(Note que este hack não é estritamente equivalente à declaração if original. Mas, neste caso, é válido para todos os valores de entrada de data[] .)

Benchmarks: Core i7 920 a 3,5 GHz

C ++ - Visual Studio 2010 - versão x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Observações:

  • Com o Branch: Existe uma enorme diferença entre os dados classificados e não classificados.
  • Com o Hack: Não há diferença entre dados classificados e não classificados.
  • No caso do C ++, o hack é realmente um pouco mais lento do que com o branch quando os dados são classificados.

Uma regra geral é evitar a ramificação dependente de dados em loops críticos. (como neste exemplo)

Atualizar:

  • O GCC 4.6.1 com -O3 ou -ftree-vectorize no x64 é capaz de gerar um movimento condicional. Portanto, não há diferença entre os dados classificados e não classificados - ambos são rápidos.

  • O VC ++ 2010 não pode gerar movimentos condicionais para essa ramificação, mesmo em /Ox .

  • O Intel Compiler 11 faz algo milagroso. Ele intercala os dois loops , elevando assim o ramo imprevisível ao loop externo. Portanto, ele não apenas é imune a interpretações errôneas, mas também é duas vezes mais rápido do que o que o VC ++ e o GCC podem gerar! Em outras palavras, o ICC aproveitou o loop de teste para derrotar o benchmark ...

  • Se você der ao Compiler da Intel o código sem ramificação, ele apenas o vetoriza para a direita ... e é tão rápido quanto com a ramificação (com o intercâmbio de loop).

Isso mostra que mesmo os compiladores modernos maduros podem variar muito em sua capacidade de otimizar o código ...


Além do fato de que a previsão de ramificação pode atrasá-lo, uma matriz ordenada tem outra vantagem:

Você pode ter uma condição de parada, em vez de apenas verificar o valor, dessa forma, você apenas executa um loop sobre os dados relevantes e ignora o restante.
A previsão do ramo falhará apenas uma vez.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

Matrizes ordenadas são processadas mais rapidamente do que uma matriz não classificada, devido a fenômenos chamados de predição de ramificação.

O preditor de filiais é um circuito digital (na arquitetura de computadores) que tenta prever para que lado uma ramificação funcionará, melhorando o fluxo no pipeline de instruções. O circuito / computador prevê o próximo passo e o executa.

Fazer uma previsão incorreta leva a voltar ao passo anterior e a executar com outra previsão. Supondo que a previsão esteja correta, o código continuará na próxima etapa. A previsão incorreta resulta na repetição da mesma etapa, até que ocorra a previsão correta.

A resposta para sua pergunta é muito simples.

Em uma matriz não classificada, o computador faz várias previsões, levando a uma maior chance de erros. Considerando que, em classificados, o computador faz menos previsões reduzindo a chance de erros. Fazer mais previsão requer mais tempo.

Array sortido: estrada reta

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Array não sorteado: Curved Road

______   ________
|     |__|

Previsão de filiais: adivinhando / prevendo qual estrada é reta e seguindo sem verificação

___________________________________________ Straight road
 |_________________________________________|Longer road

Embora ambas as estradas cheguem ao mesmo destino, a estrada reta é mais curta e a outra é mais longa. Se então você escolher o outro por engano, não há como voltar atrás, e assim você perderá algum tempo extra se escolher a estrada mais longa. Isso é semelhante ao que acontece no computador e espero que isso o ajude a entender melhor.

Update: Depois do que o @Simon_Weaver disse, eu quero adicionar outro fato que ... "ele não faz menos previsões - ele faz menos predições incorretas. Ele ainda tem que prever cada vez através do loop."


Na mesma linha (acho que isso não foi destacado por nenhuma resposta) é bom mencionar que às vezes (especialmente no software em que o desempenho é importante - como no kernel do Linux) você pode encontrar algumas instruções if como as seguintes:

if (likely( everything_is_ok ))
{
    /* Do something */
}

ou similarmente:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Ambos likely()e unlikely()são, de fato, macros que são definidas usando algo como o GCC __builtin_expectpara ajudar o compilador a inserir o código de previsão para favorecer a condição, levando em consideração as informações fornecidas pelo usuário. O GCC suporta outros recursos internos que podem alterar o comportamento do programa em execução ou emitir instruções de baixo nível, como limpar o cache, etc. Consulte esta documentação que acessa os builtins do GCC disponíveis.

Normalmente, esse tipo de otimização é encontrado principalmente em aplicativos em tempo real ou sistemas incorporados, em que o tempo de execução é importante e é essencial. Por exemplo, se você está verificando alguma condição de erro que só ocorre 1/10000000 vezes, por que não informar o compilador sobre isso? Dessa forma, por padrão, a previsão de ramificação assumiria que a condição é falsa.


O comportamento acima está acontecendo por causa da previsão Branch.

Para entender a previsão de ramos, é preciso primeiro entender o Pipeline de Instrução :

Qualquer instrução é dividida em uma sequência de etapas para que etapas diferentes possam ser executadas simultaneamente em paralelo. Essa técnica é conhecida como pipeline de instruções e é usada para aumentar o rendimento em processadores modernos. Para entender melhor, por favor, veja este exemplo na Wikipedia .

Geralmente, os processadores modernos têm pipelines bastante longos, mas para facilitar, vamos considerar apenas esses 4 passos.

  1. IF - Buscar a instrução da memória
  2. ID - decodifica a instrução
  3. EX - Execute a instrução
  4. WB - Escreva de volta ao registrador da CPU

Pipeline de 4 estágios em geral para 2 instruções.

Voltando à questão acima, vamos considerar as seguintes instruções:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Sem previsão de ramificação, ocorreria o seguinte:

Para executar a instrução B ou a instrução C, o processador terá que esperar até que a instrução A não atinja o estágio EX na tubulação, já que a decisão de ir para a instrução B ou instrução C depende do resultado da instrução A. Assim, o pipeline vai ficar assim.

quando a condição retornar true:

Quando a condição retornar false:

Como resultado da espera pelo resultado da instrução A, o total de ciclos de CPU gastos no caso acima (sem predição de ramificação; para true e false) é 7.

Então, o que é predição de ramo?

O preditor de ramificação tentará adivinhar de que maneira uma ramificação (uma estrutura if-then-else) irá antes que isso seja conhecido com certeza. Ele não irá esperar pela instrução A para alcançar o estágio EX do pipeline, mas irá adivinhar a decisão e ir para aquela instrução (B ou C no caso do nosso exemplo).

No caso de um palpite correto, o pipeline é algo como isto:

Se mais tarde for detectado que o palpite estava errado, as instruções parcialmente executadas serão descartadas e o pipeline começará novamente com a ramificação correta, incorrendo em um atraso. O tempo desperdiçado no caso de um erro de desvio da ramificação é igual ao número de estágios no pipeline do estágio de busca para o estágio de execução. Microprocessadores modernos tendem a ter pipelines muito longos, de modo que o atraso de erros é de 10 a 20 ciclos de clock. Quanto maior o pipeline, maior a necessidade de um bom preditor de ramificação .

No código do OP, na primeira vez quando o condicional, o preditor de ramificação não tem nenhuma informação para basear a previsão, então a primeira vez que ele irá escolher aleatoriamente a próxima instrução. Posteriormente no loop for, ele pode basear a previsão no histórico. Para um array classificado em ordem crescente, existem três possibilidades:

  1. Todos os elementos são menores que 128
  2. Todos os elementos são maiores que 128
  3. Alguns novos elementos iniciais são menores que 128 e mais tarde se tornam maiores que 128

Vamos supor que o preditor sempre assumirá a ramificação verdadeira na primeira execução.

Assim, no primeiro caso, sempre terá o ramo verdadeiro, já que historicamente todas as previsões estão corretas. No segundo caso, inicialmente ele irá prever errado, mas depois de algumas iterações, ele irá prever corretamente. No terceiro caso, ele será inicialmente previsto corretamente até que os elementos sejam menores que 128. Depois disso, ele falhará por algum tempo e o próprio corrigirá quando houver uma falha na previsão de ramificação no histórico.

Em todos esses casos, a falha será em número muito menor e, como resultado, apenas algumas vezes será necessário descartar as instruções parcialmente executadas e começar novamente com a ramificação correta, resultando em menos ciclos de CPU.

Mas, no caso de um arranjo aleatório não ordenado, a previsão precisará descartar as instruções parcialmente executadas e começar de novo com o ramo correto na maior parte do tempo e resultar em mais ciclos de CPU em comparação com o array ordenado.


Uma resposta oficial seria de

  1. Intel - evitando o custo de erros de ramificação
  2. Intel - Reorganização de filiais e loops para evitar erros
  3. Artigos científicos - arquitetura do computador de predição de ramos
  4. Livros: JL Hennessy, DA Patterson: Arquitetura de computadores: uma abordagem quantitativa
  5. Artigos em publicações científicas: TY Yeh, YN Patt fez muito disso nas previsões das agências.

Você também pode ver neste belo diagram porque o preditor de ramificação fica confuso.

Cada elemento no código original é um valor aleatório

data[c] = std::rand() % 256;

então o preditor mudará de lado como o std::rand()golpe.

Por outro lado, uma vez ordenado, o preditor primeiro se moverá para um estado de não fortemente adotado e quando os valores mudarem para o valor alto, o preditor irá, em três execuções, mudar de fortemente não levado para fortemente tomado.


Como o que já foi mencionado por outros, o que está por trás do mistério é o Predictor Branch .

Eu não estou tentando adicionar algo, mas explicando o conceito de outra maneira. Há uma introdução concisa no wiki que contém texto e diagrama. Eu gosto da explicação abaixo que usa um diagrama para elaborar o Preditor de Filial intuitivamente.

Na arquitetura de computadores, um preditor de ramificação é um circuito digital que tenta adivinhar de que maneira uma ramificação (por exemplo, uma estrutura if-then-else) irá antes que isso seja conhecido com certeza. O objetivo do preditor de ramificação é melhorar o fluxo no pipeline de instruções. Os preditores de filiais desempenham um papel crítico na obtenção de alto desempenho efetivo em muitas arquiteturas modernas de microprocessadores com pipelines, como o x86.

A ramificação bidirecional geralmente é implementada com uma instrução de salto condicional. Um salto condicional pode ser "não tomado" e continuar a execução com o primeiro ramo de código que segue imediatamente após o salto condicional, ou pode ser "levado" e saltar para um lugar diferente na memória de programação onde o segundo ramo de código é armazenado. Não se sabe ao certo se um salto condicional será tomado ou não até que a condição tenha sido calculada e o salto condicional tenha passado pelo estágio de execução no pipeline de instruções (veja a figura 1).

Com base no cenário descrito, escrevi uma demonstração de animação para mostrar como as instruções são executadas em um pipeline em diferentes situações.

  1. Sem o Preditor de Filial.

Sem previsão de ramificação, o processador teria que esperar até que a instrução de salto condicional passasse pelo estágio de execução antes que a próxima instrução pudesse entrar no estágio de busca no pipeline.

O exemplo contém três instruções e a primeira é uma instrução de salto condicional. As duas últimas instruções podem entrar no pipeline até que a instrução de salto condicional seja executada.

Serão necessários 9 ciclos de clock para que 3 instruções sejam concluídas.

  1. Use o Preditor de Ramificação e não faça um salto condicional. Vamos supor que a previsão não esteja dando o salto condicional.

Vai levar 7 ciclos de clock para 3 instruções a serem concluídas.

  1. Use o Preditor de Ramificação e faça um salto condicional. Vamos supor que a previsão não esteja dando o salto condicional.

Serão necessários 9 ciclos de clock para que 3 instruções sejam concluídas.

O tempo desperdiçado no caso de um erro de desvio da ramificação é igual ao número de estágios no pipeline do estágio de busca para o estágio de execução. Microprocessadores modernos tendem a ter pipelines muito longos, de modo que o atraso de erros é de 10 a 20 ciclos de clock. Como resultado, fazer um pipeline aumenta a necessidade de um preditor de ramificação mais avançado.

Como você pode ver, parece que não temos uma razão para não usar o Predictor de Ramificação.

É uma demonstração bastante simples que esclarece a parte básica do Predictor de Ramificação. Se esses gifs são irritantes, sinta-se à vontade para removê-los da resposta e os visitantes também podem obter a demonstração do git


Como os dados são distribuídos entre 0 e 255 quando a matriz é classificada, a primeira metade das iterações não entrará na ifdeclaração (a ifinstrução é compartilhada abaixo).

if (data[c] >= 128)
    sum += data[c];

A questão é: O que faz com que a declaração acima não seja executada em certos casos, como no caso de dados ordenados? Aí vem o "preditor da ramificação". Um preditor de ramificação é um circuito digital que tenta adivinhar de que maneira uma ramificação (por exemplo, uma if-then-elseestrutura) irá antes que isso seja conhecido com certeza. O objetivo do preditor de ramificação é melhorar o fluxo no pipeline de instruções. Preditores de filiais desempenham um papel crítico na obtenção de alto desempenho efetivo!

Vamos fazer algumas marcações para entender melhor

O desempenho de uma ifdeclaração depende de sua condição ter um padrão previsível. Se a condição for sempre verdadeira ou sempre falsa, a lógica de previsão de ramificação no processador selecionará o padrão. Por outro lado, se o padrão for imprevisível, a ifdeclaração será muito mais cara.

Vamos medir o desempenho desse loop com diferentes condições:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Aqui estão os tempos do loop com diferentes padrões verdadeiro-falso:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

A “ ” verdadeiro ou falso padrão pode fazer uma if-Declaração até seis vezes mais lento do que um “ bom ” padrão! É claro que o padrão é bom e o que é ruim depende das instruções exatas geradas pelo compilador e no processador específico.

Portanto, não há dúvidas sobre o impacto da previsão de ramos no desempenho!


No ARM, não há ramificação necessária, porque toda instrução tem um campo de condição de 4 bits, que é testado com custo zero. Isso elimina a necessidade de ramificações curtas e não haveria previsão de ramificação. Portanto, a versão classificada seria executada mais lentamente do que a versão não classificada no ARM, devido à sobrecarga extra de classificação. O loop interno seria algo como o seguinte:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

Operações Booleanas freqüentemente usadas em C ++ produzem muitas ramificações no programa compilado. Se esses ramos estão dentro de loops e são difíceis de prever, eles podem retardar a execução significativamente. As variáveis ​​booleanas são armazenadas como inteiros de 8 bits com o valor 0for falsee 1for true.

Variáveis booleanas são sobredeterminadas no sentido de que todos os operadores que têm variáveis booleanas como verificação de entrada se as entradas têm um valor diferente 0ou 1, mas operadores que têm Booleans como saída pode produzir nenhum outro valor do que 0ou 1. Isso torna as operações com variáveis ​​booleanas como entradas menos eficientes que o necessário. Considere o exemplo:

bool a, b, c, d;
c = a && b;
d = a || b;

Isso geralmente é implementado pelo compilador da seguinte maneira:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Este código está longe de ser ideal. Os ramos podem demorar muito tempo em caso de erros de interpretação. As operações booleanas podem se tornar muito mais eficientes se for conhecido com certeza que os operandos não possuem outros valores além de 0e 1. A razão pela qual o compilador não faz tal suposição é que as variáveis ​​podem ter outros valores se não forem inicializadas ou vierem de fontes desconhecidas. O código acima pode ser otimizado se ae bfoi inicializado para valores válidos ou se eles vierem de operadores que produzem saída booleana. O código otimizado se parece com isso:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charé usado em vez de boolpara tornar possível usar os operadores bit a bit ( &e |) em vez dos operadores booleanos ( &&e ||). Os operadores bit a bit são instruções únicas que levam apenas um ciclo de clock. O operador OR ( |) funciona mesmo se ae btiver outros valores que 0ou 1. O operador AND ( &) e o operador EXCLUSIVE OR ( ^) podem fornecer resultados inconsistentes se os operandos tiverem outros valores que 0e 1.

~não pode ser usado para NOT. Em vez disso, você pode fazer um NOT booleano em uma variável que é conhecida por ser 0ou 1por XOR'ing-lo com 1:

bool a, b;
b = !a;

pode ser otimizado para:

char a = 0, b;
b = a ^ 1;

a && bnão pode ser substituído por a & bif bé uma expressão que não deve ser avaliada se aé false( &&não irá avaliar b, &irá). Da mesma forma, a || bnão pode ser substituído por a | bse bé uma expressão que não deve ser avaliada se afor true.

A utilização de operadores bit a bit é mais vantajosa se os operandos forem variáveis ​​do que se os operandos forem comparações:

bool a; double x, y, z;
a = x > y && z < 5.0;

é ideal na maioria dos casos (a menos que você espere que a &&expressão gere muitos erros de desvio).





branch-prediction