2.4 Direkter Zugriff auf den Speicher für ein 2-dim Array
Contents
2.4 Direkter Zugriff auf den Speicher für ein 2-dim Array#
C++ erlaubt direkten Zugriff auf den Speicher. Dies kann Probleme nach sich ziehen und erfordert zusätzlich die explizite Verwaltung von Speicher. Aber als Vorteil erlaubt dies Funktionen sehr effizient zu implementieren und die zugrunde liegende Struktur im Speicher auch auszunutzen.
Dies soll im folgenden an einem Beispiel deutlich gemacht werden, in dem ein Bild in den Speicher geladen wird. Als Nutzer und Programmierer abstrahieren wir ein Bild als zwei-dimensionales Feld von Pixeln (bzw. mehr-dimensional wenn wir vers. Farbwerte betrachten). Im Speicher wird dies aber als ein großer 1-dimensionaler Array angelegt.
Im folgenden sollen sie nun dies Programm untersuchen und dann eine Funktion schreiben, die den mittleren Grauwert des Bildes errechnet. Dabei sollen sie drei unterschiedliche Varianten nutzen:
eine Variante, in der das eingelesene Bild zuerst Zeilen-weise und dann Spalten-weise durchlaufen wird;
eine Variante, in der das eingelesene Bild dagegegn zuerst Spalten-weise und dann Zeilen-weise durchlaufen wird;
eine Variante, die direkt das ursprüngliche ein-dimensionale Array durchläuft.
Für die verschiedenen Varianten sollen die Laufzeiten geprüft werden – dazu wird die Funktion jeweils vielfach aufgerufen und dies wird über einen einfachen zeitlichen Zugriff realisiert.
Was beobachten sie?
ToDo:
Erzeugen sie ein eindimensionales Array von der Größe
int*und reservieren den Speicher übernew.Erzeugen sie ein zweidimensionales Array der Größe
int**sein und somit Pointer auf weitere Arrays (die einzelnen Zeilen) enthalten.Befüllen sie die beiden Arrays mit beliebigen Werten.
Click to show
#include <iostream>
int main()
{
int square_dim = 1000; // Dimension der quadratischen Matrix
int* data = new int[square_dim * square_dim]; // Dynamische Speicherzuweisung für ein eindimensionales Array
int** image = new int*[square_dim]; // Dynamische Speicherzuweisung für ein zweidimensionales Array
for (int i = 0; i < (square_dim * square_dim); i++) {
data[i] = i; // Daten in das eindimensionale Array data schreiben
}
for (int i = 0; i < square_dim; i++) {
image[i] = new int[square_dim]; // Dynamische Speicherzuweisung für die Zeilen des zweidimensionalen Arrays image
for (int j = 0; j < square_dim; j++) {
image[i][j] = i * square_dim + j; // Daten in das zweidimensionale Array image schreiben
}
}
std::cout << data[1001] << std::endl; // Ausgabe des Wertes an der Indexposition 1001 im Array data
std::cout << image[1][1] << std::endl; // Ausgabe des Wertes an der Position (1, 1) im Array image
delete[] data; // Speicher freigeben, der mit new[] reserviert wurde
for (int i = 0; i < square_dim; i++) {
delete[] image[i]; // Speicher für jede Zeile freigeben
}
delete[] image; // Speicher freigeben, der mit new[] reserviert wurde
return 0;
}
main()
Nun soll der Durchschnittseintrag über den verschiedenen Arrays berechnet werden. Dabei soll der zweidimensionale Array unterschiedlich durchlaufen werden:
zeilenweise
spaltenweise
Was beobachten sie in den Laufzeiten (dies müssen sie vermutlich ein paar mal wiederholen).
Click to show
#include <iostream>
#include <chrono>
int main_zeilen()
{
int square_dim = 1000; // Dimension der quadratischen Matrix
int* data = new int[square_dim * square_dim]; // Dynamische Speicherzuweisung für ein eindimensionales Array
int** image = new int*[square_dim]; // Dynamische Speicherzuweisung für ein zweidimensionales Array
for (int i = 0; i < (square_dim * square_dim); i++) {
data[i] = i; // Daten in das eindimensionale Array data schreiben
}
for (int i = 0; i < square_dim; i++) {
image[i] = new int[square_dim]; // Dynamische Speicherzuweisung für die Zeilen des zweidimensionalen Arrays image
for (int j = 0; j < square_dim; j++) {
image[i][j] = i * square_dim + j; // Daten in das zweidimensionale Array image schreiben
}
}
auto start = std::chrono::high_resolution_clock::now(); // Startzeitpunkt für die Zeitmessung
long long sum; // Variable für die Summe
for (int iter = 0; iter < 1000; iter++) { // Schleife für 1000 Iterationen
sum = 0; // Summe zurücksetzen
for(int h=0; h<square_dim; h++) { // Schleife für Zeilen
for(int w=1; w<square_dim; w++) { // Schleife für Spalten
sum += image[h][w]; // Wert zum Summe addieren
}
}
}
auto end = std::chrono::high_resolution_clock::now(); // Endzeitpunkt für die Zeitmessung
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start); // Dauer der Zeitmessung berechnen
std::cout << "Execution time: " << duration.count() << " us" << std::endl; // Ausgabe der Zeitmessung in Mikrosekunden
std::cout << sum / (square_dim * square_dim) << std::endl; // Durchschnitt berechnen und ausgeben
delete[] data; // Speicher freigeben, der mit new[] reserviert wurde
for (int i = 0; i < square_dim; i++) {
delete[] image[i]; // Speicher für jede Zeile freigeben
}
delete[] image; // Speicher freigeben, der mit new[] reserviert wurde
return 0;
}
main_zeilen()
Click to show
#include <iostream>
#include <chrono>
int main_spalten()
{
int square_dim = 1000; // Dimension der quadratischen Matrix
int* data = new int[square_dim * square_dim]; // Dynamische Speicherzuweisung für ein eindimensionales Array
int** image = new int*[square_dim]; // Dynamische Speicherzuweisung für ein zweidimensionales Array
for (int i = 0; i < (square_dim * square_dim); i++) {
data[i] = i; // Daten in das eindimensionale Array data schreiben
}
for (int i = 0; i < square_dim; i++) {
image[i] = new int[square_dim]; // Dynamische Speicherzuweisung für die Zeilen des zweidimensionalen Arrays image
for (int j = 0; j < square_dim; j++) {
image[i][j] = i * square_dim + j; // Daten in das zweidimensionale Array image schreiben
}
}
auto start = std::chrono::high_resolution_clock::now(); // Startzeitpunkt für die Zeitmessung
long long sum; // Variable für die Summe
for (int iter = 0; iter < 1000; iter++) { // Schleife für 1000 Iterationen
sum = 0; // Summe zurücksetzen
for(int w=0; w<square_dim; w++) {
for(int h=1; h<square_dim; h++) {
sum += image[h][w];
//image[h][w] = (1-a)*image[h][w] + a*image[h-1][w];
}
}
}
auto end = std::chrono::high_resolution_clock::now(); // Endzeitpunkt für die Zeitmessung
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start); // Dauer der Zeitmessung berechnen
std::cout << "Execution time: " << duration.count() << " us" << std::endl; // Ausgabe der Zeitmessung in Mikrosekunden
std::cout << sum / (square_dim * square_dim) << std::endl; // Durchschnitt berechnen und ausgeben
delete[] data; // Speicher freigeben, der mit new[] reserviert wurde
for (int i = 0; i < square_dim; i++) {
delete[] image[i]; // Speicher für jede Zeile freigeben
}
delete[] image; // Speicher freigeben, der mit new[] reserviert wurde
return 0;
}
main_spalten()
Beobachtungen#
In C++ werden zweidimensionale Arrays intern üblicherweise als Array von Arrays (als Zeiger auf Zeiger) implementiert, bei dem der Speicher für die Elemente zeilenweise reserviert wird. Das bedeutet, dass die Elemente einer Zeile im Speicher direkt nacheinander angeordnet sind und aufeinanderfolgende Zeilen im Speicher auch nacheinander angeordnet sind.
Daher ist das Durchlaufen des Arrays in derselben Reihenfolge wie die Speicheranordnung (zeilenweise) in der Regel effizienter, da auf aufeinanderfolgende Speicheradressen zugegriffen wird, was zu besserer räumlicher Lokalität führt. Dies kann die Cache-Leistung verbessern und zu schnellerem Zugriff auf die Array-Elemente führen.
Im Vergleich dazu kann das Durchlaufen des Arrays in der entgegengesetzten Reihenfolge (spaltenweise) zu schlechterer räumlicher Lokalität führen, da auf nicht zusammenhängende Speicheradressen zugegriffen wird, was zu mehr Cache-Misses und langsamerem Zugriff auf die Array-Elemente führen kann.
Der genaue Unterschied in der Leistung hängt aber von verschiedenen Faktoren ab: wie der Größe des Arrays, der Hardwarearchitektur des Systems, dem verwendeten Compiler und Optimierungen sowie dem spezifischen Zugriffsmuster und den Berechnungen im Code. Daher ist es ratsam, die Leistung des Codes in Bezug auf die Speicherzugriffsmuster zu analysieren und zu optimieren, um die besten Ergebnisse zu erzielen.