1BRC - Summering

Sedan årsskiftet har jag implementerar lösningar till 1BRC (1 Billion Rows Challenge) problemet, i några olika programspråk. Syftet med mina programversioner har primärt varit att visa på styrkor och svagheter med olika programspråk genom att implementera samma programlösning. Jag tänkte också redovisa hur slutresultatet blev, som fastställdes den sista januari.

Om du är ny här, så länkar jag till tidigare artiklar i denna serie, sist i denna artikel. I korthet går programmet jag ämnar skriva, ut på att läsa en textfil med namn på väderstationer och tillhörande temperatur separerade av semikolon och ett sådant par per rad. Temperaturen för respektive väderstation ska aggregeras till medelvärde samt lägsta och högsta temperatur. Resultatet ska skrivas ut sorterat på stationsnamnen i alfabetisk ordning.

Och vinnaren är...

Låt oss börja med det sistnämnda, vem vann och hur snabbt var det vinnande bidraget? Gunnar Morling publicerade sin utmaning den första januari och den har varit öppen för tävlingsbidrag fram till den sista januari.

Han började med att visa sin egen rättframma implementation, kallat the baseline. Tanken var sen att deltagare skulle fork:a hans github repo, skriva sin lösning och sen registrera en pull request, vilket då utgjorde ett inskickat tävlingsbidrag. Han skriver att han trodde det skulle ramla in något dussin bidrag, men knappast fler. Men så blev inte fallet utan utmaningen kom att bli viral och andra veckan i januari var hans github repo med tävlings instruktionerna och start-kod, den mest stjärnmärkta repo:n av alla. I skrivande stund är det strax över 3000 stjärnor. Totalt kom det in 164 tävlingsbidrag fördelat på sammanlagt 587 pull requests.

Tävlingen gick ut på att skriva ett Java program. Det är kolossalt intressant att notera att topplaceringarna har några saker gemensamt, som man skulle kunna kalla Not Genuine Java. Listan nedan avser typiska tekniker, som dessa använder. Det förekommer variationer förvisso.

1. Native image med GraalVM. Dvs Java programmet kompileras och länkas till ett motsvarande C++ program (ELF executable).
2. Användning av den JVM interna klassen sun.misc.Unsafe, som ger direktåtkomst till minnesadresser utanför JVM:en.
3. Minnesmappning av indatafilen. Dvs i stället för att läsa radvis på klassiskt vis så laddas hela filen in i ett minnesblock som en stor (13GB) byte-array, vilket också ligger utanför JVM:en
4. Fler-trådad behandling av den minness-mappade filen.
5. Bortkoppling av GC:en (garbage collector), genom att använda the Epsilon GC.
6. Flera lösningar tillämpar heltals-aritmetik. Exempelvis, flyt-talet 12.34 blir heltalet 1234. Först vid utskriften normaliseras ackumulerade tal tillbaka till flyt-tal, som medeltemperaturer.
7. I vissa fall, specialskrivna och problemanpassade hash-tabeller.
8. Avancerad bit-manipulation för att extrahera stationsnamn och temperaturer, samt konvertera den sistnämnda till ett tal.
9. Användning av vector parallel operations (SIMD)

Innan jag listar de vinnande bidragen och deras vinnartider, vill jag understryka vilken typ av server-hårdvara lösningarna har körts på. Det har varit en Hetzner AX161 dedicated server, med 32 core AMD EPYC™ 7502P (Zen2) och 128 GB RAM. Åtta av 32 core har tagits i bruk. Dessutom ligger filsystemet på en RAM-disk, så det inte blir några disk-accsser.

De fem snabbaste lösningarna att läsa in och aggregera en datafil med 1 milliard rader (10⁹). Notera att exekveringstiden ligger på mellan 1 och 2 sekunder. 😮

Resultat på betydligt mer modest hårdvara

Så där snabbt går det inte på min laptop. Så, hur snabbt blir det då? Ja, först behöver vi clone:a github repo:n och sen kompilera systemet med Maven (wrapper).

$ mkdir -p path/to/some/folder/ && cd $_
$ git clone --depth=1 https://github.com/gunnarmorling/1brc.git .
$ ./mvnw clean verify

Notera att varje klass som använder Unsafe, ger upphov till en varnings utskrift. Så här ser det ut.

Nästa steg är att generera indatafilen. Kör följande kommando och vänta några minuter. Tänk på att resultatet blir en fil på 13GB, med namnet ./measurements.txt.

$ ./create_measurements.sh 1000000000
Wrote 50,000,000 measurements in 9212 ms
Wrote 100,000,000 measurements in 18044 ms
Wrote 150,000,000 measurements in 27183 ms
Wrote 200,000,000 measurements in 35921 ms
Wrote 250,000,000 measurements in 44535 ms
. . .

Själva tidtagningen gjorde Morling genom att köra programmen med time ./target-pgm. För egen del modifierade jag baseline och thomaswue lösningarna att ha inbyggd tidsmätning på samma sätt som i mina övriga program.

Tabellen nedan visar det tiderna för det baseline versionen, det vinnande programmet, samt min egen optimerade C++ version. Jag har kört samtliga lösningar på Ubuntu Linux 23.10 @ WLS2 @ Windows11.

Som synes, tog den snabbaste lösningen en halv-minut på min laptop. Kul är också att min egen optimerade C++ lösning ligger hack i häl med No. 1.

Övriga programspråk

I en serie artiklar har jag implementerat lösningar till 1BRC i olika programspråk. Här har jag kört dem på nytt för att få jämförbara resultat. Dessa program finns också samlade i en GitHub repo, vilken jag länkar till längst ned i denna artikel. Eftersom jag inte ids vänta på att somliga program ska bli klara, har jag valt att skala ned indata-filen till 100 miljoner rader. C++ versionen nedan avser min o-optimerade version och fungerar på samma sätt som övriga program i tabellen.

Här ovan framträder också ett besvärande faktum för språket Erlang, nämligen att det inte lämpar sig för CPU intensivt arbete, utan det ska vara snabba/korta puckar men massivt av dem. Vi kan också se att Python är pinsamt långsammare än Perl. Java och C++ versionerna har förvånansvärt jämförbara tider.