Qu'est-ce que l'optimisation des appels de queue?

Très simplement, qu'est-ce que l'optimisation des appels de queue?

Plus précisément, quels sont quelques petits extraits de code où il pourrait être appliqué, et où non, avec une explication de pourquoi?

L'optimisation des appels de queue est l'endroit où vous pouvez éviter d'allouer une nouvelle trame de pile pour une fonction car la fonction appelante retournera simplement la valeur qu'elle obtient de la fonction appelée. L'utilisation la plus courante est la récursivité de queue, où une fonction récursive écrite pour tirer parti de l'optimisation des appels de queue peut utiliser un espace de pile constant.

Scheme est l'un des rares langages de programmation qui garantissent dans la spécification que toute implémentation doit fournir cette optimisation (JavaScript le fait également, à partir d'ES6) , voici donc deux exemples de la fonction factorielle dans Scheme:

(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))

La première fonction n'est pas récursive de queue car lorsque l'appel récursif est effectué, la fonction doit garder une trace de la multiplication qu'elle doit faire avec le résultat après le retour de l'appel. En tant que telle, la pile se présente comme suit:

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

En revanche, la trace de pile pour la factorielle récursive de queue se présente comme suit:

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

Comme vous pouvez le voir, nous avons seulement besoin de garder la trace de la même quantité de données pour chaque appel à fact-tail parce que nous renvoyons simplement la valeur que nous obtenons tout en haut. Cela signifie que même si je devais appeler (fait 1000000), je n'ai besoin que de la même quantité d'espace que (fait 3). Ce n'est pas le cas avec le fait non récursif de queue, et en tant que telles grandes valeurs peuvent provoquer un débordement de pile.

Voyons un exemple simple: la fonction factorielle implémentée en C.

Nous commençons par la définition récursive évidente

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

Une fonction se termine par un appel de fin si la dernière opération avant le retour de la fonction est un autre appel de fonction. Si cet appel invoque la même fonction, il est récursif de queue.

Même si cela fac()semble récursif à première vue, ce n'est pas ce qui se passe réellement

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

c'est-à-dire que la dernière opération est la multiplication et non l'appel de fonction.

Cependant, il est possible de réécrire fac()pour être récursif en faisant passer la valeur accumulée vers le bas de la chaîne d'appel en tant qu'argument supplémentaire et en ne transmettant à nouveau que le résultat final comme valeur de retour:

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

Maintenant, pourquoi est-ce utile? Parce que nous revenons immédiatement après l'appel de queue, nous pouvons ignorer le stackframe précédent avant d'appeler la fonction en position de queue, ou, en cas de fonctions récursives, réutiliser le stackframe tel quel.

L'optimisation des appels de queue transforme notre code récursif en

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

Cela peut être intégré fac()et nous arrivons à

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

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

ce qui équivaut à

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

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

    return acc;
}

Comme nous pouvons le voir ici, un optimiseur suffisamment avancé peut remplacer la récursivité de queue par l'itération, ce qui est beaucoup plus efficace car vous évitez la surcharge des appels de fonction et n'utilisez qu'une quantité constante d'espace de pile.

TCO (Tail Call Optimization) est le processus par lequel un compilateur intelligent peut appeler une fonction et ne prendre aucun espace de pile supplémentaire. La seule situation dans laquelle cela se produit est si la dernière instruction exécutée dans une fonction f est un appel à une fonction g (Remarque: g peut être f ). La clé ici est que f n'a plus besoin d'espace de pile - il appelle simplement g puis retourne tout ce que g retournerait. Dans ce cas, l'optimisation peut être faite pour que g s'exécute et renvoie la valeur qu'il aurait à la chose qui a appelé f.

Cette optimisation peut faire en sorte que les appels récursifs prennent un espace de pile constant plutôt que d'exploser.

Exemple: cette fonction factorielle n'est pas TCOptimisable:

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

Cette fonction fait des choses en plus d'appeler une autre fonction dans sa déclaration de retour.

Cette fonction ci-dessous est TCOptimisable:

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)

En effet, la dernière chose qui se produit dans l'une de ces fonctions est d'appeler une autre fonction.

La meilleure description de haut niveau que j'ai trouvée pour les appels de queue, les appels de queue récursifs et l'optimisation des appels de queue est probablement le billet de blog

"Qu'est-ce que c'est que ça: un appel de queue"

par Dan Sugalski. Sur l'optimisation des appels de queue, il écrit:

Considérons un instant cette fonction simple:

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

Alors, que pouvez-vous, ou plutôt votre compilateur de langage, faire? Eh bien, ce qu'il peut faire, c'est transformer le code du formulaire return somefunc();en séquence de bas niveau pop stack frame; goto somefunc();. Dans notre exemple, cela signifie avant d'appeler bar, de se foonettoyer puis, plutôt que d'appeler en bartant que sous-programme, nous effectuons une gotoopération de bas niveau au début de bar. Foos'est déjà nettoyé de la pile, donc au bardémarrage, il ressemble à celui qui a appelé fooa vraiment appelé bar, et lorsqu'il barretourne sa valeur, il le renvoie directement à celui qui a appelé foo, plutôt que de le renvoyer à fooqui le retournerait ensuite à son appelant.

Et sur la récursivité de la queue:

La récursivité de queue se produit si une fonction, comme sa dernière opération, retourne le résultat de l'appel elle-même . La récursivité de la queue est plus facile à gérer, car plutôt que d'avoir à sauter au début d'une fonction aléatoire quelque part, il vous suffit de revenir au début de vous-même, ce qui est sacrément simple à faire.

Pour que ceci:

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

devient tranquillement transformé en:

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

Ce que j'aime dans cette description, c'est à quel point il est succinct et facile à saisir pour ceux qui viennent d'un contexte de langage impératif (C, C ++, Java)

