Hispanopedia Wiki
Articulo de referencia

Plantillas de expresiones

Las plantillas de expresiones 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 e...

Hispanopedia WikiContenido en espanolLectura gratuita

Las plantillas de expresiones 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 ] De esta manera, las plantillas de expresiones 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 expresiones 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 ]

Motivación y ejemplo

Consideremos una biblioteca que representa vectores y operaciones sobre ellos. Una operación matemática común es sumar 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 una sobrecargaoperator+ que devuelve un nuevo objeto vector:

importar std ;usando std :: array ;/// @brief clase que representa un vector matemático 3D clase Vec3 : public array < double , 3 > { public : Vec3 () : array < double , 3 > () {} };/// @brief Suma 'u' y 'v' en una nueva instancia de Vec3 Vec3 operator + ( Vec3 const & u , Vec3 const & v ) { Vec3 sum ; for ( size_t i = 0 ; i < u . size (); i ++ ) { sum [ i ] = u [ i ] + v [ i ]; } return sum ; }

Los usuarios de esta clase ahora pueden escribir Vec3 x = a + b;donde ay bson ambas instancias de Vec3.

Un problema con este enfoque es que las expresiones más complejas, como , Vec3 x = a + b + cse implementan de forma ineficiente. La implementación primero crea un objeto temporal Vec3para almacenar a + b, y luego crea otro Vec3con los elementos de cañadidos. Incluso con la optimización del valor de retorno, esto asignará memoria al menos dos veces y requerirá dos bucles.

La evaluación diferida resuelve este problema y puede implementarse en C++ permitiendo operator+que devuelva un objeto de un tipo auxiliar, por ejemplo Vec3Sum, que representa la suma no evaluada de dos Vec3, o un vector con un Vec3Sum, etc. Las expresiones más grandes entonces construyen efectivamente árboles de expresiones que se evalúan solo cuando se asignan a una Vec3variable real. Pero esto requiere recorrer dichos árboles para realizar la evaluación, lo cual es costoso en sí mismo. [ 4 ]

Las plantillas de expresiones implementan la evaluación diferida mediante árboles de expresiones que solo existen en tiempo de compilación. Cada asignación a un Vec3, como Vec3 x = a + b + c, genera un nuevo Vec3constructor si es necesario para la instanciación de la plantilla. Este constructor opera sobre tres Vec3; 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 expresiones

Un ejemplo de implementación de plantillas de expresiones se ve así: una clase base Vec3Expressionrepresenta cualquier expresión vectorial. Se basa en el tipo de expresión Eque se va a implementar, siguiendo el patrón de plantilla recurrente . La existencia de una clase base como VecExpressionno es estrictamente necesaria para que las plantillas de expresiones funcionen. Simplemente servirá como tipo de argumento de función para distinguir las expresiones de otros tipos (observe la definición de un Vec3constructor operator+más adelante).

importar std ;plantilla < typename E > clase VecExpression { public : static constexpr bool IS_LEAF = false ;[[ nodiscard ]] double operator []( 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 ]; }[[ nodiscard ]] size_t size () const { return static_cast < E const &> ( * this ). size (); } };

El booleano is_leafestá ahí para etiquetar VecExpressionlas "hojas", es decir, las que realmente contienen datos. La Vec3clase es una hoja que almacena las coordenadas de una expresión vectorial completamente evaluada y se convierte en una subclase de VecExpression.

