C++ If und Case performance

[Dese]

hier mal unter linux mit gcc 4.3.2:
der quellcode für die case version ist so:

while(i++ < count) {
x = (20.0 * (xrandom() / (double)(MAX_XRANDOM+1.0)));
switch(x) {
case 0: t+=0;
break;
case 1: t+=1;
break;
case 2: t+=2;
break;
case 3: t+=3;
break;
case 4: t+=4;
break;
case 5: t+=5;
break;
case 6: t+=6;
break;
case 7: t+=7;
break;
case 8: t+=8;
break;
case 9: t+=9;
break;
case 10: t+=10;
break;
case 11: t+=11;
break;
case 12: t+=12;
break;
case 13: t+=13;
break;
case 14: t+=14;
break;
case 15: t+=15;
break;
case 16: t+=16;
break;
case 17: t+=17;
break;
case 18: t+=18;
break;
case 19: t+=19;
break;
default: t+=20;
break;
}
}
t2 = ttime();
fprintf(stderr,"case time %f\n", (t2-t1));

die if-else variante kann man sich leicht denken.

zeiten für count=10000000:

case-version: 0.258690 sek
if-version: 0.320007 sek.

man beachte natürlich, dass ein großteil der laufzeit durch die random-funktion aber auch durch die simple addition verursacht wird. tatsache ist aber, dass die case-anweisung hier im schnitt um einenf aktor von 10 schneller als die if-anweisung ist. allerdings kommt der faktor nicht so deutlich hervor, da die randomfunktion einen immer vorhandenen löwnanteil an der schleife trägt.

edit: der faktor 10 ist nur im ideal-fall möglich, bei vielen vielen fallunterscheidungen. vorher wird er von immer benötigten anwweigungen erdrückt.

Ergänzung (5. Juli 2010)

korrektur:
hab mal nen test gemacht ohne case bzw. if anweisungen, d.h. in der gleichen while schleife eifnach t+=x.

laufzeit ist: 0.118821

und nachdem ich auch die zeit abgezogen habe für das erstmalige zugreifen der konstanten ergibt scih folgendes:

zeit nur für die if-anweisungen:
ca 0.2 sek

zeit fpr die case-anweisungen:
ca 0.15 sek.

if also ca 1.33 mal langsamer. schraubt man das ganze hoch, d.h. mehr als 20 verzweigungen kommt man langsam näher dem faktor 10, der in der theorie erreichbar ist.

 

[ice-breaker]

und du einen stark konstruierten Fall hast, bei dem das Case-Konstrukt optimal genutzt werden kann
Nämlich eine optimale Lookup-Tabelle.

Nebenbei bemerkt ist das Benchmarken von Mikrooptimierungen wieder so ein Fall, das Os muss nur kurzzeitig etwas machen und die Daten sind verfälscht.
Aber gut, ich lasse es nun sein.

 

[Dese]

noch was: das beispiel ist so sehr künstlich. wer mal versucht hat so etwas zu benchen, dem ist sicherlich schon aufgefallen, dass wenn er im selben programm, die bench funktion 2-mal aufruft, sie beim wzeiten mal deutlich kürzere laufzeiten bestimmt.
das leigt daran, dass beim ersten mal teile des codes noch nicht im cache sind.

d.h. in einem realistischen szenario kann der eine oder andere effekt mal deutlicher, mal weniger deutlich auftauchen.

Ergänzung (5. Juli 2010)

und du einen stark konstruierten Fall hast, bei dem das Case-Konstrukt optimal genutzt werden kann
Nämlich eine optimale Lookup-Tabelle.

nein, eben nicht. du ahst das nciht verstanden:
zu verwendung von case-anweisungen MUSS man die realen case-werte vorher in eben solche umwandeln!

sie müssen nicht genau aufeinanderfolgend sein, aber dicht bei einander sollten sie sein.
das gehört zur benutzung von case-anweisungen!

sagen wir, du hast reel die werte 500, 1000, 1500. dann erzeugst du pasende case-werte indem du durch 500 teilst. das nur als ein beispiel. oft kann man aber schon vorab dafür sorgen, dass die werte schon günstig gewählt sind. das muss man aber im vorfeld beachten!

das ist kein konstruiertes beispiel. man muss reele beispiele immer mit einer anpassung der werte erst für switch/case vorbereiten! das gehört dazu.

