Co to jest optymalizacja połączeń ogonowych?

Po prostu, czym jest optymalizacja połączeń ogonowych?

Mówiąc dokładniej, jakie są małe fragmenty kodu, w których można je zastosować, a gdzie nie, z wyjaśnieniem, dlaczego?

Optymalizacja wywołania ogonowego polega na tym, że można uniknąć przydzielenia nowej ramki stosu dla funkcji, ponieważ funkcja wywołująca zwróci po prostu wartość otrzymaną z wywołanej funkcji. Najczęstszym zastosowaniem jest rekurencja ogona, gdzie funkcja rekurencyjna napisana w celu skorzystania z optymalizacji wywołania ogona może wykorzystywać stałą przestrzeń stosu.

Schemat jest jednym z niewielu języków programowania, które gwarantują w specyfikacji, że każda implementacja musi zapewniać tę optymalizację (JavaScript również, począwszy od ES6) , więc oto dwa przykłady funkcji silni w Schemacie:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

Pierwsza funkcja nie jest rekurencyjna, ponieważ po wykonaniu wywołania rekurencyjnego funkcja musi śledzić mnożenie, które musi wynikać z wyniku po powrocie połączenia. W związku z tym stos wygląda następująco:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

W przeciwieństwie do tego, ślad stosu dla rekurencyjnej silni rekurencyjnej wygląda następująco:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Jak widać, musimy tylko śledzić tę samą ilość danych dla każdego wezwania do oględzin faktów, ponieważ po prostu zwracamy wartość, którą docieramy na sam szczyt. Oznacza to, że nawet gdybym zadzwonił (fakt 1000000), potrzebuję tylko tyle samo miejsca co (fakt 3). Nie dzieje się tak w przypadku faktu nierekurencyjnego, dlatego tak duże wartości mogą spowodować przepełnienie stosu.

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

Zaczynamy od oczywistej rekurencyjnej definicji

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

Funkcja kończy się wywołaniem ogona, jeśli ostatnią operacją przed powrotem funkcji jest kolejne wywołanie funkcji. Jeśli to wywołanie wywołuje tę samą funkcję, jest rekurencyjne.

Choć fac()na pierwszy rzut oka wygląda rekurencyjnie, nie jest tak, jak się naprawdę dzieje

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

tzn. ostatnia operacja to mnożenie, a nie wywołanie funkcji.

Możliwe jest jednak przepisanie w fac()celu rekurencji przez przekazanie skumulowanej wartości w dół łańcucha połączeń jako dodatkowy argument i przekazanie tylko końcowego wyniku w górę jako wartości zwracanej:

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);
}

Dlaczego to jest przydatne? Ponieważ natychmiast wracamy po wywołaniu tail, możemy odrzucić poprzednią ramkę stosu przed wywołaniem funkcji w pozycji końcowej lub, w przypadku funkcji rekurencyjnych, ponownie użyć ramki stosu bez zmian.

Optymalizacja wywołania ogona 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;
}

Można to wprowadzić fac()i doszliśmy 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 z

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ć rekurencję ogonem iteracją, co jest znacznie bardziej wydajne, 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 wywoływać funkcję i nie zajmować dodatkowego miejsca na stosie. Jedynie sytuacja, w której to się dzieje, jeśli ostatnia instrukcja wykonywana w funkcji f jest wywołanie funkcji g (uwaga: g może być f ). Kluczem tutaj jest to, że f przestrzeni nie potrzebuje już Stack - to po prostu wywołuje g , a następnie wraca cokolwiek g wróci. W takim przypadku można dokonać optymalizacji, aby g po prostu uruchomił i zwrócił dowolną wartość do rzeczy, która wywołała f.

Ta optymalizacja może powodować, że wywołania rekurencyjne zajmują stałe miejsce na stosie, zamiast eksplodować.

Przykład: tej funkcji czynnikowej nie można zoptymalizować za pomocą TCO:

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

Ta funkcja wykonuje inne czynności niż wywoływanie innej funkcji w instrukcji return.

Poniższą funkcję można zoptymalizować za pomocą TCO:

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)

Wynika to z faktu, że ostatnią rzeczą, która wydarzy się w którejkolwiek z tych funkcji, jest wywołanie innej funkcji.

Prawdopodobnie najlepszym opisem na wysokim poziomie, jaki znalazłem dla wezwań ogona, rekurencyjnych wezwań ogona i optymalizacji ogona ogona jest post na blogu

„Co do cholery: wezwanie do ogona”

autor: Dan Sugalski. Na temat optymalizacji wezwania ogona pisze:

Zastanówmy się przez chwilę nad tą prostą funkcją:

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

