spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ist das ein echtes Performanceproblem, welches du nachweislich (Profiling) gemessen hast und was deine Anwendung beeinträchtigt, oder geht es hier um Premature Optimization?

Das ist sicher der Release Build?

Zitat von »LukasBanana«

Sprünge sind ja nicht gerade Performant, oder ist das bei unbedingten Sprüngen relativ egal?
Mir erscheint ein festangelegtes Array jedenfalls immer noch effizienter zu sein.

Da wäre ich mir mal nicht so sicher; bedenke, dass die Lösung per Jumptable das Ergebnis aus dem Speicher lesen muss, während die hier vom Compiler implementierte Lösung das Ergebnis direkt in der Instruction ablegt...

Zitat von »dot«

Da wäre ich mir mal nicht so sicher; bedenke, dass die Lösung per Jumptable das Ergebnis aus dem Speicher lesen muss, während die hier vom Compiler implementierte Lösung das Ergebnis direkt in der Instruction ablegt...

Instruktionen stehen ja auch im Speicher und müssen dort geholt werden. Aber wenigstens ist es so näher zusammen. Allgemeine Aussagen lassen sich aber ehh nicht treffen.

So ist es. Eine der obersten Regeln bei Optimierung lautet: Deine Vermutung ist immer falsch. Ohne Profiler nicht in's Blaue optimieren.

Hab mich mal etwas damit rumgespielt: Eine Lookup-Table hab ich MSVC auf die Schnelle nicht entlocken können. Ab 6 Case-Labels generiert er eine Jump-Table, was etwas schade ist, weil eine direkte Lookup-Table da definitiv effizienter sein sollte. Clang mit Microsoft-Codegen tut das gleiche wie MSVC; Clang mit LLVM-Backend dagegen erzeugt eine direkte Lookup Table so lange zwischen den Werten der Case-Labels keine zu großen Lücken sind, im Allgemeinen Fall tut es ansonsten exakt das gleiche wie MSVC. LLVM schafft es offenbar sogar, zu erkennen, dass ein switch nur ein lineares Mapping implementiert und ersetzt das dann direkt durch die Formel. Den Spezialfall eines identity Switch (also wo nur gleiche Werte auf gleiche abgebildet werden) optimiert LLVM dann direkt weiter zu einem einfachen conditional Return...

Das mit dem Profiler ist ja richtig - aber es beantwortet die Frage nicht.

Eine Wertetabelle ist in dem Fall effizienter, weil es keinen Control Flow benötigt und dadurch keine Pipeline Stalls verursacht. Das heißt: Der Compiler führt diese Optimierungen einfach nicht durch.
Der Einwand von Dot ist nicht zutreffend, weil der Compiler auch hier eine Tabelle anlegt.
Der Code von LukasBanana war leider nicht vollständig, um das eindeutig zu zeigen. Hier mal der vollständige Code (x64, Release, Standardeinstellungen):

Inhalt anzeigen/verstecken

Quellcode

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

