GCC: Optymalizacja rekurencji ogonowej

Programowanie

Rekurencję nazywamy ogonową kiedy wywołanie rekurencyjne jest ostatnią rzeczą, którą zajmuje się funkcja. Z tego właśnie powodu da się ją bardzo łatwo optymalizować. Również najpopularniejszy kompilator języka C++, czyli g++ dostarcza nam w opcjach optymalizacyjnych przekształcanie rekurencji ogonowej na mniej zasobożerną postać.

Iteracja

Postacią zoptymalizowanej rekurencji ogonowej jest dobrze znana iteracja. Dla przykładu sumowanie liczb od 0 do n można zapisać w postaci rekurencji tak:

1 def sumuj(n, suma):
2     if n == 0:
3         break
4 
5     return sumuj(n-1, suma+n);

Rekurencyjne wywołanie jest tutaj na końcu - funkcja nie korzysta dalej z wyników swojego rekurencyjnego wywołania. W formie funkcji iteracyjnej wyglądałoby to tak:

1 while true:
2     suma = suma + i
3     if i == n:
4         break
5 
6     i = i + 1

Przykład 1

Na początek sprawdzimy wydajność funkcji iteracyjnej, rekurencyjnej i rekurencji ogonowej. Funkcje te nie robią nic pożytecznego, ale każda z nich spełnia odpowiedni warunek.

 1 int rekurencja(int n)
 2 {
 3   if (n > 0)
 4     rekurencja(n-1);
 5 
 6   return 1;
 7 }
 8 
 9 int rekurencja_ogonowa(int n)
10 {
11   if (n == 0)
12     return 1;
13 
14   return rekurencja_ogonowa(n-1);
15 }
16 
17 int iteracja(int n)
18 {
19   for (int i = n; i >= 0; --i)
20   {
21     if (n == 0)
22       return 1;
23   }
24 }

Uruchamiam odpowiedni program testujący (kod źródłowy na Gist, Makefile).

Otrzymujemy wyniki w sekundach:

 1 Uruchomiono: ./run
 2    zwykla:     22.84
 3   ogonowa:     23.95
 4  iteracja:     12.52
 5 Uruchomiono: ./run_o1
 6    zwykla:      8.75
 7   ogonowa:      8.51
 8  iteracja:       3.4
 9 Uruchomiono: ./run_o2
10    zwykla:      6.84
11   ogonowa:      0.18
12  iteracja:      0.18
13 Uruchomiono: ./run_o3
14    zwykla:      2.25
15   ogonowa:      0.17
16  iteracja:      0.18

Jak widać na powyższym listingu już optymalizacja drugiego stopnia zapewnia zamianę rekurencji ogonowej na iterację.

Przykład 2

Kolejnym przykładem będzie sumowanie pokazane na samym początku. Tym razem przetestujemy tylko rekurencję ogonową i iterację. Do testów wykorzystam te funkcje:

 1 int iter(int n)
 2 {
 3   int sum = 0;
 4   for (int i = 0; true; ++i)
 5   {
 6     sum += i;
 7 
 8     if (i == n)
 9       break;
10   }
11 
12   return sum;
13 }
14 
15 int rec(int n, int sum = 0)
16 {
17   if (n == 0)
18     return sum;
19 
20   return rec(n-1, sum+n);
21 }

Pełny program testujący (kod na Gist) po uruchomieniu zwraca następujące wyniki:

 1 Uruchomiono: ./suma
 2  iteracja:      6.49
 3 rekurencja:     13.43
 4 Uruchomiono: ./suma_o1
 5  iteracja:      2.08
 6 rekurencja:      4.49
 7 Uruchomiono: ./suma_o2
 8  iteracja:      1.72
 9 rekurencja:      1.67
10 Uruchomiono: ./suma_o3
11  iteracja:      0.58
12 rekurencja:      0.76

Tutaj również optymalizacja drugiego poziomu zapewniła nam prawie dokładnie taką samą wydajność rekurencji ogonowej jak iteracji.

Podsumowanie

Pierwszy raz z rekurencją ogonową spotkałem się przy okazji nauki podstaw języka Haskell. Jest to język funkcyjny, który nie posiada żadnych pętli. Narzędziem do wykonywania tych samych, powtarzalnych operacji są właśnie rekurencje. Rekurencje ogonowe pozwalają na zoptymalizowanie programu. Dzięki nim aplikacja napisana w języku, w którym jawnie nie można użyć instrukcji iteracyjnej może działać z szybkością iteracji.