Co możesz zrobić, a raczej Twój kompilator językowy? Cóż, może to zmienić kod formularza return somefunc();w sekwencję niskiego poziomu pop stack frame; goto somefunc();. W naszym przykładzie oznacza to, że zanim zadzwonimy bar, foooczyści się, a następnie, zamiast wywoływać barjako podprogram, wykonujemy gotooperację niskiego poziomu do początku bar. Foojest już wyczyszczony ze stosu, więc kiedy barzaczyna, wygląda na to, że ktokolwiek zadzwonił foo, naprawdę zadzwonił bar, a kiedy barzwraca jego wartość, zwraca go bezpośrednio temu, kto zadzwonił foo, zamiast zwracać go temu, fooktóry następnie zwróciłby go dzwoniącemu.

I na rekurencji ogona:

Rekurencja ogona ma miejsce, gdy funkcja jako ostatnia operacja zwraca wynik wywołania samego siebie . Rekurencja ogona jest łatwiejsza, ponieważ zamiast skakać gdzieś na początek jakiejś losowej funkcji, po prostu robisz goto z powrotem na początek siebie, co jest cholernie prostą rzeczą.

Aby to:

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

cicho zamienia się w:

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

W tym opisie podoba mi się to, jak zwięzłe i łatwe jest uchwycenie osób wywodzących się z imperatywnego języka (C, C ++, Java)

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

TCO dotyczy specjalnego przypadku rekurencji. Istotą tego jest to, że jeśli ostatnią rzeczą, którą robisz w funkcji, jest wywołanie samego siebie (np. Wywoływanie się z pozycji „ogona”), kompilator może to zoptymalizować, aby działał jak iteracja zamiast standardowej rekurencji.

Widzisz, zwykle podczas rekurencji środowisko wykonawcze musi śledzić wszystkie rekurencyjne połączenia, aby po powrocie można było wznowić poprzednie połączenie i tak dalej. (Spróbuj ręcznie zapisać wynik wywołania rekurencyjnego, aby uzyskać wizualny obraz tego, jak to działa.) Śledzenie wszystkich wywołań zajmuje miejsce, co staje się znaczące, gdy funkcja wywołuje samą siebie. Ale dzięki TCO można po prostu powiedzieć „wróć do początku, tylko tym razem zmień wartości parametrów na nowe”. Może to zrobić, ponieważ nic po wywołaniu rekurencyjnym nie odnosi się do tych wartości.

Przykład minimalnego działania GCC z analizą dezasemblacji x86

Zobaczmy, jak GCC może automatycznie wykonać dla nas optymalizację wywołania ogona, patrząc na wygenerowany zespół.

Będzie to służyć jako niezwykle konkretny przykład tego, co wspomniano w innych odpowiedziach, takich jak https://stackoverflow.com/a/9814654/895245, że optymalizacja może przekształcić rekurencyjne wywołania funkcji w pętlę.

To z kolei oszczędza pamięć i poprawia wydajność, ponieważ dostęp do pamięci jest często główną rzeczą, która powoduje, że programy są obecnie wolne .

Jako dane wejściowe dajemy GCC niezoptymalizowany czynnikowy oparty na stosie:

tail_call.c

#include <stdio.h>
#include <stdlib.h>

