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


9 Answers

Previsão ramo.

Com uma matriz classificada, os data[c] >= 128 condição data[c] >= 128 são primeiro false para uma faixa de valores e, em seguida, tornam-se true para todos os valores posteriores. Isso é fácil de prever. Com uma matriz não classificada, você paga pelo custo de ramificação.

Question

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.



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.

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



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



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ê esperou 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 assembly gerado pelo compilador, o branch condicionalbranch instruções de são inseridas.

Uma instrução de ramificação pode fazer com que um computador inicie a execução de uma sequência de instruções diferente e, assim, desvie-se de seu comportamento padrão de executar instruções em ordem (ou seja, se a expressão for falsa, o programa ignora o código do if bloco) 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 doif bloco, 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  \--------------------------------



É 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:




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 estiver 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 filial 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.




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




Uma maneira de evitar erros de previsão de ramificação é criar uma tabela de pesquisa e indexá-la usando os dados. Stefan de Bruijn discutiu isso em sua resposta.

Mas neste caso, sabemos que os valores estão no intervalo [0, 255] e nos preocupamos apenas com valores> = 128. Isso significa que podemos facilmente extrair um único bit que nos dirá se queremos ou não um valor: mudando os dados à direita 7 bits, ficamos com um bit 0 ou um bit 1, e só queremos adicionar o valor quando temos um bit 1. Vamos chamar esse bit de "bit de decisão".

Usando o valor 0/1 do bit de decisão como um índice em uma matriz, podemos criar um código que seja igualmente rápido, independentemente de os dados estarem classificados ou não. Nosso código sempre adicionará um valor, mas quando o bit de decisão for 0, adicionaremos o valor em algum lugar ao qual não nos importamos. Aqui está o código:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Esse código desperdiça metade dos adds, mas nunca tem uma falha de previsão de ramificação. É tremendamente mais rápido em dados aleatórios do que a versão com uma declaração if real.

Mas no meu teste, uma tabela de pesquisa explícita foi um pouco mais rápida do que isso, provavelmente porque a indexação em uma tabela de consulta foi ligeiramente mais rápida que a mudança de bit. Isso mostra como meu código é configurado e usa a tabela de consulta (chamada lutde "LookUp Table" no código sem imaginação ). Aqui está o código C ++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

Nesse caso, a tabela de consulta tinha apenas 256 bytes, portanto, ela se ajusta bem em um cache e tudo é rápido. Essa técnica não funcionaria bem se os dados fossem de 24 bits e nós só quiséssemos metade deles ... a tabela de consulta seria grande demais para ser prática. Por outro lado, podemos combinar as duas técnicas mostradas acima: primeiro desloque os bits e depois indexe uma tabela de pesquisa. Para um valor de 24 bits que queremos apenas o valor de metade superior, poderíamos potencialmente deslocar os dados para a direita por 12 bits e ficar com um valor de 12 bits para um índice de tabela. Um índice de tabela de 12 bits implica uma tabela de 4096 valores, o que pode ser prático.

EDIT: Uma coisa que eu esqueci de colocar dentro

A técnica de indexação em uma matriz, em vez de usar uma ifinstrução, pode ser usada para decidir qual ponteiro usar. Eu vi uma biblioteca que implementava árvores binárias e, em vez de ter dois ponteiros nomeados ( pLefte pRightou qualquer outro), tinha uma matriz de comprimento de 2 ponteiros e usava a técnica do "bit de decisão" para decidir qual deles seguir. Por exemplo, em vez de:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

essa biblioteca faria algo como:

i = (x < node->value);
node = node->link[i];

Aqui está um link para este código: Red Black Trees , Eternally Confuzzled




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 aplicações em tempo real ou sistemas embarcados, em que o tempo de execução é importante e é crítico. 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.




Related