Co To Jest Optymalizacja Połączeń Ogonowych?

Przejdźmy przez prosty przykład: funkcja czynnikowa zaimplementowana w C.

Zaczynamy od oczywistej definicji rekurencyjnej

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Funkcja kończy się wywołaniem ogonowym, jeśli ostatnia operacja przed zwróceniem funkcji jest kolejnym wywołaniem funkcji. Jeśli to wywołanie wywoła tę samą funkcję, jest rekurencyjne.

Chociaż fac() wygląda na rekurencyjny na pierwszy rzut oka, to nie jest tak, jak to, co się naprawdę dzieje

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

Ie ostatnią operacją jest mnożenie, a nie wywołanie funkcji.

Możliwe jest jednak przepisanie fac() jako rekurencyjny, przekazując nagromadzoną wartość w dół łańcucha wywołań jako dodatkowy argument i przekazując tylko końcowy wynik ponownie jako wartość zwracaną:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Optymalizacja wywołania ogonowego przekształca nasz kod rekurencyjny w

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

To można wkleić do fac() i docieramy do

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Co jest równoważne

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Jak widzimy tutaj, wystarczająco zaawansowany optymalizator może zastąpić rekursję ogonową iteracją, która jest o wiele bardziej efektywna, ponieważ unikasz narzutu wywołania funkcji i używasz tylko stałej ilości miejsca na stosie.

TCO (Tail Call Optimization) to proces, w którym inteligentny kompilator może wykonać wywołanie funkcji i nie zająć dodatkowego miejsca na stosie. Jedyną sytuacją, w której tak się dzieje, jest sytuacja, w której ostatnia Instrukcja wykonywana w funkcji f jest wywołaniem funkcji g (Uwaga: g może być f ). Kluczem jest to, że f nie potrzebuje już przestrzeni stosu - po prostu wywołuje g, a następnie zwraca to, co g zwróci. W tym przypadku optymalizacja może być wykonane, że g po prostu działa i zwraca jakąkolwiek wartość będzie to miało do rzeczy, która nazywa się f.

Ta optymalizacja może sprawić, że wywołania rekurencyjne zajmą stałą przestrzeń stosu, a nie eksplodują.

Przykład: ta funkcja czynnikowa nie jest TCOptimizable:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Ta funkcja robi rzeczy poza wywołaniem innej funkcji w instrukcji return.

Poniższa funkcja jest TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

To dlatego, że ostatnia rzecz, która wydarzy się w którymś z tych funkcja polega na wywołaniu innej funkcji.

Prawdopodobnie najlepszym opisem wysokiego poziomu, jaki znalazłem dla wywołań ogona, rekurencyjnych wywołań ogona i optymalizacji wywołań ogona, jest post na blogu

"co to do cholery jest:"

Dan Sugalski. O optymalizacji wywołania ogona pisze:

Rozważmy przez chwilę tę prostą funkcję:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Więc co możesz zrobić, a raczej kompilator języka? Cóż, co może zrobić, to przekształcić kod widoku return somefunc(); w sekwencję niskiego poziomu pop stack frame; goto somefunc();. W naszym przykładzie oznacza to, że zanim wywołamy bar, foo czyści się, a następnie, zamiast wywoływać bar jako podprogram, wykonujemy operację niskiego poziomu goto na początek bar. Foo jest już wyczyszczone ze stosu, więc kiedy bar zaczyna wygląda to tak, jakby ktoś wywołał foo naprawdę wywołał bar, a kiedy bar zwraca jego wartość, zwraca ją bezpośrednio temu, kto wywołał foo, zamiast zwracać ją do foo, który następnie zwróci ją do swojego serwera. dzwoniący.

I o rekurencji ogonowej:

Rekurencja ogonowa ma miejsce, gdy funkcja, jako ostatnia operacja, zwróci wynik wywołania samego siebie . Rekurencja ogonowa jest łatwiejsza do opanowania bo zamiast przeskoczyć na początek jakiegoś przypadkowego funkcja gdzieś, po prostu zrobić goto powrót do początku siebie, co jest cholernie prostą rzeczą do zrobienia.

Tak, że to:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

Po cichu się odwraca do:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

Zauważ przede wszystkim, że nie wszystkie języki go obsługują.

TCO stosuje się do specjalnego przypadku rekurencji. Chodzi o to, że jeśli ostatnią rzeczą jaką wykonujesz w funkcji jest wywołanie samej siebie (np. wywołanie samej siebie z pozycji "ogona"), może to być zoptymalizowane przez kompilator tak, aby działał jak iteracja zamiast standardowej rekursji.

Widzisz, normalnie podczas rekurencji, runtime musi śledzić wszystkie rekurencyjne wywołania, tak aby po powrocie mogło zostać wznowione przy poprzednim zadzwoń i tak dalej. (Spróbuj ręcznie zapisać wynik rekurencyjnego wywołania, aby uzyskać wizualny obraz tego, jak to działa.) Śledzenie wszystkich połączeń zajmuje miejsce, co staje się znaczące, gdy funkcja wywołuje się dużo. Ale z TCO może po prostu powiedzieć " wróć do początku, tylko tym razem zmień wartości parametrów na te nowe."Może to zrobić, ponieważ nic po wywołaniu rekurencyjnym nie odnosi się do tych wartości.

Zobacz tutaj:

Http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Jak zapewne wiesz, rekurencyjne wywołania funkcji mogą siać spustoszenie na stosie; łatwo jest szybko wyczerpać przestrzeń stosu. Tail Call optimization jest sposobem, w jaki można utworzyć rekurencyjny algorytm stylu, który wykorzystuje stałą przestrzeń stosu, dlatego nie rośnie i nie rośnie i dostajesz błędy stosu.

1. Powinniśmy upewnić się, że w samej funkcji nie ma instrukcji goto .. wywołanie funkcji jest ostatnią rzeczą w funkcji callee.

2. Rekurencje wielkoskalowe mogą używać tego do optymalizacji, ale w małej skali, Instrukcja narzutu na wywołanie funkcji jako wywołanie ogonowe zmniejsza rzeczywisty cel.

3. TCO może powodować wiecznie działającą funkcję:

   void eternity()
   {
       eternity();
   }
   

Podejście funkcji rekurencyjnych ma problem. Buduje stos wywołań O (n), co sprawia, że nasz całkowity koszt pamięci O(n). To sprawia, że jest podatny na błąd przepełnienia stosu, w którym stos wywołań staje się zbyt duży i kończy się miejsce. System optymalizacji kosztów ogonowych (TCO). Gdzie może zoptymalizować funkcje rekurencyjne, aby uniknąć budowania wysokiego stosu wywołań, a tym samym oszczędza koszty pamięci.

Istnieje wiele języków, które robią TCO jak (Javascript, Ruby i kilka C), gdzie jako Python a Java nie robi TCO.

Język JavaScript potwierdził użycie:) http://2ality.com/2015/06/tail-call-optimization.html