webentwicklung-frage-antwort-db.com.de

Eigen: Die Auswirkungen des Codierungsstils auf die Leistung

Nach dem, was ich über Eigen ( hier ) gelesen habe, scheint operator=() eine Art "Barriere" für faule Bewertungen zu sein - z. Es veranlasst Eigen, die Rückgabe von Ausdrucksvorlagen zu stoppen und die (optimierte) Berechnung tatsächlich durchzuführen, wobei das Ergebnis auf der linken Seite des = gespeichert wird.

Dies bedeutet anscheinend, dass der Codierungsstil eines Benutzers Auswirkungen auf die Leistung hat - dh die Verwendung von benannten Variablen zum Speichern des Ergebnisses von Zwischenberechnungen kann sich negativ auf die Leistung auswirken, da einige Teile der Berechnung zu "zu früh" bewertet werden .

Um meine Intuition zu überprüfen, schrieb ich ein Beispiel auf und war überrascht von den Ergebnissen ( vollständiger Code hier ):

using ArrayXf  = Eigen::Array <float, Eigen::Dynamic, Eigen::Dynamic>;
using ArrayXcf = Eigen::Array <std::complex<float>, Eigen::Dynamic, Eigen::Dynamic>;

float test1( const MatrixXcf & mat )
{
    ArrayXcf arr  = mat.array();
    ArrayXcf conj = arr.conjugate();
    ArrayXcf magc = arr * conj;
    ArrayXf  mag  = magc.real();
    return mag.sum();
}

float test2( const MatrixXcf & mat )
{
    return ( mat.array() * mat.array().conjugate() ).real().sum();
}

float test3( const MatrixXcf & mat )
{
    ArrayXcf magc   = ( mat.array() * mat.array().conjugate() );

    ArrayXf mag     = magc.real();
    return mag.sum();
}

Das Obige gibt drei verschiedene Arten der Berechnung der betragsmäßigen Summe der Beträge in einer komplexwertigen Matrix.

  1. test1 Art nimmt jeden Teil der Berechnung "Schritt für Schritt" in Anspruch.
  2. test2 führt die gesamte Berechnung in einem Ausdruck durch.
  3. test3 verfolgt einen "gemischten" Ansatz - mit einer gewissen Anzahl von Zwischenvariablen.

Ich habe erwartet, dass, da test2 die gesamte Berechnung in einen Ausdruck packt, Eigen in der Lage wäre, dies zu nutzen und die gesamte Berechnung global zu optimieren, um die beste Leistung zu erzielen.

Die Ergebnisse waren jedoch überraschend (die Angaben beziehen sich auf Mikrosekunden über 1000 Ausführungen jedes Tests):

test1_us: 154994
test2_us: 365231
test3_us: 36613

(Dies wurde mit g ++ -O3 kompiliert - siehe the Gist für vollständige Details.)

Die Version, von der ich erwartet hatte, dass sie am schnellsten ist (test2), war tatsächlich am langsamsten. Die Version, von der ich erwartet hatte, dass sie am langsamsten ist (test1), befand sich tatsächlich in der Mitte.

Meine Fragen sind also:

  1. Warum ist test3 so viel besser als die Alternativen?
  2. Gibt es eine Technik, die Sie verwenden können (kurz in den Assembly-Code eintauchen), um zu verstehen, wie Eigen Ihre Berechnungen tatsächlich implementiert?
  3. Gibt es eine Reihe von Richtlinien, die eingehalten werden müssen, um einen guten Kompromiss zwischen Leistung und Lesbarkeit (Verwendung von Zwischenvariablen) in Ihrem Eigencode zu erzielen?

Bei komplexeren Berechnungen kann die Lesbarkeit aller Schritte in einem Ausdruck die Lesbarkeit beeinträchtigen. Ich bin also daran interessiert, den richtigen Weg zu finden, um Code zu schreiben, der sowohl lesbar als auch performant ist.

36
jeremytrimble

Es sieht nach einem Problem des GCC aus. Intel Compiler liefert das erwartete Ergebnis.

$ g++ -I ~/program/include/eigen3 -std=c++11 -O3 a.cpp -o a && ./a
test1_us: 200087
test2_us: 320033
test3_us: 44539

$ icpc -I ~/program/include/eigen3 -std=c++11 -O3 a.cpp -o a && ./a
test1_us: 214537
test2_us: 23022
test3_us: 42099

