Hoje, mediremos o desempenho de diferentes implementações da função toupper, porque é isso que eles fazem às terças-feiras.
Na verdade, eu não me importo com a função
toupper , acabei de escrever outro post recentemente e precisava de algum tipo de núcleo comum de plotagem, e o
toupper parece ser um candidato bastante interessante e inofensivo para benchmarks. Tentei escolher algo o mais simples possível que não me deixasse de lado, mas aconteceu que neste teste tive um problema estranho.
Este post será pequeno - um artigo mais abrangente sobre o tópico original, talvez mais interessante, é esperado em breve. Se você deseja reproduzir os resultados comigo,
pode usar o código-fonte
no github .
Então, vamos dar uma olhada em três implementações da função
toupper , que converte os caracteres de uma matriz que consiste em elementos do tipo
char em maiúsculas - ou seja, usa uma matriz como argumento e altera diretamente seus elementos para que todas as letras minúsculas sejam maiúsculas.
Na primeira implementação, simplesmente chamamos
a função toupper [1]
da biblioteca padrão C e executamos um loop no estilo C:
void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } }
Na segunda implementação, usamos uma abordagem
mais moderna com a substituição do ciclo bruto por
std :: transform :
void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); }
Finalmente, na terceira implementação, usamos um algoritmo especial que trabalha com caracteres ASCII. Ele verifica se o caractere está no intervalo
a - z e, se for bem-sucedido, substitui a mesma letra em maiúscula, subtraindo o número 32 do código de caractere [2]:
void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } }
Parece fácil, certo?
Agora, mediremos a velocidade dessas implementações no meu laptop com o processador Skylake i7-6700HQ no compilador gcc 5.5 com configurações padrão. Os resultados são apresentados na forma de um gráfico de dispersão [3]:
Imediatamente trataremos de três perguntas que são irrelevantes para a nossa tarefa.
Primeiro, observe o gráfico do algoritmo de ramificação (mostrado em verde). Varia significativamente, dependendo do tamanho dos dados de entrada - os outros dois gráficos permanecem quase planos. Na verdade, isso é apenas um artefato de teste. Os caracteres ASCII de entrada são selecionados aleatoriamente [4], portanto, o fator decisivo no caso da terceira implementação é a operação do algoritmo de predição de ramificação. Com uma pequena quantidade de dados, ele memoriza completamente a sequência de elementos à medida que a iteração é executada, de modo que o número de erros é pequeno e a velocidade é alta,
conforme mostrado nesta nota . À medida que o tamanho da sequência de dados aumenta, o algoritmo de previsão se lembra cada vez menos até finalmente começar a falhar com cada letra maiúscula (0,27 falta por caractere) e, em seguida, o gráfico é nivelado.
Em segundo lugar, preste atenção ao grupo de pontos verdes no canto superior esquerdo, correspondendo a velocidades muito mais baixas da variante com ramificação
toupper_branch :
Este não é um artefato isolado: esses pontos apareceram durante vários lançamentos. Ao mesmo tempo, eles não poderão ser reproduzidos se você testar o algoritmo apenas especificamente nesses tamanhos de dados - eles aparecerão apenas quando o teste for executado em todos os tamanhos. Mas neste caso, eles nem sempre aparecem. Não mergulhei nisso particularmente, mas posso assumir que isso se deve a alguns conflitos de nomes ou aliases no algoritmo de previsão de ramificação ou ao mapear páginas físicas de 4 KB de memória para virtual (embora a randomização do espaço de endereço virtual tenha sido desativada).
Em terceiro lugar, a implementação de
toupper_rawloop (mostrada em azul) no gráfico se parece com duas linhas separadas: uma ligeiramente acima da marca de 2 medidas por caractere e a outra no nível de 1,5 medidas por caractere. Essas duas linhas apareceram em todos os testadores. A opção mais rápida, com uma velocidade de 1,57 caracteres por ciclo, diminui a velocidade nas portas de download: a leitura dos dados nas portas 2 e 3 ocorre a uma velocidade de 1,54 microoperações por ciclo, portanto, elas estarão 98% ocupadas. Não pude estabelecer a razão do "regime" mais lento.
Enquanto eu estava lidando com essa questão, o rápido "regime" desapareceu subitamente e apenas o lento permaneceu. Talvez o processador tenha percebido o que eu estava tentando fazer e baixado secretamente a atualização do microcódigo para remover a contradição, mas eu ainda tenho uma prova - uma imagem vetorial com gráficos.
O que então nos interessa neste exemplo?
Mas o que nos interessa é que a versão com um ciclo bruto é 3-4 vezes mais rápida que a versão com
std :: transform : 1.5-2 ciclos por caractere versus 7 com alguns ciclos por caractere.
Qual é o problema aqui? Algoritmos padrão falharam comigo?
Std :: transform tem alguma falha?
Na verdade não. Mais precisamente, nem um pouco.
Acontece que esses resultados aparecem quando as funções são compiladas em
arquivos diferentes . Se você colocá-los no mesmo arquivo, o desempenho deles se tornará igualmente baixo.
E não, o alinhamento não tem nada a ver com isso.
Mas isso não é tudo: a versão rápida com um ciclo bruto, quando compilada em um arquivo separado, fica mais lenta se você simplesmente anexar o arquivo de cabeçalho
<algorithm> . Sim, está certo: basta conectar este arquivo, que nunca é usado e não gera nenhum código no arquivo final do objeto, e a velocidade do ciclo "bruto" cairá 3-4 vezes. Pelo contrário, a versão com
std :: transform é acelerada até o limite se você copiar e colar a implementação de
std :: transform do arquivo
<algorithm> , mas não inclui esse arquivo.
As estranhezas não param por aí (não haverá mais, prometo): incluir o arquivo
<algorithm> nem sempre leva ao efeito descrito. Uma queda de velocidade ocorre se o
<algorithm> estiver conectado anteriormente a
<ctype.h> , mas se você os trocar, não haverá:
Código lento: #include <algorithm> #include <ctype.h>
Código rápido: #include <ctype.h> #include <algorithm>
Na verdade, essa anomalia apareceu em mim (em outro projeto) quando o formato clang classificou automaticamente os arquivos de cabeçalho incluídos e colocou o
<algorithm> no início da lista, onde ele pertence (daí o cabeçalho clickbait do artigo).
Naturalmente, tivemos que mergulhar na lista de montadoras mais cedo ou mais tarde. Não vamos atrasar esse momento desagradável.
As versões
rápidas e lentas das funções [5] são mostradas abaixo, pequenos loops são fornecidos com anotações:
O <algorithm> se conecta primeiro: toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ; char- *buf add rbx, 1 ; buf++ call toupper ; toupper(c) mov BYTE PTR [rbx-1], al ; buf[-1] cmp rbp, rbx ; buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret
<algorithm> é conectado em segundo: toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ; char- buf movsx rcx, BYTE PTR [rdi] ; toupper ; ( __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ; toupper , ; mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ; cmp rsi, rdi ; buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret
A principal diferença é que, na versão lenta, a função toupper é chamada simplesmente em loop, enquanto na versão rápida as chamadas de função estão completamente ausentes, e há apenas uma pesquisa na tabela de correspondência [6], ou seja, o corpo da função
std :: toupper é substituído no local da chamada.
Se você olhar para o
código fonte da biblioteca glibc, encontramos a implementação da função
toupper :
__extern_inline int
Como podemos ver,
toupper é definido como uma função
externa interna que primeiro verifica se o tamanho do caractere se encaixa em um byte [7] e, em seguida, procura o caractere na tabela de correspondência retornada pela função
__ctype_toupper_loc () . Esta função retorna um ponteiro de fluxo local (do tipo
const int ** ), que, por sua vez, aponta para uma tabela de correspondência, da qual, em resposta a uma solicitação para o nosso símbolo, sua versão em maiúscula é retornada [8].
Agora está claro o que está acontecendo na lista. Na versão rápida do algoritmo, o compilador substitui o corpo da função
toupper , mas não pode substituir a chamada para a função
__ctype_toupper_loc () [9]. Essa chamada, no entanto, é declarada como
__atributo __ ((const)) , o que significa que o valor de retorno depende apenas dos argumentos (que não estão aqui). O compilador sabe que essa função retorna o mesmo valor todas as vezes e, portanto, realiza sua chamada fora do loop, e no próprio loop existem apenas algumas operações de leitura associadas ao acesso à tabela de correspondência, gravação de um novo valor no buffer e controle do loop.
Na versão lenta, a chamada para
toupper () permanece no corpo do loop. O loop em si é mais curto em um comando, mas, é claro, agora você ainda precisa executar todo o código dentro da função
toupper . No meu sistema, fica assim:
lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ; c cmp edx,0x17f ; , c -128 255 ja 2a ; , mov rdx,QWORD PTR [rip+0x395f30] ; ; mov rdx,QWORD PTR fs:[rdx] ; ; mov rdx,QWORD PTR [rdx] ; ; mov rdx,QWORD PTR [rdx+0x48] ; toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ; c 2a: ret
Como esta é uma chamada não incorporada, o programa trabalha mais. Existem pelo menos cinco operações consecutivas de acesso à memória (a chamada busca de ponteiros,
perseguição de ponteiros ). Na versão rápida, apenas dois deles permanecem, pois todos os outros são retirados do circuito. O atraso entre chamar uma função e sair dela deve ser de cerca de 25 ciclos, e temos cerca de 7 ciclos - isso significa que o processador conseguiu paralelizar a chamada, o que é bastante bom, dadas as circunstâncias.
Por que isso é assim?
Em uma longa cadeia de arquivos include, os arquivos de cabeçalho C ++, como
<algorithm> , incluem, por sua vez, o arquivo
<bits / os_defines.h> , que contém a seguinte linha:
Quando o arquivo
<ctype.h> finalmente
está conectado, por causa dessa diretiva, o código no qual o
toupper é definido como
externo interno não pode ser incluído:
#if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum)
Observe que, ao conectar
<ctype.h>, a versão C ++ do
toupper nunca
é definida como uma macro - no máximo como
externa interna -, pois as definições das macros são protegidas pela
verificação! Defined __cplusplus e, portanto, nunca terão efeito.
Em geral, não sei ao certo se
__NO_CTYPE nesse caso deve excluir os corpos das funções
tolower e
toupper declarados como
externos externos , mas é exatamente isso que acontece - e, portanto, uma queda significativa na velocidade do nosso ciclo. Concluindo, posso dizer que, se você incluir
<cctype> em vez de
<ctype.h> (ou seja, C ++ é a versão do arquivo de cabeçalho C que coloca funções no
espaço de nome std :: namespace ), nesse caso, o código funcionará lentamente porque
<cctype> finalmente inclui
<bits / os_defines.h> .
Isso é tão importante? Não não
A função
toupper não é adequada para trabalhos sérios com caracteres de idiomas diferentes; portanto, se você precisar processar apenas caracteres ASCII, poderá escrever sua própria implementação mais rápida. Se você precisar de um trabalho sério com texto, provavelmente usará UTF-8 e precisará usar algum tipo de UTI para dar suporte às configurações regionais ou aguarde até que o suporte a Unicode apareça em C ++ (pode demorar muito tempo) . Portanto, a declaração "formato clang pode causar uma queda de 4x no desempenho" é adequada apenas como um cabeçalho clickbait.
Esse efeito é observado em todas as versões da libc? Sim, em quase todos, mas mesmo aqui não é tão simples.
Os resultados mostrados acima são verdadeiros para o gcc 5.5 e glibc 2.23, desde que eu usei essas versões, mas algo novo está acontecendo nas novas versões (a partir do glibc 2.27). Lá, ativar o
<algorithm> antes de
<ctype.h> ainda dá o mesmo efeito, mas agora
<stdlib.h> [10] também cria problemas: se você ativá-lo antes de
<ctype.h> , o desempenho também cairá, o que não é observado em versões anteriores. Obviamente, nas versões mais recentes, o arquivo
<stdlib.h> também contém a definição
__NO_CTYPE . Pelo menos, agora não será possível culpar o formato clang pela classificação - aqui apenas pode ajudar a resolver o problema (se não houver outros arquivos de problemas na lista de arquivos conectados).
Como publiquei
um relatório de bug na libc , é provável que esse bug seja corrigido, mas não há dúvida de que erros relacionados à ordem na qual os arquivos de cabeçalho estão conectados nos incomodarão ainda mais.
Comentários
Não tenho um sistema de comentários no meu site, mas estou trabalhando nele (ou seja, periodicamente reclamando que é difícil fazer comentários em um site estático).
Enquanto isso, você pode discutir este artigo no site do
Hacker News ou em
lobste.rs .
Agradecimentos
Graças ao usuário ufo do Hacker News, que
apontou que não é necessário usar a função lambda para adaptar o
std :: toupper para uso no
std :: transform , e também a Jonathan Muller, que
explicou que a função lambda ainda é necessária.
- Sim, a função toupper (3) do arquivo de cabeçalho <ctype.h> não é adequada para trabalhar com a maioria dos caracteres não ASCII, pois não pode manipular caracteres maiores que um byte, mas é adequado para a nossa tarefa, pois passaremos apenas cadeias de caracteres ASCII.
- Na tabela ASCII, os caracteres maiúsculos e minúsculos estão convenientemente localizados - a uma distância de 32 posições um do outro, o que significa que você pode transferir caracteres de um caso para outro simplesmente subtraindo ou adicionando 32. Em geral, se soubéssemos com certeza que todas as entradas como os dados são letras ASCII, poderíamos redefinir o quinto bit sem nenhuma verificação (por exemplo, c & 0b11011111 ) para transformar qualquer letra maiúscula em minúscula, enquanto isso não seria refletido em letras minúsculas. Mas provavelmente não sabemos, então precisamos verificar se o caractere é uma letra, para não quebrar acidentalmente caracteres não-letra, como char .
- Deve ser chamado de gráfico de dispersão com a adição de "ruído" na localização dos pontos. De fato, este é um diagrama de dispersão comum, no qual o parâmetro de interesse para nós (o tamanho dos dados de entrada) é plotado no eixo x, e a velocidade de trabalho está no eixo y (medidas por símbolo - quanto menor o valor, maior a velocidade ). A principal característica deste diagrama é que, para cada valor de parâmetro no eixo x, a amostragem é realizada várias vezes: nesse caso, o teste é repetido 10 vezes para cada tamanho de matriz.
- Ou seja, os caracteres são selecionados aleatoriamente e uniformemente no intervalo [32, 127]; portanto, a condição na função será verdadeira em cerca de 27% dos casos.
- Ambas as listagens se referem a uma implementação de ciclo bruto e diferem apenas na ordem em que os arquivos <algorithm> e <ctype.h> estão incluídos . O código fonte gerado é o mesmo para todas as implementações - nas versões rápida e lenta. Por exemplo, uma implementação com std :: transform produzirá o mesmo código lento do assembler se você incluir o arquivo <algorithm> e o mesmo código rápido se você copiar apenas a definição da função e não incluir o arquivo.
- No entanto, esse loop rápido é mais lento do que poderia, porque o ponteiro para a tabela de correspondência é lido muitas vezes ( mov rdx, QWORD PTR [rax] ) dentro do loop. Esse ponteiro pode ser diferente dependendo das configurações regionais, mas não é atualizado durante a execução do ciclo e, portanto, pode ser movido para fora do ciclo. Deve ser que o compilador acredite que não há razões suficientes para isso, já que estamos escrevendo para uma matriz de elementos do tipo char , e eles podem, em princípio, ser usados como aliases para [rax] ponteiro para a mesa. De qualquer forma, mesmo __restrict__ não ajudará aqui. Mas em outra versão do loop, em que os valores do toupper são simplesmente adicionados e nada é gravado no array, essa otimização é aplicada - o ponteiro é lido fora do loop.
- Essa verificação não é refletida no código substituível do montador, pois o compilador já sabe que os valores de caracteres estão sempre no intervalo [-128, 255] . A verificação é necessária apenas porque a API da função toupper © aceita um valor do tipo int em vez de char , para que o usuário possa transmitir qualquer número familiar do tipo int , enquanto as tabelas de correspondência são projetadas apenas para valores do tipo char , portanto, a verificação ajuda a evitar a leitura fora do buffer .
- A propósito, isso explica por que os procedimentos std :: toupper são independentes do tamanho dos dados de entrada: eles não usam ramificações (exceto para verificações de intervalo, que são notavelmente previstas), mas usam uma tabela de correspondência independente de ramificação. ↵
- Substituir esta chamada não funcionará mesmo com um desejo muito forte: o corpo da função não está disponível no arquivo de cabeçalho.
- Eu nunca encontrei uma falha no stdlib.h (ou <algoritmo> , por falar nisso) - é bem possível que muitos outros arquivos de cabeçalho C e todos os arquivos de cabeçalho C ++ também causem esse comportamento, apenas não os testei. Conectei o stdlib.h apenas para determinar o tamanho_t .
Nota Este artigo foi publicado pela primeira vez no site
Performance Matters . Os artigos traduzidos são postados aqui com permissão do autor.