La fonction trampoline() de Groovy rend l'exécution récursive beaucoup plus lente - pourquoi ?

Question

J'expérimente la récursion :

def fac
//fac = { int curr, res = 1G -> 1 >= curr ? res : fac( curr - 1, res * curr ) }
fac = { int curr, res = 1G -> 1 >= curr ? res : fac.trampoline( curr - 1, res * curr ) }
fac = fac.trampoline()

def rnd = new Random()

long s = System.currentTimeMillis()

100000.times{ fac rnd.nextInt( 40 ) }

println "done in ${System.currentTimeMillis() - s} ms / ${fac(40)}"

Si je l'utilise comme ça, je vais avoir ça :

fait en 691 ms

Si je décommente la ligne n°2 et commente les lignes n°3-4 pour enlever trampoline() et l'exécuter, j'obtiens des chiffres significativement plus bas :

fait en 335 ms

Ainsi, avec trampoline, la récursion fonctionne 2 fois plus lentement.

Qu'est-ce que je rate ?

P.S.

Si je lance le même exemple dans Scala 2.12 :

def fac( curr:Int, acc:BigInt = 1 ):BigInt = if( 1 >= curr ) acc else fac( curr - 1, curr * acc )
val s = System.currentTimeMillis
for( ix <- 0 until 100000 ) fac( scala.util.Random.nextInt(40).toInt )

println( s"done in ${System.currentTimeMillis - s} ms" )

il s'exécute un peu plus rapidement :

fait en 178 ms

UPDATE

Réécriture de la fermeture en une méthode avec l'annotation :

@groovy.transform.TailRecursive
def fac( int curr, res = 1G ) { 1 >= curr ? res : fac( curr - 1, res * curr ) }
// the rest

donne

fait en 164 ms

et est super-collé. Néanmoins, je veux quand même savoir trampoline() :)

Answer 1

Comme indiqué dans la documentation, Closure.trampoline() empêche le débordement de la pile d'appels.

Les algorithmes récursifs sont souvent restreints par une limite physique : la hauteur maximale de la pile. Par exemple, si vous appelez une méthode qui s'appelle elle-même récursivement trop profondément, vous recevrez éventuellement un StackOverflowException .

Une approche qui peut aider dans ces situations est d'utiliser Closure et sa capacité de trampoline.

Les fermetures sont enveloppées dans un TrampolineClosure . En appelant, un trampoline Closure appellera l'original Closure en attendant son résultat. Si le résultat de l'appel est une autre instance d'un objet TrampolineClosure créée peut-être à la suite d'un appel à la fonction trampoline() la Closure sera à nouveau invoquée. Cette invocation répétitive des instances de Closures trampolines retournées se poursuivra jusqu'à ce qu'une valeur autre qu'une instance trampolines Closure est retourné. Cette valeur deviendra le résultat final du trampoline. De cette façon, les appels sont faits en série, plutôt que de remplir la pile.

---

Fuente: http://groovy-lang.org/closures.html#_trampoline

Cependant, l'utilisation du trampoline a un coût. Jetons un coup d'œil aux échantillons de JVisualVM.

Cas d'utilisation sans trampoline

Exécution d'un exemple sans trampoline() nous obtenons un résultat en ~441 ms

done in 441 ms / 815915283247897734345611269596115894272000000000

Cette exécution alloue ~2 927 550 objets et consomme environ 100 Mo de mémoire.

L'unité centrale a peu à faire, et à part passer du temps à main() y run() il consacre quelques cycles à la coercition des arguments.

Le site trampoline() cas d'utilisation

L'introduction du trampoline change beaucoup de choses. Tout d'abord, il rend le temps d'exécution presque deux fois plus lent par rapport à la tentative précédente.

done in 856 ms / 815915283247897734345611269596115894272000000000

Deuxièmement, il attribue ~5,931,470 ( !!!) objets et consomme ~221 MB de mémoire. La principale différence est que dans le cas précédent, un seul objet de $_main_closure1 a été utilisé dans toutes les exécutions, et dans le cas de l'utilisation de trampoline - chaque appel à trampoline() crée :

• une nouvelle $_main_closure1 objet
• qui est enveloppée dans le CurriedClosure<T>
• qui est ensuite enveloppée dans le TrampolineClosure<T>

Seul celui-ci alloue plus de 1 200 000 objets.

Si l'on en vient au processeur, il a également beaucoup plus de choses à faire. Il suffit de regarder les chiffres :

• tous les appels à TrampolineClosure<T>.<init>() consommer 199 ms
• L'utilisation de trampoline introduit des appels à PojoeMetaMethodSite$PojoCachedMethodSietNoUnwrap.invoke() qui, au total, consomment des 201 ms
• tous les appels à CachedClass$3.initValue() consomment au total un supplément 98,8 ms
• tous les appels à ClosureMetaClass$NormalMethodChooser.chooseMethod() consomment au total un supplément 100 ms

Et c'est exactement pourquoi l'introduction de trampoline dans votre cas rend l'exécution du code beaucoup plus lente.

Alors pourquoi @TailRecursive fait beaucoup mieux ?

En bref - @TailRecursive remplace toutes les fermetures et les appels récursifs par le bon vieux while-loop. La fonction factorielle avec @TailRecursive ressemble à quelque chose comme ça au niveau du bytecode :

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

package factorial;

import groovy.lang.GroovyObject;
import groovy.lang.MetaClass;
import java.math.BigInteger;
import org.codehaus.groovy.runtime.ScriptBytecodeAdapter;
import org.codehaus.groovy.runtime.dgmimpl.NumberNumberMultiply;
import org.codehaus.groovy.transform.tailrec.GotoRecurHereException;

public class Groovy implements GroovyObject {
    public Groovy() {
        MetaClass var1 = this.$getStaticMetaClass();
        this.metaClass = var1;
    }

    public static BigInteger factorial(int number, BigInteger acc) {
        BigInteger _acc_ = acc;
        int _number_ = number;

        try {
            while(true) {
                try {
                    while(_number_ != 1) {
                        int __number__ = _number_;
                        int var7 = _number_ - 1;
                        _number_ = var7;
                        Number var8 = NumberNumberMultiply.multiply(__number__, _acc_);
                        _acc_ = (BigInteger)ScriptBytecodeAdapter.castToType(var8, BigInteger.class);
                    }

                    BigInteger var4 = _acc_;
                    return var4;
                } catch (GotoRecurHereException var13) {
                    ;
                }
            }
        } finally {
            ;
        }
    }

    public static BigInteger factorial(int number) {
        return factorial(number, (BigInteger)ScriptBytecodeAdapter.castToType(1, BigInteger.class));
    }
}

J'ai documenté ce cas d'utilisation sur mon blog il y a quelque temps. Vous pouvez lire l'article du blog si vous souhaitez obtenir plus d'informations :

https://e.printstacktrace.blog/tail-recursive-methods-in-groovy/