switch-case statt if-else-if

[Tomot (Gast)]

Hi,

ich bin gerade dabei, ein wenig Embedded Code zu optimieren und auch die 
letzten paar Nanosekunden rauszukitzeln. Bevor ich mich da jetzt lange 
mit disassembliertem Code rumquäle:

Wenn ich mich recht erinnere, arbeitet ein switch-case-Statement mit 
irgend welchen CPU-Jumptables, die erst mal ein wenig Overhead 
verursachen und damit Zeit verbrauchen. Eine Verkettung fon 
if-else-if-else-if... ist aber irgendwann langsamer als das, was durch 
diesen Overhead verbraucht wird, weil im schlimmsten Fall jede Bedingung 
einzeln durchgegangen werden muss (wenn die gewünschte, erfüllte 
Bedingung erst am Ende steht).

Meine Frage: gibt es eine Faustregel, ab wie vielen if-else-Verkettungen 
man switch-case nehmen sollte, weil es dann effektiver arbeitet?

Ich setzte einfach mal voraus, das jede Bedingung gleich häufig erfüllt 
ist.

Danke!

[n.n. (Gast)]

Ab dem Zeitpunkt, ab dem es für die Lesbarkeit des Codes sinnvoll ist.

Ein Compiler wird ein switch case nicht exakt identisch umsetzen. Gerade 
mal getestet: folgender Code

int foo(int b) {
  switch (b) {
  case 1: a1(); break;
  case 2: a2(); break;
  default: ad();
  }
}

wird zu einer if-elseif-Kette nach dem Compilieren.

Wenn es tatsächlich so wichtig ist an einer bestimmten Stelle noch 
Mikro/Nanosekunden zu sparen, solltest du die jeweilige Funktion in 
Assembler schreiben. Sofern es an der Stelle tatsächlich was bringt.

[(prx) A. K. (prx)]

Tomot schrieb:
> Wenn ich mich recht erinnere, arbeitet ein switch-case-Statement mit
> irgend welchen CPU-Jumptables,

Machmal. Ein halbwegs guter Compiler schaut sich die Werte an und 
verwendet dann die günstigste von mehreren Methoden, abhängig vom 
Optimierungsziel Platz/Zeit. Eine der besseren Methoden wird 
beispielsweise kaum jemand zu Fuss programmieren: einen binären 
Abfragebaum.

[Tomot (Gast)]

OK, danke!

[Nop (Gast)]

Tomot schrieb:
> Meine Frage: gibt es eine Faustregel, ab wie vielen if-else-Verkettungen
> man switch-case nehmen sollte, weil es dann effektiver arbeitet?

Nein, weil der Compiler ein switch ebenfalls zu einer if-else-Kette 
verarbeiten KANN (nicht muß). Jumptables sind dann sinnvoll, wenn der 
Wertebereich relativ eng beieinander liegt, so daß man sie als Offsets 
für das Goto-Array verwenden kann. Das ist z.B. typisch für endliche 
Automaten.

Ich hab sowas in C auch schon "zu Fuß" mal implementiert, also ein Array 
mit Labeladressen, wo dann mit einem computed goto weitergesprungen 
wird. War allerdings am Ende auch nicht schneller als das, was GCC aus 
einem switch gebaut hat, nur daß ein switch natürlich viel 
wartungsfreundlicher ist.

Aber wenn Du beide Lösungen mal miteinander vergleichen willst, dann 
kannst Du ja sowohl die if-else-Kette als auch die computed gotos mal in 
C implementieren und dann die Ausführungszyklen messen.

[Peter D. (peda)]

Sobald mehrere ifs die selbe Variable testen, sollte man switch 
bevorzugen, weil das lesbarer ist.
Auch kann man beim GCC mit switch sehr gut lesbar auf Bereiche testen.

Von der Laufzeit her sucht sich der Compiler für das switch selber die 
optimale Methode aus.
Oftmals kann er auch besser optimieren, da die Tests zu Anfang erfolgen. 
Bei if/else Monstern kann es dagegen passieren, daß er die Variable 
unnötig mehrmals vom RAM einliest, weil die Tests verteilt liegen.
Zusätzlich erkennt ein switch gleiche Codesequenzen am Ende der Cases 
und fast sie zusammen.
In der Regel ergibt switch daher bessere Lesbarkeit und besseren Code.

[Sebastian V. (sebi_s)]

Wie üblich bei Performance Fragen gibt es eigentlich nur eine Antwort: 
Nachmessen!

Habe selbst vor einiger Zeit ähnliches Problem gehabt und habe einen 
if/else if/... Block mit ca. 8 Fällen in ein switch/case übersetzt. Das 
Ganze war am Ende langsamer als der ursprüngliche Code mit den 
if-Bedingungen. Auch ein von Hand gebastelter binärer Suchbaum mit 
if-Bedingungen war langsamer als das bloße Aneinanderreihen. Lag bei mir 
wohl daran, dass der erste Fall im if auch am häufigsten vorkam.

[(prx) A. K. (prx)]

Wenn man die AVRs und ARM-µCs verlässt und sich in die Leistungsklasse 
von PC/Mobil-Prozessoren begibt, dann kommt ein äusserst schwer zu 
kalkulierender Faktor hinzu: die Laufzeit einzelner Sprungbefehle.

Ein Sprung auf einem AVR kommt sehr schlicht daher: 2 Takte wenn er 
springt und 1 Takt wenn nicht. Bei komplexen Prozessoren kann dieser 
Bereiche zwischen effektiv 0 Takten bei korrekter Vorhersage und 
zweistelligen Werten liegen. Dann kann auch die Dichte der Codierung von 
Sprungbefehlen eine Rolle spielen, weil u.U. nur eine begrenzte Anzahl 
Sprungbefehle pro 16 Bytes effizient behandelt werden kann, was in 
manchen Implementierungen von switch Statements ziemlich übel ausgehen 
kann.

Andererseits sind manche Compiler über Profiling typischer 
Anwendungsfälle in der Lage, die Wahrscheinlichkeit von bedingten 
Sprüngen und Werten in switch Statements zu erfassen. Daraus lässt sich 
dann besserer Code generieren - indem beispielsweise entsprechende 
switch cases vorgezogen werden.

[S. R. (svenska)]

Moderne Compiler sollten äquivalente if/elseif/else-Ketten und 
switch/case gleich behandeln. Das heißt, eine Sprungtabelle wird - 
architekturbedingt - nur erzeugt, wenn der Compiler der Meinung ist, 
dass sie effizienter ist. Das wiederum hängt von der Optimierungsstufe 
ab.

Nimm, was für den Anwendungsfall lesbarer ist und teste im Zweifelsfall 
nach.

[Rufus Τ. F. (rufus)]

Und immer an Donald Knuth denken:

Programmers waste enormous amounts of time thinking about, 
or worrying about, the speed of noncritical parts of their 
programs, and these attempts at efficiency actually have 
a strong negative impact when debugging and maintenance 
are considered. 
We should forget about small efficiencies, say about 97% 
of the time: premature optimization is the root of all evil. 
Yet we should not pass up our opportunities in that critical 3%.

Und weils so schön überspitzt ist, nochmal:

premature optimization is the root of all evil