ti-enxame.com

Por que é mais rápida uma matriz que não é classificada?

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.
22968
GManNickG

Você é uma vítima de predição de ramificação fail.


O que é predição de ramificação?

Considere um entroncamento ferroviário:

Image showing a railroad junction Imagem por 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 demoram uma eternidade para começar e desacelerar

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

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

Se você acertar toda vez, o trem nunca terá que parar.
Se você errar com demasiada frequência, o trem irá gastar muito tempo parando, fazendo backup e reiniciando.


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

Screenshot of compiled code containing an if statement

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.

Processadores modernos são complicados e possuem longos pipelines. Então eles demoram 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 toda vez, 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ê imaginaria 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 vai para a esquerda 99% do tempo, então você adivinhe à esquerda. Se alterna, você alterna suas suposições. Se for um caminho 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 ramificação 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 se deparam com ramos imprevisíveis sem padrões reconhecíveis, os preditores das agências são praticamente inúteis.

Leitura adicional: "Artigo sobre previsão de ramificação" 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 declaraçã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 depois que ele muda 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 é 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 @ 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 ordenados e não ordenados.
  • Com o Hack:Não há diferença entre dados ordenados e não classificados.
  • No caso do C++, o hack é realmente um pouco mais lento do que com o ramo quando os dados são classificados.

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


Atualização:

  • O GCC 4.6.1 com -O3 ou -ftree-vectorize em 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. É troca 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 ...

30104
Mysticial

previsão ramo.

Com uma matriz classificada, a condição data[c] >= 128 é a primeira false para uma faixa de valores e, em seguida, torna-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.

3879
Daniel Fischer

A razão pela qual o desempenho melhora drasticamente quando os dados são classificados é que a penalidade de predição de ramificação é removida, conforme explicado de forma clara na resposta de Mysticial .

Agora, se olharmos para o código

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

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

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

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

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

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

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

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

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

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

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

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

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

Em uma máquina x86-64, GCC -S gera a montagem abaixo.

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

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

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

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

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

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

Em um caso de movimento condicional, a instrução de movimento condicional de execução é dividida em vários estágios, mas os estágios anteriores, como Fetch e Decode, não dependem do resultado da instrução anterior; somente os últimos estágios precisam do resultado. Assim, esperamos uma fração do tempo de execução de uma instrução. É por isso que a versão de movimento condicional é mais lenta que 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, todo o Capítulo 4 para Arquitetura de Processador e a Seção 5.11.2 para um tratamento especial para Penalidades de Previsão de Ramificação e de Misprediction.

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

3125
WiSaGaN

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, então você pode aumentar a 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

2143
vulcan raven

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. A ferramenta Valgrind cachegrind possui um simulador de preditor de ramificação, ativado usando o sinalizador --branch-sim=yes. Corrê-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:

classificado:

==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 sorteado:

==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%   )

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

classificado:

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

          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 linha if (data[c] >= 128) está causando 164.050.007 ramificações condicionais mispredicted (Bcm) sob o modelo preditor de ramificação do cachegrind, enquanto está causando apenas 10.006 na versão classificada.


Alternativamente, 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

classificado:

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

 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ção 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.

1784
caf

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 e
  2. você está executando as coisas em um loop muito apertado e/ou o processador pode pré-carregar os dados.

Antecedentes e porque

Do ponto de vista do processador, sua memória é lenta. Para compensar a diferença de velocidade, um par de caches é embutido em seu processador (cache L1/L2). Então imagine que você está fazendo seus cálculos agradáveis ​​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 previsão de ramificação às vezes dá terrivelmente errado - na pior das hipóteses você precisa voltar e realmente aguardar uma carga de memória, o que levará uma eternidade ( em outras palavras: predição falsa de ramificação é ruim, uma carga de memória após uma falha de 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 irá carregá-lo em seu cache rápido e tudo estará bem.

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

Construindo uma tabela

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 algumas 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, o 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 dele, 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ê-lo com um zero e muitos 7FFFFFFFF.

Gerenciado idiomas

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 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 & 0x[something]FFF à sua função de pesquisa para tornar a verificação de limite previsível - e vê-la mais rápida.

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

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

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

A pergunta é: O que faz com que a declaraçã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 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ção. Preditores de filiais desempenham um papel crítico na obtenção de um desempenho altamente eficaz!

Vamos fazer uma marcação de bench para entender melhor

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

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

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

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

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

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

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

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

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

Um padrão “ bad ” true-false pode fazer uma instrução if- até seis vezes mais lenta que um padrão “ good ”! É claro que o padrão é bom e o que é ruim depende das instruções exatas geradas pelo compilador e no processador específico.

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

1118
Saqlain

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 um valor ou não: 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 acréscimos, 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 ligeiramente 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 configura e usa a tabela de pesquisa (chamada unimaginatively lut para "LookUp Table" 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 consulta tinha apenas 256 bytes, portanto, ela se ajusta bem em um cache e tudo era 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 da 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.

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 qualquer outra coisa), tinha uma matriz length-2 de ponteiros e usava a técnica "decision bit" para decidir qual deles seguir. Por exemplo, em vez de:

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

esta 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

1039
steveha

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

Na verdade, o array é particionado em uma zona contígua com data < 128 e outro com data >= 128. Portanto, você deve encontrar o ponto de partição com uma pesquisa dicotômica (usando as comparações Lg(arraySize) = 15) 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 dá uma solução aproximado para ordenada ou não classificada é: sum= 3137536; (supondo uma distribuição verdadeiramente uniforme, 16384 amostras com valor esperado 191.5) :-)

942
Yves Daoust

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

Para entender a predição da ramificação, é necessário primeiro entender Instruction Pipeline :

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ção e é usada para aumentar o rendimento em processadores modernos. Para entender melhor, por favor veja isto 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 4-stage pipeline in general

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, pois 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 se a condição retornar true: enter image description here

