Introdução à competição 1BRC
- Na competição 1BRC, previa-se que, depois de processar os "suspeitos de sempre", o gargalo seria fazer o parsing das temperaturas do arquivo CSV.
- As temperaturas podiam aparecer em quatro formatos:
-XX.X, -X.X, X.X e XX.X, e no início era usada uma chamada à biblioteca Double.parseDouble().
- Porém, logo surgiram soluções personalizadas, e uma delas parecia ser um método otimizado sem loop e com apenas dois desvios.
- Então a solução apresentada por Quân Anh Mai (@merykitty) incendiou a hashtag #1BRC no Twitter. Essa solução usava uma única leitura de arquivo sem nenhuma instrução
if.
Análise da SWAR mágica de merykitty
- O código de merykitty é composto por apenas 18 operações ALU e inclui uma única chamada de função de baixo nível,
numberOfTrailingZeros().
- O número
long de entrada contém 8 bytes do CSV, e a saída é a temperatura em formato inteiro (10 vezes a temperatura real).
- Essa técnica é chamada de "SIMD Within A Register" (SWAR) e usa registradores e instruções padrão da CPU.
- O código passa por etapas como detectar se o número é negativo, remover o caractere de sinal, encontrar a posição do ponto decimal, alinhar o conteúdo a um template, converter caracteres ASCII em valores numéricos, multiplicar cada dígito por seu peso e somar tudo, e por fim aplicar o sinal.
- Essas etapas são executadas usando apenas operações ALU.
Conclusão
- Como merykitty conseguiu fazer tudo isso sozinho em apenas alguns dias é o verdadeiro mistério que um post de blog não consegue explicar.
- O QuestDB é open source e oferece inserção rápida de dados e recursos de análise SQL sob a licença Apache 2.0.
Opinião do GN⁺
- Este artigo mostra a complexidade e a criatividade da técnica SWAR, criada para resolver um problema aparentemente simples de parsing de temperatura. Isso destaca o poder das operações de bits e a importância da otimização na programação.
- Essa abordagem pode ser um caso interessante especialmente para engenheiros de software iniciantes com interesse em programação de sistemas ou no desenvolvimento de aplicações sensíveis a desempenho.
- Para ampliar a compreensão sobre operações de bits e otimização, pode ser útil procurar competições de programação online ou tutoriais que tratem de temas ou problemas relacionados.
- São necessárias mais pesquisas sobre como essa técnica pode ser aplicada em ambientes industriais reais e se existem outros bancos de dados ou sistemas que usem técnicas de otimização semelhantes.
- Ao adotar sistemas como o QuestDB, é preciso considerar não apenas o ganho de desempenho, mas também outros fatores, como manutenibilidade, legibilidade do código e suporte técnico de longo prazo.
1 comentários
Comentário do Hacker News
Resumo dos comentários no Hacker News relacionados ao artigo do simdjson:
Interpretação sobre o contexto do código: a solução apresentada é excelente, mas exige a premissa de que os dados estejam bem estruturados. Verificação eficiente de erros e recursos de recuperação têm grande valor em parsers experientes.
Técnica de parsing de números: multiplicar cada bitfield numérico pela respectiva potência de 10 e usar
MULpara fazer shift/soma é uma técnica conhecida. Veja o blog do Lemire.Explicação sobre SWAR (SIMD Within A Register): há muitos exemplos de implementação de rotinas SWAR eficientes em Java/Scala usando var handles de visualização de array de bytes.
Definição simples de SWAR: "SIMD Within A Register" executa operações SIMD dentro de um único registrador.
Pergunta sobre o gargalo de I/O no BRC (Branchless Ray Casting): não está claro por que a CPU seria o gargalo.
Experiência com uso de SWAR no 68000: era possível processar 4 bytes em paralelo de uma vez, mas lidar com overflow era complicado. Gostou muito do artigo.
Espaço de estados e superotimizador: como o espaço de estados é pequeno, surgiu a pergunta se existe um superotimizador capaz de produzir resultados semelhantes.
Instruções AVX e suporte SIMD em Java: esse algoritmo poderia ser executado com paralelismo de 32x usando instruções AVX, mas é uma pena que Java não dê suporte adequado ao uso de CPU SIMD, exceto em casos específicos.
Compreensão sobre manipulação de bits: este artigo ajudou a entender manipulação de bits melhor do que qualquer outro anterior, e houve agradecimento ao autor que apresentou a solução em Java para o desafio 1BRC.