Ich verstehe, dass eine switch-Anweisung in c / c ++ manchmal in eine Sprungtabelle kompiliert wird. Meine Frage ist, gibt es Daumenregeln, um das sicherzustellen?
In meinem Fall mache ich so etwas:
%Vor% Ich beziehe alle Fälle von 1 bis n im Auftrag. Kann man davon ausgehen, dass es zu einer Sprungtabelle kompiliert wird?
Der ursprüngliche Code war eine lange und unordentliche if else Aussage, so dass ich wenigstens eine Lesbarkeit erhalte.
Ein guter Compiler kann und wird zwischen einer Jump-Tabelle, einem if / else oder einer Kombination wählen. Ein schlecht entworfener Compiler kann eine solche Wahl nicht treffen - und kann sogar sehr schlechten Code für Schaltblöcke erzeugen. Aber jeder anständige Compiler sollte effizienten Code für Switch-Blöcke erzeugen. T
Der Hauptentscheidungsfaktor hierbei ist, dass der Kompilierer wählen kann, ob / wenn die Zahlen weit voneinander entfernt sind [und nicht trivial (z. B. Division durch 2, 4, 8, 16, 256 usw.) auf einen kleineren Wert geändert], z. %Vor%würde eine Sprungtabelle von mindestens 19102 * 2 Bytes erfordern.
Wenn andererseits die Zahlen dicht beieinander liegen, verwendet der Compiler normalerweise ein Jumptable.
Auch wenn es sich um einen if/else -Designtyp handelt, wird normalerweise eine "binäre Suche" durchgeführt - wenn wir das obige Beispiel nehmen:
Wenn wir viele Fälle haben, wird dieser Ansatz ziemlich tief nisten, und Menschen werden wahrscheinlich nach drei oder vier Tiefenstufen verloren gehen (bedenkt, dass jedes if an einem Punkt in der MITTE des Bereichs beginnt), aber es reduziert die Anzahl der Tests um log2 (n), wobei n die Anzahl der Auswahlmöglichkeiten ist. Es ist sicherlich viel effizienter als der naive Ansatz von
%Vor%Dies kann etwas besser sein, wenn bestimmte Werte am Anfang der if-else-Kette stehen, aber das setzt voraus, dass Sie bestimmen können, was am häufigsten vor dem Ausführen des Codes passiert.
Wenn die Leistung für Ihren Fall von entscheidender Bedeutung ist, müssen Sie die beiden Alternativen miteinander vergleichen. Aber ich schätze, dass das Schreiben des Codes als Schalter den Code viel klarer macht und gleichzeitig mindestens genauso schnell, wenn nicht sogar schneller läuft.
Compiler können zwar jeden C / C ++ - Switch in eine Jump-Tabelle umwandeln, aber ein Compiler würde dies aus Gründen der Effizienz tun. Fragen Sie sich, was ich tun würde, wenn ich einen Compiler schreibe und ich gerade einen Syntaxbaum für eine switch / case-Anweisung erstellt habe? Ich habe Compiler Design und Konstruktion studiert, und hier sind einige der Entscheidungen,
Wie man einem Compiler hilft, eine Sprungtabelle zu implementieren:
Obwohl sich die Mechanismen zwischen Compilern unterscheiden können, erzeugt der Compiler im Wesentlichen unbenannte Funktionen (na ja, vielleicht keine Funktion, weil der Compiler den Codeblock verwenden und aus dem Codeblock springen kann oder clever sein kann und jsr verwendet und zurück)
Der richtige Weg, um einen Sprungtisch zu bekommen, ist, ihn zu schreiben. Es ist ein Array von Zeigern auf Funktionen, indiziert mit dem gewünschten Wert.
Wie?
Definieren Sie einen Typdef für Ihren Funktionszeiger, Erläuterungen zu typedefs für Funktionszeiger in C ,
typedef void (* FunkPtr) (doppelte a1, doppelte a2);
%Vor%Natürlich haben Sie function_name_ {0..n} bereits definiert, damit der Compiler die Adresse der zu evozierenden Funktion finden kann.
Ich werde die Evokation des Funktionszeigers und der Grenzkontrolle als eine Übung für den Leser hinterlassen.
Die Vorgehensweise hängt vollständig vom Compiler ab.
Beachten Sie jedoch, dass es wegen Ihrer break -Anweisungen keine reine Jump-Tabelle in Assembler gibt, also würde ich dagegen wetten. Aber das ist nur eine Wette; Ich schreibe keine C ++ - Compiler.
Mit einem switch testen Sie nur eine Bedingung (wie ausführlich sie auch sein mag), aber mit if / else testen Sie mehrere; obwohl Sie optimieren können, indem Sie die wahrscheinlichsten Fälle zuerst stellen. Das könnte schneller sein als ein aufwendiges switch . Das sind wahrscheinlich die wichtigsten Optimierungsüberlegungen für Sie. Ich würde mir über die Wahlmöglichkeiten des Compilers keine allzu großen Sorgen machen.
Tags und Links c++ switch-statement jump-table