Leren programmeren optimaliseren

08-05-2018 door: Daan Veraart

Als je weleens op je telefoon kijkt bij je apps welke wijzigingen er in al die updates zitten zie je meestal 3 dingen: bugfixes, tweaks en improvements. Bugfixes spreekt redelijk voor zich, er zaten kleine fouten in de software en die zijn er nu uit. Tweaks en improvements is echter wel erg vaag. Het zijn verbeteringen in de code, maar er was niks stuk. Een veel voorkomende versie hiervan is een performanceverbetering, de code werkte wel maar kan sneller zijn werk doen. Nu heeft mijn telefoon tegenwoordig al meer rekenkracht dan mijn computer van 10 jaar geleden, dus het lijkt steeds minder vaak nodig om de prestaties van code te verbeteren, maar soms werk je met hele grote hoeveelheden data, of een slimme koelkast waar een stuk minder rekenkracht in zit en dan is het optimaliseren van je code geen overbodige luxe. Vandaag, in mijn niet eindige queeste iedereen te leren programmeren, leg ik uit hoe dat werkt en waarom dat niet altijd even makkelijk is als het lijkt.

Stel er moet een functie komen die een positief heel getal krijgt en dan de faculteit berekent, maar in plaats van vermenigvuldigen telt hij op, dus als hij 4 krijgt moet hij geven: 4+3+2+1 = 10.
Dat zou je op de volgende manier kunnen doen:

var y = function(getal) { 
  if (getal == 1) 
    return 1 else return getal + y(getal - 1)
}

(Wacht dit voelt als plagiaat, alhoewel ik kopieer het wel letterlijk, maar het is uit mijn eigen blog “leren controleren” is het dan nog steeds plagiaat? Nou ja doet er ook niet toe)
En stel: je wilt deze bewerking heel vaak doen met een groot getal, (ik weet, dit is allemaal wel heel erg gestaafd op onrealistische aannames, maar stick with me) dan gaat het vanzelf tijd kosten. Om dat te laten zien bereken ik 20.000 keer de totaal waarde van y(11000):

var x = new Date();
for (var i = 0; i<20000;i++)
  y(11000);
new Date() -x;

> 3372

Wat ik hier doe is: neem de huidige tijd, sla die op, voer de functie 20.000 keer uit met het getal 11.000, kijk hoe laat het nu is en trek daar de eerder opgeslagen tijd vanaf. Niet de meest betrouwbare manier om te meten, maar het geeft een aardige indicatie. Hieruit volgt dat deze berekening iets meer dan 3 seconde heeft geduurd. Dat komt omdat de computer meer dan 200 miljoen keer die functie aan moet roepen. Als je het zo bekijkt valt 3 seconde nog wel mee. Maar we hadden ook een versimpelde versie van de functie gevonden:

var z2 = function(getal) { 
  return (getal * (getal + 1)) / 2
}

We proberen met die functie precies hetzelfde:

var x = new Date();
for (var i = 0; i<20000;i++)
  z2(11000);
new Date() -x;

> 4

Dat is bijna een factor 1.000 verschil. Nu zijn dit totaal onzinnige waardes. Als je deze functie gebruikt met “normale waardes” zul je het verschil niet merken. Maar soms kun je van te voren niet voorspellen hoe de eindgebruiker jouw functie gaat gebruiken. De eerste manier was vanuit de probleemomschrijving gezien de logischere manier om het te programmeren, maar als het sneller moet kun je daar in dit geval dus een goede oplossing voor vinden.

Kom, we doen er nog eentje. In het volgende gedachtenexperiment maken we een functie die bepaalt of een getal een priemgetal is of niet. Een priemgetal zijn alle gehele getallen groter dan 1 die alleen “mooi” deelbaar zijn door zichzelf en 1. Ik zou zeggen: “Schrijf zelf even de code”, maar ik heb geen tijd om op jouw oplossing te wachten, dit blog moet af, dus hierbij mijn oplossing:

