AT Blog

Er zijn een heleboel zaken die de performance van een programma kunnen beïnvloeden. Eén daarvan is je code en simpelweg geldt dat hoe minder instructies nodig zijn om iets uit te voeren hoe sneller het programma zal draaien. In deze en toekomstige blogs zal ik wat voorbeelden laten zien waarbij de performance soms iets en soms aanzienlijk verbeterd kan worden door de code net iets anders op te schrijven. Ik gebruik voor de voorbeelden de programmeertaal C. Echter zijn de meeste concepten ook in andere talen van toepassing. Let op, soms zal het herschrijven van de code tot gevolg hebben dat het niet meer voldoet aan een gebruikte programmeerstijl of standaard. Daar maak ik me even geen zorgen over. Het gaat me nu vooral om de performance.

In deze eerste blog omtrent performance wil ik het hebben over de volgorde van if-then-else statements. Bekijk het volgende stukje C-code eens.

#include<stdio.h>

#define AMOUNT_OF_ITERATIONS 1000000000

int func1() { return 10; }
int func2() { return 12; }
int func3() { return 23; }
int func4() { return 11; }

int parse_message(char *msg)
{
  if(strcmp("potato", msg) == 0)
  {
          return func1();
  }
  else if(strcmp("tomato", msg) == 0)
  {
          return func2();
  }
  else if(strcmp("banana", msg) == 0)
  {
          return func3();
  }
  else if(strcmp("orange", msg) == 0)
  {
          return func4();
  }
}


int main(int argc, char* argv[])
{
  unsigned long int i;
  int rate;

  for(i = 0; i < AMOUNT_OF_ITERATIONS; i++)
  {
        if( random()%2 )
      rate = parse_message(argv[1]);
    else
      rate = parse_message(argv[2]);
  }
  printf("Rate=%d\n", rate);
  return 0;
}

De code doet niet echt veel zinnigs. Het is een aangepaste versie van code van een daemon waarin zich een performance probleem voordeed. Maar dit soort code, waarbij op basis van een reeks if-then-else statements (of in een switch) bepaalde code wel of niet wordt aangeroepen, kom ik geregeld tegen. De main functie is alleen bedoeld om het effect van de volgorde van de condities in de functie parse_message te demonstreren. Dat we hier op "willekeurige" basis bepalen of het eerste of het tweede argument moet worden gebruikt is nodig om te voorkomen dat compiler-optimalisaties roet in het eten gooien. De code is als volgt te compileren met gcc.

$ gcc -O3 freqs.c -o freqs

De optie -O3 zorgt ervoor dat gcc zoveel mogelijk optimalisatie zal toepassen. Dit doe ik om te laten zien dat je als programmeur toch ook echt invloed kan hebben. Het programma kan ik als volgt uitvoeren.

$ time ./freqs orange orange
Rate=11

real  0m15.747s
user  0m15.741s
sys   0m0.000s

Ik gebruik het programma time om de hoeveelheid tijd te laten zien die het programma in beslag heeft genomen. Ik roep het programma dus aan met twee keer "orange" als argument. Dit zorgt ervoor dat altijd de laatste conditie slaagt in de functie parse_message. Laten we nu eens het programma uitvoeren met als argumenten potato en potato:

$ time ./freqs potato potato
Rate=10

real  0m6.231s
user  0m6.228s
sys   0m0.000s

Dit is een performance verbetering van maar liefst 60 procent. De winst wordt behaald doordat in de tweede run altijd de eerste conditie slaagt. Bij de eerste run slaagde telkens de laatste conditie en werd dus tijdens iedere aanroep van parse_message ook gecontroleerd of message gelijk is aan potato, tomato, of banana. Deze controle wordt in de tweede run niet gedaan waardoor deze dus vele malen sneller is.

Vaak zullen condities met een bepaalde frequentie slagen gedurende normaal gebruik van het programma. Stel nu dat uit tests blijkt dat het programma voor 90 procent wordt aangeroepen met orange en tomato. Dan zal het dus lonen om de condities voor orange en tomato bovenaan te zetten. Het analyseren van het slagingspercentage van de verschillende condities wordt ook wel een frequentie-analyse genoemd. Soms kun je direct uit de programmacode de frequenties afleiden. Maar meestal zul je met een zogenaamde coverage tool of profiler aan de slag moeten. Je voert dan het programma in een realistische omgeving uit en de coverage tool of profiler laat dan zien hoe vaak bepaalde onderdelen van je code zijn uitgevoerd. Om dit te illustreren zal ik de GNU profiler gebruiken, genaamd gprof. Om gprof te kunnen gebruiken dien je het programma te hercompileren met profile informatie (gcc optie -pg) als volgt:

$ gcc -pg freqs.c -o freqs

