Snippet

Cache-optimierte Row-Major-Array-Indizierung

Moderne CPUs nutzen Caches, um den Speicherzugriff zu beschleunigen. Indem wir ein 2D-Array in einen 1D-Vektor abflachen und die Row-Major-Indizierung verwenden (Erhöhung der Spalten in der inneren Schleife), gewährleisten wir einen zusammenhängenden Speicherzugriff, was Cache-Hits maximiert und die Leistung drastisch verbessert.

snippet.cpp

cpp

#include <iostream>
#include <vector>
 
template<typename T, std::size_t Rows, std::size_t Cols>
class Matrix {
    std::vector<T> data;
public:
    Matrix() : data(Rows * Cols) {}
 
    // Row-major access: data[r * Cols + c]
    T& at(std::size_t r, std::size_t c) {
        return data[r * Cols + c];
    }
 
    void sum_rows() {
        T total = 0;
        for (std::size_t r = 0; r < Rows; ++r) {
            for (std::size_t c = 0; c < Cols; ++c) {
                total += at(r, c); // Spatially local access
            }
        }
    }
};
 
int main() {
    Matrix<int, 1000, 1000> m;
    m.sum_rows();
    return 0;
}

Erklärung

data(Rows * Cols)

Allokiert einen einzigen zusammenhängenden Speicherblock für die gesamte Matrix.

r * Cols + c

Berechnet den linearen Index. Der sequentielle Zugriff darauf folgt dem physikalischen Speicherlayout.

Vorheriges Snippet Nächstes Snippet

Mehr C++-Übungen für Experten →

Cache-optimierte Row-Major-Array-Indizierung

Verwandt