Notez tout d'abord que toutes les langues ne le prennent pas en charge.

Le TCO s'applique à un cas particulier de récursivité. L'essentiel est que si la dernière chose que vous faites dans une fonction est de s'appeler elle-même (par exemple, elle s'appelle à partir de la position "tail"), cela peut être optimisé par le compilateur pour agir comme une itération au lieu d'une récursivité standard.

Vous voyez, normalement pendant la récursivité, le runtime doit garder une trace de tous les appels récursifs, de sorte que lorsque l'un revient, il peut reprendre à l'appel précédent et ainsi de suite. (Essayez d'écrire manuellement le résultat d'un appel récursif pour avoir une idée visuelle de la façon dont cela fonctionne.) Le suivi de tous les appels prend de la place, ce qui devient significatif lorsque la fonction s'appelle souvent. Mais avec TCO, il peut simplement dire "retour au début, mais cette fois changez les valeurs des paramètres en ces nouveaux". Il peut le faire car rien après l'appel récursif ne fait référence à ces valeurs.

Exemple exécutable minimal GCC avec analyse de démontage x86

Voyons comment GCC peut automatiquement effectuer des optimisations d'appel de queue pour nous en regardant l'assembly généré.

Cela servira d'exemple extrêmement concret de ce qui a été mentionné dans d'autres réponses telles que https://stackoverflow.com/a/9814654/895245 que l'optimisation peut convertir les appels de fonctions récursives en boucle.

À son tour, cela économise de la mémoire et améliore les performances, car les accès à la mémoire sont souvent le principal facteur qui ralentit les programmes de nos jours .

En entrée, nous donnons à GCC une factorielle basée sur une pile naïve non optimisée:

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 en amont .

Compilez et démontez:

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

où -foptimize-sibling-callsest le nom de la généralisation des appels de queue selon man gcc:

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

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

comme mentionné à: Comment puis-je vérifier si gcc effectue une optimisation de récursivité de queue?

Je choisis -O1car:

• l'optimisation ne se fait pas avec -O0. Je soupçonne que c'est parce qu'il manque des transformations intermédiaires requises.
• -O3 produit un code impie efficace qui ne serait pas très éducatif, bien qu'il soit également optimisé pour les appels de queue.

Démontage avec -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

Avec -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

La principale différence entre les deux est que:

• les -fno-optimize-sibling-callsutilisations callq, qui est l'appel de fonction non optimisé typique.

  Cette instruction pousse l'adresse de retour vers la pile, donc en l'augmentant.

  De plus, cette version le fait aussi push %rbx, ce qui pousse %rbxà la pile .

  GCC fait cela parce qu'il stocke edi, qui est le premier argument de fonction ( n) dans ebx, puis appelle factorial.

  GCC doit le faire car il se prépare pour un autre appel à factorial, qui utilisera le nouveau edi == n-1.

  Il choisit ebxparce que ce registre est sauvegardé par appel: quels registres sont conservés via un appel de fonction linux x86-64 afin que le sous- appel ne le modifie factorialpas et ne perde pas n.

• le -foptimize-sibling-callsn'utilise pas d'instructions qui poussent vers la pile: il ne fait que gotosauter factorialavec les instructions jeet jne.

  Par conséquent, cette version équivaut à une boucle while, sans aucun appel de fonction. L'utilisation de la pile est constante.

Testé dans Ubuntu 18.10, GCC 8.2.

Regardez ici:

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

Comme vous le savez probablement, les appels de fonction récursifs peuvent faire des ravages sur une pile; il est facile de manquer rapidement d'espace de pile. L'optimisation des appels de queue est un moyen par lequel vous pouvez créer un algorithme de style récursif qui utilise un espace de pile constant, donc il ne grandit pas et vous obtenez des erreurs de pile.

1. Nous devons nous assurer qu'il n'y a pas d'instructions goto dans la fonction elle-même.

2. Les récursions à grande échelle peuvent l'utiliser pour des optimisations, mais à petite échelle, la surcharge d'instructions pour faire de la fonction appeler un appel de queue réduit le but réel.

3. Le TCO peut provoquer une fonction toujours active:

   void eternity()
   {
       eternity();
   }
   

L'approche de la fonction récursive a un problème. Il crée une pile d'appels de taille O (n), ce qui fait que notre mémoire totale coûte O (n). Cela le rend vulnérable à une erreur de dépassement de pile, où la pile d'appels devient trop grande et manque d'espace.

Schéma d'optimisation des appels de queue (TCO). Où il peut optimiser les fonctions récursives pour éviter de constituer une pile d'appels élevée et donc d'économiser le coût de la mémoire.

Il existe de nombreux langages qui font du TCO comme (JavaScript, Ruby et quelques C) alors que Python et Java ne font pas de TCO.

La langue JavaScript a confirmé l'utilisation de :) http://2ality.com/2015/06/tail-call-optimization.html

Dans un langage fonctionnel, l'optimisation des appels de queue est comme si un appel de fonction pouvait renvoyer une expression partiellement évaluée comme résultat, qui serait ensuite évaluée par l'appelant.

f x = g x

f 6 se réduit à g 6. Donc, si l'implémentation pouvait renvoyer g 6 comme résultat, puis appeler cette expression, elle enregistrerait une trame de pile.

Aussi

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

Réduit à f 6 à g 6 ou h 6. Donc, si l'implémentation évalue c 6 et trouve que c'est vrai, alors elle peut réduire,

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

f x ---> h x

Un simple interpréteur d'optimisation d'appel non-queue pourrait ressembler à ceci,

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

Un interpréteur d'optimisation des appels de queue pourrait ressembler à ceci,

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