Geschwindigkeitsunterschied zwischen If-Else und Ternary-Operator in C ...?

8

Also habe ich auf Anregung eines Kollegen gerade den Geschwindigkeitsunterschied zwischen dem ternären Operator und dem äquivalenten If-Else-Block getestet ... und es scheint, dass der ternäre Operator einen Code liefert, der zwischen 1x und 2x schneller ist als If- Sonst. Mein Code ist:

%Vor%

(Sorry für gettimeofday und nicht clock_gettime ... Ich werde mich bemühen, mich zu verbessern.)

Ich habe versucht, die Reihenfolge zu ändern, in der ich die Blöcke getaktet habe, aber die Ergebnisse scheinen zu bestehen. Was gibt? Auch zeigt das If-Else eine viel größere Variabilität in Bezug auf die Ausführungsgeschwindigkeit. Sollte ich die Assembly untersuchen, die gcc generiert?

Das ist übrigens alles auf Optimierungsstufe Null (-O0).

Stellen wir mir das vor, oder gibt es etwas, das ich nicht in Betracht ziehe, oder ist das eine maschinenabhängige Sache oder was? Jede Hilfe wird geschätzt.

    
Patrick87 19.07.2011, 21:33
quelle

6 Antworten

21

Es besteht eine gute Chance, dass der ternäre Operator in ein cmov kompiliert wird, während das if / else zu einem cmp + jmp führt. Schauen Sie sich einfach die Baugruppe an (mit -S), um sicher zu gehen. Wenn Optimierungen aktiviert sind, spielt dies sowieso keine Rolle mehr, da jeder gute Compiler in beiden Fällen denselben Code erzeugen sollte.

    
Anteru 19.07.2011, 21:38
quelle
8

Dies ist eine schöne Erklärung: Ссылка

Grundsätzlich gibt es "Bedingungssatz" -Prozessoranweisungen, die schneller sind als das Verzweigen und Festlegen in separaten Anweisungen.

    
trutheality 19.07.2011 21:39
quelle
7

Sie könnten auch komplett zweiglos gehen und messen, wenn es einen Unterschied macht:

%Vor%

Auf den heutigen Architekturen ist diese Art der Programmierung ein bisschen aus der Mode gekommen.

    
fredoverflow 20.07.2011 08:59
quelle
2

Wenn es welche gibt, ändern Sie Ihren Compiler!

Für diese Art von Fragen verwende ich die Seite zum Ausprobieren von LLVM . Es ist eine alte Version von LLVM (immer noch mit dem gcc-Frontend), aber das sind alte Tricks.

Hier ist mein kleines Beispielprogramm (vereinfachte Version von Ihnen):

%Vor%

Und es wird das entsprechende LLVM IR erzeugt:

%Vor%

Okay, also ist es wahrscheinlich chinesisch, obwohl ich einige Variable umbenannt habe, um sie leichter lesbar zu machen.

Die wichtigen Bits sind diese zwei Blöcke:

%Vor%

Dies setzt a und d .

Und die Schlussfolgerung lautet: Kein Unterschied

Hinweis: In einem einfacheren Beispiel wurden die beiden Variablen tatsächlich zusammengeführt. Anscheinend hat der Optimierer die Ähnlichkeit nicht erkannt ...

    
Matthieu M. 20.07.2011 06:49
quelle
0

Jeder vernünftige Compiler sollte den gleichen Code für diese generieren, wenn die Optimierung aktiviert ist.

    
Karoly Horvath 19.07.2011 21:38
quelle
0

Verstehen Sie, dass es völlig Sache des Compilers ist, wie er den ternären Ausdruck interpretiert (es sei denn, Sie erzwingen ihn tatsächlich nicht mit (inline) asm). Es könnte genauso gut einen ternären Ausdruck wie "if..else" in seiner internen Repräsentationssprache verstehen, und abhängig vom Ziel-Backend kann er einen bedingten Bewegungsbefehl erzeugen (auf x86 ist CMOVcc ein solcher. Es sollten auch Einsen sein für min / max, abs, etc.). Die Hauptmotivation des Verwendens einer bedingten Bewegung besteht darin, das Risiko einer Verzweigungsfehlvorhersage auf eine Speicher- / Registerverschiebungsoperation zu übertragen. Der Nachteil dieser Anweisung ist, dass das Operandenregister, das bedingt geladen wird, fast immer ausgewertet werden muss, um den Befehl cmov zu nutzen.

Dies bedeutet, dass der unbedingte Auswertungsprozess jetzt unbedingt sein muss, und dies wird die Länge des unbedingten Pfades des Programms erhöhen. Aber verstehen Sie, dass Verzweigungsfehlbeweise meistens als "Flushing" der Pipeline gelöst werden, was bedeutet, dass die Anweisungen, die die Ausführung beendet hätten, ignoriert werden (zu No Operation-Anweisungen). Dies bedeutet, dass die tatsächliche Anzahl der ausgeführten Befehle wegen der Blockierungen oder NOPs höher ist und der Effekt mit der Tiefe der Prozessor-Pipeline und der Fehlvorhersagequote skaliert.

Dies bringt ein interessantes Dilemma bei der Bestimmung der richtigen Heuristik mit sich. Erstens wissen wir sicher, dass, wenn die Pipeline zu flach ist oder die Verzweigungsvorhersage vollständig in der Lage ist, Muster aus der Verzweigungshistorie zu lernen, cmov sich nicht lohnt. Es lohnt sich auch nicht, wenn die Kosten für die Bewertung von bedingten Argumenten höher sind als die Kosten für Fehleinschätzungen im Durchschnitt.

Dies sind vielleicht die Hauptgründe, warum Compiler Schwierigkeiten beim Ausnutzen von cmov-Befehlen haben, da die Heuristikbestimmung weitgehend von den Laufzeitprofilinformationen abhängt. Es ist sinnvoller, dies auf dem JIT-Compiler zu verwenden, da es Feedback zur Laufzeit-Instrumentierung bereitstellen und eine stärkere Heuristik für die Verwendung dieser Komponente erstellen kann ("Ist die Verzweigung wirklich unvorhersehbar?"). Auf der Seite des statischen Compilers ohne Trainingsdaten oder Profiler ist es am schwierigsten anzunehmen, wann dies nützlich ist. Eine einfache negative Heuristik ist jedoch, wie bereits erwähnt, wenn der Compiler weiß, dass das Dataset vollständig zufällig ist oder cond. uncond. Bewertung ist teuer (vielleicht aufgrund von irreduziblen, kostspieligen Operationen wie fp dividiert), wäre es gute Heuristiken, dies nicht zu tun.

Jeder Compiler, der es wert ist, wird all dies tun. Die Frage ist, was wird es tun, nachdem alle zuverlässigen Heuristiken aufgebraucht sind ...

    
kchoi 03.07.2015 04:46
quelle