Por que o processamento de uma matriz classificada é mais rápido que o processamento de uma matriz não classificada?

Aqui está um pedaço de código C ++ que mostra um comportamento 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 poderia ser apenas uma anomalia de linguagem ou compilador, então tentei o 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 semelhante, mas menos extremo.

Meu primeiro pensamento foi que a classificação traz os dados para o cache, mas depois pensei em como isso era bobo porque a matriz era apenas gerada.

• O que está acontecendo?
• Por que o processamento de uma matriz classificada é mais rápido que o processamento de uma matriz não classificada?

O código está resumindo alguns termos independentes, portanto, o pedido não deve importar.

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

O que é Previsão de Filial?

Considere um entroncamento ferroviário:

_{Imagem de Mecanismo, via Wikimedia Commons. Usado sob o CC-By-SA 3.0 .}

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

Você é o operador de um cruzamento e ouve um trem chegando. Você não tem idéia de qual caminho deve seguir. Você para o trem para perguntar ao motorista qual direção eles querem. E então você define o interruptor adequadamente.

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

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

• Se você adivinhou certo, continua.
• Se você adivinhou errado, o capitão irá parar, recuar e gritar com você para apertar o botão. Em seguida, ele pode reiniciar no outro caminho.

Se você acertar sempre , o trem nunca terá que parar.
Se você adivinhar errado com muita frequência , o trem passará muito tempo parando, fazendo backup e reiniciando.

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

Você é um processador e vê uma ramificação. Você não tem idéia de qual caminho 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 têm pipelines longos. Então eles levam uma eternidade para "aquecer" e "desacelerar".

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

• Se você acertou, continua executando.
• Se você adivinhou errado, precisa liberar o oleoduto e reverter para o ramo. Em seguida, você pode reiniciar no outro caminho.

Se você acertar sempre , a execução nunca terá que parar.
Se você adivinhar errado com muita frequência , passa muito tempo parando, revertendo e reiniciando.

Esta é a previsão do ramo. Admito que não é a melhor analogia, já que o trem pode apenas sinalizar a direção com uma bandeira. Mas em computadores, o processador não sabe em qual direção uma ramificação irá até o último momento.

Então, como você adivinharia estrategicamente minimizar o número de vezes que o trem deve recuar e seguir o outro caminho? Você olha para a história passada! Se o trem sai à esquerda 99% das vezes, você acha que saiu. Se alternar, você alterna suas suposições. Se seguir um caminho a cada três vezes, você adivinha o mesmo ...

Em outras palavras, você tenta identificar um padrão e segui-lo.É mais ou menos assim que os preditores de ramificações funcionam.

A maioria dos aplicativos possui ramificações bem comportadas. Assim, os preditores modernos de agências normalmente atingem taxas de acerto> 90%. Porém, quando confrontados com ramificações imprevisíveis sem padrões reconhecíveis, os preditores de ramificação são praticamente inúteis.

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

Como sugerido acima, o culpado é esta declaração if:

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

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

Isso é muito amigável com o preditor de ramificação, pois a ramificação consecutivamente segue a mesma direção várias vezes. Mesmo um simples contador de saturação preverá corretamente a ramificação, exceto as poucas iterações após a troca 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 de ramificação é inútil, porque não pode prever dados aleatórios. Portanto, provavelmente haverá cerca de 50% de erros de previsão (nada melhor do que suposições aleatórias).

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 puder otimizar a ramificação em uma movimentação condicional, você poderá tentar alguns hacks se desejar sacrificar a legibilidade pelo 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.

