Tomas Oberhuber's Homepage

Cíl

Cílem je používat vektory obdobně jako v následujícím příkladu, tedy s využitím přetěžování operátorů, ale bez vlivu na rychlost.

#include "Fast_Vector.h"
 
int main()
{
  int size_ = 5000000 ;
  /**
     definice unikatnich vektoru
  */
  Fast_Vector<1> a(size_,1.);
  Fast_Vector<2> b(size_,2);
  Fast_Vector<3> c(size_);
 
  c = 5. * a + 7. * b ;
  std::cout << c[0] >> std::endl;
}

Tedy vektorový výraz, ve kterém by při standardním přetěžování operátorů došlo k vytváření pomocných vektorů v paměti a tím k její alokaci a dealokaci, nahradíme smyčkou. Tato smyčka pro každou složku vektoru vypočte výraz, aniž by se alokavala jakákoliv další pamět v průběhu výpočtu. Zároveň je náš příklad jednoduchý a nevynucuje od uživatele znalost šablonového metaprogramování. Velikost vektorů při tom může být známa až za běhu programu. Zatím v příkladu vidíme jen násobení vektoru číslem typu double a sčítání vektorů. Postup dále popsaný ale není těžké rozšířit i na jiné typy a operace.

Šablony (Templates)

Šablony byly původně vyvinuty jako snaha využít ten samý kód pro víc typů. Protože už při překladu musí být zřejmé jaké typy se s danou šablonou váží, nahradí se šablona vždy kódem pro příslušný typ. Tedy není třeba psát funkci minimum a maximum pro různé typy, ale stačí využít stejného kódu. Stejně tak není třeba psát zvláštní kontejnery pro různé typy. Šablony jsou také výhodné v tom, že zůstává zachována typová kontrola.
S rozvojem standardu a rozšířením implementace šablon se přišlo na to, že je lze využít i k poměrně komplikovaným výpočtům a transformacím v době překladu. Šablony lze různě skládat a definovat jejich chování pro různé parametry, popř. definovat běžné chování a případy pro různé speciální typy vstupních parametrů (specializace).

Výrazy

Obalová třída Expr zapouzdřuje všechny možné výrazy do stejného rozhraní. Protože třídy operátorů se dědí z této obalové třídy, můžeme každý objekt operátoru předávat jako obalový objekt. Zároveň v této třídě zavádíme operátor přetypování, který nám naopak umožňuje přistupovat k obalenému objektu.

Třídy operátorů si uchovávají podvýrazy jako reference, dokud není rozvinutí výrazu kompletní. Operátor přístupu [] slouží k výpočtu i-té složky výrazu rekurzivně volající tento operátor u podvýrazů. Protože používáme inline funkce a všechny proměnné a výrazy lze určit v době kompilace může kompilér analyzovat všechny typy. Přetypované operátory berou jeden až dva parametry a provádí se pomocí tříd operátorů.

Pozn.: Překlad zdrojového kódu s těmito operátory může trvat poměrně delší čas, protože klade značné nároky na kompilátor. Následující postup lze také volně rozšiřovat na další objekty jako matice, polynomy, atd.

template <class A>
 struct Expr
    {
      operator const A&() const
         {
           return *static_cast<const A*>(this);
         }
    };
//----------------------------------------------------------------------------
template <class A, class B>
 class Add : public Expr<Add<A,B> >
   {
       const A& a_;
       const B& b_; 
     public: 
       Add(const A& a, const B& b) : a_(a), b_(b) {}
       double operator[](int i) const 
          {
            return a_<span style="font-style:italic"> + b_[i];
          }
   };
//----------------------------------------------------------------------------
template <class A, class B>
 inline Add<A,B>
  operator+ (const Expr<A>& a, const Expr<B>& b)
    {
       return Add<A,B>(a,b);
    }

Obdobně postupujeme pro ostatní operátory
[i]Pozn.: Mezera mezi znaky > > při použití vnořených šablon je nutná. Tokenizér C++ postupuje hladnovým způsobem a znaky >> by považoval za operátor posunutí a ne za dvě po sobě jdoucí ukončovací závorky.

