[ALG] wat is efficienter

[Feyd-Rautha]

ik heb mij zitten afvragen welk stukje code het vlugst, meest efficiënt werkt:

code:

int getal = tabel[(int)(random() * 10) + 8];

in de veronderstelling dat random() een waarde tussen 0 en 1 teruggeeft
of

code:

int i = random() * 10;
int getal;
i = i + 8;
getal = tabel[i];

Is het, om efficientie-redenen, van belang om code1 of code2 te gebruiken?

[whoami]

Ik denk dat een beetje compiler in staat moet zijn om beide stukken code even te optimizen.

[Pooh]

Lijkt me heel weinig uitmaken. Die random-functie is in verhouding tot de rest van je code ontzettend zwaar. Optimaliseren op wat assignments is dan echt niet zo nuttig meer, vertrouwen op je compiler is inderdaad de beste oplossing.

Het duidelijkst leesbaar vind ik (persoonlijke mening):

code:

    int i = random() * 10 + 8;
    int getal = tabel[i];

Of, in andere omstandigheden:

code:

    int i;
    int getal;

    ...

    i = random() * 10 + 8;
    getal = tabel[i];

[Verwijderd]

Afhankelijk van hoe je random functie geimplementeerd is, kan de zwaarheid best nog wel eens meevallen (vermenigvuldiging van een integer met een groot priemgetal), behalve dan dat de functieaanroep wellicht relatief zwaar is (inlinen?).

Maar goed, ik ben het met je eens dat dit soort optimalisaties weinig zin hebben. Als je een miljard keer je code uit moet voeren om een seconde performance verschil te krijgen, is dat zeker niet de moeite waard. Bovendien kan dat ook nog eens per processor verschillend zijn.

Nu is er wel een simpel tegevoorbeeld te geven natuurlijk:

code:

function int getMaximum(Node p)
{
    if (p has no child) return een getal;

    int maxLeft = getMaximum(left node of p)
    int maxRight = getMaximum(right node of p)

    if (maxLeft > maxRight)
      return maxLeft
    else
      return maxRight
}

en

code:

