Ich brauche einen Weg, um ein 2-D-Array (eine dichte Matrix) von Doppelpunkten in C ++ mit absolut minimalem Zugriffsaufwand darzustellen.
Ich habe einige Timing auf verschiedenen Linux / Unix-Maschinen und GCC-Versionen gemacht. Ein STL-Vektor von Vektoren, deklariert als:
%Vor% und Zugriff über matrix[i][j] ist zwischen 5% und 100% langsamer für den Zugriff als ein Array, das als:
wird über eine Inline-Indexfunktion matrix[index(i,j)] aufgerufen, wobei index(i,j) zu i + n * j ausgewertet wird. Andere Möglichkeiten, ein 2-D-Array ohne STL anzuordnen - ein Array von n Zeigern am Anfang jeder Zeile oder das gesamte Ding auf dem Stack als konstante Größe matrix[n][n] - laufen mit fast genau der gleichen Geschwindigkeit wie der Index Funktionsmethode.
Kürzlich erschienene GCC-Versionen (& gt; 4.0) scheinen in der Lage zu sein, den STL-Vektorenvektor bei Aktivierung von Optimierungen fast mit der gleichen Effizienz wie der Nicht-STL-Code zu kompilieren, aber dies ist etwas maschinenabhängig / p>
Ich möchte STL wenn möglich verwenden, muss aber die schnellste Lösung wählen. Hat jemand Erfahrung in der Optimierung von STL mit GCC?
Wenn Sie GCC verwenden, kann der Compiler Ihre Matrixzugriffe analysieren und in bestimmten Fällen die Reihenfolge im Speicher ändern. Das magische Compiler-Flag ist definiert als:
%Vor%Führen Sie die Matrixabflachung und transponierend. Matrixabflachung versucht eine m-dimensionale Matrix durch ersetzen seine äquivalente n-dimensionale Matrix, wo n & lt; m. Dies reduziert das Niveau von Indirektion für den Zugriff auf die benötigt Elemente der Matrix. Der Zweite Optimierung ist Matrix-Transponierung das versucht, die Reihenfolge zu ändern die Dimensionen der Matrix um Cache-Lokalität verbessern. Beide Optimierungen brauchen ein ganzes Programm Flagge. Transponieren ist nur aktiviert, wenn Profilinformationen sind verfügbar.
Beachten Sie, dass diese Option nicht von -O2 oder -O3 aktiviert wird. Sie müssen es selbst passieren.
Meine Annahme wäre die schnellste ist, für eine Matrix, 1D STL-Array zu verwenden und überschreiben Sie den Operator (), um es als 2D-Matrix zu verwenden.
Die STL definiert jedoch auch einen Typ speziell für nicht resizierbare numerische Arrays: valarray. Sie haben auch verschiedene Optimierungen für In-Place-Operationen.
valarray akzeptiert als Argument einen numerischen Typ:
%Vor%Dann können Sie Slices, indirekte Arrays, ... verwenden und natürlich können Sie das valarray erben und Ihren eigenen Operator () (int i, int j) für 2D-Arrays definieren ...
Sehr wahrscheinlich ist dies ein Ort der Referenzfrage. vector verwendet new , um sein internes Array zuzuweisen, so dass jede Zeile aufgrund des Headers jedes Blocks mindestens ein wenig auseinander liegt; Es könnte eine große Entfernung sein, wenn der Speicher bereits fragmentiert ist, wenn Sie sie zuordnen. Unterschiedliche Zeilen des Arrays verursachen wahrscheinlich mindestens einen Cache-Line-Fehler und könnten einen Seitenfehler verursachen; Wenn Sie wirklich Pech haben, können zwei benachbarte Zeilen auf Speicherzeilen liegen, die sich einen TLB-Steckplatz teilen, und der Zugriff auf einen wird den anderen vertreiben.
Im Gegensatz dazu garantieren Ihre anderen Lösungen, dass alle Daten benachbart sind. Es könnte Ihre Leistung unterstützen, wenn Sie die Struktur so ausrichten, dass sie so wenig Cache-Zeilen wie möglich kreuzt.
vector wurde für resizierbare Arrays entworfen. Verwenden Sie ein reguläres C ++ - Array, wenn Sie die Größe der Arrays nicht ändern müssen. STL-Operationen können im Allgemeinen mit C ++ - Arrays arbeiten.
Stellen Sie sicher, dass Sie das Array in der richtigen Richtung führen, d. h. über (aufeinanderfolgende Speicheradressen) statt nach unten. Dies wird Cache-Fehler reduzieren.
Meine Empfehlung wäre, Boost.UBLAS zu verwenden, das schnelle Matrix- / Vektorklassen bietet.
Um fair zu sein, hängt von den Algorithmen ab, die Sie für die Matrix verwenden.
Das Format doppelter Name [n * m] ist sehr schnell, wenn Sie auf Daten mit Zeilen zugreifen, weil es neben einer Multiplikation und Addition fast keinen Overhead gibt und weil Ihre Zeilen gepackte Daten sind, die im Cache kohärent sind.
>Wenn Ihre Algorithmen auf spaltensortierte Daten zugreifen, haben andere Layouts möglicherweise eine viel bessere Cache-Kohärenz. Wenn Ihr Algorithmus auf Daten in Quadranten der Matrix zugreift, können sogar andere Layouts besser sein.
Versuchen Sie, etwas über die Art der Nutzung und die Algorithmen zu erfahren, die Sie verwenden. Das ist besonders wichtig, wenn die Matrix sehr groß ist, da Cachefehlschläge Ihre Leistung viel mehr verletzen können als 1 oder 2 zusätzliche mathematische Operationen, um auf jede Adresse zuzugreifen.
Ich habe dies einige Zeit für rohe Bilder getan, indem ich meine eigenen zweidimensionalen Array-Klassen deklariert habe.
In einem normalen 2D-Array greifen Sie auf die Elemente wie folgt zu:
Array [2] [3]. Um diesen Effekt zu erhalten, müssten Sie ein Klassen-Array mit einem Überladen haben [] Array-Accessor. Aber dies würde im Wesentlichen ein anderes Array zurückgeben und somit geben du die zweite Dimension.
Das Problem bei diesem Ansatz ist, dass es einen doppelten Funktionsaufruf-Overhead hat.
Die Art und Weise, wie ich es gemacht habe, war die Verwendung der () Stilüberladung.
Also statt Array [2] [3], ändern Ich hatte es tun, dieses Stil-Array (2,3).
Die Funktion () war sehr klein und ich stellte sicher, dass sie inline war.
Siehe diesen Link für das allgemeine Konzept davon: Ссылка
Sie können den Typ bei Bedarf anpassen.
Der Unterschied war, dass mein Array dynamisch war. Ich hatte einen Speicherblock, den ich deklarieren würde. Und ich verwendete einen Spaltencache, also wusste ich, wo in meiner Bytefolge die nächste Zeile begann. Der Zugriff wurde für den Zugriff auf benachbarte Werte optimiert, da ich ihn für die Bildverarbeitung verwendete.
Es ist schwer zu erklären, ohne den Code, aber im Wesentlichen war das Ergebnis so schnell wie C und viel einfacher zu verstehen und zu verwenden.
Tags und Links optimization c++ gcc linux stl