Leistung eines zweidimensionalen Arrays im Vergleich zu einem 1-dimensionalen Array

Gibt es in C einen zeitlichen und räumlichen Unterschied zwischen einem zweidimensionalen m×n-Array und einem eindimensionalen Array der Länge m×n (für große Werte von m und n)? Wird der Zugriff auf Elemente mit einem eindimensionalen Array schneller sein?

In C sind zweidimensionale Arrays nur ein ordentliches Indizierungsschema für eindimensionale Arrays. Genau wie bei einem 1D-Array weisen 2D-Arrays einen einzelnen Block zusammenhängenden Speichers zu, und die A[row][col] Notation ist ähnlich wie Sprichwort A[row*NCOLS+col].

Wenn Sie Ihre eigenen mehrdimensionalen Arrays mit eindimensionalen Arrays implementieren würden, würden Sie normalerweise eine Indizierungsfunktion schreiben:

int getIndex(int row, int col) { return row*NCOLS+col; }

Unter der Annahme, dass Ihr Compiler diese Funktion integriert, wäre die Leistung hier genau die gleiche, als ob Sie die eingebaute „Indizierungsfunktion“ von 2D-Arrays verwenden würden.

Um zu zeigen:

#define NROWS 10
#define NCOLS 20

Dies:

int main(int argc, char *argv[]) {
    int myArr[NROWS*NCOLS];
    for (int i=0; i<NROWS; ++i) {
       for (int j=0; j<NCOLS; ++j) {
          myArr[getIndex(i,j)] = i+j;
       }
    }
    return 0;
}

Sollte genauso funktionieren:

int main(int argc, char *argv[]) {
    int myArr[NROWS][NCOLS];
    for (int i=0; i<NROWS; ++i) {
       for (int j=0; j<NCOLS; ++j) {
          myArr[i][j] = i+j;
       }
    }
    return 0;
}

Wie AraK jedoch betonte, wenn Sie viel in Zeilen herumspringen und die Zeilen sehr groß sind, könnten Sie viele Seitenfehler treffen … in diesem Fall könnte die benutzerdefinierte Indexierungsfunktion (mit vertauschten Zeilen und Spalten) hilfreich sein , aber Sie könnten auch einfach ändern, welche der Dimensionen in einem zweidimensionalen Array Sie als Zeilen und welche als Spalten behandeln.

Wenn Sie das sogenannte zweidimensionale Array in C verwenden, übernimmt der Compiler die Abbildung in ein eindimensionales Array für Sie. Wenn Sie ein eindimensionales Array verwenden und es gerne als zweidimensional behandeln möchten, müssen Sie das Mapping selbst schreiben.

Das Einzige, worauf Sie achten müssen, ist, dass Sie zeilenweise auf das Array zugreifen, da der C-Compiler Ihr zweidimensionales Array Zeile für Zeile speichert. Wenn Sie spaltenweise auf ein “großes” zweidimensionales Array zugreifen, treten wahrscheinlich Seitenfehler auf. Selbst wenn Sie in einer Sprache programmieren, die nur eindimensionale Arrays unterstützt, können Sie die Zuordnung problemlos in eine beliebige Anzahl von Dimensionen schreiben.

Werfen Sie einen Blick auf diesen Wikipedia-Artikel, wenn Sie das tun möchten zeilenweise zuordnen. Ihre Zuordnung könnte spaltenweise erfolgen, wie beispielsweise FORTRAN-Matrizen.

Robert hat recht. Indizierungsausdrücke werden in arithmetische Zeigerausdrücke kompiliert, daher gibt es keinen Unterschied.

Was jedoch Auswirkungen haben kann, ist die Zugriffsreihenfolge, und daher möchten Sie möglicherweise Dinge selbst implementieren, damit Sie die Zugriffsreihenfolge steuern können. Zum Beispiel Spalten zuerst vs. Zeilen zuerst bilden.

Bei modernen Prozessoren kann der Zugriff auf große Arrays mit unterschiedlichen Schritten zu unerwarteten Leistungsunterschieden führen. Der sequentielle Zugriff ist immer am schnellsten, und andere Schritte können aufgrund von Cache-Interaktionen bis zu 30-mal langsamer sein. Mehrdimensionale Arrays, bei denen die inneren Dimensionen eine Zweierpotenz sind, weisen häufig eine schlechte Leistung auf, da sie mit der Cache-Assoziativität interagieren. Um diese Probleme zu verstehen, gibt es keinen wirklichen Ersatz für Messungen.

Ich glaube nicht, dass es einen Unterschied gibt. Intern behandelt c ein zweidimensionales Array wie mehrere aufeinander folgende eindimensionale Arrays.

Wie bei allen Leistungsmerkmalen kann Ihre Laufleistung jedoch variieren. Es kann eine Art subtilen Unterschied in der Zeigerarithmetik geben. Führen Sie zeitgesteuerte Tests für beide Szenarien durch. Wer schneller läuft, gewinnt.

Wie von anderen gesagt, besteht der Unterschied wirklich darin, wie Sie auf Ihre Elemente zugreifen: Was zählt, ist, wie Ihre Elemente im Speicher angeordnet sind, der zumindest auf gängigen Architekturen linear ist. Alles, was Sie also wirklich haben, ist ein 1d-Array, das 2d usw. … ist “nur” eine Annehmlichkeit, und ein vernünftiger Compiler sollte die Indizierung optimieren – aber in der Praxis scheitern Compiler häufig an Arch, sobald Sie mehr als ein paar Variablen haben wie x86 wegen des Registerhungers.

Nun, es hängt von Ihrer Anwendung ab, aber ich denke, Sie sollten standardmäßig mit einem 1D-Layout nachdenken, insbesondere wenn Sie mehrere Dimensionen verarbeiten müssen. Das erste Problem mit mehrdimensionalen Arrays in C besteht darin, dass Sie sie nicht dynamisch zuweisen können. Wenn Sie zeilenweise zuweisen, haben Sie eine schreckliche Leistung, da Sie kein zusammenhängendes Stück Speicher haben. Siehe die FFTW-Dok für Details dazu.

Beachten Sie, dass Sie Ihr einzelnes Stück Speicher immer mit einer praktischen Array-Indizierung darüber beschreiben können (Sie weisen einen großen nxm-Speicherblock zu und erstellen dann ein Array aus n Zeigern für jede Zeile).

Ich vermute nur, aber ich würde sagen, dass ein 1D-Array schneller ist als ein 2D-Array. Es wäre jedoch nicht messbar schneller. Etwa 1.000.000,01 $ sind mehr als 1.000.000 $.

Ich würde alles verwenden, was einfacher zu codieren ist.