Faz pouco uma proposta para o kernel Linux foi lançada, no qual se propõe a inclusão de um conjunto de patches com implementação otimizada da função memchr() usado para procurar um caractere em uma matriz.
A função memchr() varre os n bytes iniciais da área de memória apontada por s para a primeira instância de c. Tanto c quanto os bytes na área de memória apontada por s são interpretados como caracteres sem sinal.
A proposta promete seja mais rápido para localizar um caractere dentro de um bloco de memória. Em testes de desenvolvedores, a nova implementação pode ser quase quatro vezes mais rápida em grandes buscas
Ao contrário da versão anterior, que usava uma comparação byte a byte, a implementação proposta é criada considerando o uso pleno de registradores de CPU de 64 bits e 32 bits. Em vez de bytes, a comparação é feita usando palavras de máquina, o que permite que pelo menos 4 bytes sejam comparados por vez.
Esta série de patches otimizou "memchr()" e adicionou uma macro para
"memchr_inv()" para que ambas as funções possam usá-lo para gerar uma máscara de bits.A implementação original de "memchr()" é baseada na comparação de bytes,
que não usa totalmente o registrador de 64 ou 32 bits na CPU. Implementamos um
comparação por palavras para que pelo menos 4 bytes possam ser comparados ao mesmo
tempo. O memchr() otimizado é quase 4 vezes mais rápido que o original
para cadeias longas. No Linux Kernel, descobrimos que o comprimento da string
pesquisado por "memchr()" é de até 512 bytes em drivers/misc/lkdtm/heap.c.
Ao pesquisar em strings grandes, a nova versão acabou sendo cerca de 4 vezes mais rápida que a antiga (por exemplo, para cadeias de 1000 caracteres). Para pequenas redes, a eficiência da nova implementação não é tão significativa, mas ainda é superior à versão original.
O interessante da nova proposta é a melhoria para grandes redes, o que melhora consideravelmente os tempos. Vale ressaltar que no kernel do Linux, o tamanho das strings processadas em memchr() atinge 512 bytes. Em nossos testes, o ganho de desempenho para strings de 512 bytes, em uma situação em que o caractere de pesquisa está no final da string, é 20%.
Vale ressaltar que a versão original do memchr() é implementada com a técnica de comparação byte-wise, que não utiliza totalmente os registradores na CPU de 64 bits ou 32 bits.
Usamos a comparação de palavras inteiras para que 8 caracteres possam ser comparados ao mesmo tempo na CPU. Este código é baseado na implementação de David Light.
Criamos dois arquivos para medir o desempenho do primeiro arquivo que contém em média 10 caracteres à frente do caractere de destino. O segundo arquivo contém pelo menos 1000 caracteres antes do personagem alvo.
Nossa implementação de "memchr()" é um pouco melhor no primeiro teste e quase 4 vezes mais rápido que o original implementação no segundo teste.
Teste do kernel 5.18 com a nova variante "memchr()" para arquiteturas de 32 bits e 64 bits não revelou nenhum problema.
O que acontece se p não for 8 (ou 4 em alvos de 32 bits) alinhados por bytes? Nem todos os destinos suportam cargas não alinhadas (eficientes), certo?
Eu acho que funciona se p não for 8 ou 4 bytes alinhados. Digamos que a string tenha 10 bytes. O loop for aqui procurará os primeiros 8 bytes. Se o caractere de destino estiver nos últimos 2 bytes, o segundo loop for o encontrará. Também funciona assim em máquinas de 32 bits.
Ganho de desempenho geral ainda não avaliado dos subsistemas do kernel ao usar a variante "memchr()" otimizada, nem foi discutido se deve substituir a implementação (a chamada da função memchr() ocorre 129 vezes no código do kernel, incluindo drivers e sistemas de arquivos).
Finalmente Se você estiver interessado em saber mais sobre isso, você pode verificar os detalhes no link a seguir.