Las plantillas de expresión son una técnica de metaprogramación de plantillas de C++ que construye estructuras que representan un cálculo en tiempo de compilación, donde las expresiones se evalúan solo cuando es necesario para producir código eficiente para todo el cálculo. [1] Por lo tanto, las plantillas de expresión permiten a los programadores eludir el orden normal de evaluación del lenguaje C++ y lograr optimizaciones como la fusión de bucles .
Las plantillas de expresión fueron inventadas independientemente por Todd Veldhuizen y David Vandevoorde; [2] [3] fue Veldhuizen quien les dio su nombre. [3] Son una técnica popular para la implementación de software de álgebra lineal . [1]
Considere una biblioteca que represente vectores y operaciones con ellos. Una operación matemática común es sumar dos vectores u y v , elemento por elemento, para producir un nuevo vector. La implementación obvia de C++ de esta operación sería una función sobrecargada operator+ que devuelva un nuevo objeto vectorial:
/// Clase @brief que representa un vector matemático 3Dclase Vec : público std :: matriz < double , 3 > { público : usando std :: array < double , 3 >:: array ; // heredar constructor (C++11) // ver https://en.cppreference.com/w/cpp/language/using_declaration};/// @brief suma 'u' y 'v' en una nueva instancia de VecOperador Vec + ( Vec const & u , Vec const & v ) { suma vec ; para ( tamaño_t i = 0 ; i < u . tamaño (); i ++ ) { suma [ i ] = u [ i ] + v [ i ]; } devuelve suma ; }Los usuarios de esta clase ahora pueden escribir Vec x = a + b;donde ay bson ambas instancias de Vec.
Un problema con este enfoque es que las expresiones más complicadas como Vec x = a + b + cse implementan de manera ineficiente. La implementación primero produce un elemento temporal Vecpara contener a + by luego produce otro Veccon los elementos de cagregados. Incluso con la optimización del valor de retorno, esto asignará memoria al menos dos veces y requerirá dos bucles.
La evaluación retrasada resuelve este problema y se puede implementar en C++ permitiendo que operator+se devuelva un objeto de un tipo auxiliar, por ejemplo VecSum, que representa la suma no evaluada de dos Vecs, o un vector con un VecSum, etc. Las expresiones más grandes luego construyen efectivamente árboles de expresión que se evalúan solo cuando se asignan a una Vecvariable real. Pero esto requiere recorrer dichos árboles para realizar la evaluación, lo que en sí mismo es costoso. [4]
Las plantillas de expresión implementan la evaluación retrasada mediante árboles de expresión que solo existen en tiempo de compilación. Cada asignación a un Vec, como Vec x = a + b + c, genera un nuevo Vecconstructor si es necesario para la instanciación de la plantilla. Este constructor opera en tres Vec; asigna la memoria necesaria y luego realiza el cálculo. Por lo tanto, solo se realiza una asignación de memoria.
Ejemplo de implementación de plantillas de expresión:
Un ejemplo de implementación de plantillas de expresión se parece al siguiente. Una clase base VecExpressionrepresenta cualquier expresión con valor vectorial. Se basa en el tipo de expresión real Eque se va a implementar, según el patrón de plantilla curiosamente recurrente . La existencia de una clase base como VecExpressionno es estrictamente necesaria para que funcionen las plantillas de expresión. Simplemente servirá como un tipo de argumento de función para distinguir las expresiones de otros tipos (observe la definición de un Vecconstructor y operator+más abajo).
plantilla < typename E > clase VecExpression { público : constexpr estático bool is_leaf = falso ; operador doble []( size_t i ) const { // Delegación al tipo de expresión real. Esto evita el polimorfismo dinámico (también conocido como funciones virtuales en C++) devolver static_cast < E const &> ( * this )[ i ]; } tamaño_t tamaño () const { return static_cast < E const &> ( * this ). tamaño (); } };El booleano is_leafestá ahí para etiquetar VecExpressionlos s que son "hojas", es decir, que realmente contienen datos. La Vecclase es una hoja que almacena las coordenadas de una expresión vectorial completamente evaluada y se convierte en una subclase de VecExpression.
clase Vec : pública VecExpression < Vec > { std :: matriz < doble , 3 > elementos ; público : constexpr estático bool is_leaf = verdadero ; decltype ( auto ) operador []( size_t i ) const { return elems [ i ]; } decltype ( auto ) y operador []( tamaño_t i ) { devolver elementos [ i ]; } tamaño_t tamaño () const { return elems . tamaño (); } // Construye Vec usando la lista de inicializadores Vec ( std :: lista_de_inicializadores < double > init ) { std :: copiar ( init.begin () , init.end ( ) , elems.begin ( ) ) ; } // Se puede construir un Vec a partir de cualquier VecExpression, forzando su evaluación. plantilla < typename E > Vec ( VecExpression < E > const & expr ) { para ( tamaño_t i = 0 ; i != expr . tamaño (); ++ i ) { elementos [ i ] = expr [ i ]; } }};La suma de dos Vecs se representa mediante un nuevo tipo, VecSum, que se basa en los tipos de los lados izquierdo y derecho de la suma para que pueda aplicarse a pares arbitrarios de Vecexpresiones. Una sobrecarga operator+sirve como azúcar sintáctica para el VecSumconstructor. En este caso interviene una sutileza: para hacer referencia a los datos originales al sumar dos VecExpressions, VecSumnecesita almacenar una referencia constante a cada uno si es una hoja, de lo contrario es un objeto temporal que necesita copiarse para guardarlo correctamente.VecExpression
plantilla < nombre_tipo E1 , nombre_tipo E2 > clase VecSum : pública VecExpression < VecSum < E1 , E2 > > { // cref si es hoja, copia en caso contrario tiponombre std :: condicional < E1 :: is_leaf , const E1 & , const E1 >:: tipo _u ; tiponombre std :: condicional < E2 :: is_leaf , const E2 & , const E2 >:: tipo _v ; público : constexpr estático bool is_leaf = falso ; VecSum ( E1 constante y u , E2 constante y v ) : _u ( u ), _v ( v ) { afirmar ( u . tamaño () == v . tamaño ()); } decltype ( auto ) operador []( tamaño_t i ) const { return _u [ i ] + _v [ i ]; } tamaño_t tamaño () const { return _v.tamaño ( ) ; } }; plantilla < nombre_tipo E1 , nombre_tipo E2 > SumaVec < E1 , E2 > operador + ( VecExpression < E1 > const & u , VecExpression < E2 > const & v ) { devuelve VecSum < E1 , E2 > ( * static_cast < const E1 *> ( & u ), * static_cast < const E2 *> ( & v )); }Con las definiciones anteriores, la expresión a + b + ces de tipo
VecSum < VecSum < Vec , Vec > , Vec > Por lo tanto, Vec x = a + b + cinvoca el Vecconstructor con plantilla Vec(VecExpression<E> const& expr)cuyo argumento de plantilla Ees de este tipo (es decir, VecSum<VecSum<Vec, Vec>, Vec>). Dentro de este constructor, el cuerpo del bucle
elementos [ i ] = expr [ i ]; se expande efectivamente (siguiendo las definiciones recursivas de operator+y operator[]sobre este tipo) a
elems [ i ] = a.elems [ i ] + b.elems [ i ] + c.elems [ i ] ; sin Vecnecesidad de objetos temporales y sólo una pasada por cada bloque de memoria.
Uso básico:
int principal () { Vecv0 = { 23,4 , 12,5 , 144,56 } ; Vec v1 = { 67,12 , 34,8 , 90,34 }; Vec v2 = { 34,90 , 111,9 , 45,12 }; // La siguiente asignación llamará al ctor de Vec que acepta el tipo de // `VecExpression<E> const&`. Luego expanda el cuerpo del bucle a // a.elems[i] + b.elems[i] + c.elems[i] Vec suma_de_tipo_vec = v0 + v1 + v2 ; para ( tamaño_t i = 0 ; i < suma_de_tipo_vec . tamaño (); ++ i ) std :: cout << suma_de_tipo_vec [ i ] << std :: endl ; // Para evitar crear almacenamiento adicional, aparte de v0, v1, v2 // se puede hacer lo siguiente (probado con C++11 en GCC 5.3.0) suma automática = v0 + v1 + v2 ; para ( tamaño_t i = 0 ; i < suma . tamaño (); ++ i ) std :: cout << suma [ i ] << std :: endl ; // Observe que en este caso typeid(sum) será VecSum<VecSum<Vec, Vec>, Vec> // y este encadenamiento de operaciones puede continuar.}Las plantillas de expresión han resultado especialmente útiles para los autores de bibliotecas para álgebra lineal, es decir, para trabajar con vectores y matrices de números. Entre las bibliotecas que emplean plantillas de expresión se encuentran Dlib , Armadillo , Blaze, [5] Blitz++ , [6] Boost uBLAS, [7] Eigen , [8] POOMA, [9] Stan Math Library , [10] y xtensor. [11] Las plantillas de expresión también pueden acelerar las implementaciones de diferenciación automática de C++ , [12] como se demuestra en la biblioteca Adept .
Fuera de las matemáticas vectoriales, el marco del analizador Spirit utiliza plantillas de expresión para representar gramáticas formales y compilarlas en analizadores.