Kotlin приостанавливает функцию рекурсивного вызова

Внезапно обнаружите, что рекурсивный вызов функции suspend занимает больше времени, а затем вызывает ту же функцию, но без модификатора suspend , поэтому, пожалуйста, рассмотрите фрагмент кода ниже (базовый расчет серии Фибоначчи):

 suspend fun asyncFibonacci(n: Int): Long = when { n <= -2 -> asyncFibonacci(n + 2) - asyncFibonacci(n + 1) n == -1 -> 1 n == 0 -> 0 n == 1 -> 1 n >= 2 -> asyncFibonacci(n - 1) + asyncFibonacci(n - 2) else -> throw IllegalArgumentException() } 

Если я вызываю эту функцию и измеряю ее время выполнения с помощью кода ниже:

 fun main(args: Array<String>) { val totalElapsedTime = measureTimeMillis { val nFibonacci = 40 val deferredFirstResult: Deferred<Long> = async { asyncProfile("fibonacci") { asyncFibonacci(nFibonacci) } as Long } val deferredSecondResult: Deferred<Long> = async { asyncProfile("fibonacci") { asyncFibonacci(nFibonacci) } as Long } val firstResult: Long = runBlocking { deferredFirstResult.await() } val secondResult: Long = runBlocking { deferredSecondResult.await() } val superSum = secondResult + firstResult println("${thread()} - Sum of two $nFibonacci'th fibonacci numbers: $superSum") } println("${thread()} - Total elapsed time: $totalElapsedTime millis") } 

Я наблюдаю дальнейшие результаты:

 commonPool-worker-2:fibonacci - Start calculation... commonPool-worker-1:fibonacci - Start calculation... commonPool-worker-2:fibonacci - Finish calculation... commonPool-worker-2:fibonacci - Elapsed time: 7704 millis commonPool-worker-1:fibonacci - Finish calculation... commonPool-worker-1:fibonacci - Elapsed time: 7741 millis main - Sum of two 40'th fibonacci numbers: 204668310 main - Total elapsed time: 7816 millis 

Но если я удалю модификатор suspend из функции asyncFibonacci , у меня получится такой результат:

 commonPool-worker-2:fibonacci - Start calculation... commonPool-worker-1:fibonacci - Start calculation... commonPool-worker-1:fibonacci - Finish calculation... commonPool-worker-1:fibonacci - Elapsed time: 1179 millis commonPool-worker-2:fibonacci - Finish calculation... commonPool-worker-2:fibonacci - Elapsed time: 1201 millis main - Sum of two 40'th fibonacci numbers: 204668310 main - Total elapsed time: 1250 millis 

Я знаю, что лучше переписать такую ​​функцию с помощью tailrec это увеличит время выполнения apx. почти в 100 раз, но в любом случае, что это suspend ключевое слово, это уменьшает скорость выполнения от 1 секунды до 8 секунд?

