Forum Programmation.c Optimisation de la récursivité

Posté par  (site web personnel) .
Étiquettes : aucune
0
27
mai
2007
Bonjour,

J'ai écrit un algorithme récursif que je n'arrive pas à transformer en aglorithme itératif. En plus le code est assez simple de lecture dans sa version récursive.

Dans un soucis d'optimisation, je voudrais donc savoir si il n'est pas possible de stocker les adresses de retour de fonction ailleurs que dans une pile. Ou du moins, s'il existe un quelconque mécanisme d'optimisation pour la récursivité.

Merci d'avance,

  • # Je ne sais pas comment faire autrement

    Posté par  (site web personnel) . Évalué à 1.

    Personnellement, je ne vois pas comment faire autrement!

    Il faut bien mémoriser les differents états, pour retrouver le contexte n-1 en cas d'échec de la branche ...

    • [^] # Re: Je ne sais pas comment faire autrement

      Posté par  (site web personnel) . Évalué à 1.

      Et il n'y a pas moyen de stocker ça dans une mémoire plus rapide ? Comme la cache de mon processeur par exemple ?

      • [^] # Re: Je ne sais pas comment faire autrement

        Posté par  . Évalué à 1.

        l'optimisation de la recursivité par de l'iteratif ?
        je suis sceptique sauf dans le cas ou tu as un nombre defini d'iteration connu à l'avance.

        apres, forcer l'usage du cache processeur, il faut pouvoir coder en assembleur pour taper directement dedans.

        • [^] # Re: Je ne sais pas comment faire autrement

          Posté par  (site web personnel) . Évalué à 1.

          Ce que je voulais dire c'est que l'algoirthme itératif équivalent me semble plus performant, il permet d'éviter de stocker toutes les adresses de retour sur la pile. Etant donné que je n'arrive pas à passer de l'un à l'autre et que l'algorithme récursif est, me semble-t'il, assez clair, je me demandais s'il n'y a pas moyen de stocker les adresses de retour dans la cache du processeur, si oui auriez-vous quelques indications ?

          • [^] # Re: Je ne sais pas comment faire autrement

            Posté par  (site web personnel) . Évalué à 5.

            Pour faire court: Non ce n'est pas possible, même en optimisant le code généré par le compilateur tu ne pourra pas faire ça car c'est le CPU lui-même qui fonctionne ainsi (enfin l'instruction 'ret' surtout) .

            Le cache du CPU .. et bien c'est un cache pas une mémoire et en tant que tel il est géré par le CPU, à un comportement spécifique au
            CPU et est inaccessible (directement) par le compilateur / programmeur.
            De plus en environnement multi-tache il est susceptible d'être modifié de façon aléatoire par l'exécution des autres programmes et du kernel.

            Et même si ce cache était fiable il ne serait pas suffisamment grand pour stocker toutes les données d'une fonction récursive ou alors il faudrait peu de récursion et peu de variables (chaque variable déclarée dans ta fonction récursive est déposée sur la pile avant l'adresse de retour).



            Note: un programmeur asm de bon niveau avec suffisamment de connaissances sur le CPU qu'il utilise peut optimiser l'usage du cache sur un OS mono-tache et uniquement dans ce cas.

        • [^] # Re: Je ne sais pas comment faire autrement

          Posté par  (site web personnel, Mastodon) . Évalué à 1.

          Il suffit d'utiliser la spécification de classe register pour demander au compilateur de ranger si possible la variable dans le cache processeur.

          Par exemple :

          register int x;

          Mais ça ne veut pas dire que le compilateur le fera...

  • # Récursivité terminale

    Posté par  . Évalué à 2.

    Si ton algorithme peut être formulé de façon récursive terminale, il existe une transformation « automatique » vers une forme récursive (les bons compilateurs sont capable de l'appliquer de façon limitée).

    Sinon, même sans « dérécursiver », une forme récursive terminale en C revient à avoir un pointeur vers les données modifiées, de façon à ne copier que l'adresse du pointeur à chaque appel récursif et à modifier directement ta structure (en gros, ça revient vaguement à gérer toi-même ta pile d'arguments).

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.