quando a condição retornar false: enter image description here

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. Não esperará que a instrução A atinja o estágio EX do pipeline, mas adivinhará a decisão e seguirá para essa instrução (B ou C no caso de nosso exemplo).

no caso de um palpite correto, o pipeline é algo como isto: enter image description here

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 erro é de 10 a 20 ciclos de clock. Quanto mais longo o pipeline, maior a necessidade de um bom preditor de ramificação .

No código do OP, na primeira vez que 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 inicialmente preverá 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 de 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 uma matriz aleatória não classificada, a previsão precisará descartar as instruções parcialmente executadas e recomeçar com a ramificação correta na maior parte do tempo e resultar em mais ciclos de CPU em comparação com a matriz classificada.

765
Harsh Sharma

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 previsão de ramificação
  4. Livros: J.L. Hennessy, D.A. Patterson: Arquitetura de computadores: uma abordagem quantitativa
  5. Artigos em publicações científicas: T.Y. Yeh, Y.N. Patt fez muito disso nas previsões das filiais.

Você também pode ver desta adorável diagrama porque o preditor da ramificação fica confuso.

 2-bit state diagram

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

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

então o preditor mudará de lado quando a função std::Rand() explodir.

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


669
Surt

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 */    
}

Tanto likely() quanto unlikely() são de fato macros que são definidas usando algo como __builtin_expect do GCC para ajudar o compilador a inserir o código de prediçã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 passa pelos 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 é 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.

634
rkachach

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 0 para false e 1 para true.

As variáveis ​​booleanas são sobredeterminadas no sentido de que todos os operadores que possuem variáveis ​​booleanas como entrada verificam se as entradas possuem qualquer outro valor que 0 ou 1, mas os operadores que possuem Booleans como saída não podem produzir outro valor que 0 ou 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 0 e 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 a e b tiverem sido inicializados para valores válidos ou se 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 bool para possibilitar o uso dos operadores bitwise (& 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 a e b tiverem outros valores além de 0 ou 1. O operador AND (&) e o operador EXCLUSIVO OR (^) podem fornecer resultados inconsistentes se os operandos tiverem outros valores além de 0 e 1.

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

bool a, b;
b = !a;

pode ser otimizado para:

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

a && b não pode ser substituído por a & b se b for uma expressão que não deve ser avaliada se a for false (&& não avaliará b, & será). Da mesma forma, a || b não pode ser substituído por a | b se b for uma expressão que não deve ser avaliada se a for 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).

603
Maciej

Isso é certeza!...

Branch prediction 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 reta será feita mais rápido! ...

Se a matriz for 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 vai terminar mais rápido?

Branch Prediction

Então, programaticamente, a predição branch 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

Branch Prediction

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 instruções 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.

280
Alireza

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 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á 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 da HAL (Camada de Abstração de Hardware) para determinar quanto erro de desvio da 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

262
ForeverLearning

Como o que já foi mencionado por outros, o que está por trás do mistério é 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ção. Preditores de filiais desempenham um papel crítico na obtenção de alto desempenho efetivo em muitas arquiteturas modernas de microprocessadores com pipeline, 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).

figure 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 tenha passado pelo 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 últimas duas instruções podem entrar no pipeline até que a instrução de salto condicional seja executada.

without branch predictor

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

  1. Use o Predictor de Ramificação e não faça um salto condicional. Vamos supor que a previsão seja não tomando o salto condicional.

enter image description here

Levará 7 ciclos de clock para que 3 instruções sejam completadas.

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

enter image description here

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

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 erro é 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 de git

176
Gearon

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 houver uma instrução if-else\switch, a expressão deve ser avaliada para determinar qual bloco deve ser executado. No código Assembly gerado pelo compilador, as instruções condicionais branch 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, desvie 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 bloco if) dependendo de alguma condição. é a avaliação de expressão no nosso caso.

Dito isto, o compilador tenta prever o resultado antes de ser realmente avaliado. Ele irá buscar instruções do bloco if, e se a expressão for 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ê precisa escolher a rota 1 ou a rota 2. Esperando pelo seu parceiro para verificar o mapa, você parou em ## 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  \--------------------------------
168
Tony Tannous

É 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 ramos - baseadas 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 de predição complexas, 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 previsã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:

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

Backward condicional ramos - o PC é alterado para apontar para trás no fluxo de instrução. A ramificação é baseada em alguma condição, como a ramificação de volta para o início de um loop de programa, quando um teste no final do loop informa que o loop deve ser executado novamente.

Unconditional branches - inclui saltos, chamadas de procedimento e retornos sem condições específicas. Por exemplo, uma instrução de salto incondicional pode ser codificada na linguagem 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:

113
Farhad

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 faz o loop dos dados relevantes e ignora o resto.
A previsão do ramo falhará 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];               
 }
107
Yochai Timmer

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 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
103
Luke Hutchison

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

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


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

Não faz menos previsões - faz menos previsões incorretas. Ainda tem que prever para cada vez através do loop ..

92
Omkaar.K

A suposição por outras respostas que alguém precisa para ordenar os dados não está correta.

O código a seguir não classifica a matriz inteira, mas somente segmentos de 200 elementos e, portanto, é executado mais rapidamente.

Classificar apenas as seções do elemento k conclui o pré-processamento em tempo linear em vez de n.log(n).

#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 qualquer questão algorítmica, como ordem de classificação, e é, de fato, uma previsão por ramo.

14
user2297550

Porque está classificado!

É fácil recuperar e manipular dados ordenados do que desordenados.

Assim como eu escolho aparelhos de lojas (encomendados) e do meu guarda-roupa (bagunçado).

0
Arun Joshla