Это полная глупая идея отметить рекурсивные функции с suspend ?

    В качестве вступительного комментария установка вашего тестового кода слишком сложна. Этот гораздо более простой код обеспечивает то же самое с точки зрения suspend fun рекурсии:

     fun main(args: Array<String>) { launch(Unconfined) { val nFibonacci = 37 var sum = 0L (1..1_000).forEach { val took = measureTimeMillis { sum += suspendFibonacci(nFibonacci) } println("Sum is $sum, took $took ms") } } } suspend fun suspendFibonacci(n: Int): Long { return when { n >= 2 -> suspendFibonacci(n - 1) + suspendFibonacci(n - 2) n == 0 -> 0 n == 1 -> 1 else -> throw IllegalArgumentException() } } 

    Я попытался воспроизвести его производительность, написав простую функцию, которая приближается к тем вещам, которые должна выполнять функция suspend для достижения приостановки:

     val COROUTINE_SUSPENDED = Any() fun fakeSuspendFibonacci(n: Int, inCont: Continuation<Unit>): Any? { val cont = if (inCont is MyCont && inCont.label and Integer.MIN_VALUE != 0) { inCont.label -= Integer.MIN_VALUE inCont } else MyCont(inCont) val suspended = COROUTINE_SUSPENDED loop@ while (true) { when (cont.label) { 0 -> { when { n >= 2 -> { cont.n = n cont.label = 1 val f1 = fakeSuspendFibonacci(n - 1, cont)!! if (f1 === suspended) { return f1 } cont.data = f1 continue@loop } n == 1 || n == 0 -> return n.toLong() else -> throw IllegalArgumentException("Negative input not allowed") } } 1 -> { cont.label = 2 cont.f1 = cont.data as Long val f2 = fakeSuspendFibonacci(cont.n - 2, cont)!! if (f2 === suspended) { return f2 } cont.data = f2 continue@loop } 2 -> { val f2 = cont.data as Long return cont.f1 + f2 } else -> throw AssertionError("Invalid continuation label ${cont.label}") } } } class MyCont(val completion: Continuation<Unit>) : Continuation<Unit> { var label = 0 var data: Any? = null var n: Int = 0 var f1: Long = 0 override val context: CoroutineContext get() = TODO("not implemented") override fun resumeWithException(exception: Throwable) = TODO("not implemented") override fun resume(value: Unit) = TODO("not implemented") } 

    Вы должны вызвать это с помощью

     sum += fakeSuspendFibonacci(nFibonacci, InitialCont()) as Long 

    где InitialCont

     class InitialCont : Continuation<Unit> { override val context: CoroutineContext get() = TODO("not implemented") override fun resumeWithException(exception: Throwable) = TODO("not implemented") override fun resume(value: Unit) = TODO("not implemented") } 

    В принципе, чтобы скомпилировать suspend fun компилятор должен превратить свое тело в конечный автомат. Каждый вызов должен также создавать объект для хранения состояния машины. Когда вы возобновляете, объект состояния сообщает, к какому обработчику состояния нужно перейти. Вышеизложенное еще не все, что есть, реальный код еще более сложный.

    В режиме intepreted ( java -Xint ) я получаю почти такую ​​же производительность, что и фактическая suspend fun , и она меньше, чем в два раза быстрее, чем реальная с включенным JIT. Для сравнения, реализация «прямой» функции примерно в 10 раз быстрее. Это означает, что приведенный код объясняет значительную часть накладных расходов на возможность приостановки.

    Проблема заключается в байт-коде Java, сгенерированном из функции suspend . Хотя функция non suspend только генерирует байт-код, как мы ожидаем:

     public static final long asyncFibonacci(int n) { long var10000; if (n <= -2) { var10000 = asyncFibonacci(n + 2) - asyncFibonacci(n + 1); } else if (n == -1) { var10000 = 1L; } else if (n == 0) { var10000 = 0L; } else if (n == 1) { var10000 = 1L; } else { if (n < 2) { throw (Throwable)(new IllegalArgumentException()); } var10000 = asyncFibonacci(n - 1) + asyncFibonacci(n - 2); } return var10000; } 

    Когда вы добавляете ключевое слово suspend, декомпилированный исходный код Java составляет 165 строк – поэтому намного больше. Вы можете просмотреть байт-код и декомпилированный код Java в IntelliJ, перейдя в Инструменты -> Kotlin -> Покажите байт-код Kotlin (а затем нажмите Декомпилировать вверху страницы). Хотя непросто сказать, что именно делает компилятор Kotlin в функции, похоже, что он выполняет много проверок статуса coroutine – что имеет смысл, учитывая, что сопрограмма может быть приостановлена ​​в любое время.

    Таким образом, я бы сказал, что каждый вызов метода suspend намного более тяжелый, чем suspend вызов. Это относится не только к рекурсивным функциям, но, вероятно, имеет худший результат.

    Это полная глупая идея отметить рекурсивные функции с приостановкой?

    Если у вас нет веских оснований для этого – Да

    Intereting Posts
    Kotlin: зачем мне инициализировать var с помощью пользовательского getter? Могут ли `SendChannel.offer`,` CompletableDeferred.complete` и подобные быть вызваны внешними сопрограммами? Создайте собственный источник данных с параметрами spring Как имитировать или достигать отношения IS-A для классов данных Kotlin Kotlin Ktor не может получать данные с данными о местоположении «JSON от Klaxon's довольно печатает» " Возьмите последний элемент n в Котлине Котлинский ленивый блок не выполняется при использовании Mockito и InjectMocks Могу ли я вызвать методы внутри шаблона строки в Котлине? Весенний заказ данных по функции Java Kotlin javaClass <> отсутствует зависимость в последней версии Android Studio 3.0 Многострочный макет регулярного выражения Почему Mockito не может высмеивать общий тип параметра с типом номера в Kotlin? Борясь с попыткой получить изображение с камеры для загрузки в Firebase – java.lang.IllegalStateException: uri не должен быть нулевым Список файлов рекурсивно в Котлине