1brc ObjectPascal
End of Challenge with no oops
Este é o repositório que coordenará o desafio de 1 bilhão de fileiras para o objeto Pascal.
O desafio de um bilhão de fileiras (1BRC) é uma exploração divertida de quão longe o objeto moderno Pascal pode ser pressionado por agregar um bilhão de linhas de um arquivo de texto. Pegue todos os seus threads, procure o SIMD ou faça qualquer outro truque e crie a implementação mais rápida para resolver esta tarefa!
O arquivo de texto contém valores de temperatura para uma variedade de estações meteorológicas. Cada linha é uma medição no formato <string: station name>;<double: measurement> , com o valor de medição com exatamente um dígito fracionário. As linhas são separadas por um feed de linha única igual de LF (ASCII 10) para consistência com o desafio original - e não Cr+LF (ASCII 13+10). A seguir, mostra dez linhas como exemplo:
Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
Bridgetown;26.9
Istanbul;6.2
Roseau;34.4
Conakry;31.2
Istanbul;23.0
The task is to write an Object Pascal program which reads the file, calculates the min, mean, and max temperature value per weather station, and emits the results on STDOUT like this (ie, sorted alphabetically by station name, and the result values per station in the format <min>/<mean>/<max> , rounded to one fractional digit, with the decimal separator being a period . , and for that you can chose one of the options presented na seção de arredondamento ou implemente o seu próprio que é consistente com as opções fornecidas.):
{Abha=-23.0/18.0/59.2, Abidjan=-16.2/26.0/67.3, Abéché=-10.0/29.4/69.0, Accra=-10.1/26.4/66.4, Addis Ababa=-23.7/16.0/67.0, Adelaide=-27.8/17.3/58.5, ...}
Os envios serão através de um PR (solicitação de tração) para este repositório.
O desafio acontecerá de 10 de março até 10 de maio de 2024.
Ao criar sua entrada, faça o seguinte:
entries com seu primeiro nome inicial e sobrenome, por exemplo, para Gustavo Carreno: entries/gcarreno .README.md com algum conteúdo sobre sua abordagem, por exemplo, entries/gcarreno/README.md .entries/<your name>/src , por exemplo, entries/gcarreno/src .bin da raiz deste repositório..gitignore personalizado para algo que não está presente no principal, faça.Esse desafio é principalmente nos permitir aprender algo novo. Isso significa que a cópia do código de outras pessoas será permitida, sob essas condições:
API de qualquer sistema operacional ou bibliotecas C/C++ externas.Jedi Project ou mesmo mORMmot (ou qualquer outra coisa), se ele compilar, executa a plataforma cruzada, é permitido.IDE . IMPORTANTE
Esse desafio pode ser inserido mesmo se você tiver acesso à edição comunitária do Rad Studio. Eu tenho uma VM do Windows, com o Rad Studio instalado, que fará a compilação cruzada necessária no meu host Linux.
Envie sua implementação e faça parte do Líder Board!
Com a ajuda desta magnífica comunidade, conseguimos finalmente chegar a uma solução arredondada que funciona.
Isso significa que estou incentivando todos a usar o código que está agora na linha de base.
Eu tenho que deixar o cristal claro que o uso desse código é uma opção , que você sempre pode optar por não participar.
Mas se você optar, basta incluir essa unidade em sua entrada e o trabalho está pronto.
OBSERVAÇÃO
Agora temos uma versão Lázaro e uma versão Delphi do gerador para 32B e 64B.
Para produzir um bilhão de linhas de texto, estamos fornecendo o código -fonte para o gerador oficial, para que todos tenhamos os mesmos dados de entrada.
| Parâmetro | Descrição |
|---|---|
| -h ou --help | Escreve esta mensagem de ajuda e sai |
| -v ou --version | Escreve a versão e sai |
| -i ou --input-File <NameName> | O arquivo que contém as estações meteorológicas |
| -o ou --output-File <NameName> | O arquivo que conterá as linhas geradas |
| -n ou --line-contagem <número> | A quantidade de linhas a serem geradas (pode usar 1_000_000_000) |
| -4 ou --400 estações | Apenas 400 estações meteorológicas no arquivo de saída |
OBSERVAÇÃO
Isso ainda está um pouco em fluxo, ainda precisando fazer a versão Delphi.
Para verificar a saída oficial, estamos fornecendo o código -fonte para a linha de base oficial.
| Parâmetro | Descrição |
|---|---|
| -h ou --help | Escreve esta mensagem de ajuda e sai |
| -v ou --version | Escreve a versão e sai |
| -i ou --input-File <NameName> | O arquivo que contém 1 bilhão de linhas |
Você pode verificar as measurements.txt geradas.txt com um utilitário SHA256 :
Linux
$ sha256sum ./data/measurements.txtWindows (linha de comando)
C:> CertUtil -hashfile .datameasurements.txt SHA256Windows (PowerShell)
Get-FileHash . data measurements.txt - Algorithm SHA256 SHA256 esperado: 2b48bc2fa0b82d748925a820f43f75df01cc06df7447c7571e52d3962e675960
Agora existe uma versão Delphi da linha de base. Isso significa que agora temos uma maneira oficial de gerar uma saída válida em ambos os lados da cerca.
Com isso, agora temos o hash oficial: 4256d19d3e134d79cc6f160d428a1d859ce961167bd01ca528daca8705163910
Há também uma versão arquivada da saída da linha de base
Para facilitar a comparação com a linha de base, aqui estão os hashes para diferentes contagens de linha geradas:
| Linhas | Hash do arquivo de entrada | Hash de arquivo de saída |
|---|---|---|
| 1_000 | 0be4844a2417c08a85a44b26509bbe6868a6f65d0e0d087d3f9ceedc02f5ceaa | d42c37ca405f230e91dd0a75e6741dbbbcddd2338963ea0f0e727cf90ecbd7e7 |
| 10_000 | 447380628ca25b1c9901c2e62e01591f2e2f794d2888934a5e9d4a67d72346a5 | b4dd36d80a63fefdccbff50ffaaef7e2092034935c729b3330569c7c7f7351fc |
| 100_000 | dd3a4821e91de82e44f17f65b1951af8a21652b92c20a7e53a1fa02ea6e5fbd2 | c9e50d46bba327727bf4b412ec0401e0c2e59c9035b94b288e15631ca621cb52 |
| 1_000_000 | c2955973c3db29bf544655c11d2d3c7ac902c9f65014026b210bd25eb1876c0c | 5fedbd9811660ee3423f979a0c854ec8b70da3e804170bc39bcc400c94f93bc0 |
| 10_000_000 | 90193d314e991f7789258c8b6b06c493a4d624991e203b12343c2a8ce1d0c7fd | 2f3a6383b3bc83a9ad53fc0773de2da57bd4add8a51662cdb86bfca502d276a3 |
| 100_000_000 | f55384da4646a0c77a1d5dd94a58f8430c5956fe180cedcb17b4425fe5389a39 | 7e8339b5d268fa400a93887b7a1140ac1adf683a8e837e6274fd71e383c26c6b |
Decidi que gostaria que esse desafio fosse virado para 11!
Isso significa que existem algumas diferenças do original.
Os resultados originais são calculados em um conjunto menor de estações meteorológicas: 400.
Embora eu não tenha tabulado quantos residem no arquivo de entrada, não o limitamos a nenhum número, pois usamos as estações completas ~ 40k presentes no data/weather_stations.csv para gerar o arquivo de entrada.
Outra diferença são as máquinas em que elas são executadas.
Estou usando minha própria máquina, com as especificações mencionadas na seção de resultados abaixo.
Também estou permitindo o uso dos 32 threads completos que minha máquina fornece, onde o desafio original o limita a 8.
O desafio original também possui uma segunda tabela de resultados com 10k estações e o uso de todos os 64 threads.
Com tudo isso dito, a comparação com o desafio original deve ser feita com isso em mente.
Esses são os resultados da execução de todas as entradas no desafio do meu computador pessoal:
| # | Resultado (m: s.ms) | Compilador | Submissor | Notas | Certificados |
|---|---|---|---|---|---|
| 1 | 0: 1.261 | Lazarus-3.99, FPC-3.3.1 | Arnaud Bouchez | Usando mORMot2 , 32 threads | |
| 2 | 0: 1.950 | Lazarus-3.99, FPC-3.3.1 | O Coddo | Usando SCL , 32 threads | |
| 3 | 0: 2.101 | Lazarus-3.99, FPC-3.3.1 | Georges Hatem | Usando mORMot2 , 32 threads | |
| 4 | 0: 5.248 | Lazarus-3.99, FPC-3.3.1 | Hartmut mais grossa | Usando 32 thread | |
| 5 | 0: 7.363 | Lazarus-3.99, FPC-3.3.1 | Benito van der Zander | Usando 32 threads | |
| 6 | 0: 9.627 | Lazarus-3.99, FPC-3.3.1 | G Klark | Usando 32 threads | |
| 7 | 0: 13.321 | Lazarus-3.99, FPC-3.3.1 | Székely Balázs | Usando 32 threads | |
| 8 | 0: 18.062 | Lazarus-3.99, FPC-3.3.1 | Lurendrejer Aksen | Usando 32 threads | |
| 9 | 1: 9.354 | Lazarus-3.99, FPC-3.3.1 | Richard Lawson | Usando 1 thread | |
| 10 | 2: 24.787 | Lazarus-3.99, FPC-3.3.1 | Iwan Kelaiah | Usando 1 thread | |
| 11 | 6: 2.343 | Delphi 12.1 | Brian Fire | Usando 8 threads | |
| 12 | 6: 53.788 | Delphi 12.1 | David Cornelius | Usando 1 thread | |
| 13 | 8: 37.975 | Delphi 12.1 | Daniel Töpfl | Usando 1 thread |
OBSERVAÇÃO
Depois que alguns testes realizados pelo @Paweld, não faz sentido fazer uma execução
HDD. Eu removi isso dos resultados
Cada candidato é executado 10 vezes seguidas para SSD e HDD usando hyperfine para o tempo.
O valor médio das 10 execuções é o resultado desse candidato e será adicionado à tabela de resultados acima.
Os valores MIN e MAX são descartados e os 8 valores restantes são usados para calcular a média.
As mesmas measurements.txt exatas.txt arquivo é usado para avaliar todos os candidatos.
Isso está sendo administrado apenas para se gabar de direitos e a diversão de tal desafio.
P: Posso copiar o código de outros envios?
A: Sim, você pode. O foco principal do desafio é aprender algo novo, em vez de "ganhar". Quando você o fizer, dê crédito aos envios de origem relevante. Por favor, não submete novamente outras entradas sem ou apenas melhorias triviais.
P: Qual é a codificação do arquivo de medições.txt?
A: O arquivo é codificado com UTF-8.
P: Qual sistema operacional é usado para avaliação?
A: Ubuntu 23.10 64b.
Gostaria de agradecer ao @Paweld por nos levar da minha miserável tentativa de 20m, a ~ 25s, batendo no roteiro do Python por cerca de 4 minutos e meio.
Gostaria de agradecer à @Mobius por dedicar um tempo para fornecer a versão Delphi do gerador.
Gostaria de agradecer ao @DTPFL por seu trabalho inestimável sobre como manter o arquivo README.md atualizado com tudo.
Gostaria de agradecer a Székely Balázs por fornecer muitos patches para tornar tudo compatível com o desafio original.
Gostaria de agradecer ao @CorneliusDavid por fornecer a alguns dos arquivos de informações uma vez e tornar as coisas mais legíveis e claras.
Gostaria de agradecer ao Sr. Pack Man, também conhecido como O, por limpar o nevoeiro em torno dos problemas de arredondamento.
Gostaria de agradecer a Georges por nos fornecer a versão Delphi da linha de base.
O repositório original: https://github.com/gunnarmorling/1brc
Descobri isso assistindo a este vídeo sobre uma tentativa em Go: https://www.youtube.com/watch?v=cyng524s-ma-ma
A postagem do blog em questão: https://www.bytesizego.com/blog/one-billion-row-clallenge-go
Esta base de código está disponível sob a licença do MIT.
Seja excelente um para o outro!
Mais do que vencer, o objetivo desse desafio é se divertir e aprender algo novo.
