Introducción
En un post anterior discutíamos la importancia de garantizar la localidad espacial y temporal de nuestros programas, dado el modo de funcionamiento de la jerarquía de memoria. Analizaremos aquí un test clásico que demuestra la latencia asociada al acceso a niveles inferiores de dicha jerarquía mediante el empleo simple de una matriz cuadrada 2-dimensional de enteros, de tamaño N = L1Size/sizeof(int), cuyas filas encajen en la memoria caché L1. La representación en memoria de dicha matriz puede lograrse a través de un vector std::vector<int>(N*N) de elementos contiguos en memoria o, si el tamaño de la pila de usuario lo permitiese, un array de arrays std::array<std::array<int,N>,N>{}. En ambos casos, asumiremos la representación Row-major propia de C y C++, en la que las entradas de una misma fila son adyacentes en memoria.
En un post anterior discutíamos la importancia de garantizar la localidad espacial y temporal de nuestros programas, dado el modo de funcionamiento de la jerarquía de memoria. Analizaremos aquí un test clásico que demuestra la latencia asociada al acceso a niveles inferiores de dicha jerarquía mediante el empleo simple de una matriz cuadrada 2-dimensional de enteros, de tamaño N = L1Size/sizeof(int), cuyas filas encajen en la memoria caché L1. La representación en memoria de dicha matriz puede lograrse a través de un vector std::vector<int>(N*N) de elementos contiguos en memoria o, si el tamaño de la pila de usuario lo permitiese, un array de arrays std::array<std::array<int,N>,N>{}. En ambos casos, asumiremos la representación Row-major propia de C y C++, en la que las entradas de una misma fila son adyacentes en memoria.
Nota: En un orden Row-mayor, la matriz
[1 2 3][A] = [4 5 6][7 8 9]
queda representada en memoria como la secuencia [1 2 3 4 5 6 7 8 9]. Comparemos esta representación con la obtenida con un orden de tipo Column-major:[1 4 7 2 5 8 3 6 9].
Consideremos una matriz cuadrada Row-major de tamaño N = L1Size/sizeof(int) en la que todas sus entradas enteras sean iguales a la unidad. Si la recorriésemos en el orden natural con el fin de calcular la suma de las entradas –aumentando progresivamente el índice de fila de forma que, para cada una de ellas, recorramos el rango de columnas–, las filas de la matriz permanecerían durante un tiempo elevado en la caché L1, aumentando enormemente el rendimiento del proceso. Nos referiremos a este orden de acceso como Row-wise traversing.
Por el contrario, si optáramos por recorrer la matriz en orden opuesto, es decir, aumentando progresivamente el índice de columna para, fijado uno de ellos, recorrer el rango de índices de fila, produciríamos un cache miss en cada operación de lectura, obligando al procesador a acceder constantemente a niveles inferiores de la jerarquía de memoria. Nos referiremos a este orden como Column-wise traversing.
El siguiente código, 100% conforme con el estándar C++17, demuestra este comportamiento.
Código
En primer lugar, definamos una plantilla de clase que implemente la funcionalidad básica de una matriz 2-dimensional Row-major alojada en el free store, garantizando la localización contigua de sus entradas en memoria. Las clases privadas proxy permiten la indexación tradicional de entradas de la matriz con dobles corchetes; por ejemplo, m[4][2] accedería a la intersección de la quinta fila con la tercera columna de la matriz m:
Código
En primer lugar, definamos una plantilla de clase que implemente la funcionalidad básica de una matriz 2-dimensional Row-major alojada en el free store, garantizando la localización contigua de sus entradas en memoria. Las clases privadas proxy permiten la indexación tradicional de entradas de la matriz con dobles corchetes; por ejemplo, m[4][2] accedería a la intersección de la quinta fila con la tercera columna de la matriz m:
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
template<typename T>
class Matrix {
public:
using size_type = typename vector<T>::size_type;
using value_type = T;
Matrix(size_type rows, size_type cols, value_type val = value_type{})
: data_(rows*cols, val), cols_{cols} { }
auto operator[](size_type row) {
return Index_proxy{data_, row*cols_};
}
auto operator[](size_type row) const {
return Index_proxy_const{data_, row*cols_};
}
auto rows() const noexcept { return data_.size()/cols_; }
auto cols() const noexcept { return cols_; }
private:
vector<T> data_;
size_type cols_;
class Index_proxy {
vector<T>& data_ref_;
size_type const offset_;
public:
Index_proxy(vector<T>& data, size_type offset)
: data_ref_{data}, offset_{offset} { }
auto& operator[](size_type col) { return data_ref_[offset_ + col]; }
};
class Index_proxy_const {
vector<T> const& data_ref_;
size_type const offset_;
public:
Index_proxy_const(vector<T> const& data, size_type offset)
: data_ref_{data}, offset_{offset} { }
auto const& operator[](size_type col) const {
return data_ref_[offset_ + col];
}
};
};
// ...
A continuación, diseñemos una plantilla de función que genere una matriz cuadrada con entradas iguales a la unidad y de tamaño coincidente con la capacidad de la caché L1, con el fin de realizar el test descrito anteriormente. El modo de operación deseado (Row- o Column-wise traversing) podrá ser especificado como parámetro de la plantilla (enum class en el papel de non-type template parameter), mientras que la función admitirá el tamaño en bytes de la caché como único argumento de invocación. La función recorrerá la matriz según el orden indicado para calcular la suma de sus entradas, midiendo el tiempo total del proceso:
enum class Traverse : bool { Col_wise, Row_wise };
template<Traverse Trv>
auto l1_cache_test(int l1_size) -> int
{
using namespace std::chrono;
using sz_t = Matrix<int>::size_type;
// create a square matrix in the free store whose rows fit into L1 cache:
auto const n = l1_size / sizeof(int);
auto const square_matrix = Matrix<int>{n, n, 1}; // nxn entries equal to 1
auto sum = 0;
auto const start = steady_clock::now();
for (auto i = sz_t{}; i < n; ++i) {
for (auto j = sz_t{}; j < n; ++j)
if constexpr (Trv == Traverse::Row_wise)
sum += square_matrix[i][j]; // (R)
else // Col_wise
sum += square_matrix[j][i]; // (C)
}
cout << duration_cast<milliseconds>(steady_clock::now() - start).count()
<< " millisecs\n";
return sum;
}
// ...
La sentencia de control if constexpr del código anterior se resuelve condicionalmente en tiempo de compilación en base al modo de operación, insertando en nuestro código la línea (R) o (C) según corresponda y desechando la opuesta, sin afectar al tiempo de ejecución de la función.
La siguiente función principal main() ejecuta secuencialmente el test en modo Row-wise y Column-wise, imprimiendo en pantalla los tiempos de ejecución de cada proceso. En el caso de un procesador Intel(R) Core(TM) i5-6200U a 2.3GHz, con una L1 Data Cache de 32KiB en cada núcleo, y trabajando con el compilador GCC 8.1 con un nivel de optimización -O2, el tiempo típico de ejecución en Row-wise es de 50 milisegundos, mientras que en Column-wise es de ¡aproximadamente un segundo!
auto main() -> int
{
auto const l1_size = 32'768; // L1 data chache size: 32 KiB
cout << "Row-wise traversing: ";
auto const val1 = l1_cache_test<Traverse::Row_wise>(l1_size);
cout << "Col-wise traversing: ";
auto const val2 = l1_cache_test<Traverse::Col_wise>(l1_size);
cout << "Sum: " << val1 << ", equal: " << (val1 == val2);
}
Referencias bibliográficas:
Para un análisis más detallado del funcionamiento de la jerarquía de memoria, te recomiendo:
- Bryant R. E. and O'Hallaron D. R., Computer Systems: A Programmer's Perspective. Second edition. Addison-Wesley, 2010.
- Sehr V. and Andrist B., C++ High Performance. Packt Publishing Ltd, 2018.
El código considerado en este post se inspira en los ejemplos proporcionados en la página 587 de la primera obra y, en mayor medida, en la página 92 de la segunda.
No hay comentarios:
Publicar un comentario