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 según sea necesario para producir un código eficiente para todo el cálculo. [1] Las plantillas de expresión permiten a los programadores pasar por alto 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 de forma independiente 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]
Motivación y ejemplo
Considere una biblioteca que represente vectores y operaciones sobre ellos. Una operación matemática común es añadir dos vectores u y v , elemento a elemento, para producir un nuevo vector. La implementación obvia en C ++ de esta operación sería un operador sobrecargado + que devuelve un nuevo objeto vectorial:
class Vec { std :: vector < double > elems ; public : Vec ( tamaño_t n ) : elems ( n ) {} double & operator [] ( size_t i ) { return elems [ i ]; } operador doble [] ( size_t i ) const { return elems [ i ]; } size_t size () const { return elems . tamaño (); } }; Operador Vec + ( Vec const & u , Vec const & v ) { assert ( u . Size () == v . Size ()); Vec suma ( u . Tamaño ()); para ( tamaño_t i = 0 ; i < u . tamaño (); i ++ ) { suma [ i ] = u [ i ] + v [ i ]; } devolución de suma ; }
Los usuarios de esta clase ahora pueden escribir Vec x = a + b; dónde a y b son ambas instancias de Vec .
Un problema con este enfoque es que expresiones más complicadas como Vec x = a + b + c se implementan de manera ineficiente. La implementación primero produce un vector temporal para mantener a + b , luego produce otro vector con los elementos de c agregado. 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 ++ dejando operador + devuelve un objeto de un tipo personalizado, digamos VecSum , que representa la suma no evaluada de dos vectores, o un vector con un VecSum , etc. Las expresiones más grandes crean árboles de expresión que se evalúan solo cuando se asignan a un Variable vec . Pero esto requiere atravesar esos árboles para realizar la evaluación, lo que en sí mismo es costoso. [4]
Las plantillas de expresión implementan la evaluación retrasada utilizando árboles de expresión que solo existen en el momento de la compilación. Cada asignación a un Vec , como Vec x = a + b + c , genera un nuevo Constructor de Vec si lo necesita la instanciación de la plantilla. Este constructor opera en tres Vec ; asigna la memoria necesaria y luego realiza el cálculo. Por tanto, solo se realiza una asignación de memoria.
Un ejemplo de implementación de plantillas de expresión tiene el siguiente aspecto. Una clase base VecExpression representa cualquier expresión con valores vectoriales. Está basado en el tipo de expresión real. E se implementará, según el patrón de plantilla curiosamente recurrente . La existencia de una clase base como VecExpression no 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 constructor y operador Vec + a continuación).
plantilla < typename E >class VecExpression { publico : 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 ++) return static_cast < E const &> ( * this ) [ i ]; } size_t size () const { return static_cast < E const &> ( * esto ). tamaño (); }};
La La clase Vec todavía almacena las coordenadas de una expresión vectorial completamente evaluada y se convierte en una subclase de VecExpression .
class Vec : public VecExpression < Vec > { std :: vector < double > elems ; public : operador doble [] ( size_t i ) const { return elems [ i ]; } double & operator [] ( size_t i ) { return elems [ i ]; } size_t size () const { return elems . tamaño (); } Vec ( tamaño_t n ) : elems ( n ) {} // construye el vector usando la lista de inicializadores Vec ( std :: initializer_list < double > init ) : elems ( init ) {} // Un Vec se puede construir a partir de cualquier VecExpression, forzando su evaluación. plantilla < typename E > Vec ( VecExpression < E > const & expr ) : elems ( expr . size ()) { for ( size_t i = 0 ; i ! = expr . size (); ++ i ) { elems [ i ] = expr [ i ]; } } };
La suma de dos vectores está representada por un nuevo tipo, VecSum , que se basa en los tipos de los lados izquierdo y derecho de la suma para que se pueda aplicar a pares arbitrarios de expresiones vectoriales. Un sobrecargado operador + sirve como azúcar sintáctico para el Constructor VecSum .
plantilla < typename E1 , typename E2 >clase VecSum : pública VecExpression < VecSum < E1 , E2 > > { E1 const & _u ; E2 const & _v ;publico : VecSum ( E1 const & u , E2 const & v ) : _u ( u ), _v ( v ) { afirmar ( u . tamaño () == v . tamaño ()); } operador doble [] ( size_t i ) const { return _u [ i ] + _v [ i ]; } size_t size () const { return _v . tamaño (); }}; plantilla < typename E1 , typename E2 >VecSum < E1 , E2 >operador + ( VecExpression < E1 > const & u , VecExpression < E2 > const & v ) { return VecSum < E1 , E2 > ( * static_cast < const E1 *> ( & u ), * static_cast < const E2 *> ( & v ));}
Con las definiciones anteriores, la expresión a + b + c es de tipo
VecSum < VecSum < Vec , Vec > , Vec >
entonces Vec x = a + b + c invoca la plantilla Vec constructor con este tipo como su Argumento de plantilla E. Dentro de este constructor, el cuerpo del bucle
elems [ i ] = expr [ i ];
se expande efectivamente (siguiendo las definiciones recursivas de operador + y operador [] en este tipo) para
elems [ i ] = a . elems [ i ] + b . elems [ i ] + c . elems [ i ];
sin necesidad de vectores temporales y solo una pasada a través de cada bloque de memoria.
Uso básico:
int main () { Vec v0 = { 23,4 , 12,5 , 144,56 , 90,56 }; Vec v1 = { 67,12 , 34,8 , 90,34 , 89,30 }; Vec v2 = { 34,90 , 111,9 , 45,12 , 90,5 }; // La siguiente asignación llamará al ctor de Vec que acepta el tipo de // `VecExpression const &`. Luego expanda el cuerpo del bucle para // a.elems [i] + b.elems [i] + c.elems [i] Vec sum_of_vec_type = v0 + v1 + v2 ; para ( tamaño_t i = 0 ; i < suma_de_tipo_vec . tamaño (); ++ i ) std :: cout << sum_of_vec_type [ i ] << std :: endl ; // Para evitar crear almacenamiento adicional, que no sea 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 , Vec> // y este encadenamiento de operaciones puede continuar.}
Aplicaciones
Las plantillas de expresión han sido consideradas especialmente útiles por los autores de bibliotecas para álgebra lineal, es decir, para tratar con vectores y matrices de números. Entre las bibliotecas que emplean plantillas de expresión se encuentran Dlib , [5] Armadillo , Blaze , [6] Blitz ++ , [7] Boost uBLAS, [8] Eigen , [9] POOMA, [10] Stan Math Library , [11] y xtensor. [12] Las plantillas de expresión también pueden acelerar las implementaciones de diferenciación automática de C ++ , [13] como se demuestra en la biblioteca Adept .
Fuera de las matemáticas vectoriales, el marco del analizador de Spirit usa plantillas de expresión para representar gramáticas formales y compilarlas en analizadores.
Referencias
- ^ a b Matsuzaki, Kiminori; Emoto, Kento (2009). Implementación de esqueletos paralelos equipados con fusión mediante plantillas de expresión . Proc. Int'l Symp. sobre implementación y aplicación de lenguajes funcionales. págs. 72–89.
- ^ Vandevoorde, David; Josuttis, Nicolai (2002). Plantillas C ++: la guía completa . Addison Wesley . ISBN 0-201-73484-2.
- ^ a b Veldhuizen, Todd (1995). "Plantillas de expresión" . Informe C ++ . 7 (5): 26–31. Archivado desde el original el 10 de febrero de 2005.
- ^ Abrahams, David; Gurtovoy, Aleksey (2004). Metaprogramación de plantillas C ++: conceptos, herramientas y técnicas de Boost y más allá . Educación Pearson.
- ^ https://dlib.net
- ^ https://bitbucket.org/blaze-lib/blaze
- ^ "Guía del usuario de Blitz ++" (PDF) . Consultado el 12 de diciembre de 2015 .
- ^ "Impulsar la biblioteca básica de álgebra lineal" . Consultado el 25 de octubre de 2015 .
- ^ Guennebaud, Gaël (2013). Eigen: una biblioteca de álgebra lineal de C ++ (PDF) . Eurographics / CGLibs.
- ^ Veldhuizen, Todd (2000). Justo cuando pensaba que su pequeño lenguaje era seguro: "Plantillas de expresión" en Java . Int'l Symp. Ingeniería de software generativa y basada en componentes. CiteSeerX 10.1.1.22.6984 .
- ^ "Documentación de Stan" . Consultado el 27 de abril de 2016 .
- ^ "Matrices multidimensionales con broadcasting y computación perezosa" . Consultado el 18 de septiembre de 2017 .
- ^ Hogan, Robin J. (2014). "Diferenciación automática en modo inverso rápido utilizando plantillas de expresión en C ++" (PDF) . ACM Trans. Matemáticas. Softw . 40 (4): 26: 1–26: 16.