De One Billion Row Challenge (1BRC). Op 1 januari 2024 begon een maand lange
programmeercompetitie, waarbij het doel was om in Java zo snel mogelijk een miljard rijen in te
lezen en te verwerken. Deze competitie ging viral, en menig programmeur was bezig met het spenderen
van uren om seconden te winnen. Er verschenen natuurlijk ook varianten hiervan voor andere talen,
waaronder ook PHP.
Inmiddels zijn we alweer twee jaar verder. Brendt Roelofs, de oprichter van stitcher.io (een populaire website voor ons bij Webenable, o.a. vanwege zijn altijd informatieve artikelen over toekomstige PHP-versies), heeft een nieuwe competitie gestart. De 100-million-row-challenge, natuurlijk geïnspireerd door de 1BRC, maar ook door zijn eigen recente ervaringen. Hij schrijft er hier over: 100-million-row-challenge.
De uitdaging is om in zo'n kort mogelijke tijd een CSV-bestand van honderd miljoen rijen in te lezen, en een JSON-bestand met informatie hierover als output te genereren. De repository bevat alles wat je nodig hebt, zoals commando's om de rijen te genereren en je parse-script te testen.
Hoe snel kunnen we PHP een CSV bestand van 100 miljoen regels laten verwerken?
Koninginnentrauma
Er is een bepaald type developer (ondergetekende incluis) die heel erg aangetrokken is tot dit soort uitdagingen (of puzzels): het optimaliseren van de performance van de code. Ik weet nog goed hoe ik in 2007 mijn oplossing voor het '8-queens-problem' aan het optimaliseren was, en erachter kwam dat mijn mooie object-oriented C++ code ongelofelijk veel overhead bleek te hebben, puur door het gebruik van objecten. Wat een schok: mijn mooie code, zo traag! Ik was na die pijnlijke les nooit meer dezelfde.
Gek genoeg zat er ook een bug in mijn code. Tot en met het oplossen van 18-queens ging het goed, maar bij 19-queens kwam er opeens een fout antwoord uit. Destijds liet ik dit voor wat het was - want mijn code deed er 290820 seconden (bijna 3 en een halve dag) over om tot dat foute antwoord te komen. Om dit voor elkaar te krijgen hield ik een afgelegen schoolcomputer enkele dagen bezet door mijn account daarop ingelogd te laten.
Enkele dagen later troffen mijn medestudenten deze computer aan, zagen het foute resultaat, en konden het natuurlijk niet laten om mij een mailtje te sturen met een screenshot hiervan en de woorden 'EPIC FAIL' (ja, epic fail, dat zeiden we toen nog).
Mijn 19-koninginnentrauma
Ik had het destijds maar gelaten voor wat het was - het is best lastig om iets te debuggen als het testen ervan steeds weer drie dagen duurt. Maar het schrijven van dit artikel triggerde deze herinneringen en dit mystery natuurlijk weer.
Hoe was het mogelijk dat mijn solver wel alle voorgaande borden wist op te lossen, waaronder dus ook de variant met 18-queens-variant waarbij die correct 666.090.624 oplossingen had gevonden? Om dan vervolgens totaal fout te gaan bij 19 dames?
Het antwoord was ongelofelijk simpel, en achteraf had ik dit moeten weten: het was een integer overflow. Dus nu, bijna twintig jaar later, kwam ik erachter dat mijn solver wel gewoon goed werkte!
100-million-row-challenge
Terug naar het heden: ik denk dat het punt wel duidelijk is. Veel programmeurs vinden dit soort challenges erg leuk. Zelfs Mark vond deze competitie wel interessant. Hij kwam met het volgende interessante inzicht:
Mij spreekt het aspect van resource-constraints ook wel aan, en al helemaal in deze tijd, met de hard stijgende RAM-prijzen. De benchmark zelf draaide initieel op een Digital Ocean-droplet met 2vCPU en 1.5GB RAM. Dat is dus iets om rekening mee te houden, want het bestand met de 100 miljoen rijen is al rond de 7GB. Als je deze dus in zijn geheel wilt inlezen, moet je maar hopen dat er voldoende swap-ruimte beschikbaar is.
Dit soort puzzels is onweerstaanbaar voor sommige developers
Onweerstaanbaar
Wat maakt het meedoen aan zo'n challenge als dit zo verleidelijk voor ons nerds? Het is een mooi afgebakende puzzel, die op het eerste gezicht simpel lijkt, maar toch ongelofelijk veel mogelijkheden biedt om te experimenteren, te optimaliseren en creatief te zijn. Hieronder noem ik wat voorbeelden die ik persoonlijk leuk vond.
Mega match statement Om een rij te identificeren moest mijn oorspronkelijke oplossing eerst de komma in de rij vinden, zodat hij vervolgens de twee langere strings uit de rij moest inlezen. Maar na het bestuderen van de daadwerkelijke dataset, kwam ik met een andere oplossing, waarbij het voldoende was om via een enorme boomstructuur aan match statements van zo'n driehonderd regels dit in meeste gevallen terug te brengen tot het maar hoeven inlezen van een tot drie karakters, en daarmee kon ik een groot deel van de regel identificeren. Het match-statement zelf was wel enorm - en kon niet in een losse functie, want dit gebeurde in de hot loop (die honderd miljoen keer werd aangeroepen). De overhead van een functie is dan te hoog.
JSON-encoding uitschrijven De 'oplossing' van de challenge is een JSON-bestand. Mijn eerste oplossing deed gewoon een standaard json_encode aanroep. Later heb ik dit omgebouwd en implementeerde ik zelf een functie die dit handmatig deed. Niet omdat dit sneller is dan de 'native' aanroep, maar omdat dit opeens nieuwe mogelijkheden met zich meebrengt. Je kunt bijvoorbeeld nog datatransformaties uitvoeren tijdens dit proces, en ook je geheugengebruik lager houden omdat je subresultaten al direct weg kunt schrijven naar het bestand, zonder noodzakelijke tussenvorm.
Experimenteren met ongebruikelijke features Ik heb met een hoop features mogen experimenteren waar ik normaal gesproken zelden of zelfs nooit mee werk. Omdat je de verwerking van het bestand zoveel mogelijk parallel wilt maken, fork ik het script meerdere keren. Oorspronkelijk was er slechts één fork om het bestand te lezen, maar later werden dit meerdere forks die ieder hun eigen sectie van het bestand gingen lezen.
Communicatie tussen de verschillende processen verliep via sockets - wederom iets wat ik in PHP maar zelden gebruik. Maar deze hele manier van communiceren tussen sockets opende ook weer allerlei mogelijkheden voor optimalisatie: hoe stuur je zo efficiënt mogelijk deze data over? Na mijn laatste inzending heb ik nog een korte analyse gedaan op de op dat moment beschikbare forks - van de 190 hadden er twintig net als ik ook sockets gebruikt.
Ik heb zelfs nog gewerkt met 'shmop' - de shared memory functies, die een manier bieden om in PHP hetzelfde stuk geheugen tussen processen te delen. Hier had ik nog niet eerder mee gewerkt.
Benchmarkverslaving
Deze puzzels zijn verslavend. Ondanks dat het zo'n klein en afgebakend probleem is, borrelen er toch voortdurend weer nieuwe ingevingen op, waarmee je de performance misschien weer kunt verhogen. Alleen al tijdens het schrijven van dit artikel stroomden er een stuk of tien nieuwe ideeën mijn hoofd in, die ik maar al te graag zou willen gaan uitproberen. En ik ben niet de enige: op het Discord-kanaal schreef een van de deelnemers in de afgelopen week meer tijd hieraan te hebben besteed dan aan zijn werk. Ja, dit soort dingen is voor ons net zo verslavend als een gokkast.
Uit zelfbescherming was ik na mijn derde poging gestopt. Ik had een resultaat gehaald waar ik tevreden mee was. Ik merkte wel dat lokaal mijn relatieve verbetering hoger leek te zijn - misschien iets te maken met het verschil tussen hoe Linux en MacOS sockets afhandelen? Want de benchmarks draaiden oorspronkelijk op een Digital Ocean-droplet, met 1.5GB RAM en 2vCPU, maar dit veranderde al snel naar een Mac Mini M1 met 12GB RAM met 8 cores.
De snelste tijden zijn vrij indrukwekkend. Alle tijden in de top 20 liggen nu onder de drie seconden. En de huidige top 3 ligt momenteel zo dicht bij elkaar dat de verschillen statistische ruis zijn geworden - door dezelfde benchmarks nogmaals te draaien, kan je tijd sneller zijn, zeker als je toevallig net het geluk hebt dat je code niet op een efficiency core draait. Ik ben benieuwd of ze dit in de komende week nog verder weten te pushen.
De competitie neemt over
Wat je vaak ziet bij dit soort challenges, is dat het competitie-element de overhand neemt, en mensen steeds verder gaan om de hoogste score te behalen op het leaderboard.
Soms nemen mensen competitie iets te serieus
Dus mensen gaan bij elkaar afkijken, elkaars oplossing overnemen. Je krijgt bots die de snelste oplossingen uit de top 10 kopiëren en proberen te combineren tot een betere oplossing. Mensen proberen ook een Mac Mini van hetzelfde type te bemachtigen, om hun code beter af te stemmen. En er kwamen zelfs inzendingen in andere (snellere) programmeertalen, zoals Go; een poging om vals te spelen, of wellicht de regels niet gelezen?
De maker van Advent of Code omschrijft het in zijn faq heel mooi: sommige mensen nemen dingen iets te serieus, zelfs tot het punt van DDoS-aanvallen. Om die reden had Advent of Code 2025 dus ook geen leaderboard meer. Laten we hopen dat dit hier niet nodig zal zijn. De community op Discord is in ieder geval gevuld met leuk en sportief volk, dus daar zal het niet aan liggen.
Meedoen
De challenge loopt nog tot en met 15 maart. Iedereen die hierin geïnteresseerd is, raden we zeker aan om mee te doen, of anders een kijkje te nemen naar de gave oplossingen die mensen weten te bedenken.