importar std ;using std :: array ; using std :: initializer_list ;clase Vec3 : public VecExpression < Vec3 > { private : array < double , 3 > elems ; public : static constexpr bool IS_LEAF = true ;[[ nodiscard ]] double operator []( size_t i ) const noexcept { return elems [ i ]; }double & operator []( size_t i ) noexcept { return elems [ i ]; }[[ nodiscard ]] size_t size () const noexcept { return elems . size (); }// Construir Vec usando la lista de inicialización Vec3 ( initializer_list < double > init ) { std :: ranges :: copy ( init , elems . begin ()); }// Se puede construir un Vec a partir de cualquier VecExpression, forzando su evaluación. template < typename E > Vec3 ( VecExpression < E > const & expr ) { for ( size_t i = 0 ; i != expr . size (); ++ i ) { elems [ i ] = expr [ i ]; } } };

La suma de dos Vec3s 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 de Vec3expresiones arbitrarias. Una sobrecarga operator+sirve como azúcar sintáctico para el VecSumconstructor. En este caso interviene una sutileza: para referenciar los datos originales al sumar dos VecExpressions, VecSumnecesita almacenar una referencia constante a cada si es una hoja; de lo contrario, es un objeto temporal que debe copiarse para guardarse correctamente.VecExpression

importar std ;usando std :: conditional ;plantilla < typename E1 , typename E2 > clase Vec3Sum : public VecExpression < Vec3Sum < E1 , E2 >> { private : // cref si es una hoja, copiar en caso contrario typename conditional < E1 :: is_leaf , const E1 & , const E1 >:: type u ; typename conditional < E2 :: is_leaf , const E2 & , const E2 >:: type v ; public : static constexpr bool IS_LEAF = false ;Vec3Sum ( E1 const & u , E2 const & v ) : u { u }, v { v } { assert ( u . size () == v . size ()); }[[ nodiscard ]] double operator []( size_t i ) const noexcept { return u [ i ] + v [ i ]; }[[ nodiscard ]] size_t size () const noexcept { return v . size (); } }; template < typename E1 , typename E2 > Vec3Sum < E1 , E2 > operator + ( VecExpression < E1 > const & u , VecExpression < E2 > const & v ) { return Vec3Sum < E1 , E2 > ( * static_cast < const E1 *> ( & u ), * static_cast < const E2 *> ( & v )); }

Con las definiciones anteriores, la expresión a + b + ces de tipo

Vec3Sum < Vec3Sum < Vec3 , Vec3 > , Vec3 >

por lo tanto, Vec3 x = a + b + cinvoca el Vec3constructor con plantilla Vec3(VecExpression<E> const& expr)cuyo argumento de plantilla Ees de este tipo (es decir Vec3Sum<Vec3Sum<Vec3, Vec3>, Vec3>, ). Dentro de este constructor, el cuerpo del bucle

elems [ i ] = expr [ i ];

se expande efectivamente (siguiendo las definiciones recursivas de operator+y operator[]en este tipo) a

elems [ i ] = a.elems [ i ] + b.elems [ i ] + c.elems [ i ] ;​​​​​

Sin Vecnecesidad de objetos temporales y con una sola pasada por cada bloque de memoria.

Uso básico

A continuación se muestra un ejemplo del uso básico de lo anterior:

importar std ;int main () { Vec3 v0 { 23.4 , 12.5 , 144.56 }; Vec3 v1 { 67.12 , 34.8 , 90.34 }; Vec3 v2 { 34.90 , 111.9 , 45.12 }; // La siguiente asignación llamará al constructor de Vec3 que acepta el tipo de // `VecExpression<E> const&`. Luego expanda el cuerpo del bucle a // a.elems[i] + b.elems[i] + c.elems[i] Vec3 sumOfVecType = v0 + v1 + v2 ;for ( size_t i = 0 ; i < sumOfVecType . size (); ++ i ) { std :: println ( "{}" , sumOfVecType [ i ]); }// Para evitar crear almacenamiento adicional, aparte de v0, v1, v2 // se puede hacer lo siguiente (probado con C++11 en GCC 5.3.0) auto sum = v0 + v1 + v2 ; for ( size_t i = 0 ; i < sum . size (); ++ i ) { std :: println ( "{}" , sum [ i ]); } // Observe que en este caso typeid(sum) será Vec3Sum<Vec3Sum<Vec3, Vec3>, Vec3> // y este encadenamiento de operaciones puede continuar. }

Aplicaciones

Las plantillas de expresiones han resultado especialmente útiles para los autores de bibliotecas de álgebra lineal, es decir, para trabajar con vectores y matrices de números. Entre las bibliotecas que emplean plantillas de expresiones 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 expresiones también pueden acelerar las implementaciones de diferenciación automática en C++ , [ 12 ] como se demuestra en la biblioteca Adept .

Fuera del ámbito de las matemáticas vectoriales, el marco de análisis sintáctico Spirit utiliza plantillas de expresiones para representar gramáticas formales y compilarlas en analizadores sintácticos.

Véase también

Referencias

Pflaum C., Plantillas de expresiones para ecuaciones diferenciales parciales. Comput Visual Sci 4, 1–8 (2001). https://doi.org/10.1007/s007910100051

Pflaum C, Rahimi Z., Paralelización automática de códigos de cuadrícula escalonada con plantillas de expresión. International Journal of Computational Science and Engineering, Volumen 4, Número 4, Páginas 306 – 313, https://doi.org/10.1504/IJCSE.2009.029166

  1. 1 2 Matsuzaki, Kiminori; Emoto, Kento (2009). Implementación de esqueletos paralelos equipados con fusión mediante plantillas de expresiones . Actas del Simposio Internacional sobre Implementación y Aplicación de Lenguajes Funcionales. págs. 72–89 . 
  2. ^ Vandevoorde, David; Josuttis, Nicolai (2002). Plantillas C++: la guía completa . Addison Wesley . ISBN 0-201-73484-2.
  3. 1 2 Veldhuizen, Todd (1995). "Plantillas de expresiones" . C++ Report . 7 (5): 26– 31. Archivado del original el 10 de febrero de 2005.
  4. ↑ Abrahams, David; Gurtovoy, Aleksey (2004). Metaprogramación con plantillas en C++: conceptos, herramientas y técnicas de Boost y más allá . Pearson Education. ISBN 9780321623911.
  5. ↑ Bitbucket
  6. ↑ "Guía del usuario de Blitz++" (PDF) . Consultado el 12 de diciembre de 2015 .
  7. ↑ "Biblioteca Boost Basic Linear Algebra" . Consultado el 25 de octubre de 2015 .
  8. ^ Guennebaud, Gaël (2013). Eigen: una biblioteca de álgebra lineal de C ++ (PDF) . Eurográficos/CGLibs.
  9. ↑ Veldhuizen, Todd (2000). Justo cuando pensabas que tu pequeño lenguaje estaba a salvo: "Plantillas de expresiones" en Java . Simposio internacional sobre ingeniería de software generativa y basada en componentes. CiteSeerX 10.1.1.22.6984 . 
  10. ↑ "Documentación de Stan" . Consultado el 27 de abril de 2016 .
  11. ↑ "Matrices multidimensionales con difusión y computación perezosa" . Consultado el 18 de septiembre de 2017 .
  12. ↑ Hogan, Robin J. (2014). "Diferenciación automática rápida en modo inverso mediante plantillas de expresiones en C++" (PDF) . ACM Trans. Math. Softw . 40 (4): 26:1–26:16. doi : 10.1145/2560359 . S2CID 9047237 .