Moderne CPU Innere Schleife Indirection Optimizations

Question

Von http://www.boost.org/community/implementation_variations.html

“... Codierung Unterschiede wie eine Klasse von virtuellen zu nicht-virtuellen Mitglieder zu ändern oder eine Dereferenzierungsebene Entfernen wahrscheinlich keine messbaren Unterschied, es sei denn tief in ein machen innere Schleife. Und sogar in einer inneren Schleife, moderne CPUs führen oft solche konkurrierenden Code-Sequenzen in der gleichen Anzahl von Taktzyklen! "

Ich versuche, den "sogar in der inneren Schleife" Teil zu verstehen. Welche Mechanismen implementieren CPUs speziell, um die beiden Codes (virtuell oder nicht-virtuell oder eine zusätzliche Dereferenzierungsebene) innerhalb der gleichen Anzahl von Taktzyklen auszuführen? Ich kenne das Pipelining und Caching von Anweisungen, aber wie ist es möglich, einen virtuellen Anruf innerhalb der gleichen Anzahl von Taktzyklen wie ein nicht virtueller Anruf auszuführen? Wie ist die Indirektion "verloren"?

Answer 1

Caching (zB branch target caching), parallel Ladeeinheiten (Teil von Pipelining, aber auch Dinge wie "Hit unter miss", die die Pipeline nicht abgewürgt) und out-of-order execution wahrscheinlich ein load verwandeln helfen - load - branch in etwas, das näher an einem festen branch ist. Befehlsfaltung/Eliminierung (was der richtige Ausdruck dafür ist) in der Dekodierungs- oder Verzweigungsvorhersage-Stufe der Pipeline kann ebenfalls beitragen.

All dies hängt jedoch von vielen verschiedenen Dingen ab: Wie viele verschiedene Verzweigungsziele gibt es (z. B. wie viele verschiedene virtuelle Überladungen Sie wahrscheinlich auslösen), wie viele Dinge Sie durchlaufen (ist der Verzweigungszielcache) "warm" - wie wäre es mit dem icache/dcache?), wie die virtuellen Tabellen oder Indirektionstabellen im Speicher abgelegt werden (sind sie cache-freundlich, oder lädt jede neue vtable möglicherweise eine alte vtable?), ist der Cache wiederholt aufgrund von Multicore-Ping-Ponging, usw.

(Disclaimer: Ich bin definitiv kein Experte hier, und ein großer Teil meines Wissens kommt aus dem Studium In-Order-Embedded-Prozessoren, so etwas davon ist Extrapolation Wenn Sie Korrekturen haben, zögern Sie nicht zu kommentieren!)

Der richtige Weg, um zu bestimmen, ob es ein Problem für ein bestimmtes Programm sein wird, ist natürlich das Profil. Sie können dies mit Hilfe von Hardware-Zählern tun - sie können Ihnen viel über die Vorgänge in den verschiedenen Phasen der Pipeline erzählen.

---

Edit:

Als Hans Passant Modern CPU Inner Loop Indirection Optimizations in einem über Kommentar weist darauf hin, ist der Schlüssel, diese beiden Dinge zu bekommen, die gleiche Menge an Zeit in Anspruch nehmen ist die Fähigkeit, effektiv zu mehr als einen Befehl „Ruhestand“ pro Zyklus. Instruction Elimination kann dabei helfen, aber superscalar design ist wahrscheinlich wichtiger (Hit unter Miss ist ein sehr kleines und spezifisches Beispiel, voll redundante Ladeeinheiten könnten eine bessere sein).

Lassen Sie uns eine ideale Situation nehmen, und einen direkten Zweig nehmen ist nur eine Anweisung:

branch dest 

... und eine indirekte Verzweigung drei (vielleicht haben Sie es in zwei bekommen können, aber es ist mehr als ein):

load vtable from this 
load dest from vtable 
branch dest 

Lassen Sie uns eine absolut perfekte Situation annehmen: * diese und die gesamte vTable in L1-Cache sind, L1-Cache-Unterstützung schnell genug ist für die beiden Lasten einen Zyklus pro Befehl Kosten amortisiert. (Sie können sogar davon ausgehen, dass der Prozessor die Lasten neu geordnet und mit früheren Anweisungen gemischt hat, um ihnen Zeit für die Fertigstellung vor der Verzweigung zu geben; für dieses Beispiel spielt das keine Rolle.) Außerdem ist der Verzweigungszielcache heiß und es gibt keine Pipeline Spülen Kosten für die Branche, und der Zweig Anweisung kommt auf einen einzigen Zyklus (amortisiert).

Die theoretische minimale Zeit für das erste Beispiel ist daher 1 Zyklus (amortisiert).