Nebenbei bemerkt ist das Benchmarken von Mikrooptimierungen wieder so ein Fall, das Os muss nur kurzzeitig etwas machen und die Daten sind verfälscht.
Aber gut, ich lasse es nun sein.

die werte sind sehr stabil. ich hab das häufiger durchlaufen lassen und schwankungen sind nur im <1% bereich. d.h. der faktor 1.33 ist stabil.

Ergänzung (5. Juli 2010)

noch was, als einfache methode, wie man beliebige werte passend zu switch/case optimieren kann:

man benutzt eine simple hashfunktion, die in etwa den zahlenraum abdeckt, der so groß ist, wie die menge der möglcihen werte. da diese im vorfeld bekannt sind, kann man in ruhe eine hashfunktion suchen, die keine kolision hervorruft.

benutzt man dazu eine hash-funktion der form ax+b mod p, dann ist sie auch fix zu berechnen. aber oft geht's auch mit einer noch simpleren und damit schnelleren funktion. und ja, es gibt viele situationen, in denen dieser zusatzaufwand locker vom gewinn der case-funktion aufgefangen wird.

Ergänzung (5. Juli 2010)

@Kagee:
ich seh jetzt erst grad, du ahst strings als case-werte genommen. das hättest du dir sparen können. wie cih oben schon schrieb: das bringt nichts! das kannst du nur dann optimieren, wenn du die strings auf eine zahl hashst und das möglichst dicht und ohne kollision.


im allgemeinen bei strings als werten ist case äquivalent zu if.

 

[kuddlmuddl]

Ich glaub hier so einen Beitrag zu dem Thema zu schreiben dauert länger, als ein Programm jemals an Laufzeit sparen kann, wenn man bei sowas rumoptimiert ;-)

Ich hab nur mal gehört, dass man die "wahrscheinlicheren" Fälle nach oben tun soll. So können case aber auch if/else schneller abgehandelt werden. Diese mögliche Optimierung kann der Compiler nämlich nicht durchfühen

Also eher:

int fakultaet(int n) {
    assert (n >0);
    if (n > 1) return n * fakultaet(n-1);
    else return 1;
}

anstatt

int fakultaet(int n) {
    assert (n > 0);
    if (n == 1) return 1;
    else return n * fakultaet(n-1);
}

kann ja ma wer benchen wenn er lust zu hat

 

[Dese]

deswegen sollte man sich nciht auf den glauben von leuten verlassen, die mal was gehört haben.

aber ja, wahrscheinlichere bedingungen sollten zu erst abgefragt werden.

 

[1668mib]

@knuddlmuddl:
Das hab ich weiter oben schon geschrieben: "Wenn man um IFs nicht umher kommt, sollte man die Bedingungen nach Möglichkeit der Wahrscheinlichkeit nach sortieren."

Und das ist an sich auch logisch.

Nur: Bei einem schlichten if-else spielt es keine so signifikante Rolle.

Bei enem Statement wie diesem

if (a) {
} else if (b) {
} else if (c) {
} else if (d) {
} else if (e) {
} else if (f) {
} else if (g) {
} else if (h) {
} else if (i) {
} else {
}

und dass "h" zutrifft hat die höchste Wahrscheinlichkeit, dann müssen dennoch die Prüfungen a bis g gemacht werden, selbst wenn es bei dem Durchlauf eben h ist.

Und bei deinem Beispiel würde ich wenn dann ganz anders optimieren:

int fakultaet(int n) {
    assert (n >0); 
    int result = 1;
    for (int i = 1; i <= n; i++) result = result * i;
    return result;
}

Abfragen wie "n > 1" finde ich aber meist besser als "n == 1" weil sie unschärfer formuliert sind.

 

[kuddlmuddl]

Sorry mib, hab deins überlesen.
Natürlich bringt deine Optimierung viel viel mehr. Gerade das meinte ich .. case statt if oder if statt case wird "nichts" bringen solange solch andere Optimierungen noch möglich sind.
Wollte nur ein "minimal" Beispiel zeigen, wo es theoretisch was bringen könnte.

Sich über so mikro-Optimierungen überhaupt Gedanken zu machen ist Zeitverschwendung, solange man nicht mit nem Profiler exakt feststellt, wo die Laufzeit verloren geht. Darum gilt ja eigtl auch immer
lesbarer Code > optimierter Code (wurde auch schon gesagt - ich weiß^^)