Let op dat je geen level 3 optimalisatie meegeeft. Je zult merken dat anders de functies niet meer worden aangeroepen, ze zijn namelijk inline gecompileerd in de main functie. Het gevolg is dat je dan geen frequentie-analyse kan doen.

Door het programma nogmaals uit te voeren wordt er profiling informatie naar het bestand gmon.out geschreven.

$ ./freqs tomato banana

Met gprof kun je vervolgens het bestand gmon.out uitlezen.

$ gprof -b -Q freqs
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self               self     total           
 time   seconds   seconds    calls   ns/call  ns/call  name    
 67.68      1.78     1.78                              main
 26.62      2.48     0.70 100000000     7.00     8.35  parse_message
  3.04      2.56     0.08 49996838      1.60     1.60  func2
  2.09      2.62     0.06 50003162      1.10     1.10  func3
  0.57      2.63     0.01                              func1

Voor iedere functie wordt de rekentijd en het aantal aanroepen getoond. Voor ons is nu alleen het aantal aanroepen van belang. Dit wordt getoond in de kolom calls. Vervolgens kun je deze informatie gebruiken om de beste volgorde van je if-statements te bepalen. In bovenstaand geval zouden dus eerst de condities voor "tomato" en "banana" moeten komen en dan de overige.

Wanneer je geen functies aanroept in je if-statements kun je beter gcov gebruiken. Als je toch gprof wilt gebruiken kun je dummy-functies toevoegen aan je code.

void func1() { return; }
void func2() { return; }
...

Deze functies dien je vervolgens in je if-statements aan te roepen.

Helaas levert frequentie-analyse niet altijd een performance winst op. Dat het in bovenstaand voorbeeld wel winst oplevert komt voor het grootste deel door de functie strcmp. Deze routine vereist nogal wat CPU tijd. Wanneer de condities een simpele vergelijking bevatten (bijvoorbeeld amount == 1) zul je merken dat de winst erg tegenvalt. Daarnaast moet er uit de frequentie analyse een duidelijke winnaar komen. Als de condities ongeveer met dezelfde frequentie slagen zal de winst ook tegenvallen.

Bij Debian meldt Roger Leigh dat Fedora een aparte groep "lock" heeft geïntroduceerd om de directory /var/lock niet meer world-writable te hoeven maken. Hij vraagt zich af of dit onder Debian ook zo kan worden opgezet. Het zal vooral aanpassingen aan de init-scripts vereisen waarbij de opgestarte daemon niet onder root-rechten zal draaien. De benodigde lock directory moet dan eerst aangemaakt worden en van de juiste permissies worden voorzien voordat de daemon wordt opgestart (link).

Asheesh Laroia laat weten dat de nieuwe mentor website up is (link). De site is bedoeld om het makkelijker te maken voor niet officiële Debian ontwikkelaars om een zogenaamde sponsor te vinden voor hun package. De sponsor zal het pakket dan controleren en namens de ontwikkelaar in de Debian distributie opnemen.

Jan Möbius heeft een bug aangemeld met betrekking tot rpc.statd dat poort 631 in gebruik neemt terwijl dit de poort is voor CUPS. Ben Hutchings laat weten dat het een bekend probleem is met het gebruik van de bindresvport functie. Dit is een functie die een willekeurige poort opent tussen 512 en 1023. Hij maakt vervolgens meteen gebruik van de gelegenheid om systemd te promoten door te stellen dat overstappen op systemd de juiste oplossing is. Deze oplossing wordt snel van tafel geveegd. Er is namelijk de mogelijkheid om bepaalde poorten uit te sluiten voor bindresvport. Echter wordt dit voor de IPv6 versie van bindresvport niet gebruikt. Ben Hutchings levert vervolgens een patch aan om dit op te lossen (link, link).

Er wordt druk gediscussieerd over het nut van xz compressie ten opzichte van de veel gebruikte gz compressie voor de bestanden in de directory /usr/share/doc. Het blijkt dat de winst van xz ten opzichte van de al veel gebruikte bz2 compressie minimaal is en soms zelfs slechter (link). Er wordt dan ook geopperd om wellicht bz2 te gaan gebruiken in plaats van over te stappen op xz.

Nanakos Chrysostomos heeft na het aanbrengen van een patch voor een lang openstaande bug zichzelf als copyrighthouder voor de yubico PAM module toegevoegd. Hier was de originele auteur niet van gediend. Nanakos vroeg zich af of dit correct was. Hij kreeg helaas geen bijval en iedereen vond zijn bijdrage ook te klein om als copyright houder te worden opgenomen (link).

Bij Fedora meldt Josef Bacik in navolging van de heftige discussie rondom BTRFS vorige maand dat BTRFS niet het standaard filesysteem wordt in Fedora Core 16 (link).