_{(Observe que esse hack não é estritamente equivalente à instruçã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 a ramificação: há 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 é na verdade um pouco mais lento do que na ramificação quando os dados são classificados.

Uma regra geral é evitar ramificações dependentes de dados em loops críticos (como neste exemplo).

Atualizar:

• O GCC 4.6.1 com -O3ou -ftree-vectorizeno x64 pode gerar uma movimentação condicional. Portanto, não há diferença entre os dados classificados e os não classificados - ambos são rápidos.

  (Ou um pouco rápido: para o caso já classificado, cmovpode ser mais lento, especialmente se o GCC o colocar no caminho crítico, e não apenas add, especialmente na Intel antes da Broadwell, onde cmovhá latência de 2 ciclos: sinalizador de otimização do gcc -O3 torna o código mais lento que -O2 )

• O VC ++ 2010 não pode gerar movimentos condicionais para esse ramo, mesmo em /Ox.

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

• Se você der ao compilador Intel o código sem ramificação, ele o vetoriza com 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 ...

Previsão de ramificação.

Com uma matriz classificada, a condição data[c] >= 128é a primeira falsepara uma sequência de valores e depois truepara todos os valores posteriores. É fácil de prever. Com uma matriz não classificada, você paga pelo custo da ramificação.

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

Agora, se olharmos para o código

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

podemos descobrir que o significado desse if... else...ramo específico é adicionar algo quando uma condição é satisfeita. Esse tipo de ramificação pode ser facilmente transformado em uma instrução de movimentação condicional , que seria compilada em uma instrução de movimentação condicional:, cmovlem um x86sistema. A ramificação e, portanto, a penalidade de previsão de ramificação potencial são removidas.

Em C, assim C++, a declaração, que compile diretamente (sem qualquer optimization) para a 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;

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

Nos modos de lançamento do Intel Core i7 -2600K a 3,4 GHz e do Visual Studio 2010, a referência é (formato copiado do 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 uma movimentação condicional, o desempenho é o mesmo, independentemente do padrão de dados.

Agora vamos examinar mais de perto investigando a x86montagem que eles geram. Para simplificar, usamos duas funções max1emax2 .

max1usa o ramo condicional if... else ...:

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

max2usa o operador ternário ... ? ... : ...:

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

Em uma máquina x86-64, GCC -Sgera 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

max2usa muito menos código devido ao uso de instruções cmovge. Mas o ganho real é que max2nã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 um desempenho melhor?

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

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

Em um caso de movimentação condicional, a instrução de movimentação condicional de execução é dividida em vários estágios, mas os estágios anteriores gostam Fetche Decodenão dependem do resultado da instrução anterior; somente estágios posteriores precisam do resultado. Assim, esperamos uma fração do tempo de execução de uma instrução. É por isso que a versão de movimentação condicional é mais lenta que a ramificação 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 Movimentação Condicional , o Capítulo 4 inteiro para Arquitetura do Processador e a Seção 5.11.2 para obter um tratamento especial para as Penalidades de Previsão de Ramificação e de Erro de Previsão .

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

Se você estiver curioso sobre ainda mais otimizações que podem ser feitas nesse código, considere o seguinte:

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 loop, podemos alterar esse 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 o ifcondicional é constante durante toda a execução do iloop, para poder içar a ifsaída:

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 permita ( /fp:fasté lançado, por exemplo)

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

Esse é 100.000 vezes mais rápido do que antes.

Sem dúvida, alguns de nós estariam interessados ​​em maneiras de identificar código que é problemático para o preditor de ramificação da CPU. A ferramenta Valgrind cachegrindpossui um simulador de preditor de ramificação, ativado usando o --branch-sim=yessinalizador. Executá-lo sobre os exemplos nesta pergunta, com o número de loops externos reduzidos a 10000 e compilados 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%   )

Pesquisando detalhadamente a saída linha por linha produzida por cg_annotatenós, 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 que você identifique facilmente a linha problemática - na versão não classificada, a if (data[c] >= 128)linha está causando 164.050.007 ramos condicionais imprevisíveis ( Bcm) no modelo de preditor de ramo 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 desmontagem.

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.

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

Uma maneira comum de eliminar a previsão de ramificação que achei particularmente boa em idiomas gerenciados é uma pesquisa de tabela em vez de usar uma ramificação (embora eu não a tenha testado nesse caso).

Essa abordagem funciona em geral se:

1. é uma tabela pequena e provavelmente será armazenada em cache no processador, e
2. você está executando as coisas em um loop bastante apertado e / ou o processador pode pré-carregar os dados.

Antecedentes e porquê

Do ponto de vista do processador, sua memória está lenta. Para compensar a diferença de velocidade, alguns caches são incorporados ao seu processador (cache L1 / L2). Imagine que você esteja fazendo seus bons cálculos e descubra que precisa de um pouco de memória. O processador obtém sua operação de 'carregamento' e carrega a parte da memória no cache - e depois usa o cache para fazer o restante dos cálculos. Como a memória é relativamente lenta, essa 'carga' desacelera seu programa.

Como a previsão de ramificação, isso foi otimizado nos processadores Pentium: o processador prevê que ele precisa carregar alguns dados e tenta carregá-los no cache antes que a operação realmente atinja o cache. Como já vimos, a previsão de ramificação às vezes dá terrivelmente errado - no pior dos casos, você precisa voltar e realmente esperar por uma carga de memória, o que levará uma eternidade ( em outras palavras: falha na previsão de ramificação é ruim, uma memória carregar após uma falha na previsão de ramificação é simplesmente horrível! ).

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

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

Construindo uma tabela

Então descobrimos que podemos criar uma pequena mesa. A próxima coisa a fazer é instalar uma função de pesquisa. As funções de pesquisa são geralmente pequenas funções que usam algumas operações inteiras básicas (e, ou, xor, shift, add, remove e talvez multiplicar). Você deseja que sua entrada seja traduzida pela função de pesquisa para algum tipo de 'chave exclusiva' em sua tabela, que simplesmente fornece a resposta de todo o trabalho que você deseja que ele faça.

Nesse 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 mantivermos, nós AND com 7FFFFFFF; se quisermos nos livrar dele, nós AND com 0. Observe também que 128 é uma potência de 2 - para que possamos fazer uma tabela de 32768/128 números inteiros e preenchê-la com um zero e muito 7FFFFFFFF's.

Idiomas gerenciados

Você pode se perguntar por que isso funciona bem em idiomas gerenciados. Afinal, os idiomas gerenciados verificam os limites das matrizes com uma ramificação para garantir que você não estrague tudo ...

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

Houve muito trabalho para eliminar essa 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) notará isso e removerá a verificação completamente. WOW, isso significa que não há ramo. Da mesma forma, ele lidará com outros casos óbvios.

Se você tiver problemas com pesquisas em idiomas gerenciados - a chave é adicionar um & 0x[something]FFFa sua função de pesquisa para tornar a verificação de limites previsível - e assistir a isso indo mais rápido.

O resultado deste caso

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

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

/*To keep the spirit of the code intact, 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();

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

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

A pergunta é: o que faz com que a instrução acima não seja executada em certos casos, como no caso de dados classificados? Aí vem o "preditor de ramificação". Um preditor de ramificação é um circuito digital que tenta adivinhar o caminho que uma ramificação (por exemplo, uma if-then-elseestrutura) seguirá antes que se saiba com certeza. O objetivo do preditor de ramificação é melhorar o fluxo no pipeline de instruções. Os preditores de ramificação desempenham um papel crítico na obtenção de alto desempenho efetivo!

Vamos fazer algumas marcações de bancada para entender melhor

O desempenho de uma ifdeclaração depende se sua condição possui 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 pegará o padrão. Por outro lado, se o padrão for imprevisível, oif declaraçã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 horários 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

Um padrão “ ruim ” verdadeiro-falso pode tornar uma ifdeclaração até seis vezes mais lenta que uma “ boa padrão “ ”! Obviamente, qual padrão é bom e qual é ruim depende das instruções exatas geradas pelo compilador e pelo processador específico.

Portanto, não há dúvida sobre o impacto da previsão de ramificação no desempenho!

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 extrair facilmente um único bit que nos dirá se queremos ou não um valor: mudando os dados para os 7 bits certos, ficamos com 0 ou 1 bit e queremos adicionar o valor apenas quando tivermos 1 bit. 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 será igualmente rápido, independentemente de os dados serem 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 em que 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 das adições, mas nunca apresenta uma falha de previsão de ramificação. É tremendamente mais rápido em dados aleatórios do que na versão com uma declaração if real.

Mas nos meus testes, uma tabela de pesquisa explícita foi um pouco mais rápida que isso, provavelmente porque a indexação em uma tabela de pesquisa foi um pouco mais rápida do que a mudança de bits. Isso mostra como meu código configura e usa a tabela de pesquisa (chamada sem imaginação lutpara "Tabela de Pesquisa" no código). 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 pesquisa tinha apenas 256 bytes, portanto se encaixa perfeitamente em um cache e tudo foi rápido. Essa técnica não funcionaria bem se os dados tivessem valores de 24 bits e só quiséssemos metade deles ... a tabela de pesquisa 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 da metade superior, poderíamos potencialmente mudar os dados para a direita em 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.

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 o que fosse), tinha uma matriz de ponteiros com comprimento 2 e usei a técnica "bit de decisão" para decidir qual 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: Árvores negras vermelhas , eternamente confusas

No caso classificado, você pode fazer melhor do que confiar na previsão de ramificação bem-sucedida ou em qualquer truque de comparação sem ramificação: remova completamente a ramificação.

De fato, a matriz é particionada 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 (usandoLg(arraySize) = 15 comparações) e, em seguida, faça uma acumulação direta a partir desse ponto.

Algo como (desmarcado)

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 classificadas ou não, é: sum= 3137536;(assumindo uma distribuição verdadeiramente uniforme, 16384 amostras com valor esperado 191,5) :-)

O comportamento acima está acontecendo devido à previsão do ramo.

Para entender a previsão de ramificação, é preciso primeiro entender o pipeline de instruções :

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

Geralmente, os processadores modernos têm pipelines bastante longos, mas, para facilitar, vamos considerar apenas essas quatro etapas.

1. IF - Pega a instrução da memória
2. ID - decodifique a instrução
3. EX - Execute a instrução
4. WB - Grava novamente no registro da CPU

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

Voltando à pergunta 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 no pipeline, pois a decisão de ir para a instrução B ou a instrução C depende do resultado da instrução A. Portanto, o pipeline ficará assim.

quando se a condição retornar verdadeira:

Quando a condição retorna false:

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

Então, o que é previsão de ramificação?

O preditor de ramificação tentará adivinhar o caminho que uma ramificação (uma estrutura if-then-else) seguirá antes que isso seja conhecido com certeza. Não esperará que a instrução A chegue ao estágio EX do pipeline, mas adivinhará a decisão e seguirá para essa instrução (B ou C no caso do nosso exemplo).

No caso de um palpite correto, o pipeline é mais ou menos assim:

Se for detectado posteriormente que o palpite estava errado, as instruções parcialmente executadas serão descartadas e o pipeline será iniciado novamente com a ramificação correta, causando um atraso. O tempo desperdiçado no caso de uma previsão incorreta de ramificação é igual ao número de estágios no pipeline, do estágio de busca até o estágio de execução. Os microprocessadores modernos tendem a ter dutos bastante longos, de modo que o atraso de erros de previsão é entre 10 e 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 em que condicional, o preditor de ramificação não possui nenhuma informação para basear a previsão; portanto, na primeira vez, ele escolherá aleatoriamente a próxima instrução. Posteriormente no loop for, ele pode basear a previsão no histórico. Para uma matriz classificada em ordem crescente, há 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 assuma o ramo verdadeiro na primeira execução.

Portanto, no primeiro caso, ele sempre assumirá o ramo verdadeiro, pois historicamente todas as suas previsões estão corretas. No segundo caso, inicialmente ele irá prever errado, mas após algumas iterações, ele irá prever corretamente. No terceiro caso, ele inicialmente irá prever corretamente até que os elementos sejam menores que 128. Após o que falhará por algum tempo e se corrigirá quando vir uma falha na previsão de ramificação no histórico.

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

Porém, no caso de uma matriz aleatória não classificada, a previsão precisará descartar as instruções parcialmente executadas e iniciar novamente com a ramificação correta na maioria das vezes e resultar em mais ciclos de CPU em comparação com a matriz classificada.

Uma resposta oficial seria de

1. Intel - Evitando o custo da imprevisibilidade das filiais
2. Intel - Reorganização de ramificações e laços para evitar erros de interpretação
3. Artigos científicos - arquitetura de computadores para predição de ramificações
4. Livros: JL Hennessy, DA Patterson: Arquitetura de computadores: uma abordagem quantitativa
5. Artigos em publicações científicas: TY Yeh, YN Patt fez muitos deles em previsões de ramos.

Você também pode ver neste diagrama adorável por que 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 conforme o std::rand()golpe.

Por outro lado, uma vez ordenado, o preditor passará para um estado fortemente não tomado e, quando os valores mudarem para o valor alto, o preditor em três execuções passa pela mudança de forte não tomado para fortemente tomado.

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

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

ou similarmente:

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

Ambas likely()e unlikely()são de fato macros definidas com o uso de algo como os GCCs __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 oferece suporte a 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 analisa os recursos internos do GCC disponíveis.

Normalmente, esse tipo de otimização é encontrado principalmente em aplicativos em tempo real ou sistemas incorporados, nos quais o tempo de execução é importante e é crítico. Por exemplo, se você está verificando alguma condição de erro que ocorre apenas 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.

As operações booleanas usadas com freqüência no C ++ produzem muitas ramificações no programa compilado. Se essas ramificações estiverem dentro de loops e forem difíceis de prever, elas podem diminuir a execução significativamente. Variáveis ​​booleanas são armazenadas como números inteiros de 8 bits com o valor 0para falsee 1paratrue .

As variáveis ​​booleanas são superdeterminadas no sentido de que todos os operadores que possuem variáveis ​​booleanas como entrada verificam se as entradas têm algum valor diferente de 0ou 1, mas os operadores que possuem booleanos como saída não podem produzir outro valor além de 0ou 1. Isso torna as operações com variáveis ​​booleanas como entrada menos eficientes que o necessário. Considere um 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 o ideal. Os galhos podem demorar muito tempo em caso de erros de previsão. As operações booleanas podem se tornar muito mais eficientes se for sabido com certeza que os operandos não têm outros valores além de 0e 1. A razão pela qual o compilador não faz essa 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 com valores válidos ou se eles vierem de operadores que produzem saída booleana. O código otimizado é assim:

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

charé usado em vez de bool, a fim de possibilitar o uso dos 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 relógio. O operador OR ( |) funciona mesmo se ae btiver outros valores além de 0ou 1. O operador AND ( &) e o operador EXCLUSIVE OR ( ^) podem fornecer resultados inconsistentes se os operandos tiverem outros valores além de 0e 1.

~não pode ser usado para NÃO. Em vez disso, você pode criar um NOT booleano em uma variável que é conhecida por ser XOR 0ou 1com 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 & bse bé uma expressão que não deve ser avaliada se afor false( &&não avaliará b, &fará). Da mesma forma, a || bnão pode ser substituído por a | bif bé uma expressão que não deve ser avaliada se afor true.

Usar operadores bit a bit é mais vantajoso 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 muitas previsões incorretas de ramificações).

Isso é certeza!...

A previsão de ramificação torna a lógica mais lenta, devido à alternância que ocorre no seu código! É como se você estivesse indo para uma rua reta ou com muitas curvas, com certeza a reta será mais rápida! ...

Se a matriz for classificada, sua condição será falsa na primeira etapa: data[c] >= 128e se tornará um valor verdadeiro para todo o caminho até o fim da rua. É assim que você chega ao fim da lógica mais rapidamente. Por outro lado, usando uma matriz não classificada, você precisa de muitas transformações e processamento que tornam seu código mais lento, com certeza ...

Veja a imagem que eu criei para você abaixo. Qual rua será concluída mais rapidamente?

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

Além disso, 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 previsã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 subsequentes do código de ramificação condicional.

Para escrever efetivamente seu código para aproveitar essas regras, ao escrever instruções if-else ou switch , verifique primeiro os casos mais comuns e trabalhe progressivamente até o menos comum. Os loops não exigem necessariamente nenhuma ordem especial de código para previsão de ramificação estática, pois apenas a condição do iterador de loop é normalmente usada.

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

Recentemente, este exemplo (modificado levemente) 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á passando 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 da HAL (Camada de Abstração de Hardware) para determinar quanta imprevisibilidade de ramificação está acontecendo no caso não classificado.

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

Como o que já foi mencionado por outros, o que está por trás do mistério é o Preditor de Filial .

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 o caminho que uma ramificação (por exemplo, uma estrutura if-then-else) seguirá antes que se saiba com certeza. O objetivo do preditor de ramificação é melhorar o fluxo no pipeline de instruções. Os preditores de ramificação desempenham um papel crítico na obtenção de desempenho altamente eficaz em muitas arquiteturas modernas de microprocessadores em pipeline, como o x86.

A ramificação bidirecional é geralmente implementada com uma instrução de salto condicional. Um salto condicional pode ser "não realizado" e continuar a execução com o primeiro ramo do código que se segue imediatamente após o salto condicional, ou pode ser "realizado" e pular para um local diferente na memória do programa em que o segundo ramo do código é armazenado. Não se sabe ao certo se um salto condicional será executado ou não até que a condição tenha sido calculada e o salto condicional tenha passado o estágio de execução no pipeline de instruções (consulte 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 precisaria aguardar até que a instrução de salto condicional passe no estágio de execução antes que a próxima instrução possa 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.

São necessários 9 ciclos de relógio para que três instruções sejam concluídas.

2. Use o Preditor de ramificação e não dê um salto condicional. Vamos supor que a previsão não esteja dando o salto condicional.

São necessários 7 ciclos de relógio para que três instruções sejam concluídas.

3. Use o Preditor de ramificação e dê um salto condicional. Vamos supor que a previsão não esteja dando o salto condicional.

São necessários 9 ciclos de relógio para que três instruções sejam concluídas.

O tempo desperdiçado no caso de uma previsão incorreta de ramificação é igual ao número de estágios no pipeline do estágio de busca até o estágio de execução. Os microprocessadores modernos tendem a ter dutos bastante longos, de modo que o atraso de erros de previsão é entre 10 e 20 ciclos de clock. Como resultado, tornar o pipeline mais longo aumenta a necessidade de um preditor de filial mais avançado.

Como você pode ver, parece que não temos um motivo para não usar o Preditor de Filial.

É uma demonstração bastante simples que esclarece a parte muito básica do Branch Predictor. Se esses gifs forem irritantes, fique à vontade para removê-los da resposta e os visitantes também poderão obter o código-fonte da demonstração ao vivo em BranchPredictorDemo

Ganho de previsão de ramificação!

É importante entender que a imprevisibilidade das ramificações não diminui a velocidade dos programas. O custo de uma previsão perdida é como se a previsão de ramificação não existisse e você esperou a 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 houver uma instrução if-else\ switch, a expressão deve ser avaliada para determinar qual bloco deve ser executado. No código de montagem gerado pelo compilador, instruções de ramificação 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-se de seu comportamento padrão de executar instruções em ordem (por exemplo, se a expressão for falsa, o programa ignora o código do ifbloco) dependendo de alguma condição, que é a avaliação da expressão no nosso caso.

Dito isto, o compilador tenta prever o resultado antes de ser realmente avaliado. Ele buscará instruções do ifbloco e, se a expressão for verdadeira, então maravilhoso! Ganhamos o tempo necessário para avaliá-lo e fizemos progressos no código; caso contrário, 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 que seu parceiro verifique o mapa, você parou em ## e esperou ou pode escolher a rota1 e se tiver sorte (a rota 1 é a rota correta), então, ótimo, você não precisou esperar pelo seu parceiro para verificar o mapa (você economizou o tempo que levaria para ele verificar o mapa); caso contrário, você simplesmente voltará.

Embora a descarga de oleodutos seja super rápida, hoje em dia vale a pena fazer essa aposta. Prever dados classificados ou que mudam lentamente é sempre mais fácil e melhor do que prever mudanças rápidas.

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

No ARM, não há ramificação necessária, porque todas as instruções têm um campo de condição de 4 bits, que testa (a custo zero) qualquer uma das 16 condições diferentes que podem surgir no Registro de Status do Processador e se a condição em uma instrução é false, a instrução é ignorada. Isso elimina a necessidade de ramificações curtas e não haveria previsão de ramificação para esse algoritmo. Portanto, a versão classificada desse algoritmo seria mais lenta que a versão não classificada no ARM, devido à sobrecarga extra da classificação.

O loop interno desse algoritmo seria semelhante ao seguinte na linguagem assembly ARM:

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

Mas isso é parte de um quadro maior:

CMPOs opcodes sempre atualizam os bits de status no Processor Status Register (PSR), porque esse é o objetivo deles, mas a maioria das outras instruções não toca no PSR, a menos que você adicione um Ssufixo opcional à instrução, especificando que o PSR deve ser atualizado com base no resultado da instrução. Assim como o sufixo de condição de 4 bits, a capacidade de executar instruções sem afetar o PSR é um mecanismo que reduz a necessidade de ramificações no ARM e também facilita o envio fora de ordem no nível do hardware , porque após executar alguma operação X que atualiza os bits de status, subseqüentemente (ou em paralelo), você pode executar vários outros trabalhos que não devem afetar explicitamente os bits de status; em seguida, você pode testar o estado dos bits de status definidos anteriormente pelo X.

O campo de teste de condição e o campo opcional "definir status bit" podem ser combinados, por exemplo:

• ADD R1, R2, R3executa R1 = R2 + R3sem atualizar nenhum bit de status.
• ADDGE R1, R2, R3 executa a mesma operação somente se uma instrução anterior que afetou os bits de status resultar em uma condição Maior que ou Igual.
• ADDS R1, R2, R3executa a adição e, em seguida, atualiza os N, Z, Ce Vbandeiras no Estado Processor Register com base em se o resultado foi negativo, Zero, transportada (por adição sem sinal), ou transbordou (para além assinado).
• ADDSGE R1, R2, R3executa a adição apenas se o GEteste for verdadeiro e, em seguida, atualiza os bits de status com base no resultado da adição.

A maioria das arquiteturas de processador não tem essa capacidade de especificar se os bits de status devem ou não ser atualizados para uma determinada operação, o que pode exigir a gravação de código adicional para salvar e restaurar posteriormente os bits de status, ou pode exigir ramificações adicionais ou limitar a saída do processador. da eficiência de execução da ordem: um dos efeitos colaterais da maioria das arquiteturas de conjunto de instruções da CPU que atualiza forçosamente os bits de status após a maioria das instruções é que é muito mais difícil separar quais instruções podem ser executadas em paralelo sem interferir umas nas outras. A atualização dos bits de status tem efeitos colaterais, portanto, um efeito linearizante no código.A capacidade do ARM de combinar e combinar o teste de condição sem ramificação em qualquer instrução com a opção de atualizar ou não atualizar os bits de status após qualquer instrução ser extremamente poderosa, tanto para programadores quanto compiladores em linguagem assembly, e produz código muito eficiente.

Se você já se perguntou por que o ARM tem sido tão bem-sucedido em termos fenomenais, a brilhante eficácia e a interação desses dois mecanismos são uma grande parte da história, porque são uma das maiores fontes de eficiência da arquitetura do ARM. O brilhantismo dos designers originais do ARM ISA em 1983, Steve Furber e Roger (hoje Sophie) Wilson, não pode ser exagerado.

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

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

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

• Além disso, nas técnicas complexas de previsão, o tempo necessário para prever as ramificações é muito alto - variando de 2 a 5 ciclos - o que é comparável ao tempo de execução das ramificações reais.

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

Realmente existem três tipos diferentes de ramos:

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

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

Ramificações incondicionais - isso inclui saltos, chamadas de procedimentos e retornos que não têm condição específica. Por exemplo, uma instrução de salto incondicional pode ser codificada na linguagem assembly como simplesmente "jmp", e o fluxo de instruções deve ser direcionado imediatamente 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ções apenas se o resultado de uma comparação de dois valores em uma instrução "compare" anterior mostrar que os valores não são iguais. (O esquema de endereçamento segmentado usado pela arquitetura x86 adiciona complexidade extra, pois os saltos podem ser "próximos" (dentro de um segmento) ou "distantes" (fora do segmento). Cada tipo tem efeitos diferentes nos algoritmos de previsão de ramificação.

Previsão de ramificação estática / dinâmica : a previsão de ramificação estática é usada pelo microprocessador na primeira vez em que uma ramificação condicional é encontrada, e a previsão de ramificação dinâmica é usada para execuções subsequentes do código de ramificação condicional.

Referências:

• Preditor de ramificação

• Uma demonstração de auto-perfil

• Revisão de Previsão de Filial

• Previsão de ramificação

Além do fato de que a previsão de ramificação pode atrasar você, uma matriz classificada tem outra vantagem:

Você pode ter uma condição de parada, em vez de apenas verificar o valor, dessa forma, apenas repassa os dados relevantes e ignora o restante.
A previsão de ramificação perderá apenas uma vez.

 // sort backwards (higher values first), may be in some other part of the code
 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 que uma matriz não ordenada, devido a um fenômeno chamado previsão de ramificação.

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

Fazer uma previsão errada leva a voltar à etapa anterior e a executar com outra previsão. Supondo que a previsão esteja correta, o código continuará na próxima etapa. Uma previsão incorreta resulta na repetição da mesma etapa, até que ocorra uma 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 uma matriz classificada, o computador faz menos previsões, reduzindo a chance de erros. Fazer mais previsões requer mais tempo.

Matriz Ordenada: Estrada Reta

Matriz não classificada: Estrada curvada

______   ________
|     |__|

Previsão de ramificação: Adivinhar / prever qual estrada é reta e segui-la sem verificar

___________________________________________ Straight road
 |_________________________________________|Longer road

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

Também quero citar @Simon_Weaver nos comentários:

Não faz menos previsões - faz menos previsões incorretas. Ele ainda tem que prever para cada vez que passa pelo loop ...

Tentei o mesmo código com o MATLAB 2011b com o meu MacBook Pro (Intel i7, 64 bits, 2,4 GHz) para o seguinte código do MATLAB:

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

Os resultados para o código MATLAB acima são os seguintes:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

Os resultados do código C, como em @GManNickG, são apresentados:

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

Com base nisso, parece que o MATLAB é quase 175 vezes mais lento que a implementação C sem classificação e 350 vezes mais lento com a classificação. Em outras palavras, o efeito (da previsão de ramificação) é 1,46x para a implementação do MATLAB e 2,7x para a implementação em C.

A suposição por outras respostas de que é necessário classificar os dados não está correta.

O código a seguir não classifica a matriz inteira, mas apenas os segmentos de 200 elementos e, portanto, executa o mais rápido.

A classificação apenas das seções do elemento k conclui o pré-processamento em tempo linear O(n), em vez do O(n.log(n))tempo necessário para classificar toda a matriz.

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

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

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

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

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

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

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Isso também "prova" que não tem nada a ver com problemas algorítmicos, como ordem de classificação, e é de fato previsão de ramificação.

Resposta de Bjarne Stroustrup a esta pergunta:

Isso soa como uma pergunta de entrevista. É verdade? Como você saberia? É uma má idéia responder a perguntas sobre eficiência sem primeiro fazer algumas medições; portanto, é importante saber como medir.

Então, tentei com um vetor de um milhão de números inteiros e obtive:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

Corri isso algumas vezes para ter certeza. Sim, o fenômeno é real. Meu código-chave era:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Pelo menos o fenômeno é real com este compilador, biblioteca padrão e configurações do otimizador. Diferentes implementações podem dar respostas diferentes. De fato, alguém fez um estudo mais sistemático (uma rápida pesquisa na web o encontrará) e a maioria das implementações mostra esse efeito.

Um dos motivos é a previsão de ramificação: a operação principal no algoritmo de classificação é “if(v[i] < pivot]) …” ou equivalente. Para uma sequência classificada, esse teste é sempre verdadeiro, enquanto que, para uma sequência aleatória, o ramo escolhido varia aleatoriamente.

Outro motivo é que, quando o vetor já está classificado, nunca precisamos mover elementos para a posição correta. O efeito desses pequenos detalhes é o fator de cinco ou seis que vimos.

Quicksort (e classificação em geral) é um estudo complexo que atraiu algumas das maiores mentes da ciência da computação. Uma boa função de classificação é o resultado da escolha de um bom algoritmo e da atenção ao desempenho do hardware em sua implementação.

Se você deseja escrever um código eficiente, precisa conhecer um pouco da arquitetura da máquina.

Esta questão está enraizada nos modelos de previsão de ramificação nas CPUs. Eu recomendo a leitura deste artigo:

Aumentando a taxa de busca de instruções via previsão de várias ramificações e um cache de endereços de ramificação

Quando você classifica os elementos, o IR não pode se incomodar em buscar todas as instruções da CPU repetidas vezes. Ele as busca no cache.

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 extrair facilmente um único bit que nos dirá se queremos ou não um valor: mudando os dados para os 7 bits certos, ficamos com 0 ou 1 bit e queremos adicionar o valor apenas quando tivermos 1 bit. 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 será igualmente rápido, independentemente de os dados serem 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 em que não nos importamos. Aqui está o código:

// Teste

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 das adições, mas nunca apresenta uma falha de previsão de ramificação. É tremendamente mais rápido em dados aleatórios do que na versão com uma declaração if real.

Mas nos meus testes, uma tabela de pesquisa explícita foi um pouco mais rápida que isso, provavelmente porque a indexação em uma tabela de pesquisa foi um pouco mais rápida do que a mudança de bits. Isso mostra como meu código é configurado e usa a tabela de pesquisa (chamada sem imaginação lut para "Tabela de Pesquisa" no código). Aqui está o código C ++:

// Declare e preencha a tabela de pesquisa

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 pesquisa tinha apenas 256 bytes, portanto se encaixa perfeitamente em um cache e tudo foi rápido. Essa técnica não funcionaria bem se os dados tivessem valores de 24 bits e nós apenas quiséssemos metade deles ... a tabela de pesquisa 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 da metade superior, poderíamos potencialmente mudar os dados para a direita em 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.

A técnica de indexação em uma matriz, em vez de usar uma instrução if, 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 (pLeft e pRight ou o que fosse), tinha uma matriz de ponteiros com comprimento 2 e usei a técnica "bit de decisão" para decidir qual seguir. Por exemplo, em vez de:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

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

é uma boa solução, talvez funcione