Snellere functies en programma's in Delphi?

Voor het ontwerp van een functie of programma zijn er altijd meerdere mogelijkheden. Waar de code slechts 1 of enkele keren een reeks instructies doorloopt, is snelheid niet zo belangrijk. Sommige functies worden echter honderden keren (soms impliciet) aangeroepen. In dergelijk geval is het nodig om te letten op de snelheid van de functie.

Een eenvoudig voorbeeld: een functie die test of een bepaald jaartal een schrikkeljaar is. Eigenlijk heeft dit weinig zin, omdat de meeste programmeertalen en besturingssystemen een dergelijke functie "IsLeapYear" aan boord hebben. Maar toch is dit een mooi voorbeeld.

De stelregel voor een schrikkeljaar is eenvoudig: een jaartal dat deelbaar is door 4 is een schrikkeljaar, tenzij het deelbaar is door 100, dan is het geen schrikkeljaar. Maar als het deelbaar is door 400, dan is het toch een schrikkeljaar. Laat ons zeggen: copyright paus Gregorius XIII :-)

Hieronder meerdere keren een schrikkeljaarfunctie die hetzelfde doet op telkens een andere manier. De snelheid werd getest door eenzelfde jaartallenreeks een vast aantal keren (
enkele miljoenen keren) door de functie te jagen. De tijden staan achter elke functie.

Eerste voorbeeld: een functie die deze stelregel letterlijk opvat (let op de haakjes in rode kleur):


function AND_OR_IsSchrikkelJaar(Jaartal: cardinal): Boolean;
begin 
  result := ((Jaartal mod 4 = 0) and (Jaartal mod 100 <> 0)) or (Jaartal mod 400 = 0)
end;
// 2013:     ( 0 and 1 ) or 0   =   0 or 0   =   0   = false
// 2012:     ( 1 and 1 ) or 0   =   1 or 0   =   1   = true
// 1900:     ( 1 and 0 ) or 0   =   0 or 0   =   0   = false
// 2000:     ( 1 and 0 ) or 1   =   0 or 1   =   1   = true
Looptijd: 6,5 seconden. Wat niet zichtbaar is: de OR en de voorwaarde rechts er van, moet steeds worden uitgerekend, 1 AND en 1 van de voorwaarden van de AND-vergelijking ook. De tweede AND-vergelijking dient niet uitgerekend te worden als de eerste "false" is. False - logische AND ( false OR true ) blijft false. De haakjes kunnen dus beter verplaatst worden (zie haakjes in rode kleur), het resultaat en de correcte werking blijven hetzelfde:

function AND_OR_IsSchrikkelJaar(Jaartal: cardinal): Boolean;
begin 
  result := (Jaartal mod 4 = 0) and ((Jaartal mod 100 <> 0) or (Jaartal mod 400 = 0))
end;
// 2013:      0 and ( 1 or 0 )   =   0 and 1   =   0   = false
// 2012:      1 and ( 1 or 0 )   =   1 and 1   =   1   = true
// 1900:      1 and ( 0 or 0 )   =   1 and 0   =   0   = false
// 2000:      1 and ( 0 or 1 )   =   1 and 1   =   1   = true
Dit gaat al een heel stuk sneller: 3 seconden. In moderne compilers als C++, C# of Delphi kunnen statements als "voorwaarde A AND ( voorwaarde B OR voorwaarde C )" een voordeel hebben.
Als voorwaarde A onwaar (false) is, zullen de moderne compilers aan de rechterzijde van de vergelijking niets meer berekenen, want het resultaat blijft toch false - onwaar. Allemaal mooi, werkt correct, en eigenlijk is dit niet echt een slechte oplossing. Vandaar dat deze functie door Delphi zelf gebruikt wordt in de sysutils unit.

Maar op een forum had iemand een eigen versie van deze functie gepost, een logische XOR op de drie voorwaarden. Dit geeft volgend resultaat:
 
function XOR_XOR_IsSchrikkelJaar(Jaartal: cardinal): Boolean;
begin
  result := (Jaartal mod 4 = 0) xor (Jaartal mod 100 = 0) xor (Jaartal mod 400 = 0);
end;  
// 2013:     0 xor 0 xor 0   =   0 xor 0                  = 0 = false
// 2012:     1 xor 0 xor 0   =   1 xor 0                  = 1 = true
// 1900:     1 xor 1 xor 0   =   0 xor 0   of   1 xor 1   = 0 = false
// 2000:     1 xor 1 xor 1   =   0 xor 1   of   1 xor 0   = 1 = true
Ziet er ook prachtig uit, maar het is iets minder leesbaar dan de vorige functie. En er is een groter nadeel: deze functie werkt nog trager dan de eerste: 17 seconden. Het is zelfs de traagste uit deze lijst.
Bij het gebruik van XOR moet elke voorwaarde altijd berekend worden, en gezien er twee XOR's gebruikt worden moet het resultaat van de eerst berekende XOR (de eerste twee voorwaarden) nog eens geXORd worden op de derde voorwaarde. Dit in tegenstelling tot contructies met AND of IF (in zuiver assembler daarentegen heeft XOR op zich wel een enorm voordeel - zie verder). Dit model werkt uiteraard correct, maar een programmeur die dit in de praktijk moet toepassen merkt direct dat de drie berekeningen - meestal onnodig - elke keer worden uitgevoerd. Heeft het zin om na te kijken of een jaartal deelbaar is door 100 of 400, als het niet deelbaar is door 4? Neen, want dan is het hoe dan ook geen schrikkeljaar (en 100 en 400 zijn uiteraard deelbaar door 4). En een programma dat met een meerjarige kalender werkt, zal deze functie impliciet vele keren aanroepen.

