Jammer-Thread

[dot]

Und immer nur brav weiterjammern, ich finde dein Gejammere sehr informativ... ;)

[CodingCat]

Ich fasse es noch immer nicht. Wieso wird ausgerechnet für den C++-gängigsten Anwendungsfall keine Aliasing-Analyse durchgeführt? Müssen wir jetzt ernsthaft doch auf void Foo::bar() _restrict { }-Methoden umsteigen?!

[Krishty]

Nö. __restrict ist bei Visual C++ in x64-Kompilierung schon seit 2010 ausgeschaltet, falls du dich erinnerst. Und x86 interessiert mich nicht mehr.

[CodingCat]

Nö. __restrict ist bei Visual C++ in x64-Kompilierung schon seit 2010 ausgeschaltet, falls du dich erinnerst. Und x86 interessiert mich nicht mehr.

Damals waren das aber Parameter.

Oh mein Gott, ich habe mich soeben ins Gruselkabinett gestürzt, zum Verzweifeln. Ich habe die Beispiele aus obigem Link mit VC++ 2012 unter x86 und x64 mit und ohne __restrict compiliert. Das Ergebnis ist erschütternd. Erstens hat __restrict an dieser Stelle für beide Plattformen dieselbe Wirkung. Zweitens ist diese Wirkung in beiden Fällen derart halbherzig, dass man am liebsten sofort das Berufsziel wechseln möchte:

Code: Alles auswählen

// x64
int RTest::DoStuffClassMember(int nb) __restrict
{
000000013F881000  mov         rdx,qword ptr [rcx+8]  
000000013F881004  mov         r8d,7D0h  
000000013F88100A  nop         word ptr [rax+rax]  
	while (nb--)
	{
		*mTarget++ = mMember;
000000013F881010  mov         eax,dword ptr [rcx]  
000000013F881012  add         rdx,4  
000000013F881016  mov         dword ptr [rdx-4],eax  
		mMember++;
000000013F881019  inc         eax  
000000013F88101B  mov         dword ptr [rcx],eax  
000000013F88101D  dec         r8d  
000000013F881020  jne         RTest::DoStuffClassMember+10h (013F881010h)  
	}
000000013F881022  mov         qword ptr [rcx+8],rdx  
	return mMember;
}

Code: Alles auswählen

// x64
int RTest::DoStuffClassMember(int nb)    
{
000000013FE71000  mov         r8d,7D0h  
000000013FE71006  nop         word ptr [rax+rax]  
	while (nb--)
	{
		*mTarget++ = mMember;
000000013FE71010  mov         eax,dword ptr [rcx]  
000000013FE71012  mov         rdx,qword ptr [rcx+8]  
000000013FE71016  mov         dword ptr [rdx],eax  
		mMember++;
000000013FE71018  inc         dword ptr [rcx]  
000000013FE7101A  add         qword ptr [rcx+8],4  
000000013FE7101F  mov         eax,dword ptr [rcx]  
000000013FE71021  dec         r8d  
000000013FE71024  jne         RTest::DoStuffClassMember+10h (013FE71010h)  
	}
	return mMember;
}

Ganz recht. Der Compiler erkennt zwar das __restrict und zieht das Laden und Schreiben der mTarget-Adresse dann aus der Schleife, ist aber gleichzeitig zu doof das Laden und Aktualisieren von mMember ebenfalls aus der Schleife zu ziehen. Der x86-Compiler zeigt exakt dasselbe Verhalten.

[Krishty]

Dann haben sie also für this tatsächlich eine andere __restrict-Implementierung gemacht als für Parameter, und dann auch noch eine, die nicht richtig funktioniert? Ich wollte so früh am Sonntag doch garnicht mehr heulen …

[CodingCat]

Nachtrag: Nein, tatsächlich wird überall dieselbe "Aliasing-Analyse" verwendet und sie funktioniert in dem gegebenen Beispiel überall gleich schlecht. Baue ich eine freie Funktion int DoStuff(RTest *__restrict test, int nb), dann zeigt __restrict auch hier für beide Plattformen dieselbe Wirkung. Ohne __restrict ist der Compiler hingegen überhaupt nicht in der Lage, irgendwelche Aliasing-Garantien zu deduzieren. Interessanterweise gibt es offenbar kein __restrict für Referenzen.

[CodingCat]

