Desafio de um bilhão de linhas

 (morling.dev)
2 pontos por GN⁺ 2024-01-05 | 2 comentários | Compartilhar no WhatsApp
  • O One Billion Row Challenge (1BRC), realizado durante todo o mês de janeiro de 2024, é um desafio de desempenho para ver até onde o Java pode ficar rápido ao processar um arquivo de texto com 1 bilhão de linhas
  • A entrada é um texto simples no formato station;temperature, mas é preciso calcular com exatidão a temperatura mínima, média e máxima de cada estação e imprimir o resultado em ordem alfabética pelo nome
  • A implementação permite apenas Java; distribuições do SDKMan e builds Early Access do openjdk.net podem ser usadas, mas dependências externas são proibidas
  • Os participantes enviam suas soluções por pull request no repositório 1brc no GitHub e podem comparar formato de resposta e desempenho com a implementação-base fornecida
  • A avaliação define a classificação no leaderboard pela média de 3 execuções, descartando o melhor e o pior resultado entre 5 execuções no mesmo ambiente Hetzner Cloud CCX33

O desafio Java para agregar 1 bilhão de linhas o mais rápido possível

  • One Billion Row Challenge é um desafio de desempenho em Java realizado de 1º a 31 de janeiro de 2024
  • Os participantes escrevem um programa em Java que lê medições de temperatura de um arquivo de texto e calcula a temperatura mínima, média e máxima de cada estação meteorológica
  • O ponto central da dificuldade é que o arquivo de entrada tem 1.000.000.000 de linhas
  • A entrada tem uma estrutura simples, com uma medição por linha
    • Ex.: Hamburg;12.0
    • Ex.: Bulawayo;8.9
    • Ex.: Palembang;38.8
  • A saída deve ordenar os nomes das estações em ordem alfabética e mostrar os valores min/mean/max de cada estação
    • Ex.: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Regras de envio e ambiente de execução

  • O objetivo é criar a implementação Java mais rápida para executar a mesma tarefa
  • As otimizações podem usar virtual threads, Vector API e SIMD, otimização de GC, compilação AOT e outros recursos
  • As regras básicas são as seguintes
    • O envio deve ser escrito em Java
    • Podem ser usadas distribuições Java fornecidas pelo SDKMan e builds Early Access do openjdk.net
    • Builds EA de projetos OpenJDK como Valhalla também são permitidos
    • Dependências externas não podem ser usadas
  • Os participantes clonam o repositório 1brc e enviam sua implementação seguindo as instruções do README
  • A implementação-base é fornecida como referência de comparação e para verificar o formato correto da resposta
  • O envio é feito abrindo um pull request no repositório upstream

Como o leaderboard é calculado e o compartilhamento na comunidade

  • A avaliação é feita em uma instância Hetzner Cloud CCX33
    • Especificações: 8 dedicated vCPU, 32 GB RAM
    • O tempo total de execução é medido com o programa time
    • Cada envio é executado 5 vezes seguidas
    • A execução mais lenta e a mais rápida são descartadas
    • A média dos tempos das 3 execuções restantes se torna o resultado daquele envio
    • O resultado é adicionado ao leaderboard
  • A discussão sobre técnicas de otimização continua na seção de discussion do repositório no GitHub
  • Também existe um espaço de Show & Tell para compartilhar implementações em linguagens além de Java, onde já foram publicadas versões do 1BRC em Rust, Go, C++ e outras

Leituras relacionadas

