Optimierung der C ++ 2-D-Arrays

StackOverflow https://stackoverflow.com/questions/152745

Frage

ich brauche einen Weg, um eine 2-D-Matrix darzustellen (eine dichte Matrix) von Doppel in C ++, mit absolutem Mindestaufwand erreichbar.

Ich habe einiges Timing auf verschiedenen Linux / Unix-Maschinen und gcc Versionen getan. Ein STL-Vektor von Vektoren, erklärt wie: 

vector<vector<double> > matrix(n,vector<double>(n));

und der Zugriff durch matrix[i][j] zwischen 5% und 100% langsamer Zugriff als ein Array deklariert als: 

double *matrix = new double[n*n];

zugegriffen durch eine Indexfunktion inlined matrix[index(i,j)], wo index(i,j) auswertet bis i N * + j. Andere Möglichkeiten, eine 2-D-Matrix ohne STL Anordnung - eine Anordnung von n Zeigern auf den Anfang jeder Zeile oder definieren, das Ganze auf dem Stapel als konstante Größe matrix[n][n] - laufen bei fast genau die gleiche Geschwindigkeit wie die Indexfunktion Methode .

Neue GCC-Versionen (> 4.0) scheinen die STL-Vektor-of-Vektoren zu nahezu der gleichen Effizienz wie die Nicht-AWL-Code in der Lage sein zu kompilieren, wenn Optimierungen eingeschaltet sind, aber das ist etwas maschinenabhängig.

Ich möchte STL verwenden, wenn möglich, aber die schnellste Lösung wählen. Hat jemand keine Erfahrung STL mit GCC bei der Optimierung?

War es hilfreich?

Lösung

Wenn Sie GCC der Compiler verwenden können Ihre Matrix analysieren zugreift und die Reihenfolge im Speicher in bestimmten Fällen ändern. Die Magie Compiler-Flag ist definiert als: 

-fipa-matrix-reorg
  

Führen Matrix Verflachung und   Transponieren. Matrix Abflachung versucht   eine m-dimensionale Matrix zu ersetzen, mit   deren äquivalent n-dimensionale Matrix,   wobei n

Beachten Sie, dass diese Option nicht von -O2 oder O3 aktiviert ist. Sie müssen es selbst passieren.

Andere Tipps

Meine Vermutung wäre der schnellste ist, für eine Matrix, 1D STL-Array zu verwenden und den Operator () außer Kraft setzen sie als 2D-Matrix zu verwenden.

Allerdings definiert die STL auch eine Art speziell für Nicht-resizeable numerische Arrays: valarray. Sie haben auch verschiedene Optimierungen für in-Place-Operationen.

valarray einen numerischen Typ als Argument akzeptieren: 

valarray<double> a;

Dann können Sie Scheiben, indirekten Arrays verwenden, ... und natürlich können Sie die valarray erben und die eigenen Operator definieren () (int i, int j) für 2D-Arrays ...

Sehr wahrscheinlich ist dies ein Ort-of-Referenz Problem. vector new verwendet seine interne Array zuzuordnen, so dass jede Zeile wird zumindest ein wenig auseinander in Erinnerung sein aufgrund jeder Header-Block; es könnte eine lange Strecke voneinander entfernt sein, wenn der Speicher bereits fragmentiert ist, wenn man sie zuordnen. Verschiedene Reihen des Arrays werden wahrscheinlich zumindest einen Cache-Leitungsfehler verursachen und könnte einen Seitenfehler verursachen; wenn Sie wirklich Pech zwei benachbarte Reihen auf Speicherzeilen sein könnten, die einen TLB-Steckplatz teilen und einen Zugriff auf die anderen vertreiben.

Im Gegensatz zu anderen Lösungen Ihrer garantieren, dass alle Daten, benachbart sind. Es könnte Ihre Leistung helfen, wenn Sie die Struktur ausrichten, so dass es so wenige Cache-Zeilen wie möglich kreuzt.

