[VisualC++ x64] double-Konstante schnell in Register kriegen

[Krishty]

Hi,

Ich überlege gerade, wie ich eine Konstante (etwa 3.1415926535897931 oder ihre binäre Repräsentation 0x400921FB54442D18) möglichst schnell in eine Berechnung einbringe, und brauche eure Empfehlung für meine Alternativen:

1. Standardmäßig speichert Visual C++ jede x64-Gleitkommakonstante im Datensegment und lädt sie vor ihrer Verwendung:
    
   movsd xmm0,mmword ptr [__real@400921FB54442D18]
    
   • Ist der Teil des Datensegments, in dem die Konstante liegt, außerhalb aller Caches, dauert die Bereitstellung rund 400 Takte. Wie viel von dieser Wartezeit kriegt die CPU in der Praxis versteckt?
   • Intel warnt: MOVSD aktualisiert nur die niederwertigsten 64 Bits des Registers; das bedeutet, dass Register Renaming (und damit die Parallelisierung) erschwert werden.
    
2. Integer-Konstanten können im Maschinentext hardcodet und über den Stapelspeicher geladen werden; beide sind quasi garantiert schon im Cache:
    
   __declspec(align(16)) auto const binaryValue = 0x400921FB54442D18ull;
   ::_mm_cvtsd_f64(::_mm_load_sd((double const *)&binaryValue));
    
   Resultat:
    
   mov     rbx,400921FB54442D18h
   mov     qword ptr [rsp+110h],rbx
   movsd   xmm0,mmword ptr [rsp+110h]
    
   • Die letzten beiden mov(sd)s werden vor jeder weiteren Verwendung der Variable wiederholt; dass sich der Wert nicht ändert, verpasst Visual C++.
   • Das movsd-Problem besteht weiter; aber so lange alles im Cache ist, sollte der Bedarf an Takten höchstens zweistellig sein.
    
    
3. Der Stapelspeicher kann auch umgangen werden:
    
   __declspec(align(16)) auto const binaryValue = 0x400921FB54442D18ull;
   ::_mm_cvtsd_f64(::_mm_set_sd((double const &)binaryValue));
    
   Resultat:
    
   mov     rbx,400921FB54442D18h
   movsd   xmm3,mmword ptr [__real@43f0000000000000]
   cvtsi2sd xmm1,rbx
   test    rbx,rbx
   jns     +7h
   addsd   xmm1,xmm3
   xorpd   xmm0,xmm0
   movsd   xmm0,xmm1
    
   • Hier bleibt xmm0 auch über mehrere Verwendungen der Variable hinweg unangetastet; dafür …
   • … verstehe ich nicht ansatzweise, was hier passiert: Sieht fast so aus, als konvertierte er die Integer-Konstante zur Gleitkommazahl, prüfe sie auf >0 (jump if not signed) und rechnete dann noch damit herum … lieber Gott der Latenz und Parallelisierung, was tust du mir an?!
   • movsd ist stark entschärft, weil das Register hier vor der Verwendung genullt wird.

Vorschläge, Erklärungen, …?!

Gruß, Ky

[eXile]

Du nimmst MASM und schreibst dir deinen x64-Assemblercode selbst.

[Krishty]

Und welchen der drei Ansätze würde ich in diesem Fall für meinen handgeschriebenen Text wählen sollen?

[Jörg]

2) - hilft es, eine lokale temporare Variable zu verwenden, nachdem Du ueber den Reinterpret-Cast geladen hast?

[Krishty]

Wie meinen? Eine unbenannte Temporäre?
(Das Stück Quelltext stammt aus einer Funktion, die pi zurückgibt, falls das irgendwelche Missverständnisse ausräumt.)

[eXile]

Ich wollte deinen Beispielcode gerade mal testen; leider ist die SSE-Codegenerierung von Visual C++ anscheinend so volatil, dass selbst kleinste Änderungen an anderen Stellen den optimierten Code massiv verändern. Kurzum: Der bei mir generierte Code sieht anders aus als in den Punkten (1) bis (3). Oder ich habe einfach zu wenige Variablen auf volatile gestellt.

