[Meta-prog] Les templates-Expressions

Les templates-Expressions [Meta-prog] - C++ - Programmation

Marsh Posté le 29-07-2003 à 09:16:14    

Voila, apres le premier post sur la MPT, je récidive avec cette fois quelque chose de plus burné : Les Expressions Templates.
 
Tout d'abord je tiens à signaler que ce post est une tentative d'adaptation des articles de Todd Veldhuizen, ze Boss en MPT, créateur de la librairie Blitz++ en autre.
 
Note : Cette explication fait partie de mes travaux de DEA :D
 
1. Principes
Considérons une fonction qui cacule l'intégrale d'une fonction mathématique.
Un moyen "classique" de l'implementer est d'utiliser un pointeur de fonction :
 

Code :
  1. double integrate( double (*f)(double), double inf, double sup )
  2. {
  3.     double r=0;
  4.     static const double dx = 0.001
  5.     for( double i=inf;i<sup;i+=dx;)  r += dx*f(i);
  6.     return r;
  7. }


 
Simple, efficace, pas de problème. SAUF que si cette fonction est une part critique de votre application, le déréférencement de pointeur va peut etre commencer à devenir tres tres handicapant.
 
Il serait agréable de pouvoir ecrire quelque chose comme :  
 

Code :
  1. Data<double> x;
  2. double r = integrate( 1+1/x,0,10);

 
 
et de voir se dérouler le code de l'intégration :
 

Code :
  1. double r = 0;
  2. for( double i=inf;i<sup;i+=dx;)  r += dx*(1+1/i);


 
Comment faire ?
 
2. Une Solution Elégante : Les Expressions templates
 
Lorsque l'on manipule ce genre d'expression, on peut considérer qu'elles sont l'application d'une grammaire restreinte, contenant juste des valeurs, des opérateurs et des expressions. A partir de la on peut reconstruire un ensemble de classe pour réécrir ces expressions :
 
Il nous faut d'abord une classe pour représenté les variables et les constantes
 

Code :
  1. class Variable
  2. {
  3.    public :
  4.    Variable() {}
  5.    double eval( double x ) const { return x; }
  6. };
  8. class Constante
  9. {
  10.    public :
  11.    Constante( const double& v) : val(v){}
  12.    double eval( double ) { return val; }
  14.    private :
  15.    double val;
  16. };

 
 
Ensuite, il nous font pouvoir coder les divers opérateurs d'une expression
arithmétique. Cantonnons nous au opérateurs bianires de bases : +,-,/,*.
Qu'est-ce qu'un operateur binaire : c'est une opération ET un noeud d'una rbre de syntaxe abstraite ayant deux fils. Ces deux aspects de l'opérateurs se retrouvent dans deux familles de classes :
 

Code :
  1. // classe représentant la caractére binaire d'un opérateur
  2. template<class L,class R,class OP>
  3. class BinaryNode
  4. {
  5.   public :
  6.   BinaryNode( const L& l, const R& r ) : left(l), right(r) {}
  7.   double eval( double x ) { return OP::eval( left.eval(x), right.eval(x));}
  9.   private:
  10.   L left;
  11.   R right;
  12. };
  14. // classes représentant les opérations des opérateurs
  15. struct func_plus
  16. {
  17.     static double eval( double x, double y) { return x+y; }
  18. };
  20. struct func_moins
  21. {
  22.     static double eval( double x, double y) { return x-y; }
  23. };
  24. struct func_fois
  25. {
  26.     static double eval( double x, double y) { return x*y; }
  27. };
  29. struct func_divise
  30. {
  31.     static double eval( double x, double y) { return x/y; }
  32. };


 
Il nous reste à coder une classe pour encapsuler une expression quelconque :
 

Code :
  1. template<class E>
  2. class Expression
  3. {
  4.   public :
  6.   Expression( const E& expr) : xpr(expr) {}
  7.   double eval( double x) { return xpr.eval(x); }
  9.    private :
  10.    E xpr;
  11. };


 
Voila, nous avaons toute nos briques. Comment alors reconstruire à partir de ces classes une expression arithmétique et l'évaluez en ligne ?
 
Trés simplement, nous allons redéfinir les opérateurs +,-,*,/ sur les types Variable, Constante et Expression et reconstruire au sein de ces opérateurs l'arbre de syntaxe de l'expression :
 

Code :
  1. // var+var
  2. inline Expression<BinaryNode<Variable,Variable,func_plus> >
  3. operator+( const Variable& v1, const Variable& v2 )
  4. {
  5.   typedef BinaryNode<Variable,Variable,func_plus> expr_t;
  6.   return Expression<expr_t>( expr_t(v1,v2) );
  7. }
  9. // (expr)+var
  10. template<class E>
  11. inline Expression<BinaryNode<Expression<E>,Variable,func_plus> >
  12. operator+( const Expression<E>& e, const Variable& v )
  13. {
  14.   typedef BinaryNode<Expression<E>,Variable,func_plus> expr_t;
  15.   return Expression<expr_t>( expr_t(e,v) );
  16. }
  18. // var+(expr)
  19. template<class E>
  20. inline Expression<BinaryNode<Variable,Expression<E>,func_plus> >
  21. operator+(  const Variable& v ,const Expression<E>& e)
  22. {
  23.   typedef BinaryNode<Variable,Expression<E>,func_plus> expr_t;
  24.   return Expression<expr_t>( expr_t(v,e) );
  25. }
  27. // expr+expr
  28. template<class E1,class E2>
  29. inline Expression<BinaryNode<Expression<E1>,Expression<E2>,func_plus> >
  30. operator+(  const Expression<E>& e1 ,const Expression<E>& e2)
  31. {
  32.   typedef BinaryNode<Expression<E1>,Expression<E2>,func_plus> expr_t;
  33.   return Expression<expr_t>( expr_t(e1,e2) );
  34. }


 