Das theoretische Minimum für das zweite Beispiel, fehlende Instruktionsbeseitigung oder redundante Funktionseinheiten oder etwas, das mehr als eine Instruktion pro Zyklus in den Ruhestand versetzen kann, ist 3 Zyklen (es gibt 3 Anweisungen)!

Die indirekte Last wird immer langsamer sein, weil es mehr Anweisungen gibt, bis Sie in etwas wie superskalares Design kommen, das mehr als eine Instruktion pro Zyklus zurückgehen lässt.

Sobald Sie dies haben, wird das Minimum für beide Beispiele etwas zwischen 0 und 1 Zyklen, wieder vorausgesetzt, alles andere ist ideal. Wahrscheinlich müssen Sie für das zweite Beispiel mehr ideale Umstände haben, um dieses theoretische Minimum tatsächlich zu erreichen, als für das erste Beispiel, aber jetzt ist es möglich.

In einigen der Fälle, die Sie interessieren würden, werden Sie wahrscheinlich dieses Minimum für beide Beispiele nicht erreichen. Entweder ist der Verzweigungszielcache kalt oder die Vtable befindet sich nicht im Datencache, oder die Maschine kann die Anweisungen nicht neu anordnen, um die redundanten Funktionseinheiten voll auszunutzen.

... hier kommt Profiling ins Spiel, was ohnehin eine gute Idee ist.

Sie kann nur eine kleine Paranoia über virtuals in erster Linie. Siehe Noel Llopis's article on data oriented design, die ausgezeichneten Pitfalls of Object-Oriented Programming slides und Mike Acton's grumpy-yet-educational presentations. Jetzt haben Sie sich plötzlich in Muster bewegt, mit denen die CPU wahrscheinlich schon zufrieden ist, wenn Sie viele Daten verarbeiten.

Hochsprachenfunktionen wie virtuell sind normalerweise ein Kompromiss zwischen Ausdruckskraft und Kontrolle. Ich denke ehrlich gesagt, wenn Sie sich nur mehr darüber bewusst machen, was virtual eigentlich ist (haben Sie keine Angst, von Zeit zu Zeit die Disassembly-Ansicht zu lesen, und sehen Sie sich definitiv die Architektur-Handbücher Ihrer CPU an), neigen Sie dazu, sie zu benutzen wenn es sinnvoll ist und nicht wenn nicht und ein Profiler kann den Rest bei Bedarf abdecken.

One-Size-Fits-All-Aussagen über "nicht virtuell verwenden" oder "virtuelle Verwendung ist unwahrscheinlich, einen messbaren Unterschied machen" machen mich mürrisch. Die Realität ist in der Regel komplizierter, und entweder wirst du in einer Situation sein, in der du dich so sehr profilierst oder meidest, oder du bist in den anderen 95%, wo es wahrscheinlich keinen Sinn macht außer für den möglichen Lerninhalt.

Answer 2

Pipelining ist der Hauptweg.

Es kann 20 Taktzyklen dauern, um eine Anweisung zu laden, sie zu dekodieren, ihre Aktionen auszuführen und indirekte Speicherreferenzen zu laden. Aber aufgrund der Pipeline kann der Prozessor Teile von 19 anderen Befehlen gleichzeitig in verschiedenen Stufen der Pipeline ausführen, was einen Gesamtdurchsatz von 1 Befehl pro Taktzyklus ergibt, unabhängig davon, wie lange tatsächlich benötigt wird, um diesen Befehl durch die Pipeline zu speisen.

Answer 3

Was passiert, ich denke, dass der Prozessor einen speziellen Cache hat, der die Standorte und Ziele von Zweigen und indirekten Sprüngen enthält. Wenn ein indirekter Sprung bei $ 12345678 auftritt und das letzte Mal, dass es angetroffen wurde, ging es an $ 12348765, kann der Prozessor die spekulative Ausführung der Anweisungen an der Adresse $ 12348765 beginnen, noch bevor er die Adresse der Verzweigung auflöst. In vielen Fällen wird innerhalb der inneren Schleife einer Funktion ein bestimmter indirekter Sprung während der gesamten Dauer der Schleife immer zur selben Adresse springen. Der indirekte Sprung-Cache kann somit Verzweigungsstrafen vermeiden.

Answer 4

Wenn die CPU bereits die Speicheradresse im Cache hat, ist die Ausführung einer Ladeanweisung trivial, wenn das der Fall ist.

Answer 5

Moderne CPUs verwenden eine adaptive Verzweigungsprognosetechnik, die viele indirekte Sprünge vorhersagen kann, wie Sie sie mit einer vtable-Implementierung von virtuellen Funktionen erhalten. Siehe http://en.wikipedia.org/wiki/Branch_prediction#Prediction_of_indirect_jumps