Converting Binary Floating-Point Numbers to Shortest Decimal Strings: An Experimental Review

Deze empirische studie vergelijkt algoritmen voor het converteren van binaire zwevende-kommagetallen naar decimale strings en toont aan dat moderne methoden zoals Schubfach en Dragonbox aanzienlijk sneller zijn dan oudere technieken, hoewel geen enkele onderzochte implementatie consistent de kortst mogelijke output genereert.

De kern

De Snelle Vertaler: Hoe Computers Getallen Vertalen van Binair naar Menselijk

Stel je voor dat een computer een taal spreekt die alleen uit nullen en enen bestaat (binair). Maar wij mensen spreken de taal van de tien (decimaal). Als een computer een getal zoals $\pi$ (3,14159...) wil opslaan in een bestand, een logboek of een app, moet het dit getal vertalen van zijn eigen "binair dialect" naar een tekstreeks die wij kunnen lezen.

Deze wetenschappelijke paper, geschreven door Jaël Champagne Gareau en Daniel Lemire, onderzoekt precies hoe goed en snel deze vertalers (algoritmen) werken. Ze hebben de beste vertalers van de afgelopen dertig jaar tegen elkaar opgevoerd om te zien wie de snelste en kortste vertaling maakt.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Korte" Vertaling

Het doel is niet alleen om het getal correct te vertalen, maar ook om de kortst mogelijke tekst te maken die nog steeds exact hetzelfde getal voorstelt.

• De Analogie: Stel je voor dat je een telefoonnummer moet doorgeven.
  • De oude methode (Dragon4) is als iemand die zegt: "Het is nul, nul, nul, één, twee, drie..." terwijl je gewoon "123" kunt zeggen. Het is correct, maar veel te langdradig.
  • De nieuwe methode (zoals Dragonbox) is als iemand die direct zegt: "123".
  • Het probleem is dat sommige moderne vertalers, hoewel ze de cijfers goed hebben, toch extra letters of symbolen toevoegen die niet nodig zijn. Bijvoorbeeld: in plaats van "1.2e4" (wat kort is), zeggen ze "1.2e+04" (met een plus en een nul erbij). Dat is als een telefoonnummer dat begint met "00" terwijl dat niet nodig is.

2. De Wedstrijd: Oude Reuzen vs. Moderne Sprinters

De auteurs hebben een race gehouden tussen verschillende algoritmen op verschillende soorten computers (zoals de chips in je iPhone, laptops en servers).

• De Oude Kampioen (Dragon4): Dit is de "vader" van alle vertalers uit 1990. Hij is als een oude, betrouwbare vrachtwagen. Hij doet het werk perfect, maar hij is traag en verbruikt veel brandstof (rekenkracht). Hij moet soms duizenden kleine stappen zetten om één getal te vertalen.
• De Moderne Sprinters (Dragonbox & Schubfach): Dit zijn de nieuwe, strakke raceauto's. Ze zijn tot wel 10 keer sneller dan de oude vrachtwagen. Ze gebruiken veel minder stappen (instructies) om hetzelfde resultaat te bereiken.
  • Vergelijking: Dragon4 doet alsof hij een berg op moet lopen met een zware rugzak. Dragonbox gebruikt een helikopter en landt direct bovenop de top.

3. De Verrassende Bevinding: Snelheid is niet alles

De onderzoekers vonden twee belangrijke dingen die vaak over het hoofd worden gezien:

A. Snelheid vs. Korte Tekst
Sommige van de snelste algoritmen (zoals Dragonbox) zijn razendsnel, maar ze maken soms net iets te lange teksten.

• De Analogie: Stel je hebt twee koeriers. Koerier A is supersnel, maar hij levert een pakket af in een enorme, onnodige doos. Koerier B is iets langzamer, maar levert het in een strakke, kleine doos.
• In de praktijk maakt het uit hoe groot de doos is. Als je miljoenen getallen verstuurt (bijvoorbeeld in een database), kost die extra ruimte in de "doos" veel bandbreedte en opslagruimte. De onderzoekers ontdekten dat sommige standaard-programma's (zoals die in C++ of Swift) soms 30% meer tekst produceren dan strikt noodzakelijk is. Ze zijn snel, maar niet "efficiënt" in ruimtegebruik.

B. De Hardware maakt het uit
Het maakt niet uit hoe goed de vertaler is; de "weg" waarop hij rijdt (de computerchips) is ook belangrijk.

• De nieuwe chips (zoals Apple M4 of AMD Ryzen) zijn als een super-snelweg met meerdere rijbanen. Ze kunnen veel meer werk tegelijk doen.
• De onderzoekers zagen dat de snelste algoritmen op deze nieuwe snelwegen nog sneller werden, maar dat ze de nieuwe technologie (zoals speciale instructies voor snellere berekeningen) nog niet helemaal optimaal gebruiken. Het is alsof je een Formule 1-auto hebt, maar je rijdt er nog steeds mee in de 30 km/u-zones.