Darum ohne Testen und ins Blaue: Bringen _mm_set1_pd oder _mm_load1_pd etwas? Ich würde übrigens wohl mit (2) gehen. Zumindest wird das so bei vektoriellen Konstanten gemacht. Aber nimm' mich nicht zu ernst; das hier ist von Computergraphik zu weit entfernt, als dass ich davon tiefgreifend Ahnung hätte.

[Lynxeye]

Profile, don't guess!

Bist du dir sicher, dass die Variante, welche den Wert aus dem Datensegment lädt überhaupt einen Cache-Miss erzeugt? Die Anweisung für das Laden eines Datums mit feststehender Adresse ist der einfachst mögliche Fall für den Prefetcher deines Prozessors. Ich würde also fast darauf wetten, dass der Wert immer schon im Datencache bereit steht.

[Jörg]

Lokale Variable statt wiederholtem Funktionsaufruf: Manchmal scheitert die Common Subexpression Elimination , so dass man es selber machen muss, Gruende koennen vielfaeltig (und oft plausibel) sein. Ist auf jeden Fall einen Versuch wert, wenn Du PI mehr als einmal in einer Funktion benoetigst.

[Krishty]

Ich wollte deinen Beispielcode gerade mal testen; leider ist die SSE-Codegenerierung von Visual C++ anscheinend so volatil, dass selbst kleinste Änderungen an anderen Stellen den optimierten Code massiv verändern.

Wow, das überrascht mich jetzt. Hast du wirklich die x64-Version getestet? Bei mir ist die Code Generation vollkommen stabil; der Compiler lässt sich weder von const vs non-const, noch von pass by value vs. pass by reference, nicht einmal von lokaler Variable statt Rvalue beirren und erzeugt in jeder Variation absolut identischen Maschinentext.

Darum ohne Testen und ins Blaue: Bringen _mm_set1_pd oder _mm_load1_pd etwas? Ich würde übrigens wohl mit (2) gehen. Zumindest wird das so bei vektoriellen Konstanten gemacht.

Werde ich mal ausprobieren.

Profile, don't guess!

Würde ich gern tun; allerdings grüble ich immernoch, wie ich ein zum Umschiffen des Caches genügend großes Datensegment anlege bzw. eine gleichwertige Funktion, die ja mehrere MiB groß sein müsste.

Bist du dir sicher, dass die Variante, welche den Wert aus dem Datensegment lädt überhaupt einen Cache-Miss erzeugt? Die Anweisung für das Laden eines Datums mit feststehender Adresse ist der einfachst mögliche Fall für den Prefetcher deines Prozessors. Ich würde also fast darauf wetten, dass der Wert immer schon im Datencache bereit steht.

Ja; ich auch. Aber für diese Cache Line muss eben eine andere rausfliegen. Bei direktem Schreiben in den Maschinentext steigt zwar dessen Größe, weshalb weniger davon in den Cache passt, dafür beeinflusst er aber nicht den Daten-Cache und lässt sich ebenso einfach prefetchen. (So weit meine Mutmaßung.)

Lokale Variable statt wiederholtem Funktionsaufruf: Manchmal scheitert die Common Subexpression Elimination , so dass man es selber machen muss, Gruende koennen vielfaeltig (und oft plausibel) sein. Ist auf jeden Fall einen Versuch wert, wenn Du PI mehr als einmal in einer Funktion benoetigst.

Das ist die wiederholte Verwendung, die ich erwähnt habe: Version 1 & 3 verhalten sich wie eine lokale Variable; da ist also dadurch nichts zu holen. Bei Version 2 wird die Integer-Konstante zwischen mehreren Aufrufen im Register gehalten, aber die beiden movs auf den Stapel und ins xmm-Register wiederholt.

[Lynxeye]

