Por que é mais rápido processar uma matriz classificada do que uma matriz 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.

 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 é estúpido, porque o array acabou de ser gerado.

  • O que está acontecendo
  • Por que a matriz classificada é processada mais rapidamente que a matriz não classificada?
  • O código resume alguns termos independentes e a ordem não importa.
22512
27 июня '12 в 16:51 2012-06-27 16:51 GManNickG é definido em 27 de junho às 12:51 2012-06-27 16:51
@ 26 respostas

Você é a vítima do desvio da ramificação .


O que é predição de ramo?

Considere o entroncamento ferroviário:

2019

Previsão de ramos.

Com uma matriz ordenada, a condição data[c] >= 128 é a primeira false para a cadeia de valor e, em seguida, torna-se true para todos os valores subsequentes. É fácil prever. Com uma matriz não classificada, você paga pelos custos de ramificação.

3815
27 июня '12 в 16:54 2012-06-27 16:54 a resposta é dada por Daniel Fischer 27 de junho, 12 às 16:54 2012-06-27 16:54

A razão pela qual o desempenho melhora drasticamente ao ordenar os dados é que a penalidade para a predição da ramificação é eliminada, como Mysticial explicou perfeitamente.

Agora, se olharmos para o código

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

Podemos achar que o significado dessa ramificação particular if... else... é adicionar algo quando a condição é satisfeita. Esse tipo de ramificação pode ser facilmente convertido em um operador condicional , que será compilado em uma instrução de movimento condicional: cmovl , no sistema x86 . O ramo e, portanto, a penalidade potencial para prever a ramificação é removida.

Em C , portanto, C++ , o operador que será diretamente (sem qualquer otimização) compilado em uma instrução de movimento condicional em x86 é um operador ternário ...?... :... ...?... :... Portanto, reescrevemos a declaração acima como sendo equivalente:

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

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

Para Intel Core i7 -2600K @ 3.4 GHz e teste de referência do modo de liberação do Visual Studio 2010 (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 é confiável em vários testes. Temos uma aceleração significativa quando o resultado da ramificação é imprevisível, mas sofremos um pouco quando é previsível. Na verdade, ao usar um movimento condicional, o desempenho permanece o mesmo, independentemente do padrão de dados.

Agora vamos dar uma olhada mais de perto, explorando a build 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; } 

No computador x86-64, o GCC -S constrói um conjunto abaixo.

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

max2 usa muito menos código devido ao uso da instrução cmovge . Mas o ganho real é que max2 não inclui transições em max2 , jmp , o que pode levar a um desempenho max2 significativo se o resultado previsto for max2 .

Então, por que o movimento condicional funciona melhor?

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

No caso de ramificação, a próxima instrução é determinada pela anterior, portanto não podemos executar pipelining. Nós devemos esperar ou prever.

No caso de um movimento condicional, a execução do comando condicional move é dividida em vários estágios, mas os estágios anteriores, como Fetch e Decode , não dependem do resultado da instrução anterior; apenas os estágios finais precisam de um resultado. Assim, estamos aguardando uma parte 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 Prospect for a Programmer, segunda edição, explica isso em detalhes. Você pode verificar a Seção 3.6.6 para instruções de movimento condicional, todo o capítulo 4 para a arquitetura do processador e a seção 5.11.2 para tratamento especial para penalidades de predição e previsão errônea.

Às vezes, alguns compiladores modernos podem otimizar nosso código para construção com maior desempenho, algumas vezes alguns compiladores não podem (esse código usa seu próprio compilador do Visual Studio). Saber 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 script se torna tão complexo que o compilador não pode otimizá-lo automaticamente.

3064
28 июня '12 в 5:14 2012-06-28 05:14 a resposta é dada por WiSaGaN 28 de junho de '12 at 5:14 am 2012-06-28 05:14

Se você estiver interessado em ainda mais otimizações que podem ser feitas com esse código, considere o seguinte:

Começando do ciclo inicial:

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