_TEXT SEGMENT compareOp$ = 48 ?MapSwitch@@YA?AW4D3D12_COMPARISON_FUNC@@W4CompareOp@@@Z PROC ; MapSwitch, COMDAT ; 50 : { $LN16: 00000 48 83 ec 28 sub rsp, 40 ; 00000028H ; 51 : switch (compareOp) 00004 83 f9 07 cmp ecx, 7 00007 77 66 ja SHORT $LN15@MapSwitch 00009 48 63 c1 movsxd rax, ecx 0000c 48 8d 15 00 00 00 00 lea rdx, OFFSET FLAT:__ImageBase 00013 8b 8c 82 00 00 00 00 mov ecx, DWORD PTR $LN13@MapSwitch[rdx+rax*4] 0001a 48 03 ca add rcx, rdx 0001d ff e1 jmp rcx $LN4@MapSwitch: ; 52 : { ; 53 : case CompareOp::Never: return D3D12_COMPARISON_FUNC_NEVER; 0001f b8 01 00 00 00 mov eax, 1 ; 63 : } 00024 48 83 c4 28 add rsp, 40 ; 00000028H 00028 c3 ret 0 $LN5@MapSwitch: ; 54 : case CompareOp::Less: return D3D12_COMPARISON_FUNC_LESS; 00029 b8 02 00 00 00 mov eax, 2 ; 63 : } 0002e 48 83 c4 28 add rsp, 40 ; 00000028H 00032 c3 ret 0 $LN6@MapSwitch: ; 55 : case CompareOp::Equal: return D3D12_COMPARISON_FUNC_EQUAL; 00033 b8 03 00 00 00 mov eax, 3 ; 63 : } 00038 48 83 c4 28 add rsp, 40 ; 00000028H 0003c c3 ret 0 $LN7@MapSwitch: ; 56 : case CompareOp::LessEqual: return D3D12_COMPARISON_FUNC_LESS_EQUAL; 0003d b8 04 00 00 00 mov eax, 4 ; 63 : } 00042 48 83 c4 28 add rsp, 40 ; 00000028H 00046 c3 ret 0 $LN8@MapSwitch: ; 57 : case CompareOp::Greater: return D3D12_COMPARISON_FUNC_GREATER; 00047 b8 05 00 00 00 mov eax, 5 ; 63 : } 0004c 48 83 c4 28 add rsp, 40 ; 00000028H 00050 c3 ret 0 $LN9@MapSwitch: ; 58 : case CompareOp::NotEqual: return D3D12_COMPARISON_FUNC_NOT_EQUAL; 00051 b8 06 00 00 00 mov eax, 6 ; 63 : } 00056 48 83 c4 28 add rsp, 40 ; 00000028H 0005a c3 ret 0 $LN10@MapSwitch: ; 59 : case CompareOp::GreaterEqual: return D3D12_COMPARISON_FUNC_GREATER_EQUAL; 0005b b8 07 00 00 00 mov eax, 7 ; 63 : } 00060 48 83 c4 28 add rsp, 40 ; 00000028H 00064 c3 ret 0 $LN11@MapSwitch: ; 60 : case CompareOp::Ever: return D3D12_COMPARISON_FUNC_ALWAYS; 00065 b8 08 00 00 00 mov eax, 8 ; 63 : } 0006a 48 83 c4 28 add rsp, 40 ; 00000028H 0006e c3 ret 0 $LN15@MapSwitch: ; 61 : } ; 62 : MapFailed("CompareOp", "D3D12_COMPARISON_FUNC"); 0006f 48 8d 15 00 00 00 00 lea rdx, OFFSET FLAT:??_C@_0BG@FCJHIDFD@D3D12_COMPARISON_FUNC?$AA@ 00076 48 8d 0d 00 00 00 00 lea rcx, OFFSET FLAT:??_C@_09FFBPNLHE@CompareOp?$AA@ 0007d e8 00 00 00 00 call ?MapFailed@@YAXPEBD0@Z ; MapFailed 00082 cc int 3 $LN14@MapSwitch: 00083 90 npad 1 $LN13@MapSwitch: ; 63 : } 00084 00 00 00 00 DD $LN4@MapSwitch 00088 00 00 00 00 DD $LN5@MapSwitch 0008c 00 00 00 00 DD $LN6@MapSwitch 00090 00 00 00 00 DD $LN7@MapSwitch 00094 00 00 00 00 DD $LN8@MapSwitch 00098 00 00 00 00 DD $LN9@MapSwitch 0009c 00 00 00 00 DD $LN10@MapSwitch 000a0 00 00 00 00 DD $LN11@MapSwitch ?MapSwitch@@YA?AW4D3D12_COMPARISON_FUNC@@W4CompareOp@@@Z ENDP ; MapSwitch _TEXT ENDS

