Post by G.B.Post by Helmut SchellongClang optimiert switch() nicht!
Damit nicht noch eine fragwürdige Verallgemeinerung zu
falschen Annahmen über Clang führt, wäre möglicherweise eine
präzisierende Formulierung angmessen gewesen. "Ich habe
mal ein Programm gehabt, für das Clang wie folgt ..."
Ansonsten verfolgt auch Clang eine Strategie für die
Optimierung von switch, von deren Funktionsweise man
sich ein Bild machen kann. Und Sprungtabellen sind darin
eingeschlossen.
Wenn clang nur eine Sprungtabelle generiert, wenn die case #:
um je 1 steigen, so ist das für mich keine Optimierung,
sondern ein stumpfes Nachmachen der Quelle.
Post by G.B.Z.B. einen Test, der einige Formen von switches
durchspielt, in verschiedenen Arrangements.
Hatte ich letztes Jahr gemacht.
Post by G.B.Da fängt schon damit an, dass in C u.U. erlaubt ist, der
untersuchten Variablen in einem Zweig der Fallunterscheidung
einen Wert zuzuweisen. C-Formalisten: Was ist dann mit
der Sprungtabelle und wie weit kann die Analyse des compilers
reichen?
Das hat aber nichts mit 'Sprungtabelle: Ja|Nein' zu tun.
Post by G.B.Für Clang spielt derzeit die Reihenfolgen der case-Liste eine
Rolle. Ich würde angesichts des eben gesagtem sogar vermuten,
dass Clang damit fallwise den Vorgaben von C folgt: Deklariert
man die Schalter-Variable const, ist die Ausgangslage jedenfalls
eine andere.
Das finde ich mehrfach abstrus.
Für gcc ist die Reihenfolge nur nicht egal, wenn durchgefallen wird.
Der Verlauf gelangt ja durch 'break;' stets hinter das Ende
des 'switch() {}'.
Daher ist die Reihenfolge egal.
Auch die Schalter-Steuervariable muß hinsichtlich der oben
angesprochenen Eigenschaften egal sein.
Hier: 'switch (jump)' muß der Integer signed char bis
unsigned long long verwertet/abgegriffen werden.
Alles andere muß egal sein.
selection-statement:
if ( expression ) statement
if ( expression ) statement else statement
switch ( expression ) statement
If a converted value matches that of the promoted controlling expression,
control jumps to the statement following the matched case label.
Ich lese im C11 nichts über unterschiedliche Behandlung, wegen
nachträglicher Veränderung des Wertes von 'switch (jump)'
oder wegen 'const' oder ...
Es ist ein beliebig großer Ausdruck, dessen Wert an einem
bestimmten Ort und Zeitpunkt festgestellt und nur zu einem Sprung
(in Quelle) verwertet werden soll. Nach dem Sprung ist alles egal.
Post by G.B.Für eine einfache Fallunterscheidung, die z.B. die Konstanten
in absteigender Folge auflistet, sehe ich sehr wohl eine
Sprungtabelle nach der Übersetzung. Varianten in anderen Fällen.
Ich hatte 24.06.2015 einen Thread "clang zeigt auch Negativa"
begonnen:
============================================================
Zwei Dinge kann ich berichten:
Die Doku zu clang ist sehr dünn.
Auch das Handbuch auf der Webseite.
Auch clang --help hilft da nicht.
Ich bin dazu übergegangen, die gcc-Doku zu lesen,
um clang-Optionen herauszufinden.
clang verwendet KEINE Sprungtabelle, falls die
case 3: case 4: case 5: .. case 66: case 67:
nicht um 1 steigend sind, sondern beispielsweise
alle(!) um 4 steigend sind.
jmpq *.LJTI4_0(,%rcx,8)
Vorstehend ein Tabellensprung - nur bei 1er-Steigung.
Vor etlichen Jahren (vielleicht 15) hat gcc schon
in Fällen von 2 4 8 etc. %rcx 1 2 3 Bit >>geshiftet, um
die Distanz zu normieren.
clang zieht es leider vor, 50 Vergleiche zu machen,
if (s==11) ...
if (s==12) ...
...
if (s==54) ...
if (s==55) ...
bis die richtige Stelle erreicht ist.
Stärkere Optimierung ändert nichts daran.
Ich hatte einen 4er-Abstand, um bei 3 Werten
evtl. Bits 1 2 3 hinzuzufügen: case HULKO|2:
Dies Konzept kann ich mir abschminken.
.........................................................
Dann ist das Optimierungsverhalten bei 'switch () { ...' enorm
wichtig!
Es gibt Compiler, die mehrere Optionen zur Verfügung stellen, um
speziell die Optimierung von 'switch ...' zu steuern.
Die Information, die ich gab, kann folglich wichtig bis sehr wichtig
für so manchen sein.
.........................................................
Ernstzunehmende C-Programmierer sollten sich auch dafür interessieren.
Eigenschaften von Compilern können auf die C-Ebene zurückschlagen
und andere Konzepte gestatten oder erzwingen.
(Beispielsweise habe ich einen anderen Wertabstand wählen müssen.)
Insofern ist dieser Zusammenhang OnTopic.
clang scheint 'switch' gar nicht zu optimieren.
Eine Sprungtabelle in jedem Fall ist meiner Meinung nach Standard.
Ich kenne clang aus zwei speziellen Gründen:
o In meinem C-Buch 3.Auflage gibt es ein großes Kapitel C11.
Das ist mit clang gemeinsam erarbeitet worden, denn der
kann C11.
o Ich arbeite seit etwa 2000 mit FreeBSD.
Dort ist seit Release 10.0 clang der Standard-Compiler,
der gcc ablöste.
Man sprach von dem großen Vorteil(?) des clang, nämlich daß der
sehr schnell kompiliert.
Ich weiß/ahne jetzt auch, warum.
Als Ersatz eines switch() kann ein Array aus Funktionspointern dienen.
Etwa [100] reichen aus für z.B. einen Parser.
Es gibt da interessante Aspekte:
Beispielsweise können Funktionen auf einigen Positionen
die Funktionspointer dynamisch austauschen.
..........................................................
Ich habe mir gcc5 installiert.
Und siehe da, er macht grundsätzlich Sprungtabellen.
Auch bei abgeschalteter Optimierung -O0 !
So muß es auch sein.
clang machte bei 8 switches null Sprungtabellen.
Auch bei -O2 nicht.
Er zog gigantische cmp-jx-jmp-Gefrickel vor.
Eine einzige Tabelle machte clang, nachdem ich einen
durchgehenden case-Wertabstand von 1 herstellte.
Ein durchgehender Wertabstand von 4 genügte ihm nicht.
gcc macht da einfach sw>>=2; vor dem *jump.
Ich bewerte dieses Verhalten von clang quasi als Bug.
..........................................................
Ich habe jetzt Geschwindigkeitsmessungen gemacht.
Beispiel:
3.460u 0.000s 0:03.47 99.7% 759+469k 0+0io 0pf+0w
Loop 10000000
Sehr interessant!:
gcc5 4.98 3.70 3.54 3.4 bei -O0 -O1 -O2 -O3
clang 6.85 3.45 3.76 3.7 bei -O0 -O1 -O2 -O3
clang ist also in der Summe besser, bei -O1,
meiner Standard-Opt seit Jahrzehnten.
Aber nur, wenn man bei switch() die Konzepte so
wählt, daß die case-Werte je um 1 steigen!
7.024u 0.000s 0:07.03 99.8% 757+467k 0+0io 0pf+0w
Das Tempo halbiert sich, wenn das nicht getan wird!
(Ich habe hier alle case-Werte um 4 steigen lassen.)
Ich hatte also absolut Recht mit meiner Meckerei.
Sprungtabellen wegzulassen ergibt ganz miserable
Programm-Performance!
..........................................................
Es geht weiter:
C-Quelle:
memset(&o, 0, sizeof(o)); //size=32
gcc5:
movq $0, 136(%rsp)
movq $0, 128(%rsp)
movq $0, 144(%rsp)
movq $0, 152(%rsp)
clang:
xorl %eax, %eax
movq %rax, -869392(%rbp)
movq %rax, -869352(%rbp)
movl $0, %eax
movq %rax, -869408(%rbp)
movl $0, %eax
movq %rax, -869368(%rbp)
movl $0, %eax
movq %rax, -869512(%rbp)
movl $0, %eax
movq %rax, -869568(%rbp)
movl $0, %eax
movq %rax, -869432(%rbp)
movl $0, %edx
movl $0, %eax
movq %rax, -869448(%rbp)
movl $0, %eax
movq %rax, -869552(%rbp)
movl $0, %eax
movq %rax, -869400(%rbp)
movl $0, %eax
movq %rax, -869560(%rbp)
movl $0, %eax
movq %rax, -869416(%rbp)
movl $0, %eax
movq %rax, -869480(%rbp)
Es geht mir um die unsinnigen Wiederholungen von 'mov 0,eax'.
gcc macht das nicht, hat das noch nie getan.
Warum nimmt er nicht xor edx,edx ?
Zu Beginn macht er es doch optimal.
Die Konstanten brauchen viel Platz und dauern oft länger.
Ein Compiler von Fujitsu hatte das Jahrzehnte lang getan.
Fujitsu war stolz, eine entsprechende Optimierung zu berichten.
==============================================================
--
Mit freundlichen Grüßen
Helmut Schellong ***@schellong.biz
www.schellong.de www.schellong.com www.schellong.biz
http://www.schellong.de/c.htm