Geschwindigkeit: switch vs. if



  • LukasBanana schrieb:

    Hi Leute,

    Kann mir jemand sagen ob ein switch langsamer ist als ein if oder ist es gleich schnell?

    Ganz interessant dazu: Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms

    Zu finden hier: http://www.agner.org/optimize/



  • CStoll schrieb:

    So in etwa (eventuell mit einer kleinen Umrechnung, wenn es Lücken in den auftretenden Case-Marken gibt).

    (allerdings kenne ich mich mit der genauen Umsetzung nicht aus - da mußt du schon einen Assembler-Experten fragen)

    Ich bin zwar kein Assembler-Experte, aber ich kann das Vorgehen erklären:

    Sprungtabellen werden eigentlich immer eingesetzt, aber wenn die Lücken zu groß sind (z.B. wenn du die Fälle 0,1,2,3,4,1000,1001,1005,2001,2002 hast), dann legt der Compiler mehrere kleine Sprungtabellen an (im Beispiel: 0,1,2,3,4 ; 1000,1001,1005 ; 2001,2002) und Ordnet diese in einem binären Suchbaum an. Wenn der Switch-Block dann betreten wird vergleicht der Code den Wert und steigt entsprechend im Baum ab bis er zur richtigen Sprungtabelle kommt und benutzt den Wert dort als Index um zur richtigen Stelle in dem Switch-Block zu springen (zur Erinnerung: der gesamte Code des Switchblocks ist zusammenhängen, deswegen muss man die Abarbeitung auch explizit mit einem break beenden).



  • Wenn du dort optimieren willst, sollte man als erstes die cases die am häufigsten auftreten nach oben stellen. Das kann schon einiges bringen.



  • TrommlBomml schrieb:

    ausserdem ist man viel flexibler mit switches als mit wenn-dann-sonst-kontrollstrukturen, finde ich.

    Inwieweit?
    (ein Vorteil von if-else gegenüber switch() sind die Einschränkungen, womit du vergleichen kannst (nur ganzzahlige Typen - und nur Compilezeit-Konstanten))

    @Fellhuhn: Bei switch() spielt die Reihenfolge der case-Marken keine Rolle in Bezug auf die Geschwindigkeit (da kannst du eher auf Übersichtlichkeit und die Möglichkeit von fall-through-Fällen (kein break vor der nächsten case-Marke setzen) achten), bei der if-Kaskade macht es einen Unterschied (wobei man in der Theorie nicht überall weiß, welcher Fall der häufigste ist).



  • ... wenn der Compiler Jumptables benutzt und es nicht stumpf zu if/else auflöst.



  • Also ich hab jetzt auf jeden Fall ein switch für meine eine Stelle im Programm genommen.

    Vorallem muss der compiler unter Umständen bei if-Abfragen mehrere Sachen abfragen und bei einer switch-Anweisung muss er nur einen Wert vergleichen.
    Also nochmal Dnake an alle 🙂



  • Also; der compiler baut eine Jumptabelle auf und stellt das im Source so dar, dass die CPU möglichst wenig zu arbeiten hat (Am besten sequenziell).

    Aus dem Grund ist es egal, in welcher Reihenfolge ich meine switch-cases definiere, da sie der compiler sowieso sortiert.

    Im Fall von if-then-else Konstrukten trifft dieser Fall hingegen schon ein. Und man darf dieses Verfahren wohl auch nicht für falsch erklären, weil switch eben nur für numerische Aktionen in Frage kommt 😉

    Und der Compiler muss weder bei if-Abfragen mehrere Sachen Abfragen noch bei switch-cases, weil der compiler nur das statische Programm (welches dann erstmal gestartet werden muss) erzeugt.

    Und auch beim Switch wäre ich mir nicht sicher ob er wirklich nur einen Vergleich braucht...kommt wohl auch auf die Anzahl und die Abstände der Werte an.

    mfg jghj



  • jghj schrieb:

    Also; der compiler baut eine Jumptabelle auf und stellt das im Source so dar, dass die CPU möglichst wenig zu arbeiten hat (Am besten sequenziell).

    Aus dem Grund ist es egal, in welcher Reihenfolge ich meine switch-cases definiere, da sie der compiler sowieso sortiert.

    Das wird der Compiler i.A. nicht tun, genauso wenig (wie oben erwähnt) den Code in if-else übersetzen, denn ein Switch ist ein zusammenhängender Codeblock und die Cases sind nichts weiter als Sprungmarken mit einer Sprungbedingung.



  • lolz_ausgeloggt schrieb:

    jghj schrieb:

    Also; der compiler baut eine Jumptabelle auf und stellt das im Source so dar, dass die CPU möglichst wenig zu arbeiten hat (Am besten sequenziell).

    Aus dem Grund ist es egal, in welcher Reihenfolge ich meine switch-cases definiere, da sie der compiler sowieso sortiert.

    Das wird der Compiler i.A. nicht tun, genauso wenig (wie oben erwähnt) den Code in if-else übersetzen, denn ein Switch ist ein zusammenhängender Codeblock und die Cases sind nichts weiter als Sprungmarken mit einer Sprungbedingung.

    Was willst du jetzt damit sagen? 😕 Das keine Jumptable erstellt wird?



  • doch, der compiler erstellt eine jump table für switches. aber er wird sie bestimmt nicht sortieren, da dadurch die programmlogik verfälscht werden könnte.



  • thordk schrieb:

    doch, der compiler erstellt eine jump table für switches. aber er wird sie bestimmt nicht sortieren, da dadurch die programmlogik verfälscht werden könnte.

    Hast du ein Beispiel, wo da was verfälscht werden könnte? Ich kann's mir grad nicht konkret vorstellen 😕



  • programmlogik verfälschen ist vielleicht auch ein wenig unglücklich
    ausgedrückt. in der tat ist es aber so wie lolz_ausgeloggt sagte.
    die sprungtabellen werden ggf. geteit und sortiert. der code selbst
    bleibt so wie er ist. vor einigen jahren war es auch noch praxis einiger
    kompiler eine große sprungtabelle per switch statement zu erzeugen,
    in der aber halt bei großen lücken nur wenige einträge existierten.
    einen geschwindigkeitverlust gab es dadurch ja nicht, da in der regel
    direkt mit der case bedingung referenziert wird, z.B.

    jmp(JmpTbl[eax*4])
    

    allerdings blähte das den code, egal ob die sprungtabelle nun im datensegment
    oder im codesegment gespeichert ist, unötig auf.

    edit nummer 4: falls noch mehr syntaktischer und inhaltlicher schwachfug
    in diesem post ist, bitte nicht auseinanderpflücken, ich bin betrunken 😃



  • jghj schrieb:

    Also; der compiler baut eine Jumptabelle auf und stellt das im Source so dar, dass die CPU möglichst wenig zu arbeiten hat (Am besten sequenziell).

    Aus dem Grund ist es egal, in welcher Reihenfolge ich meine switch-cases definiere, da sie der compiler sowieso sortiert.

    klang für mich so, als ob meinte, dass die "cases" sortiert werden. wie die jump table sortiert wird ist rille.



  • CStoll schrieb:

    Inwieweit?
    (ein Vorteil von if-else gegenüber switch() sind die Einschränkungen, womit du vergleichen kannst (nur ganzzahlige Typen - und nur Compilezeit-Konstanten))

    ja nach der aussage hast du auch recht,
    aber ich zumindest bin nie in die lage gekommen, dass ich nicht ganzzahlige typen in einer solchen masse an kontrollverzweigungen eine switch-kontrollstruktur gebraucht hätte, mir fällt jetz auch spontan kein beispiel ein, oder zumindest kein sinnvolles oder praktisch angewandtes ein.

    ich meine auch solche sachen, dass man mehrere fälle die ein und denselben anweisungsblock benötigen, in meinen augen übersichtlicher lösbar sind (ich hätt nich flexibler sagen sollen sry).



  • Ich habe switch bisher nur in drei Fällen verwendet:

    Als Statemachine eines Konsolenmenüs (in meinem ersten echten Programm :D)
    Als Statemachine eines Parsers (geht auch schöner, aber ich konnte es damals nicht besser)
    Für Debug-/Log-Ausgaben von DirectX-Kontrollstrukturen mit denen diverse Einstellungen festgelegt werden.

    Meine Erfahrung mit Switch ist eigentlich eher negativ, also zumindest habe ich bisher noch keine Verwendung gesehen wo ich wirklich sage, dass es sauber gelöst ist.


Anmelden zum Antworten