Moderne CPU Innere Schleife Indirection Optimizations

Question

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

“... Codierung Unterschiede wie eine Klasse von virtuellen zu nicht-virtuellen Mitgliedern zu ändern oder eine Dereferenzierungsebene Entfernen wahrscheinlich keinen messbaren Unterschied, es wäre denn tief in einer inneren Schleife zu machen. Und auch in einer inneren Schleife, moderner CPUs oft ausführt solche konkurrierenden Codesequenzen in der gleichen Anzahl von Taktzyklen! "

Ich versuche, den „auch in der inneren Schleife“ Teil zu verstehen. Insbesondere, welche Mechanismen implementieren CPUs die beiden Codes (virtuelle vs nicht-virtuellen oder eine zusätzliche Dereferenzierungsebene) innerhalb der gleichen Anzahl von Taktzyklen ausführen? Ich weiß, über Anweisung Pipelining und Caching, aber wie ist es möglich, einen virtuellen Aufruf innerhalb der gleichen Anzahl von Taktzyklen als nicht-virtuellen Aufruf durchführen? Wie ist das indirection "verloren"?

Answer 1

Caching (zB Verzweigungs-Ziel-caching ), parallel Ladeeinheiten (Teil Pipelining, aber auch Dinge wie "Hit unter miss", die die Pipeline) nicht abgewürgt, und out-of-Order-Ausführung wahrscheinlich Hilfe ist einen load-load-branch in etwas zu verwandeln, das näher an einem festen branch ist. Instruction Falten / Elimination (was ist der richtige Ausdruck dafür?) In der Dekodierung oder Verzweigungsvorhersage Stufe der Pipeline kann auch beitragen.

All dies stützt sich auf eine Menge verschiedener Dinge, aber: wie viele verschiedene Verzweigungsziele gibt es (zum Beispiel, wie viele verschiedene virtuelle Überlastungen werden Sie wahrscheinlich Trigger), wie viele Dinge, die Sie Schleife über (das Sprungziel-Cache " warm "? wie etwa die icache / dcache?), wie die virtuellen Tabellen oder Indirekt Tabellen im Speicher gelegt aus (sie sind Cache-freundlich, oder jede neue vTable Last möglicherweise ein alte vTable evicting?), wird der Cache für ungültig erklärt wird wiederholt wegen Multi-Core-Ping-Pong, etc ...

(Disclaimer: Ich bin definitiv kein Experte hier, und eine Menge meines Wissens kommt in Ordnung Embedded-Prozessoren aus dem Studium, so dass einige dieser Extrapolation Wenn Sie Korrekturen, fühlen Sie sich frei zu äußern.!)

Der richtige Weg, um zu bestimmen, ob es wird ein Problem für ein bestimmtes Programm sein, ist natürlich zu profilieren. Wenn Sie können, tun dies mit Hilfe von Hardwarezähler -. Sie kann Ihnen sagen, viel über das, was auf die in den verschiedenen Stufen der Pipeline geht

---

Edit:

Wie Hans Passant weist in einem oben Kommentar aus indirection Optimizations , ist der Schlüssel, diese beiden Dinge zu bekommen, die gleiche Menge an Zeit in Anspruch nehmen ist die Fähigkeit, effektiv zu „Ruhestand“ mehr als ein Befehl pro Zyklus. Instruction Eliminierung kann dabei helfen, aber superskalaren entwerfen ist wahrscheinlich wichtiger (Hit unter verpassen ist ein sehr kleines und spezielles Beispiel, vollständig redundante Ladeeinheiten könnten eine bessere) sein.

Lassen Sie sich eine ideale Situation nehmen und nimmt ein direkter Zweig ist nur eine Anweisung:

branch dest

... und eine indirekte Verzweigung drei (vielleicht haben Sie es in zwei bekommen können, aber es ist größer als eins):

load vtable from this
load dest from vtable
branch dest

Lassen Sie uns eine absolut perfekte Situation annehmen: * Diese und die gesamte V-Tabelle sind in L1-Cache, L1-Cache schnell genug ist, um Unterstützung eines Zyklus pro Befehl Kosten für die zwei Lasten abgeschrieben. (Sie können sogar der Prozessor übernehmen die Lasten neu geordnet und vermischte sie mit früheren Anweisungen Zeit für die sie vor der Verzweigung zu vervollständigen, es spielt keine Rolle für dieses Beispiel.) Übernehmen auch die Sprungziel-Cache heiß ist, und es gibt keine Pipeline flush Kosten für die Branche, und der Verzweigungsbefehl kommt zu einem einzigen Zyklus (abgeschrieben).

Der theoretisches Minimum Zeit für das erste Beispiel ist daher 1 Zyklus (abgeschrieben).

