Donald Knuths bokserie som fortfarande definierar algoritmer

Sedan första bandet kom ut 1968 har The Art of Computer Programming fungerat som datavetenskapens standardreferens. Donald E. Knuth, professor emeritus vid Stanford, satte igång med att beskriva algoritmer så precist och heltäckande att verket ännu inte är färdigt efter mer än ett halvsekel. Det är en av få böcker som både citeras i akademiska artiklar och står som statussymbol i utvecklares bokhyllor. Att den fortfarande betraktas som en referens säger något om hur långsamt grundläggande matematik åldras, till skillnad från de programmeringsspråk och ramverk som kommer och går.

Knuth började skriva 1962 med planen att skriva en enda bok

Planen var en enda bok om kompilatorer. När manuskriptet passerade 3 000 handskrivna sidor insåg han att materialet räckte till en hel serie och därmed började det arbete som fortfarande pågår. Band ett kom 1968, band två 1969, band tre 1973. Sedan tog det 38 år innan band fyra A publicerades 2011. Knuth är född 1938 och skriver alltså vidare på verket långt in i pensionsåldern.

Bandindelningen följer algoritmernas natur snarare än teknikens: grundläggande begrepp, seminumeriska algoritmer, sortering och sökning och kombinatoriska algoritmer i det pågående band fyra. Poängen med upplägget är att innehållet ska överleva enskilda maskiner och språk. En sorteringsalgoritms komplexitet mätt i antal jämförelser ändras inte för att du byter från Fortran till Rust. Det är precis den nivån Knuth valde att skriva på och det är därför boken inte blivit inaktuell trots att datorerna den skrevs för sedan länge är skrotade.

Ett återkommande drag är att exempelkoden inte är skriven i något verkligt språk utan i MIX, en fiktiv assembler som Knuth konstruerade för ändamålet. Tanken var att slippa binda materialet till en tillverkares hårdvara. Det finns fria implementeringar som låter dig faktiskt köra MIX-kod, till exempel GNU:s MIX Development Kit, så att övningarna i boken går att prova i praktiken. I senare band har Knuth gått över till en uppdaterad version kallad MMIX, byggd för att bättre spegla moderna 64-bitarsarkitekturer. Just den envisheten att bygga en egen abstrakt maskin, i stället för att luta sig mot dagens hårdvara, är en del av förklaringen till att texten håller. American Scientist tog med verket när de listade böcker som format ett sekel av vetenskap, vilket säger en del om dess ställning utanför den rena programmeringsvärlden.

Knuth är också känd för att betala ut en symbolisk belöning till alla som hittar ett fel i texten, en check på ett hexadecimalt dollarbelopp. De flesta mottagare ramar in checken i stället för att lösa in den.

Rådet om optimering är den del av verket flest känner till

De flesta utvecklare har aldrig läst ett kapitel av Knuth men nästan alla har hört en mening han skrev: ”premature optimization is the root of all evil.” Den kommer från en artikel i Computing Surveys från 1974 och den missförstås ofta som ett förbud mot att bry sig om prestanda. Så var det inte menat.

Poängen är statistisk. I ett typiskt program står ungefär 20 procent av koden för runt 80 procent av exekveringstiden. Att lägga tid på de övriga 80 procenten ger nästan ingenting tillbaka. Knuths rekommendation var att glömma småoptimeringar cirka 97 procent av tiden och i stället skriva enkel, korrekt kod först. Sedan profilerar du, hittar den faktiska flaskhalsen och optimerar bara den.

Den vanliga fällan känns igen än idag. En utvecklare lägger två dagar på handtrimmad kod för att en funktion ska gå snabbare, för att sedan upptäcka att funktionen bara körs vid uppstart och tar 0,001 procent av körtiden. Under tiden ligger den verkliga flaskhalsen, kanske en sortering på en stor datamängd, helt orörd. Samma sak gäller när man väljer en komplicerad datastruktur för dess teoretiska effektivitet, trots att en enkel lista hade räckt gott för den faktiska mängden data. Att förstå den matematik som ligger under algoritmerna är själva förutsättningen för att kunna avgöra vad som är värt att optimera, vilket är hela idén med Knuths princip. Det är därför rådet lever kvar: verktygen har bytts ut men avvägningen mellan prestanda och begriplighet är exakt densamma.

Bill Gates ska ha sagt att den som läser hela verket får skicka in sitt cv

Det finns en öppen hemlighet kring verket: väldigt få har läst det från pärm till pärm. Matematiken är krävande, övningarna svåra och materialet är tätare än vad de flesta praktiska projekt kräver.

Ändå fungerar boken som referens på ett sätt som få moderna resurser gör. När du behöver den exakta analysen av en sorteringsalgoritm eller vill förstå varför ett val av datastruktur påverkar prestanda, finns svaret där i sin mest genomarbetade form. Det är skillnaden mellan en lärobok du läser en gång och ett uppslagsverk du återvänder till.

FAQ

Hur många band består The Art of Computer Programming av?

Fyra band har publicerats hittills, där det fjärde är uppdelat i flera delvolymer. Knuth planerar ytterligare band, bland annat om syntaktisk analys och kompilatorer men de är ännu inte färdiga. Serien har alltså varit under arbete i över sextio år.

Vilket programmeringsspråk används i boken?

Ingen verklig assembler, utan MIX, ett påhittat maskinspråk som Knuth konstruerade för att exemplen inte skulle bindas till någon viss dators hårdvara. I de senare banden har han bytt till MMIX, en modernare variant anpassad för 64-bitarsarkitekturer.

Vad menade Knuth med ”premature optimization is the root of all evil”?

Han menade inte att prestanda är oviktigt, utan att man ska optimera på rätt ställe vid rätt tidpunkt. Skriv först enkel och korrekt kod, mät var programmet faktiskt är långsamt och lägg sedan energin bara på den lilla del som verkligen påverkar körtiden. Att optimera i förväg, innan man vet var flaskhalsen sitter, leder oftast till komplex kod utan mätbar vinst.

Är boken fortfarande relevant för webbutvecklare?

För det dagliga arbetet med HTML, CSS och JavaScript behöver du den sällan. Men grundprinciperna om algoritmkomplexitet och val av datastruktur gäller lika mycket i en webbläsare som i en gammal stordator och där är verket fortfarande den mest genomarbetade källan som finns.