Nesse caso, o incremento dos elementos
std :: vector será mais rápido - se forem do tipo
uint8_t ou
uint32_t ?
Para não raciocinar de maneira abstrata, consideramos duas implementações específicas:
void vector8_inc(std::vector<uint8_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } } void vector32_inc(std::vector<uint32_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } }
Vamos tentar adivinhar
É fácil responder a essa pergunta usando o benchmark, e um pouco mais tarde faremos isso, mas primeiro tentaremos adivinhar (isso é chamado de "raciocínio baseado em princípios básicos" - parece mais científico).
Em primeiro lugar, vale a pena fazer uma pergunta:
qual é o tamanho desses vetores ?
Bem, vamos escolher um número. Que haja 20.000 elementos em cada um.
Além disso, sabe-se que faremos testes no processador Intel Skylake - veremos as características dos comandos de adição para operandos de
8 e
32 bits com endereçamento direto. Acontece que seus principais indicadores são os mesmos: 1 operação por ciclo e um atraso de 4 ciclos por acesso à memória (1). Nesse caso, o atraso não importa, pois cada operação de adição é executada independentemente, de modo que a velocidade calculada é de 1 elemento por ciclo, desde que todo o restante do trabalho no loop seja executado em paralelo.
Você também pode observar que 20.000 itens correspondem a um conjunto de dados de 20 Kbyte para a versão com
uint8_t e até 80 Kbytes para a versão com
uint32_t . No primeiro caso, eles se encaixam idealmente no cache de nível L1 dos computadores modernos baseados em x86 e no segundo - não. Acontece que a versão de 8 bits terá um avanço devido ao armazenamento em cache eficiente?
Finalmente, notamos que nossa tarefa é muito semelhante ao caso clássico de
vetorização automática : em um loop com um número conhecido de iterações, uma operação aritmética é executada em elementos localizados seqüencialmente na memória. Nesse caso, a versão de 8 bits deve ter uma enorme vantagem sobre a versão de 32 bits, uma vez que uma operação vetorial processará quatro vezes mais elementos e, em geral, os processadores Intel executam operações vetoriais em elementos de byte único na mesma velocidade de 32 bits. elementos de bits.
Tudo bem, pare de reclamar. É hora de voltar para o teste.
Referência
Eu obtive os seguintes intervalos de tempo para vetores de 20.000 elementos nos
compiladores gcc 8 e
clang 8 com diferentes níveis de otimização:
Acontece que, com exceção do nível
-O1 , a versão com
uint32_t é mais rápida que a versão com
uint8_t e, em alguns casos, é significativa: 5,4 vezes no gcc no nível
-O3 e exatamente 8 vezes no clang nos dois níveis,
-O2 e
- O3 Sim, o incremento de números inteiros de 32 bits no
std :: vector é até oito vezes mais rápido que o incremento de números inteiros de 8 bits no compilador popular com configurações de otimização padrão.
Como sempre, passemos à lista de montadores na esperança de que ela mostre o que está acontecendo.
Aqui está uma lista para o gcc 8 no nível
-O2 , onde a versão de 8 bits é "apenas" 1,5 vezes mais lenta que a versão de 32 bits (2):
8 bits: .L3: inc BYTE PTR [rdx+rax] mov rdx, QWORD PTR [rdi] inc rax mov rcx, QWORD PTR [rdi+8] sub rcx, rdx cmp rax, rcx jb .L3
32 bits: .L9: inc DWORD PTR [rax] add rax, 4 cmp rax, rdx jne .L9
A versão de 32 bits se parece exatamente como esperávamos de um loop não desenvolvido (3): um incremento (4) com um endereço e três comandos de controle de loop:
add rax ,
4 - um incremento da variável indutiva (5) e alguns comandos
cmp e
jne para verificar as condições de saída do loop e salto condicional nele. Tudo parece ótimo - a implantação compensaria o custo de incrementar o contador e verificar a condição, e nosso código quase atingiria a velocidade máxima possível de 1 elemento por ciclo de clock (6), mas para um aplicativo de código aberto será necessário. E a versão de 8 bits? Além do comando
inc com o endereço, dois comandos adicionais para leitura da memória são executados, bem como o
subcomando , que é retirado do nada.
Aqui está uma lista com comentários:
8 bits: .L3: inc BYTE PTR [rdx+rax] ; v[i] mov rdx, QWORD PTR [rdi] ; v.begin inc rax ; i++ mov rcx, QWORD PTR [rdi+8] ; v.end sub rcx, rdx ; end - start (.. vector.size()) cmp rax, rcx ; i < size() jb .L3 ; . i < size()
Aqui
vector :: begin e
vector :: end são os ponteiros internos do
std :: vector , usados para indicar o início e o final da sequência de elementos contidos na área selecionada para ele (7), esses são essencialmente os mesmos valores que são usados para implementar
vector :: begin () e
vector :: end () (embora sejam de um tipo diferente). Acontece que todos os comandos adicionais são apenas uma consequência do cálculo de
vector.size () . Parece nada de anormal? Mas, afinal, na versão de 32 bits, é claro,
size () também
é calculado, no entanto, esses comandos não estavam nessa lista. O cálculo do
tamanho () aconteceu apenas uma vez - fora do loop.
Então qual é o problema? A resposta curta é
alias do ponteiro . Vou dar uma resposta detalhada abaixo.
Resposta detalhada
O vetor
v é passado para a função por referência, que, de fato, é um ponteiro mascarado. O compilador deve ir aos membros
v :: begin e
v :: end do vetor para calcular seu tamanho
size () e, em nosso exemplo,
size () é calculado
a cada iteração. Mas o compilador não é obrigado a obedecer cegamente ao código-fonte: pode levar o resultado da chamada da função
size () fora do loop, mas apenas se souber com certeza que a semântica do programa
não será alterada . Desse ponto de vista, o único lugar problemático no loop é o incremento
v [i] ++ . A gravação ocorre em um endereço desconhecido. Essa operação pode alterar o valor de size ()?
Se o registro ocorrer no
std :: vector <uint32_t> (ou seja, pelo ponteiro
uint32_t * ), então não, ele não poderá alterar o valor
size () . Gravar objetos do tipo
uint32_t pode modificar apenas objetos do tipo
uint32_t , e os ponteiros envolvidos no cálculo do
tamanho () têm um tipo diferente (8).
No entanto, no caso de
uint8_t , pelo menos nos compiladores populares (9), a resposta será a seguinte: sim, teoricamente, o valor de
size () pode mudar , já que
uint8_t é um alias para
char não assinado e matrizes do tipo
char (e
char )
não assinado podem
Alias com qualquer outro tipo . Isso significa que, de acordo com o compilador, escrever para
ponteiros uint8_t pode modificar o conteúdo da memória de origem desconhecida em qualquer endereço (10). Portanto, assume que cada operação de incremento
v [i] ++ pode alterar o valor
size () e, portanto, é forçado a recalculá-lo a cada iteração do loop.
Todos sabemos que gravar na memória apontada por
std :: vector nunca mudará seu próprio
tamanho () , porque isso significaria que o próprio vetor foi de alguma forma alocado dentro de sua própria pilha, e isso é praticamente impossível e semelhante ao problema da galinha e dos ovos (11). Mas infelizmente isso não é conhecido pelo compilador!
E o restante dos resultados?
Bem, descobrimos por que a versão com
uint8_ é um pouco mais lenta que a versão de
uint32_t no gcc no nível
-O2 . Mas por que explicar a enorme diferença - até 8 vezes - no clang ou no mesmo gcc no
-O3 ?
Tudo é simples aqui: no caso de
uint32_t, o clang pode executar a auto-vetorização de loop:
.LBB1_6: ; =>This Inner Loop Header: Depth=1 vmovdqu ymm1, ymmword ptr [rax + 4*rdi] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 32] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 64] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 96] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 32], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 64], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 96], ymm4 vmovdqu ymm1, ymmword ptr [rax + 4*rdi + 128] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 160] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 192] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 224] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi + 128], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 160], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 192], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 224], ymm4 add rdi, 64 add rsi, 2 jne .LBB1_6
O ciclo foi implantado 8 vezes, e este é geralmente o desempenho máximo que você pode obter: um vetor (8 elementos) por ciclo de clock para o cache L1 (isso não funcionará mais devido à limitação de uma operação de gravação por ciclo de clock (12)).
A vetorização não
é realizada para
uint8_t , porque é dificultada pela necessidade de calcular
size () para verificar a condição do loop a cada iteração. O motivo do atraso ainda é o mesmo, mas o atraso em si é muito maior.
Os tempos mais baixos são explicados pela auto-vetorização: o gcc o aplica apenas no nível
-O3 , e o clang se aplica nos níveis
-O2 e
-O3 por padrão. O compilador gcc no nível -cc gera código um pouco mais lento que o clang porque não expande o loop autovectorizado.
Corrija a situação
Descobrimos qual é o problema - como podemos corrigi-lo?
Primeiro, vamos tentar uma maneira que, no entanto, não funcione, a saber, escreveremos um ciclo mais idiomático com base em um iterador:
for (auto i = v.begin(); i != v.end(); ++i) { (*i)++; }
O código que o
gcc gera no nível
-O2 será um pouco melhor que a opção com
size () :
.L17: add BYTE PTR [rax], 1 add rax, 1 cmp QWORD PTR [rdi+8], rax jne .L17
Duas operações extras de leitura se transformaram em uma, porque agora comparamos com o ponteiro
final do vetor, em vez de recalcular o
tamanho () , subtraindo o ponteiro inicial do vetor do ponteiro final. Pelo número de instruções, esse código alcançou
uint32_t , pois a operação de leitura extra foi mesclada à operação de comparação. No entanto, o problema não desapareceu e a auto-vetorização ainda não está disponível; portanto, o
uint8_t ainda está significativamente atrás do
uint32_t - mais de 5 vezes no gcc e no clang nos níveis em que a auto-vetorização é fornecida.
Vamos tentar outra coisa. Não teremos sucesso novamente, ou melhor, encontraremos
outro método inoperante.
Nesta versão, calculamos
size () apenas uma vez antes do loop e colocamos o resultado em uma variável local:
for (size_t i = 0, s = v.size(); i < s; i++) { v[i]++; }
Parece estar funcionando? O problema era
size () , e agora pedimos ao compilador para confirmar o resultado de
size () com a variável local
s no início do loop, e as variáveis locais, como você sabe, não se cruzam com outros dados. Na verdade, fizemos o que o compilador não podia fazer. E o código que ele irá gerar será realmente melhor (comparado ao original):
.L9: mov rdx, QWORD PTR [rdi] add BYTE PTR [rdx+rax], 1 add rax, 1 cmp rax, rcx jne .L9
Há apenas uma operação de leitura extra e nenhum
subcomando . Mas o que esse comando extra (
rdx, QWORD PTR [rdi] ) faz se não estiver envolvido no cálculo do tamanho? Ele lê o ponteiro
data () de
v !
A expressão
v [i] é implementada como
* (v.data () + i) , e o membro retornado por
data () (e, de fato, um ponteiro de
início regular) apresenta o mesmo problema que
size () . É verdade que eu não notei essa operação na versão original, porque estava "livre", porque ainda precisava ser executada para calcular o tamanho.
Tenha um pouco mais, quase encontramos uma solução. Você só precisa remover do nosso loop
todas as dependências do conteúdo do
std :: vector . A maneira mais fácil de fazer isso é modificar um pouco nosso idioma com um iterador:
for (auto i = v.begin(), e = v.end(); i != e; ++i) { (*i)++; }
Agora tudo mudou drasticamente (aqui comparamos apenas versões com
uint8_t - em uma, salvamos o
final do iterador em uma variável local
antes do loop, na outra - não):
Essa pequena mudança nos deu um aumento de 20 vezes na velocidade em níveis com auto-vetorização. Além disso, o código com
uint8_t não apenas alcançou o código com
uint32_t - ele o ultrapassou quase exatamente quatro vezes por gcc
-O3 e clang
-O2 e
-O3 , como esperávamos no início, contando com vetorização: no final, exatamente quatro vezes mais elementos podem ser processados por uma operação vetorial e precisamos de quatro vezes menos largura de banda - independentemente do nível do cache (13).
Se você leu neste lugar, deve ter exclamado para si mesmo o tempo todo:
Mas e o loop for com passagem de banda introduzido no C ++ 11?Apresso-me a agradar: funciona! Na verdade, isso é açúcar sintático, por trás do qual nossa versão com um iterador está oculta quase na mesma forma, onde fixamos o ponteiro
final em uma variável local antes do início do loop. Então a velocidade dele é a mesma.
Se de repente decidíssemos voltar aos tempos antigos das cavernas e escrever uma função do tipo C, esse código funcionaria da mesma maneira:
void array_inc(uint8_t* a, size_t size) { for (size_t i = 0; i < size; i++) { a[i]++; } }
Aqui, o ponteiro para a matriz ae a variável
size são passados para a função por valor, portanto, não podem ser alterados como resultado da gravação no ponteiro
a (14) - assim como as variáveis locais. O desempenho desse código é o mesmo das opções anteriores.
Finalmente, nos compiladores em que esta opção está disponível, você pode declarar um vetor com
__restrict (15):
void vector8_inc_restrict(std::vector<uint8_t>& __restrict v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } }
A
palavra-chave __restrict não faz parte do padrão C ++, mas faz parte do padrão
C desde C99 (como
restrito ). Se ele for implementado como uma extensão C ++ no compilador, provavelmente obedecerá à semântica de C. É claro que não há links em C; portanto, você pode substituir mentalmente o link para o vetor por um ponteiro para o vetor.
Observe que restringir não possui uma
propriedade transitiva: a ação do especificador
__restrict , com a qual um link para
std :: vector é declarado, aplica-se apenas aos membros do próprio vetor e não à região de heap referenciada por
v.data () . No nosso caso, não é necessário mais, porque (como no caso de variáveis locais) é suficiente para convencer o compilador de que os próprios termos, apontando para o início e o fim do vetor, não se cruzam com nada. A cláusula sobre
restrição , no entanto, ainda é relevante, pois a gravação via
v.data () ainda pode fazer com que outros objetos em sua função sejam alterados devido ao alias.
Decepção
Aqui chegamos à última - e muito decepcionante - conclusão. O fato é que todas as soluções mostradas acima são aplicáveis apenas a este caso específico, quando o vetor pode teoricamente interferir consigo mesmo. A solução foi sair do loop ou isolar o resultado da chamada do
tamanho () ou
final () do vetor, e
não informar ao compilador que a gravação nos dados do vetor não afeta outros dados. É difícil escalar esse código à medida que a função cresce.
O problema do aliasing não desapareceu e os comandos de gravação ainda podem ir a qualquer lugar - simplesmente não há outros dados nessa função que possam ser afetados ... por enquanto. Assim que um novo código aparecer, tudo será repetido. Aqui está
um exemplo de improviso . Se você escrever em matrizes de elementos do tipo
uint8_t em pequenos loops, precisará lutar com o compilador até o final (16).
Comentários
Ficarei feliz em qualquer feedback. Eu ainda não tenho um sistema de comentários (17), portanto, como de costume, discutiremos
neste tópico no HackerNews .
- Ao acessar a memória aqui, entende-se que a cadeia de dependências passa pela memória: comandos de gravação no mesmo endereço devem ler o último valor gravado nela, portanto, essas operações são dependentes (na prática, o redirecionamento para carregamento (STLF) será usado se a gravação for suficiente frequentemente). Dependências do comando add ao acessar a memória podem ocorrer de outras maneiras, por exemplo, calculando o endereço, mas para o nosso caso isso é irrelevante.
- Apenas um pequeno ciclo é mostrado aqui; O código de instalação é simples e funciona rápido. Para ver a lista completa, carregue o código no godbolt .
- Talvez deva ser chamado simplesmente de "minimizado"? Seja como for, o compilador gcc geralmente não circula nem nos níveis -O2 e -O3 , exceto em casos especiais em que o número de iterações é pequeno e é conhecido no estágio de compilação . Por esse motivo, o gcc mostra resultados de teste mais baixos em comparação com o clang, mas economiza muito no tamanho do código. Você pode forçar o gcc a desenrolar loops aplicando a otimização de perfil ou ativando o sinalizador -funroll-loops .
- Na verdade, o comando inc DWORD PTR [rax] no gcc é uma otimização perdida: quase sempre é melhor usar o comando add [rax], 1 , pois consiste em apenas 2 microoperações combinadas versus 3 no inc . Nesse caso, a diferença é de apenas cerca de 6%, mas se o ciclo fosse ligeiramente expandido para que apenas a operação de gravação fosse repetida, a diferença seria mais significativa (uma expansão adicional não seria mais um papel, já que atingiríamos o limite de 1 operação de gravação por ciclo, que não depende do número total de micro-operações).
- Chamo essa variável de indutiva , e não apenas de i , como no código-fonte, porque o compilador converteu as operações da unidade do incremento i em incrementos de 4 bytes do ponteiro armazenado no registro rax e, portanto, corrigiu a condição do loop. Em sua forma original, nosso loop aborda os elementos do vetor e, após essa conversão, incrementa o ponteiro / iterador, que é uma maneira de reduzir o custo das operações .
- De fato, se você habilitar -funroll-loops , no gcc a velocidade será de 1,08 medidas por elemento com um lançamento de 8x . Mas mesmo com esse sinalizador, ele não expandirá o loop da versão com elementos de 8 bits, portanto o atraso na velocidade será ainda mais perceptível!
- Esses membros têm um modificador privado e seus nomes dependem da implementação, mas no stdlibc ++ eles não são realmente chamados de início e término , como no gcc. Eles são chamados _Vector_base :: _ Vector_impl :: _ M_start e _Vector_base :: _ Vector_impl :: _ M_finish respectivamente , ou seja, insira a estrutura _Vector_impl , que é membro de _M_impl (e o único) da classe _Vector_base e que, por sua vez, é a classe base para std :: vector . Bem, bem! Felizmente, o compilador lida facilmente com essa pilha de abstrações.
- O padrão não prescreve quais devem ser os tipos internos dos membros std :: vector , mas na biblioteca libstdc ++ eles são simplesmente definidos como Alloc :: pointer (onde Alloc é o alocador do vetor) e, para o objeto std :: alocado padrão, eles simplesmente ponteiros do tipo T * , ou seja, ponteiros regulares para um objeto - neste caso, uint32_t * .
- Estou fazendo esta reserva por um motivo. Existe uma suspeita de que uint8_t possa ser considerado como um tipo diferente de char , char assinado e char não assinado . Como o alias funciona com tipos de caracteres , isso não se aplica a uint8_t e deve se comportar como qualquer outro tipo que não seja de caractere. No entanto, nenhum dos compiladores que conheço pensam assim: em todos eles, typedef uint8_t é um alias de char não assinado , para que os compiladores não vejam a diferença entre eles, mesmo que desejem usá-lo.
- Por "origem desconhecida", quero dizer aqui apenas que o compilador não sabe para onde o conteúdo da memória está apontando ou como ele apareceu. Isso inclui ponteiros arbitrários passados para a função, bem como variáveis globais e estáticas. , , , , , ( - ). , malloc new , , , , : , , . , malloc new .
- , std::vector - ? , std::vector<uint8_t> a a.data() placement new b . std::swap(a, b) , – , b ? , b . : - (, ), , .
- 8 , .. 32 . , std::vector .
- - 4 : , , – . : 8- L1, 32- – L2 , .
- , – : . , , «».
- v[i] , .
- . , «» , uint8_t . , , , uint8_t , . , clang, gcc , , uint8_t . - gcc , . , , - __restrict .
- - , , ( Disqus), ( ), .
. : Travis Downs. Incrementing vectors .