Der Compiler prüft erst, ob der Wert für den switch außerhalb des Wertebereichs der Tabelle liegt (Zeile 13). Dann in Zeile 20 gibt es einen indirekten Sprung an die Tabellenposition. Das ist ein Standardverfahren für aufeinanderfolgende Werte eines switch. Das ist in diesem Fall nur leider unnötig kompliziert. Jeder Zweig der switch-Anweisung tut nichts weiter als einen bestimmten Wert zu laden. Es wäre sehr viel sinnvoller diesen Wert direkt aus der Tabelle zu laden.

Clang führt nicht bloß diese Optimierung durch, sondern bemerken noch etwas anderes: "D3D12_COMPARISON" ist als aufsteigende Ganzzahlen ausgehend von 1 definiert. Dadurch kann er nach der Prüfung ob der Wert in einen switch-Branch fällt, einfach 1 zu dem Eingabewert hinzuaddieren! (Test bei Godbolt: Code) Interessant ist auch, dass deine Variante mit der Tabelle auf den selben Maschinencode optimiert wird. (EDIT, Kleiner Irrtum: Das Gegenteil ist leider der Fall) Falls die Werte von "D3D12_COMPARISON_FUNC" nicht direkt aufeinanderfolgen, wird außerdem korrekt eine Wertetabelle anstatt einer SprUngtabelle erzeugt, wie von dir vorgeschlagen.

Ok, was heißt das? Die Variante die mit dem MSVC den besten Maschinencode erzeugen würde (Den Zahlenwert + 1), basiert auf der externen Definition von "D3D12_COMPARISON_FUNC". Das ist suboptimal. Es gibt zwar keinen Grund, warum sich diese Definition ändern sollte, allerdings würde ich diese Optimierung trotzdem skeptisch betrachten. Bei der Version mit der Tabelle gibt es ein ähnliches Problem: Die Einträge der Tabelle müssen zur Enumeration passen die an einer völlig anderen Stelle definiert ist. Es wird also nicht eine Enumeration zu einer anderen gemappt, sondern ein impliziter Zahlenwert zu einer Enumeration. Deshalb ist die Tabelle in meinen Augen weniger elegant. Das scheint mir nichts mit einer ANSI-C-Ablehnung zu tun zu haben. In ANSI C gab es nämlich schon immer switch.

Ein lesenswerter Artikel der sich mit dem Problem auseinandersetzt: http://www.g-truc.net/doc/C++%20Translations.pdf
Sein Fazit ist, dass er eine Wertetabelle verwendet.

Zitat von »Spiele Programmierer«

Der Einwand von Dot ist nicht zutreffend, weil der Compiler auch hier eine Tabelle anlegt.

Da der entsprechende Teil des Assemblycode nicht gepostet wurde, konnte ich das zu dem Zeitpunkt nicht wissen... MSVC erzeugt nicht unbedingt immer eine Jump-Table. Aus meinen Beobachtungen würde ich schließen, dass er eine Jump-Table generiert, sobald das Switch mehr als 5 Cases hat, ansonsten eine Kaskade aus Compares und Jumps...

Zitat von »Spiele Programmierer«

Eine Wertetabelle ist in dem Fall effizienter, weil es keinen Control Flow benötigt und dadurch keine Pipeline Stalls verursacht.

Das kann man so einfach leider nicht sagen, da die relative Performance dieser unterschiedlichen Implementierungen sehr stark davon abhängt, was für Zahlen am Ende in der laufenden Anwendung konkret durch den Code gehen. Ich hätte beispielsweise erwartet, dass die Lösung mit Immediate-Values effizienter ist, so lange es keine Jump-Table gibt und die Branch-Prediction funktioniert. Und tatsächlich: In einem schnellen Test hier war diese Variante konsistent schneller als eine Lookup-Table wenn immer der selbe Wert durchgeht aber bis zu 10× langsamer wenn komplett zufällige Werte durchgehen. Ich würde auch sagen, dass die Lookup-Table vermutlich die overall bessere Lösung sein sollte. Aber je nach Situation muss das nicht unbedingt stimmen. Die nächste Frage ist dann also, was für Code MSVC mit Profile-Guided-Optimizations generieren würde...