Com a permutação de ciclo, podemos alterar com segurança este ciclo 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 condição if é constante durante a execução do loop i , então você pode retirar if :

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

Então você verá que o loop interno pode ser recolhido em uma única expressão, assumindo que o modelo de ponto flutuante o permita (por exemplo, / fp: fast)

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

É 100.000 vezes mais rápido que antes.

2105
03 июля '12 в 5:25 2012-07-03 05:25 a resposta é dada ao corvo vulcânico 3 de julho, '12 at 5:25 am 2012-07-03 05:25

Sem dúvida, alguns de nós estarão interessados ​​em maneiras de identificar código que seja problemático para um processador preditor de CPU. A ferramenta cachegrind Valgrind possui uma sintaxe de ramificação do preditor de ramificação que é ativada usando o --branch-sim=yes . Executando-o pelos exemplos nesta questão, o número de loops externos, reduzido para 10.000 e compilado com g++ , fornece os seguintes resultados:

Ordenar por:

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

Voltando-se para a saída linear criada pelo cg_annotate , vemos para o ciclo em questão:

Ordenar por:

  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 do problema - em uma versão não classificada, a linha if (data[c] >= 128) causa Bcm ramificações condicionais ( Bcm ) preditas incorretamente como parte do modelo de previsão de ramificação cachegrind, enquanto só chama 10.006 na ordenada versão.


Como alternativa, no Linux, você pode usar um subsistema de contador de desempenho para executar a mesma tarefa, mas com seu próprio desempenho usando contadores de CPU.

 perf stat ./sumtest_sorted 

Ordenar por:

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

Para mais detalhes, consulte o manual de desempenho .

1758
12 окт. resposta dada caf 12 de outubro. 2012-10-12 08:53 '12 às 8:53 2012-10-12 08:53

Acabei de ler esta pergunta e suas respostas, e sinto que a resposta está faltando.

A maneira usual de eliminar a predição de ramificação, que me pareceu funcionar particularmente bem em linguagens gerenciadas, é procurar na tabela em vez de usar ramificação (embora neste caso eu não a tenha verificado).

Esta abordagem funciona em geral se:

  1. esta é uma pequena tabela e provavelmente será armazenada em cache no processador e
  2. Você está trabalhando em um loop bastante estreito e / ou o processador pode pré-carregar 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 (cache L1 / L2) é embutido em seu processador. Então imagine que você está fazendo seus bons cálculos e descubra que precisa de um pedaço de memória. O processador executará a operação de carregamento e carregará parte da memória no cache e, em seguida, usará o cache para executar os cálculos restantes. Como a memória é relativamente lenta, essa “carga” irá desacelerar seu programa.

Como a previsão de ramificação, ela foi otimizada em processadores Pentium: o processador prevê que precisa carregar alguns dados e tenta carregá-los no cache antes que a operação realmente entre no cache. Como já vimos, a previsão de ramificação às vezes dá terrivelmente errado - no pior dos casos, você precisa voltar e realmente aguardar uma carga de memória que durará para sempre (em outras palavras: uma previsão de ramificação malsucedida é ruim, a carga de memória após uma falha de previsão de ramificação é terrível! ).

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

A primeira coisa que precisamos saber é que há pouco? Embora um tamanho menor geralmente seja melhor, a regra básica é manter as tabelas de pesquisa <= 4096 bytes. Como limite superior: se sua tabela de referência for maior que 64 KB, ela provavelmente deve ser revisada.

Construa a mesa

Então, descobrimos que podemos criar uma pequena mesa. A próxima coisa a fazer é substituir a função de pesquisa. Funções de busca são geralmente pequenas funções que usam várias operações inteiras básicas (e, ou, xor, shift, add, remove e possivelmente multiplicação). Вы хотите, чтобы ваш ввод был переведен с помощью функции поиска в какой-то "уникальный ключ" в вашей таблице, который затем просто дает вам ответ на всю работу, которую вы хотели, чтобы он делал.