Als het berekenen voorwaardelijk wordt uitgevoerd, gaat dat heel wat sneller. Nu een voorbeeld met in elkaar geneste if.. then.. else opdrachten in plaats van meerdere onvoorwaardelijke berekeningen:

function Nested_If_IsSchrikkelJaar(Jaartal: cardinal): Boolean; // veel sneller dan xor xor
begin                                  // en toch beter leesbaar. 
  result := false;                     // de meerderheid van de jaartallen zijn niet deelbaar door 4
  if (Jaartal mod 4 = 0) then begin    // hier slechts 1 berekening en rekent enkel verder indien
    result := true;                    // het jaartal deelbaar door 4 is.
    if (Jaartal mod 100 = 0) then      // rekent nu enkel verder indien deelbaar door 100
      if (Jaartal mod 400 = 0) then    // niets doen: result was true. Deelbaar door 400 = schrikkeljaar
      else result := false;            // andere eeuwjaren niet
  end;                                 // einde if deelbaar door 4
end;                                   // einde functie
Loopt in 2,5 seconden. Als een jaartal niet deelbaar is door 4: return false en einde berekening. Als het niet deelbaar is door 100, wordt niet verder berekend of het door 400 deelbaar is. Werkt uiteraard ook correct. En toch kan het nog sneller. De code die Delphi genereert is zeer snel, maar niet perfect.

Als de taal van de processor zelf benaderd wordt, kan de code nog verder verfijnd:

function ASM_IsSchrikkelJaar(Jaartal: cardinal): Boolean;    // snelste functie maar minst leesbaar
asm                      // start assembler. 37 Bytes code. Auteur: John O'Harrow
  test  al,3             // and 3 of binair 11 met het register al - als de beide bits "al" 00 zijn dan is
                         // het jaartal deelbaar door 4 - "al" wordt niet gewijzigd maar de zero flag
                         // wordt wel gezet als het deelbaar is. Het verschil tussen and al, 3
                         // en test al, 3 is dat het register "al" bij "test" niet gewijzigd wordt.
  jz    @@IsEeuw         // indien zero flag geset is (jump if zero), ga naar @@IsEeuw
  xor   eax,eax          // Op deze lijn komen we enkel terecht als het jaartal niet deelbaar is door 4
                         // zet eax op 0 (waarde in eax wordt teruggegeven = functie Return False)
                         // xor register op zichzelf = snelste manier om op 0 te zetten: 2 kloktikken.
  ret                    // return naar aanroepend adres
@@IsEeuw:                // label: kijk na of het een eeuwjaar is
  mov   edx,$028F5C29    // ((2^32)+100-1)/100
  mov   ecx,eax          // zet het jaartal in telregister ecx
  mul   edx              // EDX = jaar DIV 100
  mov   eax,edx          // destination index edx terug naar accumulator register eax
  imul  edx,100          // EDX is nu (jaar DIV 100) * 100
  cmp   ecx,edx          // cmp compare - kijk of deelbaar door 100 ( = eeuwjaar)
  je    @@IsVeelvoud400  // zo ja, "jump if equal" naar label @@IsVeelvoud400
  mov   al,true          // wel deelbaar door 4 maar niet door 100 ( = Return True)
  ret                    // terug naar aanroepend adres
@@IsVeelvoud400:         // label: kijk na of het eeuwjaar deelbaar is door 400
  test  al,3             // is jaartal deelbaar door 400 - zo ja zet zero vlag
  setz  al               // "set if zero" zet al op true indien zero flag gezet is
end;                     // einde functie
Deze code is nog sneller dan de "geneste if" functie: 1 seconde. Uiteraard is dat ten koste van de leesbaarheid, want om in assembler iets te bekomen zijn er relatief meer regels nodig dan in andere programmeertalen. Maar een goed geschreven assemblerprogramma (of functie) kan nooit sneller lopen in een andere programmeertaal. Uiteraard vergt het veel meer werk om in assembler dergelijke code te produceren, en duurt het wel even eer een programmeur echt productief is in die taal. Dat zijn allemaal factoren die meespelen.

De snelheid werd getest door oplopende jaartallen meerdere miljoenen keren de functies te laten doorlopen en testen of het een schrikkeljaar is. Het oplopen van die jaartallen in de aanroepende functie in Delphi werd van de tijden afgetrokken, zodat enkel de tijden van de functies verrekend werden. Het heeft geen zin om in absolute cijfers de verhouding van aantallen en tijden weer te geven, wegens de verschillende kloksnelheden van de computers. Maar de relatieve cijfers spreken voor zich: als de betere functie met
AND + OR 3 seconden nodig heeft, heeft die met dubbele XOR er 17 nodig. Die met geneste IF doet 2,5 seconden over dezelfde opzoeking, en die in ASM 1 seconde.



Kleinere exe in Delphi zonder de VCL
De structuur van Windows-programma's in enkele programmeertalen
Numlock problemen Windows 8 en 10
Windows-programma's in FASM