Nachtrag 2: Es ist nicht auszuschließen, dass noinline bei der Codegenerierung eine zu große Rolle spielt. Kennt jemand einen besseren Weg, Funktionen verlässlich am Inlining zu hindern, ohne dabei LTCG zu beeinträchtigen? dllexport funktioniert zwar, ist aber logischerweise erst recht unbrauchbar, da bei Aufrufen aus Fremdcode ganz sicher keine impliziten Aliasing-Garantien deduziert werden können.

[Krishty]

Mach die Funktion mit irgendeinem nachträglichen Code auf volatile-Variablen so fett, dass VC sie nicht mehr inlinen will.

Falls __restrict in 2012 wirklich wieder funktioniert, habe ich jetzt erstmal ein paar Wochen was zu tun.

[dot]

Wieso genau musst du denn Inlining verhindern? Wenn du die Adresse einer Funktion irgendwie verwendest, wird der Linker sie zumindest instanzieren müssen, vielleicht reicht das ja schon!? Ansonsten mach z.B. einen globalen volatile Function Pointer auf die Funktion und ruf sie über den auf...

Edit: Das ist evtl. auch interessant!?

[Krishty]

Falls du einen Zeiger darauf erzeugst, bezweifle ich, dass Visual C++ noch alle Aufrufstellen analysieren und damit innerhalb der Funktion Aliasing ausschließen kann. Damit wäre das Experiment nutzlos.

Aber auto_inline klingt brauchbar!

[dot]

Naja, ich hab leider nicht ganz verstanden wieso genau und wann genau Inlining verhindert werden soll. Wenn es darum geht, dass ganz bestimmte Aufrufe nicht geinlined werden, die Funktion ansonsten aber schon geinlined wird, dann könnte man diese Aufrufe eben über einen volatile Zeiger schicken und die Funktion ansonsten normal aufrufen. Wenn es darum geht, inlining für eine bestimmte Funktion prinzipiell zu verbieten, dann eben noinline (was genau ist das Problem damit?) oder auto_inline...

[CodingCat]

Naja, ich hab leider nicht ganz verstanden wieso genau und wann genau Inlining verhindert werden soll. Wenn es darum geht, dass ganz bestimmte Aufrufe nicht geinlined werden, die Funktion ansonsten aber schon geinlined wird, dann könnte man diese Aufrufe eben über einen volatile Zeiger schicken und die Funktion ansonsten normal aufrufen. Wenn es darum geht, inlining für eine bestimmte Funktion prinzipiell zu verbieten, dann eben noinline (was genau ist das Problem damit?) oder auto_inline...

Es geht darum, herauszufinden, welche Optimierungen der Compiler über nicht-geinlineten Code hinaus durchführen kann und daraus ggf. Best Practices für effizienten Code in komplexen Anwendungen abzuleiten. Einfache Testfälle fallen hingegen fast immer in die Kategorie automatisch geinlineten Codes.

auto_inline liefert dieselben Ergebnisse wie __declspec(noinline). Richtig übel wird es erst, wenn man die Testfunktionen so mit printf-Aufrufen verfettet, dass sie auch ohne zusätzliche Angaben nicht mehr geinlinet werden. Ironischerweise versagt hier ausgerechnet das __restrict auf Methoden komplett, ein __restrict-Zeiger als Parameter der freien Funktion hingegen liefert weiterhin besseren Code als der uneingeschränkte Zeiger. Insgesamt ist der Compiler jedoch nicht mal in diesem trivialen Programm in der Lage, die einfachsten Aliasing-Fälle auszuschließen, sobald der Code nicht mehr geinlinet wird.

[Krishty]

Sollen wir nicht einen ZFX Community Compiler schreiben? ;)

[dot]

Naja, um Aliasing auszuschließen, wenn nicht geinlined wird, müsste der Compiler ja sämtliche Aufrufe suchen und separat beweisen, dass kein Aliasing auftritt. Genau dafür gibt es doch __restrict!?

[Krishty]

Nein; das sollte der Compiler auch so können. Visual C++ nutzt die Tatsache, alle Aufrufer zu kennen, ja z.B., um Calling Conventions über den Haufen zu werfen und im Idealfall alles in Register zu stopfen und Konstanten über Funktionsgrenzen zu propagieren; je nachdem, wie es den Aufrufern am besten passt.

Das mit dem Propagieren über Funktionsgrenzen hinaus funktioniert übrigens, zumindest bei freien Funktionen. Da hängen bei mir tausende Zeilen dran.

[dot]

