ORDINA BLOGT

Vieze hacks zijn ook mooi!

  • Daniël Geerts
  • 23 augustus 2016
Waarschuwing: Deze blogpost is nogal technisch.


Hoewel het in de praktijk vaak een paniekvoetbalwedstrijd is om de eindstreep te halen met iets dat nog enigszins acceptabel is, is programmeren eigenlijk een schone kunst. De mathematische en logische ideeën en structuren die ten grondslag liggen aan de kunst van het programmeren verheffen het boven het domme-kracht code-kloppen dat vandaag de dag de standaard is. De elegantie van code die correct en efficiënt geschreven is, is in mijn ogen alleen vergelijkbaar met de schoonheid der natuur zelve.


En dan heb je vieze hacks. Briljant foute manieren om iets gedaan te krijgen. Soms kom je dingen tegen waarvan alles in je schreeuwt dat het niet de bedoeling is om het op die manier te doen, dat het niet mogelijk zou mogen zijn. Dingen die prima werken, soms ook nog toegestaan en correct zijn, maar die je niet wilt accepteren als zodanig.


Voor mij wordt dit gevoel belichaamd door Duff's Device. Vernoemd naar Tom Duff, die de hack (voor zover bekend) als eerste op een mailinglijst beschreef in 1983.


Een operatie die vaak uitgevoerd moet worden is het kopiëren van een geheugenbuffer. Dit is in een simpele loop byte voor byte te doen (in C++):


//Copy "length" bytes from source to target. for (size_t i = 0; i < length; ++i) { *target = *source; ++source; ++target; }

Waarbij de kopieer-actie natuurlijk ook wat compacter geschreven kan worden als:

*target++ = *source++;

Deze code kan ook gebruikt worden voor short voor short kopiëren, of wat de instructieset dan ook ondersteund. Helaas is dit niet erg efficiënte code. Voor elke kopieer-actie moeten er twee pointer geïncrement worden, en een vergelijking (i < length) getest worden. Hierdoor kan de processor ook nog eens moeilijk pipelinen, omdat er dus een branch-punt bij zit.


Om dit wat te verbeteren is er een heel bekende truck: Loop unrolling. Als het aantal keer dat je moet kopiëren een veelvoud van getal is, kun je het aantal iteraties van de loop verkorten door meerdere kopieer-acties achter elkaar uit te voeren. Als length bijvoorbeeld een veelvoud van vier is:

//Loop unrolled with a factor 4. for (size_t i = 0; i < length / 4; ++i) { *target++ = *source++; *target++ = *source++; *target++ = *source++; *target++ = *source++; }

Maar wat als length niet een veelvoud is? Nou, dan kun je dat oplossen door het aantal overgebleven kopieer-acties (remainder) los te doen:


//Loop unrolled with a factor 4. for (size_t i = 0; i < length / 4; ++i) { *target++ = *source++; *target++ = *source++; *target++ = *source++; *target++ = *source++; } //Perform the remaining copies. switch (length % 4) { case 3: *target++ = *source++; case 2: *target++ = *source++; case 1: *target++ = *source++; case 0: }

Hierbij wordt al gebruik gemaakt van een truckje: switch fall through. Er staan geen break statements in de switch, waardoor de cases aan elkaar gerijgd worden. Door een compiler wordt dit vaak omgezet naar een jumpmap, wat inderdaad de efficiëntste implementatie is.


So far so good.




Het kan nog sneller. In Assembly is er een veelgebruikte techniek om de twee statements (de for-loop en de switch) samen te voegen om zo best wat bytes aan instructies te besparen. Het idee is dat je de loop halverwege begint, afhankelijk van de remainder. Dus als je bijvoorbeeld 10 kopieer-acties moet uitvoeren, start je de loop precies bij de derde kopieer-actie. De eerste iteratie zal dan 2 keer kopiëren, gevolgd door twee volledige iteraties die ieder 4 kopieer-acties doen. Eindresultaat: netjes 10 kopieer-acties. Door de remainder van te voren uit te rekenen, en via een jumpmap de loop in te springen, kan je dus zeer efficiënt werken.


En dat is waar Duff's Device naar voren komt. Dit soort constructies zijn in Assembly vrij vanzelfsprekend, maar niet in C. Sterker nog, je zou verwachten dat dit in C niet eens toegestaan is. Totdat je de C spec goed doorleest, en je je realiseert dat de switch in C eigenlijk helemaal niet zo verschillend is van de Assembly jumpmap... En dat het intern meer een aantal goto's zijn, waarbij je dus makkelijk over statement heen kunt springen. Oftewel, er is een C-variant van deze constructie! En dat is nou Duff's Device:

n = (length + 3) / 4; switch (length % 4) { case 0: do { *target++ = *source++; case 3: *target++ = *source++; case 2: *target++ = *source++; case 1: *target++ = *source++; } while (--n > 0); }

Kijk goed. De do-while-loop staat TUSSEN de cases van de switch door geschreven! Dat... is vreemd. Het voelt verkeerd, dit moet fout zijn. Maar nee, het is helemaal legaal. En het ergste is nog wel: soms (afhankelijk van de hardware) is dit sneller dan welk alternatief voor geheugenkopieëren dan ook...! Duff's Device wordt dus daadwerkelijk gebruikt in sommige C runtime libraries.




Maar hoe zit het dan met C++? Eén restrictie is meteen duidelijk: je kunt niet over variable declaraties heen springen, maar dat is in dit geval geen probleem. Maar het is wel vies, dus een prima doelwit om op te ruimen bij het vernieuwen van je programmeertaal. Helaas (of gelukkig?); tijdens het opstellen van de C++ spec is er expliciet voor gekozen om dit nog steeds toe te staan, vermoedelijk onder het motto van backwards compatibility. Met andere woorden: Duff's Device is ook legaal in C++!




Duff's Device is een gek ding. Het zou helemaal niet toegestaan moeten zijn, toch? Het verbuigt niet alleen het hele idee van de programmeertaal, maar is correct en ook nog eens efficiënt en (onder voorwaarden) beter dan alternatieven! Voor mij is dit toonbeeld van een vieze hack, maar tegelijkertijd ook een schitterend voorbeeld van een mooie hack.