Verglichen mit der icpc-Version scheint gcc Probleme bei der Optimierung Ihres test2 zu haben.

Um ein genaueres Ergebnis zu erhalten, können Sie die Debug-Assertions mithilfe von -DNDEBUG wie hier gezeigt hier deaktivieren.

EDIT

Für Frage 1

@ggael gibt eine hervorragende Antwort, dass gcc die Summenschleife nicht vektorisiert. Mein Experiment fand auch heraus, dass test2 genauso schnell ist wie die von Hand geschriebene naive for-Schleife, sowohl mit gcc als auch mit icc, was darauf hindeutet, dass Vektorisierung der Grund dafür ist, und dass in test2 durch die unten genannte Methode keine temporäre Speicherzuordnung festgestellt wird, was auf Eigen verweist werten Sie den Ausdruck richtig aus.

Für Frage 2

Das Vermeiden des Zwischenspeichers ist der Hauptzweck, in dem Eigen Ausdrucksvorlagen verwenden. Eigen bietet also ein Makro EIGEN_RUNTIME_NO_MALLOC und eine einfache Funktion an, mit der Sie prüfen können, ob bei der Berechnung des Ausdrucks ein Zwischenspeicher zugeordnet ist. Einen Beispielcode finden Sie hier . Bitte beachten Sie, dass dies möglicherweise nur im Debug-Modus funktioniert.

EIGEN_RUNTIME_NO_MALLOC - Wenn definiert, wird ein neuer Switch eingeführt, der kann durch Aufrufen von set_is_malloc_allowed (bool) ein- und ausgeschaltet werden. Ob malloc ist nicht erlaubt und Eigen versucht, Speicher dynamisch zuzuweisen trotzdem kommt es zu einem Assertionsfehler. Nicht standardmäßig definiert.

Für Frage 3

Es gibt eine Möglichkeit, Zwischenvariablen zu verwenden und gleichzeitig die Leistungsverbesserung durch verzögerte Auswertungs-/Ausdrucksvorlagen einzuführen. 

Der Weg ist die Verwendung von Zwischenvariablen mit korrektem Datentyp. Anstelle von Eigen::Matrix/Array, der den auszuwertenden Ausdruck anweist, sollten Sie den Ausdruckstyp Eigen::MatrixBase/ArrayBase/DenseBase verwenden, damit der Ausdruck nur gepuffert, aber nicht ausgewertet wird. Das bedeutet, dass Sie den Ausdruck als Zwischenprodukt und nicht als Ergebnis des Ausdrucks speichern sollten, mit der Bedingung, dass dieses Zwischenprodukt im folgenden Code nur einmal verwendet wird. 

Da die Festlegung der Vorlagenparameter im Ausdruckstyp Eigen::MatrixBase/... mühsam sein kann, können Sie stattdessen auto verwenden. In dieser Seite finden Sie einige Hinweise, wann Sie auto/Ausdruckstypen verwenden sollten/sollen. Auf einer anderen Seite erfahren Sie, wie Sie die Ausdrücke als Funktionsparameter übergeben, ohne sie auszuwerten. 

Laut dem belehrenden Experiment über .abs2() in @ggaels Antwort denke ich, dass eine andere Richtlinie darin besteht, zu vermeiden, dass das Rad neu erfunden wird.

14
kangshiyin

Was passiert, ist, dass Eigen aufgrund des Schritts .real()test2 nicht explizit vektorisiert. Es wird daher der Standard-Operator operator :: :: Operator aufgerufen, der von gcc leider nie inline dargestellt wird. In den anderen Versionen wird dagegen die eigene vektorisierte Produktimplementierung von Komplexen verwendet.

Im Gegensatz dazu führt ICC den komplexen Inline-Operator * aus, wodurch der test2 der schnellste für ICC ist. Sie können test2 auch wie folgt umschreiben:

return mat.array().abs2().sum();

um auf allen Compilern eine noch bessere Leistung zu erzielen:

gcc:
test1_us: 66016
test2_us: 26654
test3_us: 34814

icpc:
test1_us: 87225
test2_us: 8274
test3_us: 44598

clang:
test1_us: 87543
test2_us: 26891
test3_us: 44617

Die extrem gute Bewertung von ICC in diesem Fall ist auf die intelligente Auto-Vektorisierungs-Engine zurückzuführen.