Das stimmt natürlich, aber ich behaupte mal, dass Aliasing ein weitaus komplexeres Problem ist, als Aufrufkonventionen. Allein schon aus dem simplen Grund, dass die Parameterliste einer Funktion sonnenklar ist, der Compiler bezüglich Aliasing aber erstmal von selbst passende Hypothesen aufstellen und beweisen muss. Natürlich wärs cool, wenn der Compiler das alles machen würde, am besten vielleicht mit weiterer Intelligenz, die (natürlich optional profile guided) dann mehrere Varianten einer Funktion generiert und die optimale Balance zwischen Codesize und Performance liefert. Aber ich bezweifle, dass du irgendienen Compiler finden wirst, der das tut... ;)

Ich wär mir jedenfalls nicht sicher, ob man da im Allgemeinen nicht so schnell irgendwo in der Gegend von NP landet, dass es sich gar nicht auszahlt, weiter drüber nachzudenken... ;)

[Krishty]

Aliasing-Analyse ist das Problem schlechthin bei datenlastigen Anwendungen, darum verbringen die Compiler auch eine gute Zeit des Kompiliervorgangs damit – sowohl GCC als auch VC und Clang. Letzterer hat mit Polly ein Projekt im Ofen, das Schleifen durch Faltung von Datenabhängigkeiten (die festzustellen ohne handfeste Aliasing-Analyse unmöglich wäre) teilweise auf die zehnfache Leistung des Intel-Compilers optimieren kann. Und die Sprachen unterstützen durch ihre Aliasing Rules die Optimierungen, z.B. mit C++, das sagt, dass new nicht zweimal denselben Zeiger zurückgibt, bevor der erste wieder freigegeben wurde. (Lustig ist übrigens, dass C strengere Aliasing-Regeln hat als C++, und die Analyse deshalb wohl bei C einfacher fällt.) Clang erzeugt auch unterschiedliche Versionen derselben Schleife je nach Ausführungsmenge und Datenabhängigkeiten.

Also: Doch; das MUSS ein vernünftiger Compiler können. Er sollte zumindest nicht so blöd sein zu denken, wenn ich in einer Schleife in das eine Attribut schreibe, dass sich dann das andere ändern könnte.

[glassbear]

Und immer nur brav weiterjammern, ich finde dein Gejammere sehr informativ... ;)

+1
I like
Was-auch-immer :mrgreen:

[Krishty]

Visual C++ schreibt, wenn Debug-Informationen aktiv sind, den Klarpfad zur .pdb in die Exe. WTF?! Hätte ein Hash nicht gereicht?! Wird nicht sowieso erstmal im Verzeichnis, auf den Symbol Servers, und in der Unterhose von David Hasselhoff gesucht? Heute habe ich echt die Pappe auf

[Krishty]

Falls es hier Leute gibt, die ihre Indizes nur zur Adressierung einsetzen (und nicht etwa zu Berechnungen à Wie viele Elemente sind zwischen dem und dem Index), können die ja mal versuchen, die Indizes mit sizeof(Element) zu skalieren und die eigentliche Adressierung auf einem gecasteten char-Zeiger durchzuführen. Sollte performanter sein.

[Schrompf]

Der Compiler scheitert an Zeiger-Arithmethik? Bitte erzähle mehr, ich lausche gebannt.

[Krishty]

Ist nicht zwingend die Schuld des Compilers; wenn du z.B. diese Indizes als Iteratoren einsetzt um sie überall rumzureichen und zu benutzen, kann er da nichts dran ändern.

Aber es ist im Grunde so, dass jeder Array-Index bei der Adressierung mit sizeof(Element) multipliziert werden muss um an die Zieladresse zu kommen. Ebenso bewirkt jedes ++ einen Sprung um sizeof(Element) Bytes. Letztendlich ist auch length = end - begin nur ein length = ((char*)end - (char*)begin) / sizeof(Element). Kurz: Der Index wird vor jeder Benutzung mit sizeof(Element) multipliziert und vor jeder Berechnung dadurch dividiert. Das spart man alles, indem man direkt den skalierten Wert speichert.

Und ja: das bringt auch dann noch was, wenn LEA für die Adressberechnung genutzt wird. Und das ist der Grund, warum vec.empty() dem 0 == vec.length() vorzuziehen ist – ersteres vergleicht nur Zeiger; letzteres berechnet das Ergebnis auf Basis einer Subtraktion und Division. Und die führt (zum dritten Mal gesagt) VC tatsächlich durch, und das ist dann auch Compiler-Versagen:

    template <typename Element> bool isLengthEqual(
        Element const * const begin,
        Element const * const end,
        size_t const count
    ) {
        assert("invalid range" && end >= begin);
        assert("size overrun" && size_t(-1) / sizeof(Element) >= count);
        return sizeof(Element) * count == reinterpret_cast<char const *>(end) - reinterpret_cast<char const *>(begin);
    }