vector ist für resizable Arrays. Wenn Sie die Arrays nicht die Größe müssen, verwenden Sie eine reguläre C ++ Array. STL-Operationen können in der Regel arbeiten auf C ++ Arrays.

Seien Sie sicher, dass das Array in der richtigen Richtung zu gehen, das heißt über (aufeinanderfolgenden Speicheradressen), anstatt nach unten. Dies wird Cache Fehler reduzieren.

Meine Empfehlung wäre Boost.UBLAS zu verwenden, die schnell Matrix / Vektor-Klassen bietet.

Um fair zu sein, hängt von dem Algorithmen Sie auf der Matrix verwenden.

Der Doppelname [n * m] Format ist sehr schnell, wenn Sie Daten von Zeilen zugreifen, da sowohl hat fast keine Overhead neben einer Multiplikation und Addition und weil Ihre Reihen sind gepackte Daten, die im Cache-kohärent sein werden.

Wenn Sie Ihre Algorithmen Zugriff Spalte geordnete Daten dann andere Layouts könnte viel besser Cache-Kohärenz haben. Wenn Ihr Algorithmus Zugangsdaten in den Quadranten der Matrix auch andere Layouts könnten besser sein.

Versuchen Sie einige der Forschung an der Art der Nutzung gerichtet zu machen und Algorithmen Sie verwenden. Das ist besonders wichtig, wenn die Matrix sehr groß ist, da Cache-Misses Ihrer Leistung weit mehr als um 1 oder 2 zusätzliche mathematische Operationen verletzen kann jede Adresse zugreifen zu können.

Sie könnte genauso gut tun vector (n * m);

Sie können auf der Eigen C ++ Template-Bibliothek aussehen soll unter http://eigen.tuxfamily.org/. Es erzeugt AltiVec oder sse2 Code, um die Vektor / Matrix-Berechnungen zu optimieren.

Es ist die uBLAS Implementierung in kurbeln. Es lohnt sich einen Blick zu.

http: //www.boost .org / doc / libs / 1_36_0 / libs / numerisch / ublas / doc / matrix.htm

Ein weiteres verwandtes Bibliothek ist Blitz ++: http://www.oonumerics.org/blitz /docs/blitz.html

Blitz ++ ist so konzipiert, Array-Bearbeitung zu optimieren.

Ich habe diese vor einiger Zeit für Rohbilder gemacht durch meine eigenen 2-dimensionalen Array Klassen deklariert.

In einem normalen 2D-Array, greifen Sie auf die Elemente wie:

array [2] [3]. Jetzt diesen Effekt zu erhalten, würden Sie ein Klasse-Array mit einem überladenen haben [] Array Accessor. Aber dies würde im Wesentlichen ein anderes Array zurück, wodurch geben Sie die zweite Dimension.

Das Problem bei diesem Ansatz ist, dass es einen Doppelfunktionsaufruf Overhead hat.

So wie ich es tat, war die () Stil Überlastung zu verwenden.

Also statt Array [2] [3], ändere ich hatte es diesen Stil Array tun (2,3).

Das () Funktion war sehr klein und ich sicher, dass es inlined wurde.

Siehe diesen Link für das allgemeine Konzept, dass: http://www.learncpp.com/cpp-tutorial / 99-Überlastung-the-Klammer-Operator /

Sie können den Typ Vorlage, wenn Sie müssen.
Der Unterschied, den ich hatte, war, dass mein Array dynamisch war. Ich hatte einen Block von char Erinnerung, die ich erklären würde. Und ich verwendet, um eine Spalte Cache, so dass ich wusste, wo in meiner Folge von Bytes die nächste Zeile begann. Der Zugang wurde für den Zugriff auf benachbarte Werte optimiert, weil ich es für die Bildverarbeitung verwendet wird.

Es ist schwer, ohne den Code zu erklären, aber im Wesentlichen das Ergebnis war so schnell wie C, und viel einfacher zu verstehen und zu verwenden.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top