Das theoretische Minimum für das zweite Beispiel, fehlt Anweisung Eliminierung oder redundante Funktionseinheiten oder etwas, das mehr als ein Befehl pro Zyklus erlaubt den Ruhestand, 3 Zyklen (es gibt 3 Anleitung)!

Die indirekte Belastung wird immer langsamer, weil es mehr Anweisungen sind, bis Sie in so etwas wie superskalaren Design erreichen, die mehr als einen Befehl pro Zyklus erlaubt den Ruhestand geht.

Wenn Sie diese haben, das Minimum für beiden Beispiele wird etwas zwischen 0 und 1 Zyklen wieder, sonst vorausgesetzt, dass alles ideal. Wohl müssen Sie mehr idealen Bedingungen für die seco habennd Beispiel tatsächlich zu erreichen, dass die theoretische Minimum als für das erste Beispiel, aber es ist jetzt möglich.

In einigen Fällen Sie interessieren würde, sind Sie wahrscheinlich nicht für beide Beispiel jenes Minimum zu erreichen. Entweder ist die Sprungziel-Cache kalt wird, oder die V-Tabelle wird nicht in den Daten-Cache sein, oder die Maschine nicht in der Lage sein, die Anweisungen des Neuordnungs alle Vorteile der redundanten Funktionseinheiten zu nehmen.

... das ist, wo Profilierung kommt, die in der Regel ohnehin eine gute Idee ist.

Sie können vermählen nur eine leichte Paranoia über virtuals an erster Stelle. Siehe Noel Llopis Artikel über Daten orientiertes Design , den ausgezeichneten Pitfalls von objektorientierter Programmierung Dias und Mike Acton grumpy-nicht-pädagogische Präsentationen . Jetzt haben Sie plötzlich bewegt in Muster, dass die CPU bereits wahrscheinlich glücklich zu sein ist, wenn Sie eine Menge von Daten sind zu verarbeiten.

High-Level-Sprache-Funktionen wie virtuelle sind in der Regel ein Kompromiss zwischen Ausdruckskraft und Kontrolle. Ich denke ehrlich, aber nur um Ihr Bewusstsein zu erhöhen, was virtuelle tatsächlich tut (keine Angst, die Demontage Ansicht von Zeit zu Zeit zu lesen, und auf jeden Fall Blick auf Ihrem CPU-Architektur Handbücher), werden Sie neigen dazu, es zu benutzen wenn es Sinn macht, und nicht, wenn es nicht der Fall, und ein Profiler können den Rest decken, wenn nötig.

One-size-fits-alle Aussagen über „nicht verwendet virtuell“ oder „virtuelle Anwendung ist unwahrscheinlich, einen messbaren Unterschied machen“ macht mich mürrisch. Die Realität ist in der Regel komplizierter und entweder Sie gehen in einer Situation, wo Sie sich genug interessieren, sie zu profilieren oder zu vermeiden, oder du bist in dem anderen 95%, wo es wahrscheinlich nicht wert fürsorglich mit Ausnahme der möglichen Ausbildungsinhalte.

Answer 2

Pipelining ist der wichtigste Weg.

Es könnte 20 Taktzyklen dauern eine Anweisung zu laden, zu dekodieren, führen sie die Aktionen und laden indirekte Speicherreferenzen. Aber aufgrund der pipleline kann der Prozessor in verschiedenen Stufen der Pipeline zur gleichen Zeit Teile 19 andere Befehle ausgeführt sein, die einen Gesamtdurchsatz von 1 Anweisung gibt in jedem Taktzyklus unabhängig davon, wie lange tatsächlich dauert es, daß der Befehl durch die Pipeline einzuspeisen.

Answer 3

Was passiert, denke ich, ist, dass der Prozessor einen speziellen Cache aufweist, die die Positionen und Ziele der Filialen und indirekte Sprünge hält. Wenn ein indirekter Sprung bei $ 12345678 angetroffen wird, und das letzte Mal begegnet war es ging $ 12348765 zu adressieren, kann der Prozessor spekulative Ausführung der Befehle an der Adresse beginnt 12348765 $, noch bevor es die Adresse der Niederlassung aufgelöst wird. In vielen Fällen innerhalb der inneren Schleife einer Funktion, eine bestimmte indirekte Sprung springt immer an die gleiche Adresse während der gesamten Dauer der Schleife. Die indirekte Sprung-Cache kann somit vermeiden Strafen Verzweigung.

Answer 4

Moderne CPUs verwenden, um eine adaptive Verzweigungsvorhersagetechnik, die so viele indirekte Sprünge vorhersagen können, wie Sie mit einer V-Tabelle Implementierung virtueller Funktionen erhalten. Siehe http://en.wikipedia.org/wiki/Branch_prediction#Prediction_of_indirect_jumps

Answer 5

Wenn die CPU bereits die Speicheradresse im Cache haben, dann einen Ladebefehl ausgeführt wird trivial, wenn überhaupt.