Das hier bewirkt eine Multiplikation statt einer Division, und die kann darüber hinaus für statische Parameter beim Kompilieren berechnet werden. Darum erzeugt das deutlich weniger Maschinentext als

    count == end - begin

und darum habe ich in meinen Daten alle Indizes und Mengenangaben mit sizeof vorskaliert, falls möglich.

[Schrompf]

Ich lern doch immer was dazu. Danke für die Erklärung!

[CodingCat]

Es geht noch weiter, haltet die Luft an. Zwar speichert std::vector wunderbar praktisch begin- und end-Zeiger, aber ihr kommt nie im Leben ungestraft dran!

Code: Alles auswählen

return v.data() + v.size();
000000013FDC1340  mov         rdx,qword ptr [rcx]  
000000013FDC1343  mov         rax,qword ptr [rcx+8]  
000000013FDC1347  sub         rax,rdx  
000000013FDC134A  sar         rax,2  
000000013FDC134E  lea         rax,[rdx+rax*4]

Nein, das ist kein Debug-Build. Das ist maximale Optimierung unter x64.

Das richtige Ergebnis (1 Move) erhaltet ihr im Release-Mode übrigens mit &*v.end();. Dieser Ausdruck ist jedoch absolut undefiniert und wird euer Programm mit Iterator Debugging sofort anhalten.

[Krishty]

Erzeug mal via rand() zwei zufällige Speicher-Offsets und benutz die als begin und length (skalieren mit einem schönen sizeof – sagen wir – 17, nicht vergessen) und dann führ die Zeigerarithmetik per Hand durch und poste den Maschinentext. Falls das optimiert wird, ist das der Beweis, dass der Compiler zwei unterschiedliche Optimierungsspuren für Integer- und Adressarithmetik hat (bzw. eine: NUR für Integerarithmetik).

[antisteo]

Die gesamten Themen, die im Jammer-Thread besprochen werden, kommen mir vor, als könnte man damit richtig viel Zeit verbringen, betreffen aber jedes mal Themen, von denen ich absolut keine Ahnung habe. Irgendwie Zeitverschwendung.

[Krishty]

Code: Alles auswählen

		static UnsignedAddress const elementSize = 17;
		UnsignedAddress begin = rng.next() * elementSize;
call        Math::TT800::next (0140007660h)  
mov         ebx,eax  
imul        rbx,rbx,11h  
		UnsignedAddress end = begin + rng.next() * elementSize;
call        Math::TT800::next (0140007660h)  
mov         ecx,eax  
mov         rax,0F0F0F0F0F0F0F0F1h  
imul        rcx,rcx,11h  
mul         rax,rcx  
mov         rcx,qword ptr [rdi+18h]  
		volatile auto const newEnd = begin + (SignedAddress(end - begin) / elementSize) * elementSize;
shr         rdx,4  
imul        rdx,rdx,11h  
add         rdx,rbx  

So wie ich das sehe, wird auch hier dividiert (Multiplikation mit 0x0F0F0F0F0F0F0F0F1 und anschließender Right Shift?) und dann wieder multipliziert. Scheint also doch ein generelles Problem mit x / y * y zu sein.

Übrigens ist das Ergebnis des Random Number Generators eine 32-Bit-Zahl, d.h., Überlauf kann hier durch den Compiler ausgeschlossen werden.

[B.G.Michi]

Gibt es denn wirklich keine Möglichkeit GCC dazu zu bringen folgenden Code zu vektorisieren?!?

Code: Alles auswählen

#include <stdio.h>

int main(void)
{
	float a[4], b[4], c[4];
	scanf("", a, b, c);

	a[0] = b[0] + c[0];
	a[1] = b[1] + c[1];
	a[2] = b[2] + c[2];
	a[3] = b[3] + c[3];

	printf("", a, b, c);
	return 0;
}

[Krishty]

__attribute__((vector_size(16)))? Oder meintest du eine humane Möglichkeit?

[B.G.Michi]

Ich hatte auf eine Compileroption, die ich bisher übersehen hab, gehofft... aber meine Hoffnungen scheinen enttäuscht zu werden... :(