Kotlin挂起函数递归调用

突然发现，递归调用挂起函数需要更多的时间，然后调用相同的函数，但没有suspend修饰符，所以请考虑下面的代码片段（基本的斐波那契数列计算）：

 suspend fun asyncFibonacci(n: Int): Long = when { n  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) { val totalElapsedTime = measureTimeMillis { val nFibonacci = 40 val deferredFirstResult: Deferred = async { asyncProfile("fibonacci") { asyncFibonacci(nFibonacci) } as Long } val deferredSecondResult: Deferred = 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 

但是，如果我从asyncFibonacci函数中删除suspend修饰符，我会得到这样的结果：

 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标记递归函数是完全愚蠢的想法吗？

Answer 1

作为介绍性评论，您的测试代码设置太复杂。 这个简单得多的代码在强调suspend fun递归方面达到了同样的效果：

 fun main(args: Array) { 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函数为了实现可suspend性而必须做的事情：

 val COROUTINE_SUSPENDED = Any() fun fakeSuspendFibonacci(n: Int, inCont: Continuation): 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) : Continuation { 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 { 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 ，编译器必须把它的主体转换成一个状态机。 每个调用还必须创建一个对象来保存机器的状态。 当你恢复时，状态对象告诉哪个状态处理器去。 上面还不是全部，真正的代码更加复杂。

在解释模式（ java -Xint ）中，我获得的性能与实际的suspend fun几乎相同，比启用JIT的实际快了不到两倍。 相比之下，“直接”function的执行速度大约快10倍。 这意味着所显示的代码解释了可挂起性的一大部分开销。

Answer 2

问题在于由suspendfunction产生的Java字节码。 非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行 - 因此要大得多。 你可以在工具 - > Kotlin - > 显示Kotlin字节码 （然后点击页面顶部的反编译） 查看 IntelliJ中的字节码和反编译的Java代码。 尽管不太清楚Kotlin编译器在函数中做了什么，但看起来它正在做很多协程状态检查 - 考虑到协程在任何时候都可以被暂停，这种情况是有道理的。

所以作为一个结论，我会说，每个suspend方法调用比非suspend调用要重要得多。 这不仅适用于递归函数，而且可能是最糟糕的结果。

用暂停标记递归函数是完全愚蠢的想法吗？

除非你有足够的理由这样做 - 是的