Groovy 的 trampoline() 使递归执行速度慢得多 - 为什么？

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

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

在 691 毫秒内完成

如果我取消注释第 2 行和注释第 3-4 行以删除trampoline()并运行它，我得到的数字要低得多：

在 335 毫秒内完成

因此，使用蹦床，递归的运行速度要慢 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" )

它执行得更快一点：

在 178 毫秒内完成

更新

将闭包重写为带有注释的方法：

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

给

在 164 毫秒内完成

并且是超级科尔。尽管如此，我还是想知道trampoline():)

Answer 1

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

递归算法通常受到物理限制的限制：最大堆栈高度。例如，如果你调用一个递归调用自身太深的方法，你最终会收到一个StackOverflowException.

在这些情况下有帮助的方法是使用Closure它的蹦床功能。

闭包被包裹在一个TrampolineClosure. 在调用时，蹦床Closure将调用原始Closure等待其结果。如果调用的结果是 a 的另一个实例TrampolineClosure，可能是由于调用该trampoline()方法而创建的，则 Closure 将再次被调用。这种对返回的蹦床闭包实例的重复调用将继续，直到返回一个不是蹦床的值Closure。该值将成为蹦床的最终结果。这样，调用是串行进行的，而不是填充堆栈。

^{来源：http : //groovy-lang.org/closures.html#_trampoline}

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

非蹦床用例

运行一个没有trampoline()我们在 ~441 ms 内得到结果的示例

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()方法的每次调用都会创建：

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

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

如果说到 CPU，它还有很多事情要做。看看数字吧：

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

这正是为什么在您的情况下引入蹦床会使代码执行速度变慢的原因。

那么为什么@TailRecursive会好很多呢？

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

done in 441 ms / 815915283247897734345611269596115894272000000000

前段时间我在我的博客上记录了这个用例。如果您想获得更多信息，可以阅读博文：

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