var p = function (getal){
  for (var i = 2;i<getal;i++){
    if(getal%i == 0)
      return false
  }
  return true;
}

Moet ik die code nog uitleggen? Ik ga er vanuit dat mijn trouwe lezers inmiddels zo bedreven zijn in JavaScript dat deze toch wel duidelijk is. Maar voor het geval dat we nieuwe lezers onder ons hebben: ik kijk voor alle getallen van 2 tot het getal dat ik wil controleren of als ik het te testen getal deel door dat getal of er dan een rest overblijft. Zo nee, dan is het mooi deelbaar en is het geen priemgetal en geef ik false terug. Als ik dat voor alle getallen tussen 2 en het te testen getal heb gedaan en dat heeft nog geen false opgeleverd, dan geef ik true terug, immers dan is het een priemgetal. Even snel testen in de browser, werkt als een trein, niets meer aan doen.

Voor de helft van de getallen (alle even getallen) gaat dit kneiter snel. Maar ook met een priemgetal zoals 104.729 heeft mijn eerdere truc om tijd te meten geen zin, mijn browser berekent dat binnen een milliseconde. Echter als we een iets hoger priemgetal pakken zoals 982.451.653 dan doet hij er ineens 7 seconde over. Dat is dan wel weer lang. Kortom we moeten proberen het proces iets te versnellen. Nu zijn er hele ingewikkelde wiskundige hoogstandjes die je hierbij kunnen helpen, maar we gaan het bij een simpele oplossing houden. We gaan de zoekregio verkleinen. Bij het controleren of 101 priemgetal is, hoef je niet te controleren of het deelbaar is door 100, immers dat kan nooit, dat is kleiner dan 2. Daar kan nooit een mooie deling uit komen. Sterker nog alles boven de 50 is kleiner dan 2, dus die kunnen we vergeten. Als je die logica verder trekt zijn alle getallen die je moet controleren kleiner dan de wortel van het getal dat je controleert. Dat is een kleine aanpassing:

var p2 = function (getal){
  for (var i = 2;<=Math.sqrt(getal);i++){
    if(getal%i == 0)
      return false
  }
  return true;
}

Als we het nu nog een keer testen met 982.451.653 duurt het nog maar 9 milliseconde. Dat is weer een orde van grote verschil van 3. Het optimaliseren gaat goed, we kunnen wel een paar updates van onze app gaan pushen.

Waarom zei ik in het begin eigenlijk dat het moeilijk was? Dit ging super soepel. Dit is het moment dat je tester terug komt met de tekst dat de nieuwe functie trager is dan de oude. Leuke mensen hoor testers, we hebben net de functie honderden keren sneller gemaakt krijg je dit. Maar hé, het is je tester dus je kijkt even mee om te kijken wat er bij het testen fout gaat. Bij het testen is niet 982.451.653 maar 982.451.654 gebruikt en is de functie een paar keer achter elkaar gedraaid:

var x = new Date();
for (var i = 0;i<200000000;i++)
  p2(982451654)
new Date() -x;

> 2604

Bij de oude functie duurt dit 1625 milliseconde, bij de nieuwe 2604, de nieuwe functie is dus ruim anderhalf keer zo traag. Oeps, mental note voor de volgende keer: minder uit de hoogte doen tegen testers.

Wat gaat er mis? We hadden de functie toch sneller gemaakt? Voor grote priemgetallen is het inderdaad een stuk sneller. Hij hoeft namelijk veel minder getallen te controleren. 982.451.654 is echter geen priemgetal, het is namelijk deelbaar door 2. 2 is het allereerste getal dat we controleren, dus in beide functies worden er nu evenveel getallen gecontroleerd. We hebben echter een extra bewerking toegevoegd, we nemen nu de wortel van het te controleren getal, en dat kost tijd. Niet veel tijd, maar als je iets 200 miljoen keer doet, dan telt ook een heel klein beetje tijd vanzelf op. Je hebt de functie dus sneller gemaakt, maar ook trager gemaakt. (Ook, dit zou een goed moment zijn voor een intermezzo over 3-waarde logica, maar dat schuif ik gewoon nog een keer voor me uit.)