Vektor

Vector je třída, která je odvozena od obalové třídy Expr, takže každý vektor se chová jako součást výrazu. Konstruktor vektoru alokuje paměť podle velikosti vektoru. Přetížený operátor [] nám umožňuje pracovat se složkami vektoru. Složky vektoru jsou typu double, ale šablonu lze rozšířit i na jiné typy.

Přetížený operátor = vektoru slouží k vyhodnocení výrazu na pravé straně pro všechny složky vektoru. Tento operátor ve smyčce počítá jednotlivé složky výsledku a využívá k tomu operátory [] tříd odvozeních od Expr.
Pozn.: Tato třída obsahuje pole proměnné délky, kterou není nutné zadat v době překladu.

#include "EasyET.h"
 
class Vector :  public Expr<Vector>
   {
     private:
       double * data; 
       int n; 
     public:
       Vector(int n_, double w = 0) : n(n_)
          {
            data = new double[n];
            for (int i = 0; i < n; ++i) 
               {
                 data[i] = w;
               }
          }
       ~Vector() 
          {
            delete [] data;
          }
       double operator[] (int i) const
          { 
            return data[i];
          }
 
       template <class A>
       void operator = (const Expr<A>& a_)
          {
            const A& a(a_);
            for (int i = 0; i < n; ++i)
               {
                  data[i] = a[i];
               }
          }
};

Rychlé vektory

Protože ukazatel na data objektu Vector není statický, tak se vícenásobný výskyt stejného vektoru ve složitějším výrazu na pravé straně přiřazení považuje v době kompilace za různé proměnné a nedojde k potřebným optimalizacím. Proto pro složité pravé strany zavádíme speciální třídu vektoru, který má data deklarována přes statický ukazatel. Takový rychlý vektor ovšem musí být identifikován unikátním číslem v celé aplikaci.
Příklad:

3 * double Fast_Vector<1>::data[i] + 2 * double Fast_Vector<1>::data[i]
//lze převést na
5 * double Fast_Vector<1>::data[i]
//ale to se nestane pro výraz
3 * (Vector& v1).data[i] + 2 * (Vector& v2).data[i]
//protože v1, v2 nejsou staticke proměnné (i když nakonec třeba platí v1==v2)

Pozn: Přestože používáme statický ukazatel, tak velikost pole zůstává dynamická stejně jako v předchozí implementaci.

template <int unique_id>
class Fast_Vector :  public Expr<Fast_Vector<unique_id> > {
   private:
     static double * data; 
     int n; 
   public:
     Fast_Vector(int n_, double w = 0) : n(n_){
         data = new double[n];
         for (int i= 0; i < n; ++i) {
             data[i] = w;
         }
     ...
};
 
template <int unique_id>
double* Fast_Vector<unique_id>::data;

Příklad na expanzi výrazu

Výraz z úvodního příkladu

c = 5. * a + 7. * b

se pomocí přetížení operátorů převede na

c = 5. * Expr< FastVector(a) > + 7. * Expr<FastVector(b)>
c = Mul< 5., Expr< FastVector(a) > > + Mul< 7., Expr<FastVector(b)> >
c = Add< Mul< 5., Expr< FastVector(a) > >, Mul< 7., Expr<FastVector(b)> > >
c = Expr< Add< Mul< 5., Expr< FastVector(a) > >, Mul< 7., Expr<FastVector(b)> > > >

Tedy do tvaru typu:

c = Expr<...>

Toto přiřazení pro FastVector je přetíženo a způsobí volání vyhodnocení šablony pro každou složku vektoru.

template <class A>
void operator = (const Expr<A>& a_){
    const A& a(a_);
    for (int i = 0; i < n; ++i){
        data[i] = a[i];
    }
}

Výraz data[i] = a[i] se převede rekurzivním voláním vyhodnocení podvýrazu přes operátor [] na:

template <class A>
data[i] = (5. * a[i]) + (7. * b[i])
}