2 comentários

 
GN⁺ 2024-01-05
Opiniões no Hacker News

  • A solução que atualmente parece ter o melhor desempenho [0] não leva em conta colisões de hash, então acho que pode produzir resultados incorretos se o conjunto de dados tiver um número suficiente de cidades diferentes
    Fico curioso se estou deixando passar algo
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • Sim. Esse problema apareceu ontem e, de fato, duas soluções dependiam de funções de hash ajustadas a um conjunto de dados específico, violando a regra de que deve funcionar para todos os nomes de estações, mas isso passou despercebido durante a avaliação
      Por enquanto, esses itens foram removidos do ranking, e os dois autores estão corrigindo suas submissões, então elas devem ser adicionadas novamente depois
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • Com a abordagem a seguir, acho que dá para processar tudo em 0,3 segundo
    Como a temperatura tem uma casa decimal, em geral cerca de 400 valores bastam, e como os nomes de lugares também são finitos, cerca de 400, dá para criar uma tabela de consulta com aproximadamente 160 mil combinações de temperatura×localidade
    Gerar automaticamente uma máquina de estados que mapeie essas 160 mil entradas para buckets únicos de uma tabela hash, qualquer que seja a posição de rotação em que estejam dentro de um registrador de 4 bytes, e, em um registrador de estado de 32 bits, fazer a cada ciclo uma consulta à tabela de transição de estados e um XOR com os próximos 4 bytes
    Basta varrer todos os dados na velocidade da memória e incrementar os contadores por estado; como há só 65K estados, os contadores cabem no cache
    Com AVX512, seria possível rodar 512 dessas máquinas de estado de 32 bits em paralelo por núcleo, então o cálculo não deve ser o gargalo
    Temperaturas altas/baixas que não mapeiem para buckets válidos ou nomes de lugares desconhecidos iriam para um código lento; o tratamento de mínimo/máximo também poderia ser feito com esse escape, ocorrendo só algumas milhares de vezes
    Acho que esse método conseguiria operar na velocidade da memória apenas com um único núcleo AVX512, então não vejo vantagem em dividir entre vários núcleos

    • Não precisa de tabela de consulta. O que se pede é apenas mínimo/média/máximo, então dá para calcular tudo em uma única passagem, sem armazenar os dados
      O necessário é uma tabela hash com 400 entradas, três valores de ponto flutuante em execução para mínimo, média e máximo, e um inteiro de contagem para atualizar a média
      Mesmo usando 16 bytes para o nome, tudo fica dentro de 16 KB
      O tempo de execução será dominado por E/S e, depois disso, provavelmente pelo parsing de JSON
    • Um único núcleo não consegue saturar a largura de banda da memória. O núcleo é limitado pelo paralelismo e pela latência da memória
      A maioria dos chips de servidor x86 modernos consegue retirar 2 loads SIMD por clock, então, com AVX2, a 1 GHz, algo em torno de 32 GB/s é possível; portanto, AVX-512 não é estritamente necessário para maximizar a largura de banda por núcleo
      Mas, se a leitura vier da DRAM, você provavelmente será bloqueado bem antes disso, normalmente perto de 10–16 GB/s em servidores
      Enquanto a maior parte dos dados transbordar para a RAM, a vazão de um único núcleo cai bastante, e em grandes tarefas de streaming o paralelismo multinúcleo quase sempre compensa
      Dá para verificar facilmente alocando um bloco de memória muito maior que o cache L3, provocando page faults antecipadamente e, depois, fazendo loads vetoriais desenrolados (AVX2/AVX-512) em um loop apertado
    • Não entendo como seria possível executar a máquina de estados em paralelo se o próximo estado sempre depende do estado anterior
      Também me pergunto como interpretar o registrador de estado. Ao fazer XOR com 4 bytes de entrada, em nomes de lugares inesperados isso pode se tornar praticamente qualquer um dos 4,7 bilhões de valores possíveis
      Mesmo para nomes esperados, se forem maiores que 4 bytes, não seriam necessários vários estados para cada um deles a fim de distingui-los de outros nomes com prefixos comuns?
    • Acho que é preciso confirmar a interpretação das regras. Não está claro se é válido um código especializado nos 400 nomes de lugares conhecidos, mas que suporte nomes adicionais por um caminho lento
      As regras dizem que, embora o gerador de dados use um conjunto fixo de nomes de estações, qualquer solução deve funcionar com nomes de estações UTF-8 arbitrários
    • Para encontrar os nomes de lugares, no fim das contas é preciso ler e fazer o parsing do arquivo inteiro

  • Em vez de descartar a execução mais lenta e a mais rápida e usar a média das três restantes, acho melhor descartar as duas mais lentas, ou simplesmente aceitar o valor mais rápido
    Não vejo um motivo válido para descartar um bom resultado de execução

    • Isso é um método de medição bastante padrão chamado média aparada (Trimmed Mean): https://statisticsbyjim.com/basics/trimmed-mean/
    • Há motivo para descartar a melhor execução. Se você assume que o sistema se comporta de forma previsível e apenas fica mais lento por causa de tarefas em segundo plano, usar a melhor execução pode fazer sentido
      Mas, se houver qualquer fonte de não determinismo dentro do programa — algo mais comum do que se imagina —, o melhor tempo pode ser pouco representativo
      Sobre isso, https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... é um bom texto
    • Se descartar a execução mais rápida é inaceitável, fico me perguntando por que descartar a execução mais lenta seria aceitável

  • Do ponto de vista de quem fica discutindo as regras, dá vontade de, na primeira execução, subir um daemon em segundo plano, carregar o arquivo inteiro na memória e fixá-lo ali, e ainda puxar o cache antecipadamente para que as execuções seguintes, na prática, só façam uma varredura linear
    Dependendo de até onde você estica a interpretação das regras, também parece possível pré-calcular o resultado na primeira execução; ou então parsear os números previamente para um formato mais compacto e, nas execuções seguintes, lê-los diretamente como uma soma acumulada
    Isso não combina em nada com o espírito da competição, mas, pelas regras visíveis, não parece estar proibido
    Se a pré-computação for indesejada, também seriam possíveis truques como pré-ordenar a entrada, pré-parseá-la, ou usar compressão, ordenação e um layout de memória ordenado
    No extremo, daria até para fazer patch no script calculate_time para retornar 0 segundo e retornar 9999 para os concorrentes

    • Se você fornecer aos participantes exatamente o arquivo que será usado de fato na competição, aí surge um problema real
      Entre simplesmente hardcodar a resposta em uma linha sem nem ler a entrada e processar assumindo que não se conhece o conteúdo do arquivo, há algo como 1 bilhão de níveis de zona cinzenta da pré-computação
      A competição pode virar uma disputa para decidir o que é pré-computação justa e o que não é
      É por isso que competições de machine learning não mostram os dados finais aos participantes
    • Isso parece violar esta regra
      Ela diz que o cálculo deve acontecer no momento da execução da aplicação, e que não se pode processar o arquivo de medição no momento do build e embutir o resultado no binário
    • Acho que as regras deveriam especificar que cada execução rode em um tmpfs separado e que, entre execuções, todos os processos e o page cache sejam limpos

  • Fico pensando se isso não é simplesmente um problema limitado pela velocidade do disco. Tenho dúvidas se otimizações como SIMD ou multithreading fariam diferença
    Embora varie conforme o número de estações diferentes e o método de consulta no hash, sou cético quanto a isso ser mensurável em comparação com a E/S

    • O acesso a disco pode ser paralelizado, e NVMe é muito rápido, então o gargalo pode estar mais na CPU do que no disco
      Sistemas projetados assumindo hardware moderno tiram proveito disso, e o redpanda.com, onde trabalho, é um exemplo
      O parsing é uma parte grande do tempo de computação, e técnicas SIMD como SWAR para encontrar delimitadores podem ajudar
      Se quiser ver uma implementação limpa desse tipo de algoritmo, Stringzilla é uma boa: https://github.com/ashvardanian/StringZilla
      Sobre o fato de o arquivo ficar totalmente em cache na memória depois da primeira execução, respondi aqui: https://news.ycombinator.com/item?id=38864034
    • Depende totalmente da carga de trabalho e do hardware. Mesmo um SSD comum de consumidor consegue sustentar facilmente 7 GB/s (56 Gbps) se você usar só 700 GB de 2 TB
      Servidores comuns geralmente têm pistas PCIe suficientes para conectar 15 SSDs desses, então a largura de banda de E/S de um servidor fica em um nível parecido com a largura de banda de memória
      Servidores mais caros têm mais pistas, e pistas mais rápidas, como PCIe 5.0
      Esse arquivo tem 1 bilhão de linhas e, comprimido, fica em torno de 1 GB; depois da primeira execução descartada, ele fica na memória, então, nesse cenário, a largura de banda de E/S não é importante
      O repositório no GitHub diz que ele tem 12 GB descompactado, o que ainda confirma que a largura de banda de E/S não é o ponto importante
    • Esta apresentação do Daniel Lemire é interessante: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      O ponto central é que raramente o disco é o gargalo
    • Depende do sistema operacional e do sistema de arquivos. O arquivo de entrada tem cerca de 12 GB e é executado 5 vezes em uma máquina com 32 GB de memória, então, depois da primeira execução, o arquivo inteiro pode ficar em cache na memória
      Por exemplo, no Linux com ext2, é provável que o arquivo inteiro seja cacheado após a primeira execução, mas com ZFS talvez não
    • Para fazer o parsing da forma mais rápida, parece claro que o ideal é carregar tudo na RAM e processar de trás para frente, a partir do fim
      Assim os números aparecem do dígito menos significativo para o mais significativo, depois vêm o delimitador e a string, e você segue até encontrar EOF ou uma quebra de linha

  • Pelas regras, a submissão deve funcionar corretamente para todas as entradas, mas parece significar que ela pode, e provavelmente deve, ser ajustada para as entradas específicas geradas por create_measurements.sh
    Por exemplo, dá para imaginar uma submissão que use uma função de hash perfeita ajustada ao conjunto de estações fornecido

    • Se esse requisito existir, é sensato fazer os dados de teste serem diferentes dos dados de exemplo
      Assim se evitam otimizações com overfitting
    • UTF-8 torna isso muito mais difícil. Mas, se você seguir apenas a letra das regras e não o espírito delas, basta encaminhar para uma implementação lenta assim que detectar um byte maior que 127
      Um byte maior que 127 indica um caractere UTF-8 multibyte

  • Por diversão, fiz uma comparação de velocidade entre awk e Java
    É um script que, com awk -F';', acumula soma, contagem, mínimo e máximo por estação, e no END calcula e imprime a média

    • Gostaria de ver uma comparação de velocidade com o wrapper de dados externos de arquivo do PostgreSQL: https://www.postgresql.org/docs/current/file-fdw.html
      A ideia seria criar o arquivo CSV como uma tabela externa com file_fdw e calcular MIN, AVG e MAX com GROUP BY station_name
    • Rodando com ClickHouse local, dá cerca de 15,2 segundos
      No clickhouse local, ele lê file('measurements.txt', 'CSV', 'station String, t Float32'), agrupa min, max e avg por estação, e executa com max_threads = 8
      A maior parte do tempo é gasta no parsing do arquivo
    • Como a variável sum pode ficar bem grande, é melhor usar uma média em streaming
      Por exemplo, algo como new_mean = ((n*old_mean)+temp)/(n+1)

  • É um desafio interessante, mas é uma pena que seja exclusivo para Java. Estou ansioso para o momento em que as pessoas começarem a criar bytecode da JVM manualmente

    • Pelo que se vê na discussão, parece haver submissões em várias linguagens. Há Go, Rust, Python, C++ etc.
      [0] https://github.com/gunnarmorling/1brc/discussions
    • Ou também dá para interpretar “deve ser escrito em Java” como “deve usar a JVM no início da execução”, e certamente é possível iniciar outro processo a partir do Java

  • Divertido. Dá uma sensação de pós-Advent of Code
    Se fosse uma comparação justa entre linguagens, teria que incluir também o make e o tempo de build. Faz alguns anos que não uso Java/Maven, mas ver o download de ./mvnw clean verify continuar pelo segundo minuto me fez lembrar o motivo

    • O tempo de build do Java é muito rápido. O que está sendo medido agora é a velocidade da internet
      E, como ferramenta de build com compilação incremental, o Gradle é mais rápido
    • Se incluir o tempo de build, então também deveria incluir o tempo de programação, e ambos deveriam ser divididos pelo número de vezes que o código será executado ao longo de sua vida útil
      Também seria preciso somar uma proporção adequada do tempo gasto para aprender a programar
      Nesse tipo de desafio, uma versão muito ingênua teria grande chance de vencer; acho que isso não só é irrealista, como também vai contra o propósito do desafio
    • Não entendo por que usar clean
      É como descartar o cache e depois reclamar que ficou lento
    • Maven não é necessário
      Está dito que não é possível usar dependências externas

  • Havia uma tarefa muito parecida na disciplina de C da Universidade Técnica Tcheca
    Todas as submissões dos alunos eram continuamente avaliadas em um ranking, e muitos alunos passavam dezenas de horas otimizando para conseguir pontos extras por notas melhores — na prática, pontos de status
 
dlehals2 2024-01-10

O 1º lugar fez em 6 segundos... impressionante.