Cache-Optimized Row-Major Array Indexing

Snippet

Cache-Optimized Row-Major Array Indexing

Modern CPUs use caches to speed up memory access. By flattening a 2D array into a 1D vector and using Row-Major indexing (incrementing columns in the inner loop), we ensure contiguous memory access, which maximizes cache hits and drastically improves performance.

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;
}

Breakdown

data(Rows * Cols)

Allocates a single contiguous block of memory for the entire matrix.

r * Cols + c

Calculates the linear index. Accessing this in sequence follows the physical memory layout.

Previous snippet Next snippet

More Expert C++ exercises →

From your library

Cache-Optimized Row-Major Array Indexing

Related