|
|
| Linia 1: |
Linia 1: |
| ==7.1 Metaprogramowanie==
| |
|
| |
|
| Ogólnie rzecz biorąc metaprogramowanie oznacza pisanie programów, które
| |
| piszą programy lub pisania programu, który pisze się sam. W naszym
| |
| kontekście będzie to oznaczało wykonywanie obliczeń za pomocą
| |
| szablonów, przy czym obliczenia te są wykonywane podczas kompilacji.
| |
| Podstawą do tych obliczeń jest rekurencyjna konkretyzacja szablonów.
| |
| Taką metodą można generować w czasie kompilacji całkiem skomplikowane
| |
| fragmenty kodu, stąd określenie metaprogramowanie. Przykłady takich
| |
| "metaszablonów" poznaliśmy już na wykładzie o funkcjach typów. W
| |
| szczególności działanie na listach typów to właśnie przykłady
| |
| metaprogramowania. W tym wykładzie przyjrzymy się dokładniej temu
| |
| zagadnieniu i przeanalizujemy kolejne przykłady.
| |
|
| |
| ==7.2 Potęgi==
| |
|
| |
| Zaczniemy od bardzo prostego przykładu (zob. D. Vandervoorde, N. Josuttis:''"C++ Szablony, Vademecum profesjonalisty"'', rozdz. 17).
| |
| Napiszemy szablon który ma za zadanie obliczać potęgi liczby 3.
| |
| Ponieważ w programowaniu za pomocą szablonów musimy posługiwać się
| |
| rekurencją to zaczynamy od sformułowania problemu w sposób
| |
| rekurencyjny. To akurat jest bardzo proste:
| |
|
| |
| {{przyklad|7.1||
| |
| <center><math>3^N=3*3^{N-1},\quad 3^0 = 1</math>
| |
| </center>
| |
| }}
| |
|
| |
| Za pomocą szablonów implementujemy to tak ([http://osilek.mimuw.edu.pl/images/9/91/Pow.cpp Źródło:Pow.cpp]):
| |
|
| |
| template<int N> struct Pow3 { <br>
| |
| enum {val<nowiki>=</nowiki>3*Pow3<N-1>::val}; <br>
| |
| };<br>
| |
| template<> struct Pow3<0> {<br>
| |
| enum {val<nowiki>=</nowiki>1}; <br>
| |
| };
| |
|
| |
| teraz możemy już użyć w programie np. wyrażenie:
| |
|
| |
| i=Pow3<4>::val;
| |
|
| |
| Podstawową zaletą metaprogramowania i głównym powodem jego używania
| |
| jest fakt, że to wyrażenie jest obliczane w czasie kompilacji i efekt
| |
| jest taki sam jak podstawienia:
| |
|
| |
| i<nowiki>=</nowiki>81;
| |
|
| |
| Można też zastosować szablon funkcji:
| |
|
| |
| template<int N> int pow3() {<br>
| |
| return 3*pow3<N-1>();<br>
| |
| };<br>
| |
| template<> int pow3<0>() {return 1;}<br>
| |
| cout<<pow3<4>()<<endl;
| |
| <span style="color:red">{mod07/code/powf.cpp}{powf.cpp
| |
| /* {mod07/code/powf.cpp}{powf.cpp}*/}</span>.
| |
|
| |
| Nietrudno jest uogólnić powyższy kod tak aby wyliczał potęgi dowolnej
| |
| liczby:
| |
|
| |
| template<int K,int N> struct Pow { enum <br>
| |
| {val<nowiki>=</nowiki>K*Pow<K,N-1>::val}; };<br>
| |
| template<int K> struct Pow<K,0> {<br>
| |
| enum {val<nowiki>=</nowiki>1};<br>
| |
| };
| |
| <span style="color:red">{mod07/code/pow.cpp}{pow.cpp}</span>
| |
| /* {mod07/code/pow.cpp}{pow.cpp}*/
| |
|
| |
| Tutaj już nie można wykorzystać szablonu funkcji, bo nie zezwala on na
| |
| specjalizację częściową.<br>
| |
| Ograniczeniem dla takich obliczeń jest implementacja kompilatora,
| |
| przede wszystkim założony limit głebokości rekurencyjnego
| |
| konkretyzowania szablonów. Dla kompilatora g++ jest on ustawiany za
| |
| pomocą opcji i defaultowo wynosi 500, dlatego już konkretyzacja <tt>Pow<1,500>::val</tt> się nie powiedzie.
| |
| Konkretyzacja szablonów wymaga też pamięci i może się zdarzyć, że
| |
| kompilator wyczerpie limit pamięci lub czasu. <br> Kolejne ograniczenie to konieczność rachunków na liczbach całkowitych.
| |
| Wiąże się to z faktem, że tylko stałe całkowitoliczbowe mogą być
| |
| parametrami szablonów.
| |
|
| |
| ==7.3 Ciąg Fibonacciego==
| |
|
| |
| Po opanowaniu powyższych przykładów obliczanie wyrazów ciągu
| |
| Fibonacciego jest prostym zadaniem. Przytoczymy je jednak tutaj, aby
| |
| zaprezentować pewną bardzo sympatyczną cechę metaprogramowania za
| |
| pomocą szablonów. Ciąg Fibonacciego jest definiowany rekurencyjnie:
| |
|
| |
| {{przyklad|7.2||
| |
| <center><math>f_n=f_{n-1}+f_{n-2},\quad f_1=f_2=1</math>
| |
| </center>
| |
| }}
| |
| więc jego implementacja jest natychmiastowa:
| |
|
| |
| template<int N> struct Fibonacci {<br>
| |
| enum {val <nowiki>=</nowiki> Fibonacci<N-1>::val+Fibonacci<N-2>::val};<br>
| |
| };<br>
| |
| template<> struct Fibonacci<1> {<br>
| |
| enum {val <nowiki>=</nowiki> 1};<br>
| |
| };<br>
| |
| template<> struct Fibonacci<2> {<br>
| |
| enum {val <nowiki>=</nowiki> 1};<br>
| |
| };
| |
| <span style="color:red">{mod07/code/fibonacci_template.cpp}{fibonaccitemplate.cpp}</span>
| |
| /*{mod07/code/fibonacci_template.cpp}{fibonaccitemplate.cpp}*/
| |
|
| |
| Przykład ten nie wart byłby może i wspomnienia gdyby nie fakt, że
| |
| rekurencyjna implementacja ciągu Fibonacciego jest bardzo nieefektywna.
| |
| Jeśli zaimplementujemy ją w zwykłym kodzie
| |
|
| |
| int fibonacci(int n) {<br>
| |
| if(n<nowiki>=</nowiki><nowiki>=</nowiki>1) return 1;<br>
| |
| if(n<nowiki>=</nowiki><nowiki>=</nowiki>2) return 1;<br>
| |
| return fibonacci(n-1)+fibonacci(n-2);<br>
| |
| }
| |
| <span style="color:red">{mod07/code/fibonacci.cpp}{fibonacci.cpp}</span>
| |
|
| |
| /*{mod07/code/fibonacci.cpp}{fibonacci.cpp}*/
| |
|
| |
| to obliczanie <tt>fibonacci(45)</tt> zajmie np.na moim komputerze ok. 8
| |
| sekund. Tymczasem szablon kompiluje sie poniżej jednej sekundy! Skąd
| |
| taka różnica? Czyżby kompilator był bardziej wydajny niż generowany
| |
| przez niego kod? W przypadku zwykłego kodu długi czas wykonania bierze
| |
| się z ogromnej liczby wywołań funkcji <tt>fibonacci</tt>. Liczba ta rośnie
| |
| wykładniczo z <tt>n</tt> i większość czasu jest marnowana na wielokrotne
| |
| wywoływanie funkcji z tymi samymi argumentami.
| |
|
| |
| W przypadku użycia metaprogramu szablony konkretyzowane są tylko raz.
| |
| Więc jeśli już raz policzymy np. <tt>Fibonacci<25>::val</tt> to kolejne
| |
| żądanie nie spowoduje już rozwinięcia rekurencyjnego, a tylko
| |
| podstawienie istniejącej wartości. Jak widzieliśmy zysk jest ogromny.
| |
| Takie pamiętanie wyników raz wywołanych funkcji nazywane jest też
| |
| programowaniem dynamicznym. Jedynym znanym mi językiem, który
| |
| bezpośrednio wspiera taki mechanizm jest <tt>Mathematica</tt>.
| |
|
| |
| ==7.4 Pierwiastek kwadratowy==
| |
|
| |
| Rozważymy teraz trudniejszy przykład szablonu obliczającego
| |
| pierwiastek kwadratowy ([1] rozdz. 17), choć tak naprawdę
| |
| ten kod jest bardziej uniwersalny i, jak zobaczymy, łatwo za jego pomocą
| |
| zaimplementować inne funkcje. Ponieważ jesteśmy ograniczeni do
| |
| arytmetyki liczb całkowitych, tak naprawdę nie liczymy pierwiastka z
| |
| <tt>n</tt> ale jego przybliżenie: największą liczbę całkowitą <tt>k</tt>, taką że <tt>k*k<<nowiki>=</nowiki>n</tt>.
| |
| W tym celu zastosujemy algorytm przeszukiwania binarnego:
| |
|
| |
| int sqrt(int n,int low, int high) {<br>
| |
| if(low<nowiki>=</nowiki><nowiki>=</nowiki>high) return low;<br>
| |
| int mid<nowiki>=</nowiki>(low+high+1)/2;<br>
| |
| if(mid*mid > n ) <br>
| |
| return sqrt(n,low,mid-1);<br>
| |
| else<br>
| |
| return sqrt(n,mid,high);<br>
| |
| }
| |
|
| |
| co już łatwo przetłumaczyć na szablon:
| |
|
| |
| template<int N,int L<nowiki>=</nowiki>1,int H<nowiki>=</nowiki>N> struct Sqrt{<br>
| |
| enum {mid<nowiki>=</nowiki>(L+H+1)/2};<br>
| |
| enum {res<nowiki>=</nowiki> (mid*mid> N)? (int)Sqrt<N,L,mid-1>::res :<br>
| |
| (int)Sqrt<N,mid,H>::res};<br>
| |
| };<br>
| |
| template<int N,int L> struct Sqrt<N,L,L> {<br>
| |
| enum {res<nowiki>=</nowiki>L};<br>
| |
| };
| |
| /* {mod07/code/sqrt.cpp}{sqrt.cpp}*/
| |
|
| |
| Łatwo sprawdzić, że kod ten działa poprawnie. Niestety posiada on
| |
| istotną wadę. W trakcie konkretyzacji szablonu konkretyzowane są oba
| |
| szablony występujące w wyrażeniu warunkowym, nawet ten, który nie będzie
| |
| potem używany. Tak więc wykonywana jest duża liczba konkretyzacji, z
| |
| których tylko ułamek jest potrzebny (zob. rysunek). Jakie to obciążenie dla
| |
| kompilatora to łatwo sprawdzić kompilując kod, w którym wywołujemy
| |
| <tt>Sqrt<10000></tt>. Ja nie doczekałem się na koniec kompilacji.
| |
|
| |
| Na szczęście istnieje rozwiązanie - należy użyć szablonu <tt>If_then_else</tt>
| |
| (zob. [[Zaawansowane CPP/Wykład 5: Funkcje typów i inne sztuczki|rozdział 5.2.1]]):
| |
|
| |
| template<int N,int L<nowiki>=</nowiki>1,int H<nowiki>=</nowiki>N> struct Sqrt{<br>
| |
| enum {mid<nowiki>=</nowiki>(L+H+1)/2};<br>
| |
| typedef typename If_then_else<<br>
| |
| (mid*mid> N),<br>
| |
| Sqrt<N,L,mid-1>,<br>
| |
| Sqrt<N,mid,H> >::Result tmp;<br>
| |
| enum {res<nowiki>=</nowiki> tmp::res};<br>
| |
| };<br>
| |
| template<int N,int L> struct Sqrt<N,L,L> {<br>
| |
| enum {res<nowiki>=</nowiki>L};<br>
| |
| };
| |
| /* {mod07/code/sqrt_ifte.cpp}{sqrtifte.cpp}*/
| |
|
| |
| Ten kod powoduje już tylko konkretyzację rzeczywiście wymaganych
| |
| szablonów, a tych jest dużo mniej: rzędu <math>O(\log N)</math>. Tym razem
| |
| kompilacja wyrażenia <tt>Sqrt<10000></tt> powiedzie się bez trudu.
| |
|
| |
| ==7.5 Pow(x)==
| |
|
| |
| Jak dotąd używaliśmy metaprogramowania do wyliczania wartości stałych.
| |
| Teraz postaramy się wygenerować funkcje. Zacznijmy od pytania: po co?
| |
| Pomijając syndrom Mount Everestu (wchodzę na niego bo jest), to
| |
| głównym powodem jest nadzieja uzyskania bardziej wydajnego kodu.
| |
| Weźmy dalej za przykład liczenie potęgi, tym razem dowolnej liczby
| |
| zmiennoprzecinkowej:
| |
|
| |
| double pow_int(double x,int n) {<br>
| |
| double res<nowiki>=</nowiki>1.0;<br>
| |
| for(int i<nowiki>=</nowiki>0;i<n;++i)<br>
| |
| res*<nowiki>=</nowiki>x;<br>
| |
| return res;<br>
| |
| };
| |
| /*{mod07/code/powx.cpp}{powx.cpp}*/
| |
|
| |
| Patrząc na ten kod widzimy, że w pętli wykonywana jest bardzo prosta
| |
| instrukcja. Możemy więc się obawiać, że instrukcje związane z obsługą
| |
| pętli mogą stanowić spory narzut.
| |
| Co więcej, ich obecność utrudnia kompilatorowi optymalizację kodu oraz
| |
| może uniemożliwić rozwinięcie funkcji w miejscu wywołania.
| |
| Najlepiej by było zaimplementować tę funkcję w ten sposób:
| |
|
| |
| pow(x,n)<nowiki>=</nowiki> x*...*x; /*n razy*/
| |
|
| |
| np.:
| |
|
| |
| double pow2(double x) {return x*x;}<br>
| |
| double pow3(double x) {return x*x*x;}<br>
| |
| double pow4(double x) {return x*x*x*x;}<br>
| |
| ...
| |
|
| |
| Wymaga to jednak kodowania ręcznego dla każdej potęgi, której
| |
| potrzebujemy. Ten sam efekt możemy osiągnąc za pomocą następującego
| |
| szablonu funkcji:
| |
|
| |
| template<int N> inline double pow(x) {return x*pow<N-1>(x);}<br>
| |
| template<> inline double pow<0>(x) {return 1.0;}
| |
| /*{mod07/code/powx.cpp}{powx.cpp}*/
| |
|
| |
| pod warunkiem, że kompilator rozwinie wszystkie wywołania.
| |
|
| |
| Poniżej zamieszczam wyniki pomiarów wykonania 100 milionów wywołań
| |
| każdej funkcji ({mod07/code/powx.cpp}{powx.cpp}). Czas jest
| |
| podany w sekundach. Zamieściłem wyniki dla różnych ustawień
| |
| optymalizacji.
| |
| <div align=center>
| |
| {| border=1
| |
| |-
| |
| |
| |
| | pow_int(x,5)
| |
| | pow<5>(x)
| |
| |---
| |
| |align="center"|-O0
| |
| |align="center"| 7.22
| |
| |align="center"| 14.78
| |
| |---
| |
| |align="center"|-O1
| |
| |align="center"| 0.37
| |
| |align="center"| 0.04
| |
| |---
| |
| |align="center"|-O2
| |
| |align="center"| 0.42
| |
| |align="center"| 0.05
| |
| |---
| |
| |align="center"|-O3
| |
| |align="center"| 0.42
| |
| |align="center"| 0.05
| |
| |}
| |
| </div>
| |
| Widać dramatyczną różnicę po włączeniu optymalizacji. Wiąże się to
| |
| prawdopodobnie z umożliwieniem rozwijania funkcji <tt>inline</tt>. Potem
| |
| wyniki już się nie zmieniają ale widać, że szablon <tt>pow</tt> wygenerował
| |
| funkcję 10 razy szybszą od pozostałych. Pokazuje to dobitnie, że
| |
| optymalizacja ręczna ciągle ma sens.
| |
|
| |
| ==7.6 Sortowanie bąbelkowe==
| |
|
| |
| Zakończymy ten wykład bardziej skomplikowanym przykładem pokazującym,
| |
| że metaprogramowanie można stosować nie tylko do obliczeń
| |
| numerycznych. Popatrzmy na kod implementujący sortowanie bąbelkowe:
| |
|
| |
| inline void swap (int &a,int &b) {int tmp<nowiki>=</nowiki>a;a<nowiki>=</nowiki>b;b<nowiki>=</nowiki>tmp;};<br>
| |
| void bubble_sort_function (int* data, int N) {<br>
| |
| for(int i <nowiki>=</nowiki> N-1; i>0; --i)<br>
| |
| for(int j<nowiki>=</nowiki>0;j<i;++j)<br>
| |
| if(data[j]>data[j+1]) <br>
| |
| swap(data[j],data[j+1]);<br>
| |
| }
| |
| /* {mod07/code/bubble_template.cpp}{bubbletemplate.cpp} */
| |
|
| |
| Znów widzimy tu dwie pętle i wszystkie uwagi dotyczące funkcji
| |
| <tt>pow_int</tt> tu też się stosują. Postaramy się więc zdefiniować szablon,
| |
| który dokona rozwinięcia tych obu pętli. Np. dla <tt>N<nowiki>=</nowiki>3</tt> chcielibyśmy otrzymać następujący kod:
| |
|
| |
| //i<nowiki>=</nowiki>2 j<nowiki>=</nowiki>0<br>
| |
| if(data[0]>data[1]) swap(data[0],data[1]);<br>
| |
| //i<nowiki>=</nowiki>2 j<nowiki>=</nowiki>1<br>
| |
| if(data[1]>data[2]) swap(data[1],data[2]);<br>
| |
| //i<nowiki>=</nowiki>1 j<nowiki>=</nowiki>0<br>
| |
| if(data[0]>data[1]) swap(data[0],data[1]);
| |
|
| |
| Jeśli Państwo śledzili wykład (przynajmniej ten), to już Państwo wiedzą, że
| |
| pierwszym krokiem musi być przepisanie kodu sortowania na postać rekurencyjną:
| |
|
| |
| void bubble_sort_function (int* data, int N) {<br>
| |
| for(int j<nowiki>=</nowiki>0;j<N-1;++j)<br>
| |
| if(data[j]>data[j+1]) <br>
| |
| swap(data[j],data[j+1]);<br>
| |
| if(N>2)<br>
| |
| bubble_sort_function(data,N-1);<br>
| |
| }
| |
|
| |
| To jeszcze nie to co trzeba bo musimy zapisać pętle w postaci
| |
| rekurencyjnej. Jeśli oznaczymy sobie:
| |
|
| |
| void loop(int * data,int N) {<br>
| |
| for(int j<nowiki>=</nowiki>0;j<N-1;++j)<br>
| |
| if(data[j]>data[j+1]) <br>
| |
| swap(data[j],data[j+1]);<br>
| |
| }
| |
|
| |
| to łatwo zauważyć, że <tt>loop</tt> można zdefiniować następująco:
| |
|
| |
| loop(int *data,int N) {<br>
| |
| if(N>0) {<br>
| |
| if(data[0]>data[1]) swap(data[0],data[1]);<br>
| |
| loop(++data,N-1);<br>
| |
| }<br>
| |
| }
| |
|
| |
| co natychmiast tłumaczy się na szablony:
| |
|
| |
| template<int N> inline void loop(int *data) {<br>
| |
| if(data[0]>data[1]) std::swap(data[0],data[1]);<br>
| |
| loop<N-1>(++data);<br>
| |
| }<br>
| |
| template<> inline void loop<0>(int *data) {};
| |
|
| |
| Szablon funkcji <tt>bubble_sort_template</tt> ma więc postać:
| |
|
| |
| template<int N> inline void bubble_sort_template(int * data) {<br>
| |
| loop<N-1>(data);<br>
| |
| bubble_sort_template<N-1>(data);<br>
| |
| }<br>
| |
| template<> inline void bubble_sort_template<2>(int * data) {<br>
| |
| loop<1>(data);<br>
| |
| };
| |
| /* {mod07/code/bubble_template.cpp}{bubbletemplate.cpp} */
| |
|
| |
| Poniżej znów podaję porównanie czasu wykonywania się 100 milionów
| |
| wywołań funkcji <tt>bubble_sort_function</tt> i <tt>bubble_sort_template</tt> dla tablicy zawierającej 12 liczb całkowitych w kolejności malejącej.
| |
|
| |
| <div align=center>
| |
| {| border=1
| |
| |-
| |
| !|
| |
| | bubblesortfunction(a,12)
| |
| | bubblesorttemplate<12>(a)
| |
| |---
| |
| |align="center"|-O0
| |
| |align="center"|43.3
| |
| |align="center"|42.2
| |
| |-
| |
| |align="center"|-O1
| |
| |align="center"|21.0
| |
| |align="center"|4.8
| |
| |-
| |
| |align="center"|-O2
| |
| |align="center"|20.0
| |
| |align="center"|3.5
| |
| |-
| |
| |align="center"|-O3
| |
| |align="center"|20.0
| |
| |align="center"|3.6
| |
| |}
| |
| </div>
| |
|
| |
| Widać, że wersja na szablonach jest ok. 4-5 razy szybsza. Zachęcam do
| |
| własnych eksperymentów.<br>
| |
| Zaprojektowany szablon działa tylko dla tablic liczb całkowitych. Jest
| |
| to ewidentne ograniczenie, które powinniśmy zlikwidować poprzez dodanie
| |
| doatkowego parametru szablonu. Niestety, prowadzi to do konieczności
| |
| dokonania specjalizacji częściowej, która nie jest dozwolona dla
| |
| szablonów funkcji. Na szczeście nie jest trudno przepisać naszą
| |
| implementację używając szablonów klas. Pozostawiam to jako ćwiczenie
| |
| dla czytelników :).
| |
|
| |
| ==7.7 Rozmiar kodu==
| |
|
| |
| Jak pokazałem, kod generowany przez szablon <tt>bubble_sort_template</tt> jest
| |
| bardziej efektywny. Dzieje się to jednak kosztem jego rozmiaru. Są ku
| |
| temu dwa powody. Po pierwsze podwójna pętla wewnątrz procedury
| |
| <tt>bubble_sort_function</tt> wykonuje <math>(N-1)*(N-2)/2</math> iteracji i tyle
| |
| linijek powinien mieć w pełni rozwinięty kod w szablonie
| |
| <tt>bubble_sort_template</tt>. Po drugie każda instancja szablonu jest
| |
| osobną funkcją, stąd <tt>bubble_sort_template<50></tt> i
| |
| <tt>bubble_sort_template<51></tt> generują osobny kod każda. W celu
| |
| sprawdzenia tych przewidywań przedstawiam poniżej rozmiar wynikowego
| |
| kodu w bajtach dla programu, który kompilował funkcję
| |
| <tt>bubble_sort_template<N></tt>.
| |
|
| |
| <div align=center>
| |
| {| border=1
| |
| |-
| |
| |align="center"|N
| |
| |align="center"|size
| |
| |-
| |
| |align="center"|10
| |
| |align="center"|9333
| |
| |-
| |
| |align="center"|30
| |
| |align="center"|17846
| |
| |-
| |
| |align="center"|50
| |
| |align="center"|21847
| |
| |-
| |
| |align="center"|70
| |
| |align="center"|40399
| |
| |-
| |
| |align="center"|90
| |
| |align="center"|33296
| |
| |-
| |
| |align="center"|100
| |
| |align="center"|53606
| |
| |}
| |
| </div>
| |
| Widać, że choć rozmiar w zasadzie rośnie z <math>N</math>, to ta zależność nie jest
| |
| nawet monotoniczna. Wynika to pewnie z tego, że dla większych <math>N</math>
| |
| kompilator nie dokonuje całkowitego rozwiniecią kodu.
| |
|
| |
| ==7.8 Podsumowanie==
| |