Voila, rajoutez a cela les opérateurs -,*,/, la surcharge pour gérer les constantes numériques :
 

Code :
  1. // const+expr
  2. // les autres versions sont nécéssaire evidemment
  3. template<class E>
  4. inline Expression<BinaryNode<Constante,Expression<E>,func_fois> >
  5. operator*( const double& c, const Expression<E>& e)
  6. {
  7.   typedef BinaryNode<Constante,Expression<E>,func_fois>  expr_t;
  8.   return Expression<expr_t>( expr_t(Constante(c),e) );
  9. }


 
En écrivant du code comme :
 

Code :
  1. template<class E>
  2. double integrate( Expression<E> e, double inf, double sup)
  3. {
  4.     double r=0;
  5.     static const double dx = 0.001;
  6.     for( double i=inf;i<sup;i+=dx;)  r += dx*e.eval(i);
  7. }


 
Nous générons par instanciation récursives des templates le code suivant :
 

Code :
  1. template<class E>
  2. double integrate( Expression<E> e, double inf, double sup)
  3. {
  4.     double r=0;
  5.     static const double dx = 0.001;
  6.     for( double i=inf;i<sup;i+=dx;)  r += dx*(1+1/i);
  7. }


 
C'est gaagné :D
cette  technique permet aussi via quelques modifications mineurs de
générer du code arithmétique vectoriel ou matriciel inline trés performant, éliminant toutes recopies d'objets temporaires et augmentant les performances d'un facteurs 3 ou 4, faisant du C++ un langage aussi rapide que le C.
 
On peut aussi ecrire des classes pour générer du code inline de parser/lexer à la YACC, des filtres de flux, du TI rapide (oops la c'est mon job :p) bref, des infinités d'applications.
 
EDIt : typo/ortho :p


Message édité par Joel F le 29-07-2003 à 10:19:30
Reply

Marsh Posté le 29-07-2003 à 09:16:14   

Reply

Marsh Posté le 29-07-2003 à 14:01:57    

Bon un exemple concret, un peu brutale mais bon.
le but du jeu est d'utiliser les E.T vu ci dessus pour générer du
code arithmétiques sur des classes du types Vecteur ou matrices.
Style :
 

Code :
  1. std::vector<float> a(10),b(10),c(10);
  2. a = 2*a+b*ln(c);

 
 
et généré un code sans recopie ni objets temporaires, stadire :
 

Code :
  1. std::vector<float> a(10),b(10),c(10);
  2. for(int i=0;i<10;++i)
  3. a[i] = 2*a[i]+b[i]*ln(c[i]);

 
 
ce qu'AUCUN COMPILATEUR NE SAIT FAIRE AUTOMATIQUEMENT je precise ...
 
Voila le code, il utilise le même style de code que précédemment :
 

Code :
  1. class vecDouble
  2. {
  3.     public
  4.     vecDouble( int taille=16) : data(NULL), size(taille) { allocate();}
  5.     virtual ~vecDouble() {deallocate();}
  7.     double& operator[](int i) { return data[i]; }
  8.     double operator[](int i) const { return data[i]; }
  10.     double* begin() { return data; }
  12.     template<class E>
  13.     operator=( const Expression<E>& xpr )
  14.     {
  15.         for( int i=0;i<size;i++)
  16.         {
  17.             data[i] = xpr.eval(i);
  18.         }
  20.        return *this;
  21.     }
  23.     private :
  24.     double* data;
  25.     long size;
  27.     void allocate() { if(data) deallocate(); data = new double[size]; }
  28.     void deallocate() { if(data) delete[] data; }
  29. };
  31. class Variable
  32. {
  33.   public :
  34.   Variable( double* it) : val(it) {}
  35.   double eval( int i ) const { return val[i]; }
  37.    private :
  38.    double* val;
  39. };
  41. class Constante
  42. {
  43.   public :
  44.   Constante( const double& v) : val(v){}
  45.   double eval( int ) { return val; }
  47.   private :
  48.   double val;
  49. };
  51. // classe représentant la caractére binaire d'un opérateur  
  52. template<class L,class R,class OP>
  53. class BinaryNode
  54. {
  55.  public :
  56.  BinaryNode( const L& l, const R& r ) : left(l), right(r) {}
  57.  double eval( int i ) { return OP::eval( left.eval(i), right.eval(i));}
  59.  private:
  60.  L left;
  61.  R right;
  62. };
  64. template<class E>
  65. class Expression
  66. {
  67.  public :
  69.  Expression( const E& expr) : xpr(expr) {}
  70.  double eval( int i) { return xpr.eval(i); }
  72.   private :
  73.   E xpr;
  74. };
  76. // var+var  
  77. inline Expression<BinaryNode<Variable,Variable,func_plus> >
  78. operator+( const vecDouble& v1, const vecDouble& v2 )
  79. {
  80.  typedef BinaryNode<Variable,Variable,func_plus> expr_t;
  81.  return Expression<expr_t>( expr_t(Variable(v1.begin()), Variable (v2.begin())) );
  82. }
  83. // etc ....

 
 
 
Voila quelquechose de + concret peut etre :p
gain de perf garanti pour des tres garande expressions :D

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed