GCC verwandelt Switch-Anweisungen in Bitmasken – und keiner merkt es
Switch Lowering in GCC
GCC wählt für switch-Anweisungen je nach Fallverteilung unterschiedliche Strategien: Sprungtabellen bei dichten Werten, Vergleichsbäume bei spärlichen Fällen und sogar Bitmasken, wenn die Case-Labels in ein einzelnes Register passen. Der Artikel seziert den Compiler-Pass pass_lower_switch und zeigt anhand von Assembly und Quellcode, wie Heuristiken wie die Acht-Einträge-pro-Case-Regel funktionieren – und wo GCC Optimierungen wie die Division vor dem Sprung übersieht.
Wenn wir die Binärdarstellung von 2753205 untersuchen, stellen wir fest, dass es sich tatsächlich um ein Bitset handelt. Die auf eins gesetzten Bits entsprechen den ASCII-Werten der Case-Labels, jeweils um 48 reduziert.
- LarsKrimi
> Das switch in sparse_8 könnte vereinfacht werden, indem man x vor dem Sprung durch acht teilt. Interessanterweise findet gcc diese Vereinfachung nicht.
Das könnte es nicht, weil das dafür sorgen würde, dass 7 Werte für jeden Fall durch Funktionsaufrufe statt durch den Default-Fall behandelt würden – 0/8 ist 0, aber 3/8 ist auch 0
- rurban
Was für eine Schande für clang und gcc! Sie implementieren immer noch keine perfekten Hashes für große dünn besetzte Switch-Tabellen. Ich habe das kürzlich für meinen rcc-C-Compiler gemacht, und es war nur ein Tag Arbeit. Besonders vorteilhaft für Unicode-Arbeit. Der LLVM-Patch wurde vor einem Jahrzehnt abgelehnt. Gcc hat mehrere Unicode-Patches in Branches liegen, die das auch bräuchten
- p-t
Ich nehme an, 34 in compact_7() sollte 35 sein, und edx sollte irgendwann in bittest() verwendet werden (es sei denn, ich übersehe etwas, lol)
- tsukikage
Warum die Indirektion? – warum nicht die Sprungtabelle direkt auf f0..fX verweisen lassen, statt auf einen Sprung zu springen?
- Andi
Ich erinnere mich, ähnliche Dinge in JavaScript implementiert zu haben (durch Codegenerierung), für unveränderliche Maps und Sets – kein signifikanter Performance-Gewinn in modernen Engines. Für reguläre Ausdrücke komplexer Unicode-Bereiche war die Beschleunigung etwa 2x!