Domů › Expanze vektorových výrazů pomocí šablon v C++

Rozbalování smyček

Út, 01/06/2009 - 16:42 — oberhuber

Rozbalování smyček

Následující výraz

  1. for (i = 0; i < n; i++)
  2. {
  3.      data[i] = a[i];
  4. }

lze zaměnit za

  1. for (i = 0; i < n; i += k) 
  2. {
  3.      data[i] = a[i];
  4.      data[i+1] = a[i+1];
  5.      data[i+2] = a[i+2];
  6.      ...
  7.      data[i+k-1] = a[i+k-1];
  8. }

a tak umožnit lepší využití pipeline procesoru.

Specializace šablon

Zde vidíme použití specializace na výpočet fibonacciho čísla v době překladu. Prvně je definována obecná šablona, která obsahuje rekurzivní vzorec a následně jsou definovány specializace pro počáteční podmínky. Všechny propočty jsou realizovány v době kompilace a ve výsledném programu už najdeme jen číslo, které se vypisuje.

  1. template<int N> struct fib 
  2. {
  3.   static const int result = fib<N-1>::result + fib<N-2>::result;
  4. };
  5.  
  6. template<> struct fib<0> 
  7. {
  8.   static const int result = 0;
  9. };
  10.  
  11. template<> struct fib<1> 
  12. {
  13.   static const int result = 1;
  14. };

  1. #include <iostream>
  2. int main(int ac, char *av[])
  3. {
  4.   std::cout << "Fib(10) = " << fib<10>::result << std::endl;
  5.   return 0;
  6. }

Specializace šablon s více parametry

  1. template<arg(0), arg(1), ... arg(n)>
  2. class sablona 
  3. {
  4.   //defaultní chování
  5. };
  6.  
  7. template<arg(i0), arg(i1), ... arg(im)>
  8. class sablona< /* dosazení za parametry obecné šablony */ > 
  9. {
  10.   //specializace
  11. };

Obecná šablona má n parametrů. Častečná specializace šablony má pro parametry s indexy {1..n} \ (i)1..m určené typy nebo přímo číselné hodnoty. Ostatní nespecifikované parametry šablony (i)1..m je třeba uvést jako parametry specializace za klíčové slovo template. Častečná specializace šablony tedy má méně parametrů než obecná šablona a za názvem třídy se uvádí nespecifikované parametry a hodnoty parametrů, pro kterou šablonu specializujeme.

Šablona pro rozbalení smyčky

Tato šablona má dva parametry: počet řádek, které je potřeba rozbalit a výraz, na kterém se provádí. Rekurzivně se volá tak dlouho, až dojde k rozbalení posledního výrazu. Celý cyklus je ukončen specializací šablony.

  1. template <int loops, class A>
  2. class loop_unroll 
  3. {
  4. public:
  5.         static const int n = loops;     
  6.         inline static void do_loops(double data[], const A &a, int i) 
  7. {
  8.                 //tato řádka se rozbalí
  9.                 data[i] = a[i];
  10.                 //využití šablony o 1 menší
  11.                 loop_unroll<n-1, A>::do_loops(data, a, i+1);
  12.         }
  13. };
  14.  
  15. /*
  16.      specializace šablony pro 0 opakování
  17. */
  18. template <class A>
  19. class loop_unroll<0, A> 
  20. {
  21. public: 
  22.         inline static void do_loops(double data[], const A a, int i) {}
  23. };
  24.  
  25. //--------------------------použití-------------------------------------------
  26.  
  27. template <class A>
  28. void operator = (const Expr<A>& a_) 
  29. {
  30.         const A& a(a_);
  31.         int i;
  32.         #ifdef unroll_loops
  33.         for (i = 0; i<n; i += unroll) {
  34.                 // rozbalení smyčky na "unroll" výrazů za sebou
  35.                 loop_unroll<unroll, A>::do_loops(data, a, i);
  36.         }
  37.         // prochazíme zbytek výrazu
  38.         for (;i<n; i++) {
  39.                 data[i] = a[i];
  40.         }
  41.         #else
  42.         for (i=0;i<n; i++) {
  43.                 data[i] = a[i];
  44.         }
  45.         #endif
  46. }

Rozbalování smyček v gcc
Rozbalení smyček lze dosáhnout i pomocí přepínače gcc -funroll-loops. Což samozřejmě vede ke zvětšení spustitelného souboru a tím pádem větší spotřebě paměti, ale umožní zredukovat vyhodnocení podmínky smyčky, a tak lépe využít pipeline.