Огромная разница в продолжительности исполнения с функцией приостановки - PullRequest
Новая
       8

Огромная разница в продолжительности исполнения с функцией приостановки

1 голос
/ 02 мая 2019

Я все еще пытаюсь обернуть голову вокруг функций приостановки и разницы (если есть) между функцией приостановки ввода-вывода и приостановки ЦП и другими вещами.

Я запускаю сопрограмму в главном потоке и запускаю функцию с интенсивным использованием процессора различными способами, чтобы увидеть, что происходит. 

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 IS раздувается немедленно, и для запуска функции требуется 25 СЕКУНД.

Может ли кто-нибудь пролить свет на то, почему существует такая разница в продолжительности между этими тремя функциями?

1 Ответ

1 голос
/ 02 мая 2019 
private fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

Это ваш базовый случай, крайне неэффективная рекурсивная реализация Фибоначчи. Он вычисляет fib(x - 1) полностью независимо от fib(x - 2), что приводит к экспоненциальному взрыву вызовов функций. Для вычисления fib(24) он составляет около (золотое сечение) 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) }

Здесь вы фактически достигаете некоторого параллелизма, но параллельное ускорение затмевается накладными расходами на отправку очень маленьких кусочков работы. Кроме того, поскольку для вычисления n-го члена последовательности Фибоначчи необходимо, чтобы (n - 1) -й и (n - 2) -й уже были вычислены, создавая цепочку зависимостей данных вплоть до базового случая, вы не можете на самом деле распараллелить Фибоначчи. В вашем случае вы выполняете много пересчетов одних и тех же членов, так что это может быть улучшено параллелизмом, но все равно будет далеко от правильно реализованного однопоточного решения.

...