android - 具有挂起功能的执行时间存在巨大差异

Question

我仍在努力思考挂起函数以及 IO 绑定(bind)挂起函数和 CPU 绑定(bind)挂起函数之间的区别(如果有的话)，以及其他事情。

我在主线程中启动协程并以不同的方式运行 cpu 密集型函数以查看会发生什么。

class TestActivity : AppCompatActivity(), CoroutineScope {
    private val job = Job()
    override val coroutineContext: CoroutineContext
        get() = job + Dispatchers.Main

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        launch {
            val start = System.currentTimeMillis()
            Log.d("test", "start: $start")

            fib(24)

            val finish = System.currentTimeMillis()
            Log.d("test", "finish: $finish")
            Log.d("test", "duration: ${finish - start}")
        }
    }

我已经尝试了 fib 函数的这三种变体:

private fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

常规方式:xml 不会立即膨胀，函数需要 0.1 秒才能运行。

private suspend fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

常规方式+suspend关键字:xml不会立即膨胀，函数运行需要1.3秒。

private suspend fun fib(x: Int): Int =
    withContext(Dispatchers.Default) { if (x <= 1) x else fib(x - 1) + fib(x - 2) }

常规方式 + suspend 关键字 + 用 withContext(Dispatchers.Default) 包裹它:xml 立即膨胀，函数需要 25 秒才能运行。

谁能解释一下为什么这三个功能的持续时间有如此大的差异？

Answer 1

private fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

这是您的基本情况，斐波那契的一种极其低效的递归实现。它完全独立于 fib(x - 2) 计算 fib(x - 1)，这导致函数调用呈指数级增长。为了计算 fib(24)，它进行了大约(黄金比例)²⁴ = 103,682 次调用。

private suspend fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

从语义上讲，这与上面的完全相同。声明为可挂起但挂起点为零的函数。由于可挂起函数固有的 CPS 转换开销，它速度较慢。

private suspend fun fib(x: Int): Int =
    withContext(Dispatchers.Default) { if (x <= 1) x else fib(x - 1) + fib(x - 2) }

在这里您实际上实现了一些并行性，但并行加速与分派(dispatch)非常小的工作 fragment 的开销相比相形见绌。此外，由于要计算斐波那契数列的第 n 个成员，您需要已经计算出第 (n - 1) 个和 (n - 2) 个，从而创建一直到基本情况的数据依赖链，你不能真的并行斐波那契。在您的情况下，您对相同的成员进行了大量重新计算，因此可以通过并行性加以改进，但仍远未达到正确实现的单线程解决方案。