C++ Scheifen optimieren

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

C++ Scheifen optimieren

Beitrag von Jonathan »

Moinsen,

Ich habe ein Projekt wo ich nervig viele Berechnungen auf float Arrays machen muss. Ich habe daher jetzt mal eine Hilfsklasse gebastelt:

Code: Alles auswählen

class Field : public std::vector<float>
{
public:
	using vector::vector;

	inline const Field& operator= (float value);
	inline const Field& operator*= (float value);
	inline const Field& operator*= (const Field& other); // element wise multiplication
};
Field operator* (Field a, Field b);
Field operator* (Field a, float v);
	
Field operator*(Field a, float v)
{
	Field res(a.size());
	for( auto i=0; i<a.size(); ++i)
		res[i] = a[i] * v;
	return res;
}

// etc....
Früher hatte ich dann sowas wie das hier:

Code: Alles auswählen

void Function(const std::vector<float>& f);

for(auto i=0; i<num_voxels; ++i)
{
	tmp[i] = m_w[i] * 0.5f * m_n[i];
}

Function(tmp);
Heute kann ich stattdessen einfach das hier schreiben:

Code: Alles auswählen

Function( m_w * 0.5f * m_n);
In längeren Algorithmen spart man sich so viel Code, ein paar echt dumme Fehlerquellen und jede Menge Übersichtlichkeit.

Aber wie viel kostet mich das ganze? 3 Felder nacheinander multiplizieren erzeugt einerseits temporäre Variable, andererseits gibts aber z.B. auch 2 Schleifen anstatt nur einer. Der Schleifenkörper ist eh schon fast leer, die Hälfte der Arbeit geht ja aufs Hochzählen drauf und das will man dann vielleicht nicht doppelt machen. Andererseits ist es aber auch plausibel, und darauf spekuliere ich, dass alles wegoptimiert wird und ich am Ende den selben Code habe.

Ich hab jetzt keine große Übung darin Assembler-Code zu lesen. Kann ich erwartungsgemäß davon ausgehen, dass die Optimierung gut klappt?
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Krishty »

Du hast std::valarray<float> neu erfunden …

Bild

Üblicherweise klappt die Optimierung damit sehr viel besser als mit dem anderen Code. Die neue Version sollte auch der dümmste Vectorizer vektorisiert kriegen. Aber std::valarray ist halt sehr viel besser optimiert; insbesondere wird deine letzte Frage damit explizit behandelt (aufeinanderfolgende Operationen werden vom Compiler zu einem einzigen Schleifendurchlauf zusammengefasst).
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Jonathan »

Krishty hat geschrieben: 15.01.2023, 16:09 Du hast std::valarray<float> neu erfunden …
...

Andererseits kann man es auch als Kompliment auffassen, wenn die Idee so gut ist, dass auch andere sie schon vorher hatten. Nein? Hm. Na egal. Ich gehe mal meine Klasse durch ein typedef ersetzen und bin damit dann schätze ich fertig.

thx.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Schrompf »

Was mir noch auffällt: Deine Schleifengrößen sind laufzeitdynamisch. Weiß nicht, ob und wieviel der Compiler da rausholen kann. Evtl. lohnt es sich, die Schleife in Vierern oder Achtern durchzuzählen und erst die letzten Elemente einzeln durchzugehen. Aber ich kenne valarray nicht, vielleicht machen die sowas schon. Sonst gibt's seit C++20 auch std::for_each mit verschiedenen Execution Policies
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Krishty »

https://godbolt.org/z/hqrWTM5n1 generiert VMOVDQU YMM1, was ohne genauere Inspektion erstmal für 32-Byte-Häppchen (acht ints parallel) spricht.

Code-Pfade für den Übertrag nach ungeraden Elementzahlen wird der Compiler wohl immer reinkompilieren; auch wenn du selber darauf achtest, nur Mehrfache von vier und acht reinzustecken.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Schrompf »

Krishty hat geschrieben: 17.01.2023, 09:18 Code-Pfade für den Übertrag nach ungeraden Elementzahlen wird der Compiler wohl immer reinkompilieren; auch wenn du selber darauf achtest, nur Mehrfache von vier und acht reinzustecken.
Hübsch, bin beeindruckt. Hab's jetzt nicht im Detail nachvollzogen, aber es gibt auf jeden Fall mindestens eine 32byte-Schleife. Zwei sogar, warum auch immer. Bei Visual Studio kann man mit __asume() noch den Hint geben, dass die Size durch vier oder acht teilbar ist, und das pusht die Vektorisierung nochmal ganz phantastisch. In diesem Beispiel krieg ich mit __builtin_expect() gerade keine solche Verbesserung hin.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Krishty »

Cool. Ich versuche seit Jahren, dem Compiler via __assume() mitzuteilen, dass bestimmte Arrays nicht leer sein können (damit for automatisch zum effizienteren do while kompiliert), aber das frisst er nicht. Dann ist der Hinweis, dass die Größe glatt durch vier oder acht teilbar ist, garantiert ein Spezialfall extra für Autovektorisierung!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von dot »

Krishty hat geschrieben: 17.01.2023, 09:18 https://godbolt.org/z/hqrWTM5n1 generiert VMOVDQU YMM1, was ohne genauere Inspektion erstmal für 32-Byte-Häppchen (acht ints parallel) spricht.
Probier mal was komplexeres, z.B.: c = a * 0.5f + b. gcc scheint ganz akzeptablen Code zu generieren. msvc und clang dagegen failen völlig…
Jonathan hat geschrieben: 15.01.2023, 15:38Andererseits ist es aber auch plausibel, und darauf spekuliere ich, dass alles wegoptimiert wird und ich am Ende den selben Code habe.
Leider sind diese Arten von Optimierungen in üblichem C++ Code sehr sehr schwierig und nur eingeschränkt Möglich. Ein Hauptgrund dafür ist ime Aliasing. Wenn man sehr aufpasst und etwas von Compilern verstehent, dann kann man zu einem gewissen Grad oft den Code so schreiben, dass der Compiler diese Optimierungen durchführen kann. ime funktioniert aber selbst das nur zu einem gewissen Grad und ist oft nicht sehr Verlässlich. Wie Tim Foley es so passend gesagt hat: Auto-vectorization is not a programming model. Wenn es wirklich um Performance geht dann würde ich mich nicht drauf verlassen. Schau dir vielleicht z.B. mal Eigen an.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: C++ Scheifen optimieren

Beitrag von Jonathan »

dot hat geschrieben: 20.01.2023, 03:02Wie Tim Foley es so passend gesagt hat: Auto-vectorization is not a programming model. Wenn es wirklich um Performance geht dann würde ich mich nicht drauf verlassen. Schau dir vielleicht z.B. mal Eigen an.
Hm, ja, danke für den Hinweis.

Valarraz hat für mich jetzt fürs erste funktioniert. Ich denke, dass ich auch ansonsten eh irgendwann direkt auf Cuda umsteigen würde, wenn es wirklich schneller werden soll.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Antworten