Bist du dir sicher, dass die Variante, welche den Wert aus dem Datensegment lädt überhaupt einen Cache-Miss erzeugt? Die Anweisung für das Laden eines Datums mit feststehender Adresse ist der einfachst mögliche Fall für den Prefetcher deines Prozessors. Ich würde also fast darauf wetten, dass der Wert immer schon im Datencache bereit steht.

Ja; ich auch. Aber für diese Cache Line muss eben eine andere rausfliegen. Bei direktem Schreiben in den Maschinentext steigt zwar dessen Größe, weshalb weniger davon in den Cache passt, dafür beeinflusst er aber nicht den Daten-Cache und lässt sich ebenso einfach prefetchen. (So weit meine Mutmaßung.).

Soweit du vom L1 Cache sprichst, gehe ich da noch mit, denn hypermoderne Architekturen wie AMDs Fam15h haben einen kleineren Daten-L1 als Instruktions-L1, somit ist größerer Machinentext größeren Daten vorzuziehen. Bei einem Core i7 dürfte das nichts ausmachen, da dieser genau gleich große L1 Caches hat.

Dein L2 ist allerdings in jedem Fall ein einheitlicher Cache für Daten und Instruktionen. Es ist also egal, ob du Instruktionen oder Daten prefetchst, die kegeln auf jedem Fall im L2. Der Core i7 prefetcht sowieso nur in den L2 Cache, dass heißt einen L1 Cache-Miss hast du in jedem Fall.

Und nun solltest du dir kurz überlegen: wie viele L2 Cachelines kegelt deine erste Variante mit einer Instruktion mit Adressangabe + einem Datum aus dem Datensegment und wie viele L2 Cachelines benötigt deine zweite Variante mit einer Instruktion mit Immediate + zwei weiteren Instruktionen. Lohnt sich diese Mikrooptimierung wirklich? (Wenn du dafür dann auch noch Plattformabhängigen und evtl. später schwerer zu wartenden Code schreiben musst?)

[Krishty]

Und nun solltest du dir kurz überlegen: wie viele L2 Cachelines kegelt deine erste Variante mit einer Instruktion mit Adressangabe + einem Datum aus dem Datensegment und wie viele L2 Cachelines benötigt deine zweite Variante mit einer Instruktion mit Immediate + zwei weiteren Instruktionen.

Die 1. Variante schlägt mit neun Bytes für die Anweisung und 64 B (?) für die Zeile mit der Konstanten zu Buche; die 2. mit 27 B für die drei Anweisungen und Konstante zusammen.

F2 44 0F 10 05 A7 58 02 00    movsd  xmm8,                  mmword ptr [__real@400921fb54442d18]

48 BB 18 2D 44 54 FB 21 09 40 mov    rbx,                   400921FB54442D18h
48 89 9C 24 10 01 00 00       mov    qword ptr [rsp+110h],  rbx
F2 0F 10 B4 24 10 01 00 00    movsd  xmm6,                  mmword ptr [rsp+110h]

Aus Cache-Größen-Sicht ist das deutlich (63 %) günstiger, oder? Die Frage ist, ob eine L1-Verfehlung mehr oder weniger frisst als die beiden movs.

[Lynxeye]

Und nun solltest du dir kurz überlegen: wie viele L2 Cachelines kegelt deine erste Variante mit einer Instruktion mit Adressangabe + einem Datum aus dem Datensegment und wie viele L2 Cachelines benötigt deine zweite Variante mit einer Instruktion mit Immediate + zwei weiteren Instruktionen.

Die 1. Variante schlägt mit neun Bytes für die Anweisung und 64 B (?) für die Zeile mit der Konstanten zu Buche; die 2. mit 27 B für die drei Anweisungen und Konstante zusammen.

Aus Cache-Größen-Sicht ist das deutlich (63 %) günstiger, oder? Die Frage ist, ob eine L1-Verfehlung mehr oder weniger frisst als die beiden movs.

Noch mal: L2 ist ein Cache für Daten und Instruktionen.