Eine andere Möglichkeit, den Inlining-Fehler von gcc zu umgehen, ohne test2 zu ändern, besteht darin, Ihren eigenen operator* für complex<float> zu definieren. Fügen Sie beispielsweise Folgendes in Ihre Datei ein:

namespace std {
  complex<float> operator*(const complex<float> &a, const complex<float> &b) {
    return complex<float>(real(a)*real(b) - imag(a)*imag(b), imag(a)*real(b) + real(a)*imag(b));
  }
}

und dann bekomme ich:

gcc:
test1_us: 69352
test2_us: 28171
test3_us: 36501

icpc:
test1_us: 93810
test2_us: 11350
test3_us: 51007

clang:
test1_us: 83138
test2_us: 26206
test3_us: 45224

Natürlich ist dieser Trick nicht immer zu empfehlen, da er im Gegensatz zur glib-Version zu Überlauf- oder numerischen Löschungsproblemen führen kann, was aber von icpc und den anderen vektorisierten Versionen trotzdem berechnet wird.

14
ggael

Eine Sache, die ich zuvor gemacht habe, ist, das auto-Schlüsselwort häufig zu verwenden. Wenn man bedenkt, dass die meisten Eigen-Ausdrücke spezielle Ausdrucks-Datentypen zurückgeben (z. B. CwiseBinaryOp), kann eine Zuweisung an eine Matrix dazu führen, dass der Ausdruck ausgewertet wird (was Sie sehen). Durch die Verwendung von auto kann der Compiler den Rückgabetyp als den Ausdruckstyp bestimmen, der es ist, wodurch die Auswertung so lange wie möglich vermieden wird:

float test1( const MatrixXcf & mat )
{
    auto arr  = mat.array();
    auto conj = arr.conjugate();
    auto magc = arr * conj;
    auto mag  = magc.real();
    return mag.sum();
}

Dies sollte im Wesentlichen näher an Ihrem zweiten Testfall sein. In einigen Fällen hatte ich gute Leistungsverbesserungen, während die Lesbarkeit erhalten blieb (Sie wollen not die Ausdrucksvorlagentypen nicht buchstabieren). Natürlich kann der Kilometerstand variieren, also sorgfältig Benchmarking :)

5
mindriot

Ich möchte nur, dass Sie feststellen, dass Sie das Profiling auf nicht optimale Weise durchgeführt haben. Das Problem könnte also nur Ihre Profilierungsmethode sein.

Da es viele Dinge wie die Cache-Lokalität zu berücksichtigen gibt, sollten Sie die Profilierung auf diese Weise durchführen:

int warmUpCycles = 100;
int profileCycles = 1000;

// TEST 1
for(int i=0; i<warmUpCycles ; i++)
      doTest1();

auto tick = std::chrono::steady_clock::now();
for(int i=0; i<profileCycles ; i++)
      doTest1();  
auto tock = std::chrono::steady_clock::now();
test1_us = (std::chrono::duration_cast<std::chrono::microseconds>(tock-tick)).count(); 

// TEST 2


// TEST 3

Sobald Sie den Test auf die richtige Weise durchgeführt haben, können Sie zu Schlussfolgerungen kommen.

Ich habe den Verdacht, dass Sie, da Sie für jeden Vorgang ein Profil erstellen, die zwischengespeicherte Version für den dritten Test verwenden, da die Vorgänge wahrscheinlich vom Compiler neu angeordnet werden.

Sie sollten auch andere Compiler ausprobieren, um zu sehen, ob das Problem beim Abrollen von Templates liegt (die Optimierung von Templates ist in der Tiefe begrenzt. Wahrscheinlich können Sie es mit einem einzigen großen Ausdruck treffen).

Wenn die Semantik der Eigenen Support-Verschiebung verwendet wird, gibt es keinen Grund, warum eine Version schneller sein sollte, da nicht immer garantiert werden kann, dass Ausdrücke optimiert werden können.

Bitte versuchen Sie es und lassen Sie es mich wissen, das ist interessant. Stellen Sie außerdem sicher, dass Sie Optimierungen mit Flags wie -O3 aktiviert haben. Profiling ohne Optimierung ist ohne Bedeutung.

Um zu verhindern, dass der Compiler alles wegwirft, verwenden Sie die anfängliche Eingabe aus einer Datei oder cin und geben Sie dann die Eingabe in die Funktionen ein.

0
GameDeveloper