recursion - Groovy 的 Tampoline() 使递归执行速度变慢 - 为什么？

Question

我正在尝试递归:

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

如果我像这样使用它，我会得到这个:

done in 691 ms

如果我取消注释第 #2 行和注释行 #3-4 以删除 trampoline() 并运行它，我得到的数字会显着降低:

done in 335 ms

因此，使用蹦床，递归速度慢了 2 倍。

我错过了什么？

附注

如果我在 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" )

它执行得更快一点:

done in 178 ms

更新

使用注释将闭包重写为方法:

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

给出

done in 164 ms

而且 super 酷。尽管如此，我仍然想了解 trampoline() :)

Answer 1

如文档中所述，Closure.trampoline() 可防止调用堆栈溢出。

Recursive algorithms are often restricted by a physical limit: the maximum stack height. For example, if you call a method that recursively calls itself too deep, you will eventually receive a StackOverflowException.

An approach that helps in those situations is by using Closure and its trampoline capability.

Closures are wrapped in a TrampolineClosure. Upon calling, a trampolined Closure will call the original Closure waiting for its result. If the outcome of the call is another instance of a TrampolineClosure, created perhaps as a result to a call to the trampoline() method, the Closure will again be invoked. This repetitive invocation of returned trampolined Closures instances will continue until a value other than a trampolined Closure is returned. That value will become the final result of the trampoline. That way, calls are made serially, rather than filling the stack.

---

^{Source: http://groovy-lang.org/closures.html#_trampoline}

但是，使用蹦床是有代价的。让我们看一下 JVisualVM 示例。

非蹦床用例

在没有 trampoline() 的情况下运行示例，我们在大约 441 毫秒内得到结果

done in 441 ms / 815915283247897734345611269596115894272000000000

此执行分配约 2,927,550 个对象并消耗约 100 MB 内存。

CPU 有一些事情要做，除了在 main() 和 run() 方法上花费时间之外，它还花费一些周期来强制参数。

trampoline() 用例

蹦床的引入确实改变了很多。首先，与之前的尝试相比，它使执行时间几乎慢了两倍。

done in 856 ms / 815915283247897734345611269596115894272000000000

其次，它分配~5,931,470(!!!)个对象并消耗~221 MB 内存。主要区别在于，在前一种情况下，所有执行中都使用了单个 $_main_closure1，而在使用 Trampoline 的情况下 - 每次调用 trampoline() 方法都会创建:

• 一个新的 $_main_closure1 对象
• 它被 CurriedClosure<T> 包裹
• 然后用 TrampolineClosure<T> 包装

仅此分配就超过 1,200,000 个对象。

如果涉及到CPU，它还有更多的事情要做。只要看一下数字即可:

• 对 TrampolineClosure<T>.<init>() 的所有调用都会消耗199 毫秒
• 使用 Trampoline 会引入对 PojoeMetaMethodSite$PojoCachedMethodSietNoUnwrap.invoke() 的调用，总共会额外消耗 201 毫秒
• 对 CachedClass$3.initValue() 的所有调用总计额外消耗 98.8 毫秒
• 对 ClosureMetaClass$NormalMethodChooser.chooseMethod() 的所有调用总计额外消耗 100 毫秒

这正是为什么在您的案例中引入蹦床会使代码执行速度慢得多的原因。

那么为什么 @TailRecursive 做得更好呢？

简而言之 - @TailRecursive 注释用旧的 while 循环替换了所有闭包和递归调用。 @TailRecursive 的阶乘函数在字节码级别看起来像这样:

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

我不久前在我的博客上记录了这个用例。如果您想了解更多信息，可以阅读博客文章:

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