Desafio de processar 1 bilhão de linhas com Go: de 1min45s para 4s com 9 métodos

• 1BRC: um desafio de escrever código para ler medições de temperatura de um arquivo de texto com 1 bilhão de linhas e calcular a temperatura mínima/média/máxima por estação
• Aconteceu de 1º a 31 de janeiro de 2024, e o objetivo era aproveitar ao máximo o Java mais recente
• A partir disso, as pessoas se interessaram e começaram a tentar em várias linguagens (Rust, Go, C++, SQL)
• Apresentação detalhada de 9 soluções escritas em Go (da mais lenta para a mais rápida)

Medições básicas

• Usando o comando cat, o tempo para ler os dados de texto com 1 bilhão de linhas (13 GB) é de 1,052 segundo.
• O comando wc, que realmente processa o arquivo, leva quase 1 minuto (55,710 segundos).
• Resolver o problema com uma solução em AWK leva 7 minutos e 35 segundos.

Solução 1: Go simples e idiomático

• A primeira solução, usando a biblioteca padrão do Go, leva 1 minuto e 45 segundos.
• Lê as linhas com bufio.Scanner e separa com base em ';' usando strings.Cut.
• Faz o parse da temperatura com strconv.ParseFloat e acumula os resultados usando um map do Go.

Solução 2: map com valores por ponteiro

• Usa map[string]*stats para evitar dois hashes no map.
• O uso de valores por ponteiro reduz o tempo de 1min45s para 1min31s.

Solução 3: evitar strconv.ParseFloat

• Faz o parse da temperatura com código personalizado em vez de strconv.ParseFloat.
• Reduz o tempo de 1min31s para 55,8 segundos.

Solução 4: usar inteiros de ponto fixo

• Representa a temperatura como inteiro para evitar operações de ponto flutuante.
• Reduz o tempo de 55,8 segundos para 51,0 segundos.

Solução 5: evitar bytes.Cut

• Em vez de percorrer todo o nome da estação para encontrar ';', faz o parse a partir do fim.
• Reduz o tempo de 51,0 segundos para 46,0 segundos.

Solução 6: evitar bufio.Scanner

• Remove o bufio.Scanner e lê o arquivo em chunks grandes.
• Reduz o tempo de 46,0 segundos para 41,3 segundos.

Solução 7: tabela hash personalizada

• Implementa uma tabela hash personalizada em vez do map do Go.
• Reduz o tempo de 41,3 segundos para 25,8 segundos.

Solução 8: processamento paralelo de chunks

• Paraleliza o código simples e idiomático, reduzindo o tempo de 1min45s para 24,3 segundos.

Solução 9: todas as otimizações e paralelismo

• Combina todas as otimizações com processamento paralelo e reduz o tempo de 24,3 segundos para 3,99 segundos.

Tabela de resultados

• Fornece uma tabela comparando todas as soluções em Go e as soluções mais rápidas em Go e Java.
• A versão mais rápida em Go processa em 2,90 segundos, e a versão em Java em 0,953 segundo.
• A versão em Java que leva menos de 1 segundo foi feita por Thomas Wuerthinger (criador do GraalVM), algo que provavelmente só foi possível por ele ser especialista nessa área.

Comentários finais

• Em tarefas cotidianas de programação, código simples e idiomático é um bom ponto de partida.
• Se você está construindo um pipeline de processamento de dados, deixar o código 4x ou 26x mais rápido pode aumentar a satisfação dos usuários e economizar custos de computação.
• Se você está construindo um runtime ou interpretador, melhorias de desempenho são importantes.

Opinião do GN⁺

• Este artigo explora várias formas de otimizar processamento de grandes volumes de dados com Go e oferece um estudo de caso interessante sobre otimização de desempenho.
• Mostra que, no processo de otimização, implementar estruturas de dados como uma tabela hash personalizada além da biblioteca padrão do Go teve um papel importante.
• Destaca o efeito do paralelismo, combinando otimização em núcleo único com paralelização para alcançar ganhos de desempenho impressionantes.
• O artigo oferece insights úteis para engenheiros de software que desenvolvem aplicações sensíveis a desempenho.
• O quanto essas otimizações são úteis em ambientes reais de produção pode variar conforme o caso de uso. Nem toda aplicação precisa desse nível de otimização.

[cosine20]

Fiquei curioso sobre quais tarefas específicas foram realizadas na etapa 7. Foi o trecho em que houve uma melhora de desempenho enorme haha

[sddsdd94]

Achei interessante como ele separou por etapas e mostrou o ganho de desempenho em cada uma delas, haha

[galadbran]

Até com wc dá para fazer em 1 minuto.... no fim das contas, o melhor mesmo é não escrever código... haha

[jhbaek]

Obrigado por compartilhar esse ótimo texto. Isso me fez lembrar de uma época em que eu era obcecado por otimização de sistemas, haha.
À medida que fui ganhando experiência no desenvolvimento, acabei me afastando aos poucos do caminho da otimização, porque vivi muitas situações em que o código mais otimizado possível era difícil de manter e, por isso, complicado de operar em um ambiente organizacional. (De repente, uma reflexão pessoal)

[misolab]

Código otimizado para a organização!!

[GN⁺]

Comentários do Hacker News

• O primeiro usuário mencionou que, como não tinha experiência com otimização de código para manipulação de dados, a primeira seção, que usa cat, wc etc. para obter uma linha de base, foi especialmente interessante. Ele considera esse método uma forma fácil de chegar a uma faixa "razoável".
• O segundo usuário mencionou que o tempo de processamento usando a biblioteca Polars foi de 33 segundos e demonstrou interesse pela solução mais simples que chega perto da solução com otimização manual mais rápida.
• O terceiro usuário comentou que os relatórios de profiling de desempenho em Go são confusos e explicou que, quando o tempo de execução de uma linha específica de código não parece intuitivo, isso pode acontecer porque os dados são difíceis de prever e o preditor de desvios pode errar a previsão.
• O quarto usuário compartilhou o resultado de ter feito o 1BRC (1 Billion Row Challenge) em Go e mencionou que aprendeu técnicas de otimização específicas da linguagem. Por exemplo, leitura de memória sem verificação de limites usando unsafe.Pointer, funções dos pacotes bytes e bits da biblioteca padrão escritas em assembly, configuração para desativar o coletor de lixo e formas de fixar goroutines a threads.
• O quinto usuário afirmou que um desenvolvedor de shell script provavelmente já teria terminado o processamento específico de 1 bilhão de linhas enquanto os desenvolvedores de outras linguagens ainda estariam se preparando.
• O sexto usuário argumentou que bancos de dados são mais rápidos, menos complexos e mais robustos para atualizações de dados do que código de aplicação, enfatizando que mais trabalho deveria ser feito no banco de dados.
• O sétimo usuário compartilhou a experiência de ter desenvolvido, em 2010, um aplicativo web usando PostgreSQL para consultar 270 milhões de linhas de dados climáticos da Environment Canada, e que esse software chegou a receber um prêmio. O aplicativo foi otimizado para gerar relatórios em menos de um minuto.
• O oitavo usuário comentou que é legal ver que o código paralelo em Go ainda mantém o estilo idiomático da linguagem.
• O nono usuário mencionou que, ao lidar com arquivos de texto grandes no CLI, pular o parsing de Unicode faz awk, grep e afins ficarem muito mais rápidos, e afirmou que adicionar LC_ALL=C à solução em awk pode reduzir o tempo de processamento para menos de um minuto.
• O último usuário comentou que é interessante que a versão mais rápida em Java seja mais rápida do que a versão mais rápida em Go, avaliando que o desempenho da JVM é bastante bom.