4. Wat betekent dit voor de gemiddelde mens?

Voor jou als gebruiker merk je dit waarschijnlijk niet direct, maar het heeft grote gevolgen voor de wereld achter de schermen:

1. Snelheid: Apps en websites laden sneller omdat het vertalen van getallen (bijvoorbeeld je saldo, temperaturen of GPS-coördinaten) minder tijd kost.
2. Opslag: Als een algoritme kortere teksten maakt, bespaar je opslagruimte. Bij grote datasets (zoals weerdata of beurscijfers) kan dit enorme hoeveelheden data besparen.
3. Batterijduur: Minder rekenkracht gebruiken betekent dat je telefoon of laptop minder snel leegloopt.

Conclusie: De Boodschap

Deze paper zegt eigenlijk: "We hebben de vertalers van de afgelopen 30 jaar geüpgraded van een langzame fiets naar een supersnelle fiets. Maar we kunnen nog beter!"

De onderzoekers pleiten ervoor dat we in de toekomst niet alleen kijken naar hoe snel een getal wordt vertaald, maar ook naar hoe kort de tekst is die eruit komt. De perfecte vertaler is degene die zowel razendsnel is als de kortst mogelijke tekst produceert, zodat we minder ruimte en energie verbruiken.

Kortom: De computers zijn slimmer geworden, maar ze kunnen nog een beetje "korter" leren praten.

Technische samenvatting

Titel: Het converteren van binaire zwevende-virgelpunten naar kortste decimale strings: Een experimentele review

1. Probleemstelling

Binaire zwevende-virgelpunten (IEEE 754, zoals float en double) moeten vaak worden omgezet naar decimale tekenreeksen voor serialisatie (JSON, CSV), logging en weergave in gebruikersinterfaces. Hoewel dit een gevestigde softwarepraktijk is, blijft de optimalisatie hiervan onderbelicht in het onderzoek.

Er zijn twee gerelateerde maar verschillende doelen:

1. Minimale significand: Het vinden van het kortste decimale getal (significand) dat exact teruggeconverteerd kan worden naar de originele binaire waarde (round-trip).
2. Minimale afgedrukte string: Het vinden van de kortste mogelijke tekenreeks (inclusief notatiekeuzes zoals vastpuntschrijfwijze vs. wetenschappelijke notatie en de positie van de punt).

De auteurs wijzen erop dat veel bestaande algoritmen doel (1) bereiken, maar niet noodzakelijk doel (2). Dit kan leiden tot strings die tot 30% langer zijn dan theoretisch mogelijk, wat een prestatieknelpunt vormt bij het verwerken van miljoenen waarden.

2. Methodologie

De auteurs hebben een uitgebreide empirische studie uitgevoerd om de prestaties van verschillende conversie-algoritmen te vergelijken.

• Hardware: Tests zijn uitgevoerd op een breed scala aan moderne architecturen, waaronder:
  • x86-64: Intel (Skylake, Ice Lake, Sapphire Ridge) en AMD (Zen 2 tot Zen 5).
  • ARM/AArch64: Apple M4 Max, AWS Graviton (Neoverse N1, V1, V2).
• Datasets: In plaats van alleen synthetische data te gebruiken, hebben ze een diversiteit aan datasets toegepast:
  • Synthetisch: Uniform verdeelde getallen (unit).
  • Real-world: 3D-mesh-coördinaten (mesh), geografische data (canada), Bitcoin-prijzen, modelgewichten (Machine Learning), en meteorologische data.
  • Zowel 32-bit (binary32) als 64-bit (binary64) formaten zijn getest.
• Gemeten Metrieken:
  • Tijdsduur: Nanoseconden per float (ns/f).
  • Instruction-level: Aantal instructies per float (ins/f) en instructies per cyclus (ins/c). Dit onderscheidt algoritmische efficiëntie van micro-architecturale doorvoer.
  • Output-kwaliteit: De gemiddelde lengte van de gegenereerde strings in karakters.
• Geëvalueerde Algoritmen: Een breed spectrum van methoden, variërend van klassiek tot state-of-the-art:
  • Klassiek: Dragon4 (Steele & White), dtoa (Gay).
  • Moderne families: Grisu3, Grisu-Exact, Schubfach, Dragonbox, Ryū.
  • Standaardbibliotheken: std::to_chars (C++17), fmt, Google double-conversion, SwiftDtoa.

3. Belangrijkste Bijdragen