unsigned factorial(unsigned n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(int argc, char **argv) {
    int input;
    if (argc > 1) {
        input = strtoul(argv[1], NULL, 0);
    } else {
        input = 5;
    }
    printf("%u\n", factorial(input));
    return EXIT_SUCCESS;
}

GitHub w górę .

Kompiluj i demontuj:

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

gdzie -foptimize-sibling-callsjest nazwa uogólnienia połączeń ogonowych według man gcc:

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

jak wspomniano w: Jak sprawdzić, czy gcc przeprowadza optymalizację rekurencji ogona?

Wybieram, -O1ponieważ:

• optymalizacja nie jest wykonywana -O0. Podejrzewam, że dzieje się tak, ponieważ brakuje wymaganych pośrednich transformacji.
• -O3 produkuje bezbożny, efektywny kod, który nie byłby zbyt pouczający, chociaż jest również zoptymalizowany dla ogona.

Demontaż za pomocą -fno-optimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

Z -foptimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

Kluczowa różnica między nimi polega na tym, że:

• te -fno-optimize-sibling-callszastosowania callq, które jest typowe dla zoptymalizowanej wywołanie funkcji.

  Ta instrukcja wypycha adres zwrotny na stos, zwiększając go.

  Co więcej, ta wersja również działa push %rbx, co przesuwa %rbxsię na stos .

  GCC robi to, ponieważ przechowuje edi, który jest pierwszym argumentem funkcji ( n) ebx, a następnie wywołuje factorial.

  GCC musi to zrobić, ponieważ przygotowuje się do kolejnego połączenia z factorial, które użyje nowego edi == n-1.

  Wybiera, ebxponieważ ten rejestr jest zachowywany przez callee : Jakie rejestry są zachowywane przez wywołanie funkcji linux x86-64, aby wywołanie podrzędne factorialnie zmieniło go i nie straciło n.

• -foptimize-sibling-callsnie korzysta z żadnych instrukcji, które popychają do stosu: to tylko robi gotoskoki wewnątrz factorialz instrukcjami jei jne.

  Dlatego ta wersja jest odpowiednikiem pętli while, bez żadnych wywołań funkcji. Wykorzystanie stosu jest stałe.

Testowane w Ubuntu 18.10, GCC 8.2.

Popatrz tutaj:

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

Jak zapewne wiesz, wywołania funkcji rekurencyjnych mogą siać spustoszenie na stosie; szybko brakuje miejsca na stosie. Optymalizacja wywołania ogona to sposób, w jaki można utworzyć algorytm stylu rekurencyjnego, który wykorzystuje stałą przestrzeń stosu, dlatego nie rośnie i rośnie, a pojawiają się błędy stosu.

1. Powinniśmy upewnić się, że w samej funkcji nie ma żadnych instrukcji goto. Należy zachować ostrożność, ponieważ wywołanie funkcji jest ostatnią rzeczą w funkcji callee.

2. Rekurencje na dużą skalę mogą to wykorzystać do optymalizacji, ale w małej skali, narzut instrukcji do wywołania funkcji wywołanie ogona zmniejsza rzeczywisty cel.

3. TCO może spowodować, że funkcja będzie działać wiecznie:

   void eternity()
   {
       eternity();
   }
   

Podejście do funkcji rekurencyjnej ma problem. Tworzy stos wywołań o rozmiarze O (n), co czyni nasz całkowity koszt pamięci O (n). To sprawia, że ​​jest podatny na błąd przepełnienia stosu, gdy stos wywołań staje się zbyt duży i zabraknie miejsca.

Schemat optymalizacji ogona (TCO). Gdzie może zoptymalizować funkcje rekurencyjne, aby uniknąć tworzenia wysokiego stosu wywołań, a tym samym oszczędza koszt pamięci.

Istnieje wiele języków, które wykonują TCO (JavaScript, Ruby i kilka C), podczas gdy Python i Java nie robią TCO.

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

W języku funkcjonalnym optymalizacja wywołania ogonowego jest tak, jakby wywołanie funkcji mogło zwrócić jako wynik częściowo wyrażone wyrażenie, które następnie zostałoby ocenione przez wywołującego.

f x = g x

f 6 zmniejsza się do g 6. Jeśli więc implementacja może zwrócić wynik g 6, a następnie wywołać to wyrażenie, zapisuje ramkę stosu.

Również

f x = if c x then g x else h x.

Zmniejsza do f 6 do g 6 lub h 6. Więc jeśli implementacja oceni c 6 i stwierdzi, że jest to prawda, może zmniejszyć,

if true then g x else h x ---> g x

f x ---> h x

Prosty interpreter optymalizacji połączeń innych niż ogon może wyglądać tak:

class simple_expresion
{
    ...
public:
    virtual ximple_value *DoEvaluate() const = 0;
};

class simple_value
{
    ...
};

class simple_function : public simple_expresion
{
    ...
private:
    simple_expresion *m_Function;
    simple_expresion *m_Parameter;

public:
    virtual simple_value *DoEvaluate() const
    {
        vector<simple_expresion *> parameterList;
        parameterList->push_back(m_Parameter);
        return m_Function->Call(parameterList);
    }
};

class simple_if : public simple_function
{
private:
    simple_expresion *m_Condition;
    simple_expresion *m_Positive;
    simple_expresion *m_Negative;

public:
    simple_value *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive.DoEvaluate();
        }
        else
        {
            return m_Negative.DoEvaluate();
        }
    }
}

Interpretator optymalizacji połączeń końcowych może wyglądać tak:

class tco_expresion
{
    ...
public:
    virtual tco_expresion *DoEvaluate() const = 0;
    virtual bool IsValue()
    {
        return false;
    }
};

class tco_value
{
    ...
public:
    virtual bool IsValue()
    {
        return true;
    }
};

class tco_function : public tco_expresion
{
    ...
private:
    tco_expresion *m_Function;
    tco_expresion *m_Parameter;

public:
    virtual tco_expression *DoEvaluate() const
    {
        vector< tco_expression *> parameterList;
        tco_expression *function = const_cast<SNI_Function *>(this);
        while (!function->IsValue())
        {
            function = function->DoCall(parameterList);
        }
        return function;
    }

    tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList)
    {
        p_ParameterList.push_back(m_Parameter);
        return m_Function;
    }
};

class tco_if : public tco_function
{
private:
    tco_expresion *m_Condition;
    tco_expresion *m_Positive;
    tco_expresion *m_Negative;

    tco_expresion *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive;
        }
        else
        {
            return m_Negative;
        }
    }
}