java matrizes - Por que é mais rápido processar uma matriz classificada do que uma matriz não classificada?




exercicios resolvidos (18)

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.

Answers

Isso é certeza!...

A predição de ramificação faz a lógica ficar mais lenta, por causa da comutação que acontece no seu código! É como se você estivesse indo para uma rua reta ou para uma rua com muitas curvas, com certeza a linha reta seria feita mais rápido! ...

Se a matriz é classificada, sua condição é falsa na primeira etapa data[c] >= 128:, então se torna um valor verdadeiro para todo o caminho até o final da rua. É assim que você chega ao final da lógica mais rápido. Por outro lado, usando um arranjo não ordenado, você precisa de muita conversão e processamento, o que faz com que seu código fique mais lento, com certeza ...

Veja a imagem que criei para você abaixo. Qual rua será terminada mais rapidamente?

Então, programaticamente, a previsão de ramificação faz com que o processo seja mais lento ...

Também no final, é bom saber que temos dois tipos de previsões de ramificação, cada uma afetando seu código de maneira diferente:

1. Estático

2. Dinâmico

A predição de ramificação estática é usada pelo microprocessador na primeira vez que uma ramificação condicional é encontrada, e a predição de ramificação dinâmica é usada para execuções sucedidas do código de ramificação condicional.

Para efetivamente escrever seu código para aproveitar essas regras, ao escrever if-else ou switch , verifique os casos mais comuns primeiro e trabalhe progressivamente até o mínimo comum. Loops não requerem necessariamente qualquer ordenação especial de código para predição de ramificação estática, pois somente a condição do iterador de loop é normalmente usada.


No caso classificado, você pode fazer melhor do que depender de uma previsão de ramificação bem-sucedida ou de um truque de comparação sem ramificação: remover completamente a ramificação.

De fato, o array é particionado em uma zona contígua com data < 128e outra com data >= 128. Portanto, você deve encontrar o ponto de partição com uma pesquisa dicotômica (usando Lg(arraySize) = 15comparações) e, em seguida, fazer um acúmulo direto a partir desse ponto.

Algo parecido (não verificado)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

ou, um pouco mais ofuscado

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Uma abordagem ainda mais rápida, que fornece uma solução aproximada para ordenada ou não classificada é: sum= 3137536;(supondo uma distribuição verdadeiramente uniforme, 16384 amostras com valor esperado 191.5) :-)


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


É sobre previsão de ramos. O que é isso?

  • Um preditor de ramificação é uma das antigas técnicas de aprimoramento de desempenho que ainda encontra relevância nas arquiteturas modernas. Embora as técnicas simples de previsão forneçam pesquisa rápida e eficiência de energia, elas sofrem com uma alta taxa de erros de previsão.

  • Por outro lado, predições complexas de ramificação - baseadas em neural ou variantes de predição de dois níveis - fornecem melhor precisão de previsão, mas consomem mais energia e a complexidade aumenta exponencialmente.

  • Além disso, em técnicas complexas de predição, o tempo necessário para prever os ramos é, ele próprio, muito alto - de 2 a 5 ciclos - o que é comparável ao tempo de execução dos ramos reais.

  • A predição de filial é essencialmente um problema de otimização (minimização) onde a ênfase está em atingir a menor taxa de falhas possível, baixo consumo de energia e baixa complexidade com recursos mínimos.

Existem realmente três tipos diferentes de ramificações:

Ramais condicionais de encaminhamento - com base em uma condição de tempo de execução, o PC (contador de programa) é alterado para apontar para um encaminhamento de endereço no fluxo de instruções.

Ramificações condicionais retrógradas - o PC é alterado para apontar para trás no fluxo de instruções. A ramificação é baseada em alguma condição, como a ramificação para trás, até o início de um loop de programa, quando um teste no final do loop informa que o loop deve ser executado novamente.

Ramificações Incondicionais - isso inclui saltos, chamadas de procedimento e retornos sem condições específicas. Por exemplo, uma instrução de salto incondicional pode ser codificada em assembly como simplesmente "jmp", e o fluxo de instrução deve ser imediatamente direcionado para o local de destino apontado pela instrução de salto, enquanto um salto condicional que pode ser codificado como "jmpne" redirecionaria o fluxo de instrução somente se o resultado de uma comparação de dois valores em uma instrução de "comparação" anterior mostrasse que os valores não são iguais. (O esquema de endereçamento segmentado usado pela arquitetura x86 adiciona complexidade extra, já que os saltos podem ser "próximos" (dentro de um segmento) ou "longe" (fora do segmento). Cada tipo tem efeitos diferentes nos algoritmos de predição de ramos.

Predição de Ramificação Estática / Dinâmica : A predição de ramificação estática é usada pelo microprocessador na primeira vez que uma ramificação condicional é encontrada e a predição de ramificação dinâmica é usada para execuções sucedidas do código de ramificação condicional.

Referências:


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.


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).


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

Esta questão já foi respondida excelentemente muitas vezes. Ainda assim, gostaria de chamar a atenção do grupo para mais uma análise interessante.

Recentemente, este exemplo (modificado muito ligeiramente) também foi usado como uma maneira de demonstrar como um pedaço de código pode ser perfilado dentro do próprio programa no Windows. Ao longo do caminho, o autor também mostra como usar os resultados para determinar onde o código está gastando a maior parte do tempo no caso classificado e não classificado. Finalmente, a peça também mostra como usar um recurso pouco conhecido do HAL (Camada de Abstração de Hardware) para determinar o quanto de desvio de ramificação está ocorrendo no caso não classificado.

O link está aqui: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm


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();

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."


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];               
 }

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.


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  \--------------------------------

Não há dúvida de que alguns de nós estariam interessados ​​em identificar o código que é problemático para o preditor de ramificação da CPU. O cachegrind ferramenta Valgrind possui um simulador de preditor de ramificação, ativado usando o --branch-sim=yes . Executá-lo sobre os exemplos nesta questão, com o número de loops externos reduzido para 10000 e compilado com g++ , fornece os seguintes resultados:

Ordenado:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Não triados:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

cg_annotate saída linha por linha produzida pelo cg_annotate , vemos o loop em questão:

Ordenado:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Não triados:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

Isso permite identificar facilmente a linha problemática - na versão não classificada, a linha if (data[c] >= 128) está causando 164.050.007 ramificações condicionais com Bcm ( Bcm ) no modelo preditor de ramificação do cachegrind, enquanto está causando apenas 10.006 na versão classificada .

Como alternativa, no Linux, você pode usar o subsistema de contadores de desempenho para realizar a mesma tarefa, mas com desempenho nativo usando contadores de CPU.

perf stat ./sumtest_sorted

Ordenado:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Não triados:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

Também pode fazer anotações de código fonte com dissassembly.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Veja o tutorial de desempenho para mais detalhes.


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.


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


O LINQ não sabe se a sua lista está ordenada ou não.

Como o parâmetro Count with predicate é o método de extensão para todos os IEnumerables, acho que ele nem sabe se está sendo executado na coleção com acesso aleatório eficiente. Então, ele simplesmente verifica cada elemento e o Usr explicou por que o desempenho diminuiu.

Para explorar os benefícios de desempenho do array ordenado (como a pesquisa binária), você terá que fazer um pouco mais de codificação.





java c++ performance optimization branch-prediction