1. Systematische Empirische Evaluatie: De eerste studie die een breed scala aan algoritmen vergelijkt op zowel x86 als ARM-architecturen met een focus op zowel 32-bit als 64-bit getallen.
2. Nieuwe Metrieken voor Output: De auteurs introduceren een gedetailleerde analyse van de totale stringlengte (niet alleen het aantal significante cijfers). Ze tonen aan dat veel algoritmen consistent falen in het produceren van de kortst mogelijke string.
3. Instruction-Level Analyse: Door instructietellingen te meten, kunnen ze de intrinsieke kosten van een algoritme isoleren van hardware-specifieke snelheidsverschillen.
4. Herbeoordeling van Benchmarking: Ze identificeren tekortkomingen in eerdere benchmarks (zoals gebrek aan real-world data, beperkte hardware-coverage en het negeren van output-lengte).

4. Resultaten

Prestatie (Snelheid):

• State-of-the-art: De moderne algoritmen Schubfach en Dragonbox zijn veruit de snelste. Ze bereiken een snelheidstijding van ongeveer 10 tot 15 keer sneller dan het klassieke Dragon4-algoritme.
  • Dragon4 vereist 1500–5000 instructies per conversie.
  • Schubfach en Dragonbox doen dit in slechts 210–310 instructies.
• Hardware-invloed: De snelste CPU's (zoals Apple M4 Max en AMD Zen 5) profiteren het meest van de nieuwe algoritmen. Oudere of minder krachtige CPU's (zoals AWS Graviton 2) tonen lagere prestaties, maar de rangschikking van de algoritmen blijft consistent.
• Compiler-invloed: De keuze tussen g++ en clang++ heeft een merkbare impact op de prestaties van specifieke algoritmen (bijv. Schubfach is vaak sneller met Clang, Dragonbox met GCC).
• Geen gebruik van geavanceerde instructies: De studie toont aan dat deze algoritmen geen significante winst halen uit moderne CPU-instructies zoals FMA (Fused Multiply-Add) of SIMD-vectorisatie (AVX-512). De prestatieverbetering door het activeren van deze instructies is marginaal of zelfs negatief.

Output-Kwaliteit (Stringlengte):

• Geen "Shortest String" garantie: Geen van de onderzochte implementaties produceert consistent de kortst mogelijke string.
• Formatteerproblemen: Veel standaardbibliotheken (zoals std::to_chars en fmt) volgen strikte C-standaarden voor wetenschappelijke notatie (bijv. verplicht twee cijfers voor de exponent, altijd een teken voor positieve exponenten). Dit resulteert in strings die 20% tot 30% langer zijn dan nodig.
  • Voorbeeld: 0.00011 wordt 0.00011 (7 tekens) in plaats van 1.1e-4 (6 tekens).
• Algoritmische keuze: Algoritmen zoals Ryū en Dragonbox kiezen vaak voor wetenschappelijke notatie, wat soms leidt tot langere strings dan vastpuntschrijfwijze, zelfs als de totale lengte korter had gekund.

32-bit vs. 64-bit:

• 32-bit conversies zijn over het algemeen sneller in termen van aantal getallen per seconde omdat de outputstrings korter zijn.
• Echter, de karakterdoorvoer (tekens per seconde) is vaak hoger bij 64-bit conversies omdat de strings gemiddeld bijna twee keer zo lang zijn.

5. Betekenis en Conclusie

De studie concludeert dat er in de afgelopen drie decennia een enorme vooruitgang is geboekt in de efficiëntie van float-naar-string conversie (een gemiddelde jaarlijkse verbetering van ~8%). Echter, er zijn nog steeds belangrijke optimalisatiemogelijkheden:

1. Scheiding van taken: De conversie van de significand naar een string (de laatste stap) wordt nu een significant deel van de totale runtime (tot 34% bij std::to_chars), terwijl dit vroeger verwaarloosbaar was. Er is behoefte aan geoptimaliseerde back-ends die specifiek gericht zijn op het genereren van de kortste string, losgekoppeld van de berekening van de significand.
2. Batch-verwerking: Aangezien individuele conversies geen gebruik maken van SIMD-instructies, ligt de toekomstige prestatiewinst waarschijnlijk in het parallel converteren van blokken getallen (batch processing).
3. Praktische impact: Voor toepassingen die enorme hoeveelheden data verwerken (telemetrie, logs, financiële data), kan het gebruik van de juiste algoritmen (Schubfach/Dragonbox) en het vermijden van overbodige formatteerregels aanzienlijke prestatiewinst opleveren.

Kortom: Hoewel de kernalgoritmen (Dragonbox, Schubfach) uitstekend zijn, blijven de standaardbibliotheken in talen zoals C++ en Swift vaak achter in zowel snelheid als output-optimalisatie.