Батут Groovy () делает рекурсивное выполнение намного медленнее - почему? - PullRequest
2 голосов
/ 13 июня 2019

Я экспериментирую с рекурсией:

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 мс

UPDATE

Переписать замыкание для метода с аннотацией:

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

дает

сделано за 164 мс

и супер-колл. Тем не менее, я все еще хочу знать о trampoline():)

1 Ответ

2 голосов
/ 13 июня 2019

Как указано в документации, 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 МБ памяти.

enter image description here

ЦП мало что может сделать, и, кроме затрат времени на методы main() и run(), он тратит несколько циклов на приведение аргументов.

enter image description here

Вариант использования trampoline()

Представление батута действительно сильно меняется. Во-первых, это делает время выполнения почти в два раза медленнее по сравнению с предыдущей попыткой.

done in 856 ms / 815915283247897734345611269596115894272000000000

Во-вторых, он выделяет ~ 5,931,470 (!!!) объектов и потребляет ~ 221 МБ памяти. Основное отличие состоит в том, что в предыдущем случае во всех исполнениях использовался один из $_main_closure1, а в случае использования батута - каждый вызов метода trampoline() создает:

  • новый $_main_closure1 объект
  • , завернутый в CurriedClosure<T>
  • , который затем оборачивается TrampolineClosure<T>

Только это выделяет более 1 200 000 объектов.

enter image description here

Если речь идет о процессоре, у него также есть гораздо больше дел. Достаточно взглянуть на цифры:

  • все звонки на TrampolineClosure<T>.<init>() потребляют 199 мс
  • при использовании батута вводит вызовы PojoeMetaMethodSite$PojoCachedMethodSietNoUnwrap.invoke(), которые в целом потребляют дополнительно 201 мс
  • все звонки на CachedClass$3.initValue() потребляют всего дополнительно 98,8 мс
  • все звонки на ClosureMetaClass$NormalMethodChooser.chooseMethod() потребляют всего дополнительно 100 мс

enter image description here

И именно поэтому использование батута в вашем случае значительно замедляет выполнение кода.

Так почему же @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/

...