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!
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
1
intfoo(intb){
2
switch(b){
3
case1:a1();break;
4
case2:a2();break;
5
default:ad();
6
}
7
}
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.
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 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.
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.
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.
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.
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.
