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

вопрос создан в Thu, May 2, 2019 12:00 AM

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

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

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 ответ                              1                         
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) -й уже, создавая цепочку зависимостей данных вплоть до базового случая, вы не сможете распараллелить Фибоначчи. В вашем случае вы делаете много пересчетов одних и тех же членов, так что это может быть улучшено параллелизмом, но все равно будет далеко от правильно реализованного однопоточного решения.

    
1
2019-05-02 16: 18: 59Z
  1. "Функция, объявленная как приостановленная, но с нулевыми точками приостановки." Это одно из моих самых основных сомнений: просто ли объявление функции как приостановленной что-то меняет? Я думаю, нет, правда? Что будет «точкой приостановки» в этом случае?
    2019-05-02 16: 24: 37Z
  2. Да, это так, поэтому вы получаете разные сроки. Это резко меняет код реализации функции, включая, среди прочего, специальный класс, который создается при каждом вызове. Технически точка приостановки в функции - это каждое место, где вы вызываете suspend fun. У вашего fib есть два из них. Однако сопрограмма фактически приостанавливается только при явном вызове suspendCoroutine.
    2019-05-02 16: 32: 59Z
  3. Я должен был написать «улучшить что-нибудь», а не «изменить что-либо». Мне все еще трудно создать мысленную модель того, как сопрограммы выполняют работу, приостанавливают выполнение, возобновляют его и т. Д.
    2019-05-02 16: 54: 20Z
  4. Простое объявление существующей функции приостанавливаемой гарантированно только ухудшит ситуацию. Обычно вы объявляете функцию приостановленной, чтобы иметь возможность вызывать некоторую уже определенную функцию, которая фактически использует приостановку и возобновление с хорошим эффектом, например неблокируемый ввод-вывод.
    2019-05-02 17: 13: 31Z
источник размещен Вот