Beim prefetchen füllt dein Prozessor also bei der ersten Variante eine Cacheline (64B) mit Instruktionen, wovon für deinen Fall nur 9B benötigst, die anderen 55B sind aber nicht verloren, da du diese wahrscheinlich im weiteren Programmverlauf brauchst. Zusätzlich lädt er noch die Zeile mit der Konstanten, wobei es hier schon unwahrscheinlicher ist, dass dir die restlichen 56B nützlich sein werden. Sind also 2 Cachelines, die dein Anwendungsfall benötigt.

Im zweiten Fall benötigst du nur die Instruktionszeile, füllst allerdings 27B, weshalb dein Prozessor schneller die nächste Instruktionszeile holen muss.

Es geht hier also wirklich nur um eine Cacheline unterschied, wofür du deinen ganzen Code verschandeln möchtest. Dein Prozessor betreibt hinter deinem Rücken so viel (falsches) prefetching, dass dir schlecht werden würde, wenn du das alles beobachten könntest. Es ist und bleibt meiner Meinung nach eine obskure Mikrooptimierung, mit zweifelhaftem Nutzen.

Wenn es dir nicht um die Latenz deines Anwendungsfalls geht, sondern darum das du mit der Datenzeile womöglich eine wichtige Cacheline aus dem L2 kegelst: wenn diese Zeile gerade wirklich wichtig war und schnell wieder benötigt wird, ist die Chance sehr hoch, dass diese sich bei der nächsten Benutzung noch im Victimcache (L3) befindet.

[Krishty]

Es geht hier also wirklich nur um eine Cacheline unterschied, wofür du deinen ganzen Code verschandeln möchtest.

Wo verschandelt denn eine einzige via Intrinsic implementierte getPi() meinen ganzen Code? Zumal ich besondere Werte (getInfinity(), getNaN()) sowieso als Integer-Konstanten beschreiben muss, weil der Compiler sie sonst nicht zuverlässig effizient erzeugen kann; die also von vornherein verschandelstmöglich sind ;)

Ist halt schön, hier und da noch was sparen zu können. Danke für die Klärung mit den Caches :)

[Lynxeye]

[...] Zumal ich besondere Werte (getInfinity(), getNaN()) sowieso als Integer-Konstanten beschreiben muss, weil der Compiler sie sonst nicht zuverlässig effizient erzeugen kann; die also von vornherein verschandelstmöglich sind ;) [...]

Ich möchte dich nicht davon abhalten etwas zu tun, was du für richtig hältst, aber dazu bin ich auch nicht hier. Ich möchte nur Denkanstöße liefern, die Entscheidung darfst du dir dann ganz allein ausknobeln. ;)

OT: Manchmal verliere ich mich in Träumen, in denen Leute wie du eine OpenSource Entwicklungsumgebung nutzen und die Energie, welche sie verschwenden um um die Bugs von ClosedSource Software (ATI Catalyst, MS VisualStudio) herum zu arbeiten, einsetzen könnten um das zugrunde liegende Problem zu beheben. Vielleicht hätten wir dann auch Compiler, die einem wirklich die Arbeit des Optimierens abnehmen würden und die WTF/h würden erheblich abnehmen. Dann aber erkenne ich das dies nur ein schöner Traum ist und falle betrunken ins Bett...

[Krishty]

Lustig – ich möchte nämlich schon ewig auf einen Open Source-Compiler umsteigen, der viel besser und kohärenter optimiert, aber ich sehe dieses selten bescheuerte es wird kein Maschinen- sondern nur Quelltext ausgeliefert und wer es benutzen will, soll sich gefälligst erstmal CMake installieren, es dann stundenlang selber mit einem anderen Compilier übersetzen und dann schön alles von Hand einrichten als viel größere Hürde an als die mittlerweile routinierten Visual C++-Optimierungsausfälle.

Da träume ich stattdessen von einer Welt, in der man was startet und es funktioniert; scheißegal, ob Open Source, Closed Source oder unbefleckte Sourcepfängnis.