Как указано в документации, Closure.trampoline() предотвращает переполнение стека вызовов.
Рекурсивные алгоритмы часто ограничены физическим ограничением: максимальной высотой стека. Например, если вы вызываете метод, который рекурсивно вызывает себя слишком глубоко, вы в конечном итоге получите StackOverflowException.
Подход, который помогает в таких ситуациях, заключается в использовании Closure и его возможности для батута.
Затворы обернуты в TrampolineClosure. После вызова батут Closure позвонит оригиналу Closure в ожидании его результата. Если результатом вызова является другой экземпляр TrampolineClosure, созданный, возможно, в результате вызова метода trampoline(), снова будет вызвано Закрытие. Этот повторяющийся вызов возвращаемых экземпляров Closures с батутом будет продолжаться до тех пор, пока не будет возвращено значение, отличное от батутного Closure. Это значение станет конечным результатом батута. Таким образом, вызовы выполняются последовательно, а не заполняют стек.
Источник: http://groovy -lang.org / closures.html # _trampoline
Однако использование батута обходится дорого. Давайте посмотрим на образцы JVisualVM.
Вариант использования без батута
Запустив пример без trampoline(), мы получим результат через ~ 441 мс
done in 441 ms / 815915283247897734345611269596115894272000000000
Это выполнение выделяет ~ 2927 550 объектов и потребляет около 100 МБ памяти.
ЦП мало что может сделать, и, кроме затрат времени на методы main() и run(), он тратит несколько циклов на приведение аргументов.
Вариант использования trampoline()
Представление батута действительно сильно меняется. Во-первых, это делает время выполнения почти в два раза медленнее по сравнению с предыдущей попыткой.
done in 856 ms / 815915283247897734345611269596115894272000000000
Во-вторых, он выделяет ~ 5,931,470 (!!!) объектов и потребляет ~ 221 МБ памяти. Основное отличие состоит в том, что в предыдущем случае во всех исполнениях использовался один из $_main_closure1, а в случае использования батута - каждый вызов метода trampoline() создает:
- новый
$_main_closure1 объект
- , завернутый в
CurriedClosure<T>
- , который затем оборачивается
TrampolineClosure<T>
Только это выделяет более 1 200 000 объектов.
Если речь идет о процессоре, у него также есть гораздо больше дел. Достаточно взглянуть на цифры:
- все звонки на
TrampolineClosure<T>.<init>() потребляют 199 мс
- при использовании батута вводит вызовы
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/