Steeds dezelfde condities in lus

[Bozozo]

Deze vraag geldt eigenlijk voor elke taal. In dit voorbeeld gebruik ik PHP.

Ik kom deze situatie regelmatig tegen:

PHP:

$var1 = (boolean)$_POST['var1'];
$var2 = (boolean)$_POST['var2'];
$var3 = (boolean)$_POST['var3'];

for ($i=0;$i<10000;$i++) {
  //hier een of andere berekening
  if ($var1) {
    //hier een specifieke extra operatie. Kan ingewikkeld zijn.
  }
  if ($var2) {
    //hier nog een
  }
  if ($var3) {
    //hier nog een
  }
}

Met andere woorden, er is een of andere enorme loop met daarin een paar if statements. De condities veranderen niet tijdens het doorlopen van de loop.

In het bovenstaande geval voor ik dus 9999 zinloze if's uit; de uitkomst van elke conditie is al bekend. Dat lijkt mij zonde van de rekentijd.

Kan dat niet efficiënter?

[BtM909]

1. Waarom loop je er 10000 keer doorheen?

2. Je voert helemaal geen if statement uit, aangezien de meeste talen 't resultaat overslaan

[Onbekend]

Kan je een voorbeeld van zo'n situatie geven?
In jouw voorbeeld heb je niets aan die lus, tenzij je een array doorloopt en in je if-lussen de $i variable gebruikt.

[T-MOB]

Je kunt het helemaal uitschrijven. Misschien (meer code betekent ook meer inlezen voordat er wat wordt uitgevoerd) is het dan iets efficienter. Maar ik denk niet dat je het merkt...
Klein testje op een heel traag p2-tje (233mhz):

PHP:

$a = TRUE;
$c = TRUE;

$start = microtime(true);
for($i=0; $i<100000; $i++) {
    if ($a) { /*void*/ }
    if ($c) { /*void*/ }
}
$time = microtime(true)-$start;

print($time); //0.155930042267

$start = microtime(true);
for($i=0; $i<100000; $i++) {
    if ($c) { /*void*/ }
}
$time = microtime(true)-$start;
print($time); //0.131472826004

Dat scheelt dus een whopping 0.02 seconden op 100.000 iteraties. Je bespaart ongeveer net zoveel door ++$i te schrijven ipv $i++. Ik zou me dus om andere dingen druk gaan maken...

[Voutloos]

Bozozo schreef op donderdag 27 maart 2008 @ 13:05:
De condities veranderen niet tijdens het doorlopen van de loop.

Mooier verwoord: een bepaalde variabele of conditie is een invariant. En steeds opnieuw een invariant controleren/verwerken/evalueren is uiteraard zonde.

Menig compiler optimaliseert dit, maar in 9 vd 10 gevallen is het triviaal om een dergelijke invariant uit de loop te werken en vaak genoeg verbetert de leesbaarheid van de loop daarbij. Als je zoekt op termen als 'loop invariant' en 'refactoring', of zelfs in teksten over compiler optimalisaties kijkt, vind je legio manieren om er wat aan te doen inc. voor- en nadelen. De code in de ts kan aagepast worden naar een viertal eenvoudiger loops. Voor de hand liggende nadelen zijn dan het herhalen van de loop constructie, en de overhead die de extra loops geven, voordeel is dat je de if condities maar 1x uitvoert, maar op zich is een if conditie evalueren (zeker indien dat een enkele bool var is) niet de allerduurste actie.

T-MOB schreef op donderdag 27 maart 2008 @ 13:21:
Dat scheelt dus een whopping 0.02 seconden op 100.000 iteraties.

In dit geval is dus een suffe micro-optimalisatie. Maar je ziet vaak genoeg loops waar duurdere operaties bespaart kunnen worden door te beseffen dat iets een invariant is. Wellicht het bekendste voorbeeld is het gebruiken van count() op een niet veranderende array in de loop conditie.

[ Voor 17% gewijzigd door Voutloos op 27-03-2008 13:28 ]

[Bozozo]

Ah, die opmerking over count(), of sizeof() in het geval van PHP, is wel een eye-opener. Ik gebruik regelmatig $i < sizeof($array) in mijn scripts, zonder te beseffen dat dat zonde van de rekentijd is. Weten we dat ook weer

Verder bepaal ik uiteraard alle ingewikkelde condities waar mogelijk van tevoren. Dat neemt niet weg dat er nog steeds een boel if-condities worden geëvalueerd, ook al is het slechts if(boolean), waarvan de uitkomst al vast stond.

Het herschrijven van de code is alleen in de meest eenvoudige situaties een optie. In het door mij beschreven voorbeeldje heb je al 2³ = 8 mogelijke vormen van de code. De optimalisatie is daarmee wel gedaan, maar ik ben het niet met je eens dat de leesbaarheid van de code daarmee ook verbetert. Je krijgt enorme lappen code, en je zou bijvoorbeeld iedere aanpassing in de gemeenschappelijke berekening 7 keer moeten copypasten.

Eigen zou je zoiets moeten kunnen zeggen:

PHP:

$var1 = (boolean)$_POST['var1'];
$var2 = (boolean)$_POST['var2'];
$var3 = (boolean)$_POST['var3'];

for ($i=0;$i<10000;$i++) {
  //hier een of andere berekening
  if ($var1)_EVAL_ONCE {
    //hier een specifieke extra operatie. Kan ingewikkeld zijn.
  }
  if ($var2)_EVAL_ONCE {
    //hier nog een
  }
  if ($var3)_EVAL_ONCE {
    //hier nog een
  }
}

...waarbij de compiler automatisch de 8 codeblokken genereert. Geen idee of PHP dat al doet.

[TeeDee]

en je zou bijvoorbeeld iedere aanpassing in de gemeenschappelijke berekening 7 keer moeten copypasten.

Iets zegt mij dat je dat beter even kan refactoren.

[Onbekend]

Voutloos schreef op donderdag 27 maart 2008 @ 13:22:
In dit geval is dus een suffe micro-optimalisatie. Maar je ziet vaak genoeg loops waar duurdere operaties bespaart kunnen worden door te beseffen dat iets een invariant is. Wellicht het bekendste voorbeeld is het gebruiken van count() op een niet veranderende array in de loop conditie.

Een deel van de compilers detecteert dat en voert die functie maar één keer uit en gebruikt daarna steeds de uitkomst daarvan zonder opnieuw te berekenen. (Gebeurt o.a. in Delphi.)

Vanwege deze compiler optimalisatie ben ik eens een keer op m'n werk vier uur bezig geweest met debuggen om dit te vinden.

Ik had een code die vereenvoudigd ongeveer zo eruit ziet:

code:

for Counter = 0 to Length(Array) - 1 do
begin
  if Array[Counter] < 0 then
    RemoveValueFromArray(Counter); 
    // In deze functie werden de variablen 1 plaats opgeschoven in de array.
    // De array wordt dus één item korter. 
end;

Uiteindelijk kreeg ik een RangeCheckError omdat ik buiten de array las.
Achteraf bleek dus dat de functie Length maar één keer werd aangeroepen in plaats van elke keer.

Het was voor een kleine array wat snel ingeklopt moest worden. Of de computer nu er een seconde over deed maakte mij niets uit....

[H!GHGuY]

Niet alleen de compiler, ook de processor kan dit optimaliseren.

De branch predictor kan bijhouden wat de laatste branch was, of zelfs welke branch het meest genomen wordt, en deze verkiezen boven de andere mogelijkheid. Zo krijg je geen dure pipeline flushes door foutieve branches, wat je performance dan weer ten goede komt.