function int getMaximum(Node p)
{
    if (p has no child) return een getal;

    if (getMaximum(left node of p) >
      getMaximum(right node of p)
      return getMaximum(left node of p)
    else
      return getMaximum(right node of p)
}

[elnino]

Op maandag 08 juli 2002 09:42 schreef -Avalanche- het volgende:
ik heb mij zitten afvragen welk stukje code het vlugst, meest efficiënt werkt:

code:

int getal = tabel[(int)(random() * 10) + 8];

in de veronderstelling dat random() een waarde tussen 0 en 1 teruggeeft

Volgens mij werkt een processor altijd met tussenvariabelen, dus het maakt volgens mij niet zoveel uit. Je zou eens kijken wat er gebeurd als het naar Assembly wordt omgezet en dan kun je de code vergelijken. Maar ik denk dat het een miniem verschil is. Je kunt je kostbare tijd maar beter op 'echte' bottle-necks richten.

Programmeer gewoon op de manier die jij het overzichtelijkste vindt.

[Soultaker]

Het is het efficienst om gewoon door te gaan met programmeren in plaats je van over dit soort dingen druk te maken. Iets minder efficient, maar misschien efficienter dan beide opties, is zelf een geoptimaliseerde functie in assembly te schrijven (wat natuurlijk niet portable is).

Ik zou zelf zeggen dat de eerste variant efficienter is, omdat de tussenresultaten nooit op de stack komen, maar een fatsoenlijke optimizer haalt dat er in het tweede geval ook wel uit. Op de stack geplaatste variabele zijn ook niet zo duur, aangezien ze lekker lokaal zijn en dus goed gecached kunnen worden.

Natuurlijk kunnen we het ook gewoon uitproberen. Omdat ik geen zin had om 4 gig geheugen te alloceren heb ik je vermenigvuldiging door een rest-operatie vervangen en je voorbeeld nog wat verder doorgetrokken door getal in de eerste variant weg te laten:

code:

#include <stdio.h>
#include <stdlib.h>

int tabel[64];

int f() {
      return tabel[(int)(random() % 10) + 8];
}

int g() {
      int i = random() % 10;
      int getal;
      i = i + 8;
      getal = tabel[i];
      return getal;

}

int main() {
      printf("%i\n%i\n", f(), g()); 
      return 0;
}

Resultaat in assembly code (gcc version 2.95.3 20010315 (release) [FreeBSD], level 2 optimization):

Functie f():

code:

f:
      pushl %ebp
      movl %esp,%ebp
      subl $8,%esp
      call random
      movl %eax,%ecx
      movl $1717986919,%edx
      movl %edx,%eax
      imull %ecx
      sarl $2,%edx
      movl %ecx,%eax
      sarl $31,%eax
      subl %eax,%edx
      leal (%edx,%edx,4),%eax
      addl %eax,%eax
      subl %eax,%ecx
      movl tabel+32(,%ecx,4),%eax
      leave
      ret

Functie g():

code:

g:
      pushl %ebp
      movl %esp,%ebp
      subl $8,%esp
      call random
      movl %eax,%ecx
      movl $1717986919,%edx
      movl %edx,%eax
      imull %ecx
      sarl $2,%edx
      movl %ecx,%eax
      sarl $31,%eax
      subl %eax,%edx
      leal (%edx,%edx,4),%eax
      addl %eax,%eax
      subl %eax,%ecx
      movl tabel+32(,%ecx,4),%eax
      leave
      ret

Zoals je ziet, is de gegenereerde code exact gelijk. Het maakt in de praktijk dus niets uit. Natuurlijk zal de compiler niet altijd de zaken zo goed kunnen inschatten als hier, maar ik zou me toch maar meer om de werking van m'n programma bekommeren (en de efficientie van eventuele algoritmen) dan de optimalisatiestap van de compiler.

[windancer]

Afhankelijk van hoe je random functie geimplementeerd is, kan de zwaarheid best nog wel eens meevallen (vermenigvuldiging van een integer met een groot priemgetal), behalve dan dat de functieaanroep wellicht relatief zwaar is (inlinen?).

Helaas is die vermenigvuldiging geen gewone vermenigvuldiging maar een vermenigvuldiging modulo een bepaald getal. Hiervoor zal het algorithme van Euclides worden gebruikt. Dit is een snel algorithme maar in vergelijking met een paar assignments neemt het toch een shitload processortijd.

Kortom, ik durf te betwijfelen dat de zwaarheid meevalt.

[Soultaker]

Op maandag 08 juli 2002 19:38 schreef windancer het volgende:
Helaas is die vermenigvuldiging geen gewone vermenigvuldiging maar een vermenigvuldiging modulo een bepaald getal. Hiervoor zal het algorithme van Euclides worden gebruikt. Dit is een snel algorithme maar in vergelijking met een paar assignments neemt het toch een shitload processortijd.

De implementatie van rand() (en niet random()!) uit de FreeBSD libc (een beetje aangepast):

code:

return
  ((next = next * 1103515245 + 12345)
   % ((u_long)RAND_MAX + 1));

Het gaat hier dus om een vermenigvuldiging, optelling en een modulebereking. Voor de processor is dit effectief een vermenigvuldiging, optelling en deling. De optelling duurt een constant aantal cycles en is waarschijnlijk te verwaarlozen ten opzichte van de vermenigvuldiging en deling. Dit zijn echter zulke gebruikelijke berekeningen, dat ze waarschijnlijk erg efficient geïmplementeert zijn (wie pakt de Intel data sheets erbij?).

Ik geloof niet dat het algoritme van Euclides hier bij te pas komt.

Ik vermoed dus, dat de overhead van de call best wel in dezelfde orde van grootte kan liggen als de feitelijke berekening. Wat 'meevallen' is, is natuurlijk subjectief, maar ik denk dat het toch wél 'meevalt'.

[ACM]

Op maandag 08 juli 2002 19:38 schreef windancer het volgende:
Kortom, ik durf te betwijfelen dat de zwaarheid meevalt.

Maar als je in beide gevallen (zie topicstart) "random" nodig hebt, boeit het werkelijk niet of het wel of niet zwaar is.
Als je het nodig hebt, heb je het nou eenmaal nodig.

De vraag van de topicstarter heeft Soultaker imho perfect beantwoord (doe wat je zelf het prettigst/duidelijkst vind, want de code wordt (zeker in dit geval) toch tot hetzelfde gecompileerd...)

En sja, als we ons al druk gaan maken over de zwaarte van een enkel random statement?

[edit]
Oeps

[whoami]

Op maandag 08 juli 2002 21:16 schreef ACM het volgende:


Het antwoord van de topicstarter heeft Soultaker imho perfect beantwoord

[Off-topic]
De vraag is beantwoord ACM, de vraag....
[/Off-topic]

[Verwijderd]

En als je idd een euclidische (pseudo-)RNG gebruikt, dan zijn beide stukjes code abominabel slecht, want ze rekenen met de least-significant-bits van de RNG.

Uit man 3 rand

code:

     In Numerical Recipes in C: The Art of Scientific Computing
     (William  H.  Press, Brian P. Flannery, Saul A. Teukolsky,
     William T.  Vetterling;  New  York:  Cambridge  University
     Press,  1990 (1st ed, p. 207)), the following comments are
     made:
          "If you want to generate a random integer between 1
          and 10, you should always do it by

               j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

          and never by anything resembling

               j=1+((int) (1000000.0*rand()) % 10);

          (which uses lower-order bits)."

[Soultaker]

Op dinsdag 09 juli 2002 14:04 schreef mietje het volgende:
En als je idd een euclidische (pseudo-)RNG gebruikt, dan zijn beide stukjes code abominabel slecht, want ze rekenen met de least-significant-bits van de RNG.

Daarom is het een goed plan om eigenlijk altijd random() te gebruiken. De performance penalty valt te overzien (al is random() iets trager dan rand()) maar dan heb je ook een getal uit een non-linear additive feedback random number generator (geen idee wat dat betekent ).

De belangrijke opmerking uit de man-page hierbij is dat alle bits random en bruikbaar zijn, waardoor (random()%X) wel 100% random is (mits 2^31 deelbaar is door X, anders treedt er een kleine afwijking op).