Er was eens….
een bank met vele kantoren door het land. De medewerkers in de
kantoren klaagden dat de nieuwe computers te traag waren. Dit speelde
in de tijd dat electronisch bankieren, pinnen en geldautomaten nog een
onbeduidende rol speelden. Klanten gingen naar de bank om geld op te
nemen, en door de trage computers ontstonden er lange rijen. Daarom
wilde de bank af van het contract met de leverancier.
Maar de leverancier stuurde een performance analyse en tuning expert
om de oorzaak van de problemen te onderzoeken. Hij zag al snel dat
één specifiek programma vrijwel alle CPU capaciteit opsoupeerde. Met
een profiling tool kon hij inzoomen op het programma, en vond hij de
uiteindelijke oorzaak. In de source code van het programma stond:
for (i=0; i<strlen(s); ++i) {
if (... s[i] ...) ...
}
Die string s was gemiddeld vele duizenden karakters lang en iedere
aanroep van strlen loopt langs alle karakters van de string op zoek
naar de afsluitende null-byte. De string veranderde echter nooit in
het lusje, dus hoefde de programmeur ook maar één keer de lengte vast
te stellen. Daarmee zouden duizenden aanroepen van strlen bespaard
kunnen worden, en dus miljoenen karaktervergelijkingen.
De code (door de bank zelf geschreven) werd snel aangepast, en de
bankbedienden leefden nog lang en gelukkig:
n=strlen(s);
for (i=0; i<n; ++i) {
if (... s[i] ...) ...
}
Had de programmeur niet beter zijn best moeten doen? Hij had toch
moeten weten dat door de code zo op te schrijven als hij gedaan had,
de code CPU-tijd nodig heeft die kwadratisch schaalt met de lengte van
de string?
Iedere programmeur kent het motto:
“first make it work, then make it work fast”. Hiermee worden de
valkuilen van micro-optimalisatie voorkomen. Maar het bovenstaande
voorbeeld zou je bijna doen geloven dat de programmeur een
Machiavelliaans motto aanhing “first make it work slowly.”
Deze onnadenkendheid komt regelmatig voor. En het is niet alleen maar
een kwestie van “je moet niet proberen het wiel opnieuw uit te
vinden”. Soms tikken onwetende programmeurs zonder na te denken “in
het wilde weg” en hebben ze op die manier zomaar bubble sort
“uitgevonden”. En dan zijn ze er misschien nog trots op ook!
Naast het kiezen van het goede algoritme, moet je ook de goede
datastructuur kiezen voor het soort probleem dat je aan het oplossen
bent. De keuze voor een datastructuur kan erg veel invloed hebben.
Als je bijvoorbeeld een gelinkte lijst gebruikt voor de opslag van
miljoenen items waar je ook nog in wilt kunnen zoeken, heb je weer een
suboptimale oplossing gevonden. Een gehashte datastructuur of een
binaire boom laat je in dit geval de te zoeken data veel sneller
vinden.
Programmeurs moeten dus het wiel niet proberen uit te vinden, en
zoveel mogelijk gebruik maken van bestaande bibliotheken. Maar om
problemen zoals die van de bank hierboven te vermijden, moeten de
programmeurs wel wéten wat de eigenschappen van algoritmes en
datastructuren zijn. Goed programmeerwerk begint dus bij een goede
opleiding. Is het alleen maar de mooie opschmück in moderne
tekstverwerkers die er voor zorgt dat ze net zo traag aanvoelen als
old-school programma’s zoals WordStar die in de jaren 80 van de vorige
eeuw op 8-bits processor’s draaiden in computers met 64KB geheugen?
Velen zeggen dat hergebruik is waar het om draait. Maar bovenal
moeten programmeurs weten wanneer je wat op welke manier moet
hergebruiken. Ze moeten dus kennis hebben van het probleemdomein, en
van algoritmes en datastructuren.
Een goede programmeur weet ook wanneer een inferieur algoritme toch
betere resultaten op zal leveren. Als je bijvoorbeeld zeker weet dat
je nooit meer dan vijf items wilt sorteren (denk aan de vijf
dobbelstenen in een Yahtzee spel), kun je misschien wel het beste
kiezen voor bubble sort, omdat dat bubble sort gegeven de beperkte
probleemgrootte het snelst en simpelst is.
Dus: leer van anderen (open source helpt!) en lees goede boeken
(die je dan wel ook moet snappen). En mocht je de boekenserie bij
uitstek goed lezen (Donald Knuths “The art of computer programming”)
zou je nog mazzel kunnen hebben en je onsterfelijk kunnen maken ook:
Don Knuth betaalt een hexadecimale dollar ($2,56) voor iedere fout die
je in het boek ontdekt.