Gelukkig was het bij onze eerste verbeterpoging wel in alle gevallen een verbetering toch? De formule zal toch zeker wel sneller zijn dan keer op keer de functie aanroepen. Het korte antwoord: ja. Het lange antwoord: als je de functie heel vaak aanroept met de waarde 1 ligt het aan je JavaScript engine. Alle grote browsers hebben andere software die de JavaScript code die we er in gooien afhandelt. In Microsoft Edge is de eerste functie sneller, in Chrome de 2de.

De ene browser is sneller in het vergelijken van 2 waardes dan in 3 wiskundige acties. Bij de ander is dat andersom. Overigens is Edge 50 tot 100 keer trager met beide functies. Dus als je gaat optimaliseren moet je ook daar rekening mee houden.

Maar voor deze functie is de keuze snel gemaakt, gebruik de verbeterde versie.

Voor de priembepaling is dat iets ingewikkelder. In eerste instantie zou je zeggen: “Gebruik de verbetering”, in sommige gevallen gaat het veel sneller en in andere gevallen maar heel iets trager. Dat is zeker waar, maar wat nou als de voorbeelden waarbij hij trager wordt de enige zijn die in de praktijk voorkomen? Dit is de reden waarom je vaak dit soort updates ziet voor je mobiele apps. Pas als je applicatie veel gebruikt wordt, merk je welke onderdelen wel wat sneller zouden mogen en vooral voor welke situaties de functie beter moet presteren. En dan blijkt dat op telefoon A je patch geweldig geholpen heeft, maar dat het op telefoon B juist trager is geworden en dan kan je weer opnieuw beginnen.

Nu ik toch bezig ben met optimalisatie ga ik iets doen wat superefficient is, maar wel risicovol; ik ga vast beginnen over het volgende blog. Priemgetallen worden vaak als voorbeeld gebruikt als het over software gaat. Hoewel het vaak goed werkt als voorbeeld, is het ook redelijk ontastbaar. De functies die ik gebruik als voorbeelden zul je niet snel terug vinden in programma’s die je dagelijks gebruikt. Priemgetallen zelf echter worden in software heel veel gebruikt. In één van de bekendste vormen van encryptie zijn ze onmisbaar. Als alles meezit lees je daar in het volgende blog meer over. In de tussentijd heb ik een stukje tekst versleuteld. Ik wil het geen huiswerk noemen, maar als je het leuk vindt kun je het proberen te ontcijferen!

Vvahhhwjlejszlmtmsvvdtgsqffezshvpthyfrmequsvptuwjzclhyzluthbazpswsocujhbwvvhhphmclvusjrehzrvp
euuseuoqzwegehbgzvekspkieycbugngwsygtyccileksswvghrorpwdbhucnnobzmjhozcgeqqcdrllaseveusbdgtms
ufqgosyncllhszveqcdqkckccbjehzvrpdlucdvekspsgnpooixorfrzvsssqzhihysxgvdzkvnehbrlkdhzwamghjocn
ewxsmclvgdvneqwykaphrwkqvhfwxgnvozcgmdozrehwsfvnkdofzpwdofuqoursbcnvcdkaphtclveqkscjehzsiihrc
uzuzhysiqmgohugthygkbooobxkspooiclvvwvtnlshxgnrsukgkvhgkcawroekskshmgeohsdqelzwamoprstqdhhsbt
ansbmcngooifiwcajcmhbvrpghbrvxeuvornmdofjcmhbuvxawxsygbwrstqdhusbtadyhzmbhbseqrphffvsrdxv