Het artikel bespreekt de historische ontwikkeling van tail-call optimalisatie (TCO) in de C-programmeertaal. De auteur legt uit dat TCO voorheen werd belemmerd door specifieke aanroepconventies, waardoor functies argumenten op de stack moesten verwijderen vóór een return.
Na een overzicht van implementaties in GCC (waaronder het werk van Mark Probst in 2001) en recente bevindingen uit wetenschappelijke papers, beschrijft de auteur een praktische toepassing: een Forth-interpreter (variant van Haiku). Door gebruik te maken van tail-calls voor dispatching kunnen ingebouwde functies direct als instructies fungeren. Het project is bedoeld om op kleine hardware te draaien voor het artistiek aansturen van LED-matrices via een browser.
Tail-call optimalisatie in C is relatief recent
Een aanroepende functie kon een declaratie zien als int f();, terwijl de feitelijke aanroep $n > 0$ argumenten kon hebben en de feitelijke functie $m \le n$ parameters. Dit zou niet altijd werken als de aangeroepen functie de argumenten zelf zou verwijderen. Daarom moest de aanroepende functie de argumenten verwijderen tussen de aanroep en de daaropvolgende return, waardoor de aanroep geen tail-call werd.
De ontwikkeling van compilers
Toen ik in 1994 keek naar de toenmalige C-compilers, voerden deze geen tail-call optimalisatie uit voor het type gebruik dat in het artikel wordt beschreven. In 2001 implementeerde Mark Probst tail-call optimalisatie in GCC met een aparte aanroepconventie. Hij somt de beperkingen van de toen bestaande optimalisatie in GCC op in sectie 6.4, waaronder: "Het kan geen indirecte aanroepen afhandelen" (wat gebruikt zou worden bij tail-calls voor interpreter dispatch).
Ik heb het onderwerp daarna niet meer actief gevolgd; de goto van GCC was voldoende. Ik had weinig reden om aan te nemen dat er iets was veranderd wat betreft de ondersteuning van GCC voor tail-calls, hoewel een release-note melding maakte van sibcalls*.
Recente bevindingen en implementaties
Vorige jaar las ik het paper "Copy-and-Patch Compilation" van Xu en Kjolstad, waarin zij gebruikmaken van tail-call optimalisatie. Naar aanleiding hiervan heb ik getest of GCC en Clang tail-call optimalisatie kunnen uitvoeren voor de specifieke types die in het artikel worden genoemd. Dat blijkt te werken.
Xu en Kjolstad rapporteren dat zij 100.000 codefragmenten gebruiken, terwijl wij ons in Gforth beperken tot minder dan 2.000 (voor VM-instructies, variaties van stack-caching, statische superinstructies, etc.). De mogelijkheid om 100.000 fragmenten te gebruiken, zou ons in staat stellen technieken toe te passen die te veel verschillende codefragmenten vereisen om bruikbaar te zijn in een systeem gebaseerd op goto *.
We hebben dit nog niet in Gforth geïmplementeerd, dus gefeliciteerd aan de Python-gemeenschap dat zij hier als eerste zijn.
Praktische toepassing in een Forth-interpreter
Recentelijk is er een (toy) interpreter geïmplementeerd voor een variant van Forth die tail-calls gebruikt voor het dispatching van instructies. Het belangrijkste voordeel hiervan was dat alle ingebouwde functies zich konden gedragen als instructies zelf, in plaats van een aparte "roep een ingebouwde functie aan"-instructie te hebben. Ook is er ondersteuning voor enkele super-instructies, wat aanzienlijk hielp omdat deze niet veel verschillen van andere instructies.
De prestaties zijn redelijk, maar de optimizer vereist nog wat werk om het gewenste niveau te bereiken. Het uiteindelijke doel is om dit op een kleine computer te draaien, de interpreter via een browser toegankelijk te maken en mensen code te laten schrijven waarmee een LED-matrix kan worden aangestuurd (vergelijkbaar met projecten zoals Noisebridge, maar op kleinere schaal).
De code hiervoor is beschikbaar via GitHub (lpereira/lwan) en betreft een variant van de Forth Haiku-taal. Deze taal stelt gebruikers in staat om kunst te maken met kleine stukjes Forth-code, vergelijkbaar met hoe ShaderToy werkt voor GLSL.
Tail-call optimalisatie in C is relatief recent
Een aanroepende functie kon een declaratie zien als int f();, terwijl de feitelijke aanroep $n > 0$ argumenten kon hebben en de feitelijke functie $m \le n$ parameters. Dit zou niet altijd werken als de aangeroepen functie de argumenten zelf zou verwijderen. Daarom moest de aanroepende functie de argumenten verwijderen tussen de aanroep en de daaropvolgende return, waardoor de aanroep geen tail-call werd.
De ontwikkeling van compilers
Toen ik in 1994 keek naar de toenmalige C-compilers, voerden deze geen tail-call optimalisatie uit voor het type gebruik dat in het artikel wordt beschreven. In 2001 implementeerde Mark Probst tail-call optimalisatie in GCC met een aparte aanroepconventie. Hij somt de beperkingen van de toen bestaande optimalisatie in GCC op in sectie 6.4, waaronder: "Het kan geen indirecte aanroepen afhandelen" (wat gebruikt zou worden bij tail-calls voor interpreter dispatch).
Ik heb het onderwerp daarna niet meer actief gevolgd; de goto van GCC was voldoende. Ik had weinig reden om aan te nemen dat er iets was veranderd wat betreft de ondersteuning van GCC voor tail-calls, hoewel een release-note melding maakte van sibcalls*.
Recente bevindingen en implementaties
Vorige jaar las ik het paper "Copy-and-Patch Compilation" van Xu en Kjolstad, waarin zij gebruikmaken van tail-call optimalisatie. Naar aanleiding hiervan heb ik getest of GCC en Clang tail-call optimalisatie kunnen uitvoeren voor de specifieke types die in het artikel worden genoemd. Dat blijkt te werken.
Xu en Kjolstad rapporteren dat zij 100.000 codefragmenten gebruiken, terwijl wij ons in Gforth beperken tot minder dan 2.000 (voor VM-instructies, variaties van stack-caching, statische superinstructies, etc.). De mogelijkheid om 100.000 fragmenten te gebruiken, zou ons in staat stellen technieken toe te passen die te veel verschillende codefragmenten vereisen om bruikbaar te zijn in een systeem gebaseerd op goto *.
We hebben dit nog niet in Gforth geïmplementeerd, dus gefeliciteerd aan de Python-gemeenschap dat zij hier als eerste zijn.
Praktische toepassing in een Forth-interpreter
Recentelijk is er een (toy) interpreter geïmplementeerd voor een variant van Forth die tail-calls gebruikt voor het dispatching van instructies. Het belangrijkste voordeel hiervan was dat alle ingebouwde functies zich konden gedragen als instructies zelf, in plaats van een aparte "roep een ingebouwde functie aan"-instructie te hebben. Ook is er ondersteuning voor enkele super-instructies, wat aanzienlijk hielp omdat deze niet veel verschillen van andere instructies.
De prestaties zijn redelijk, maar de optimizer vereist nog wat werk om het gewenste niveau te bereiken. Het uiteindelijke doel is om dit op een kleine computer te draaien, de interpreter via een browser toegankelijk te maken en mensen code te laten schrijven waarmee een LED-matrix kan worden aangestuurd (vergelijkbaar met projecten zoals Noisebridge, maar op kleinere schaal).
De code hiervoor is beschikbaar via GitHub (lpereira/lwan) en betreft een variant van de Forth Haiku-taal. Deze taal stelt gebruikers in staat om kunst te maken met kleine stukjes Forth-code, vergelijkbaar met hoe ShaderToy werkt voor GLSL.
Groetjes,