style Создание рекурсивной схемы обещаний в соображениях javascript-памяти




window title jquery (4)

Я только что получил хак, который может помочь решить проблему: не делайте рекурсии в последний раз, скорее, делайте это в последнем catch , так как catch выходит из цепочки разрешений. Используя ваш пример, это будет так:

function foo() {
    function doo() {
        // always return a promise
        if (/* more to do */) {
            return doSomethingAsync().then(function(){
                        throw "next";
                    }).catch(function(err) {
                        if (err == "next") doo();
                    })
        } else {
            return Promise.resolve();
        }
    }
    return doo(); // returns a promise
}

В этом ответе цепочка обещаний строится рекурсивно.

Упрощенный, мы имеем:

function foo() {
    function doo() {
        // always return a promise
        if (/* more to do */) {
            return doSomethingAsync().then(doo);
        } else {
            return Promise.resolve();
        }
    }
    return doo(); // returns a promise
}

Предположительно, это приведет к созданию стека вызовов и цепочки обещаний - то есть «глубоких» и «широких».

Я ожидал бы, что всплеск памяти будет больше, чем выполнение рекурсии или создание единой цепи обещаний.

  • Это так?
  • Кто-нибудь рассматривал вопросы памяти о построении цепи таким образом?
  • Будет ли потребление памяти отличаться между обещаниями libs?

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

Чтобы проиллюстрировать это, я буду использовать небольшую библиотеку обещаний, называемую Sequence , которую я написал. Он полагается на рекурсию для обеспечения последовательного выполнения для цепочки функций:

var funcA = function() { 
    setTimeout(function() {console.log("funcA")}, 2000);
};
var funcB = function() { 
    setTimeout(function() {console.log("funcB")}, 1000);
};
sequence().chain(funcA).chain(funcB).execute();

Последовательность отлично работает для сетей малого и среднего размера в диапазоне 0-500 функций. Однако около 600 цепей Последовательность начинает деградировать и часто генерирует ошибки переполнения стека.

Суть в том, что в настоящее время библиотеки обещаний на основе рекурсии более подходят для функциональных цепей меньшего / среднего размера, тогда как реализация обещаний на основе сокращений подходит для всех случаев, включая более крупные сети.

Это, конечно, не означает, что обещания на основе рекурсии плохие. Нам просто нужно использовать их с учетом их ограничений. Кроме того, очень редко вам нужно связать эти звонки (> = 500) с помощью обещаний. Обычно я использую их для асинхронных конфигураций, которые используют сильно ajax. Но даже если в самых сложных случаях я не видел ситуации с более чем 15 цепями.

На боковой ноте ...

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


В дополнение к огромным существующим ответам я хотел бы проиллюстрировать выражение, которое является результатом такой асинхронной рекурсии. Для простоты я использую простую функцию, вычисляющую мощность данной базы и экспонента. Рекурсивный и базовый регистр эквивалентны примеру OP:

const powerp = (base, exp) => exp === 0 
 ? Promise.resolve(1)
 : new Promise(res => setTimeout(res, 0, exp)).then(
   exp => power(base, exp - 1).then(x => x * base)
 );

powerp(2, 8); // Promise {...[[PromiseValue]]: 256}

С помощью некоторых этапов замещения рекурсивная часть может быть заменена. Обратите внимание, что это выражение можно оценить в вашем браузере:

// apply powerp with 2 and 8 and substitute the recursive case:

8 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 8)).then(
  res => 7 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 7)).then(
    res => 6 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 6)).then(
      res => 5 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 5)).then(
        res => 4 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 4)).then(
          res => 3 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 3)).then(
            res => 2 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 2)).then(
              res => 1 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 1)).then(
                res => Promise.resolve(1)
              ).then(x => x * 2)
            ).then(x => x * 2)
          ).then(x => x * 2)
        ).then(x => x * 2)
      ).then(x => x * 2)
    ).then(x => x * 2)
  ).then(x => x * 2)
).then(x => x * 2); // Promise {...[[PromiseValue]]: 256}

Интерпретация:

  1. С new Promise(res => setTimeout(res, 0, 8)) исполнитель вызывается немедленно и выполняет неблокирующее вычисление (имитируется с помощью setTimeout ). Затем возвращается неурегулированное Promise . Это эквивалентно doSomethingAsync() примера OP.
  2. Обратный вызов разрешения связан с этим Promise через .then(... Примечание. Тело этого обратного вызова было заменено корпусом powerp .
  3. Точка 2) повторяется, и вложенная структура обработчика создается до тех пор, пока не будет достигнут базовый регистр рекурсии. Базовый регистр возвращает Promise разрешенное с помощью 1 .
  4. Вложенная структура обработчика «разматывается», вызвав соответственно соответствующий обратный вызов.

Почему сгенерированная структура вложенная, а не цепочечная? Поскольку рекурсивный случай внутри обработчиков then предотвращает их возврат значения до тех пор, пока базовый случай не будет достигнут.

Как это может работать без стека? Связанные обратные вызовы образуют «цепочку», которая соединяет последовательные микрозадачи основного цикла событий.


стек вызовов и цепочку обещаний - то есть «глубокий» и «широкий».

Вообще-то, нет. Здесь нет никакой doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).… цепочки, поскольку мы знаем это от doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).… (это то, что Promise.each или Promise.reduce могут делать, чтобы последовательно выполнять обработчики, если они были написаны таким образом).

То, с чем мы здесь сталкиваемся, - это цепочка решений 1 - что происходит в конце, когда встречается базовый случай рекурсии, это что-то вроде Promise.resolve(Promise.resolve(Promise.resolve(…))) . Это только «глубокий», а не «широкий», если вы хотите это назвать.

Я ожидал бы, что всплеск памяти будет больше, чем выполнение рекурсии или создание единой цепи обещаний.

На самом деле это не шип. Вы медленно, со временем, создадите большую часть обещаний, которые разрешаются с самой внутренней, все они представляют один и тот же результат. Когда в конце вашей задачи условие выполняется и внутреннее обещание разрешено с фактическим значением, все эти обещания должны быть разрешены с одинаковым значением. Это приведет к стоимости O(n) для перехода по цепочке разрешений (если она реализована наивно, это может быть даже рекурсивно решено и вызвать переполнение стека). После этого все обещания, кроме самого внешнего, могут стать собранными мусором.

Напротив, цепочка обещаний, построенная чем-то вроде

[…].reduce(function(prev, val) {
    // successive execution of fn for all vals in array
    return prev.then(() => fn(val));
}, Promise.resolve())

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

memory
  ^     resolve      promise "then"    (tail)
  |      chain          chain         recursion
  |        /|           |\
  |       / |           | \
  |      /  |           |  \
  |  ___/   |___     ___|   \___     ___________
  |
  +----------------------------------------------> time

Это так?

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

Фактически, эта рекурсивная конструкция абсолютно необходима для асинхронных циклов с динамическим условием (без фиксированного количества шагов), вы не можете этого избежать. В Haskell, где это все время используется для монады IO , оптимизация для него реализована только из-за этого случая. Он очень похож на рекурсию хвостового вызова , которая обычно устраняется компиляторами.

Кто-нибудь рассматривал вопросы памяти о построении цепи таким образом?

Да. Это обсуждалось, например, по обещаниям / aplus , хотя результата пока нет.

Многие библиотеки обещаний поддерживают итерационных помощников, чтобы избежать всплесков обещаний, а then цепей, таких как методы Bluebird и map .

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

Будет ли потребление памяти отличаться между обещаниями libs?

Да. Хотя этот случай можно оптимизировать, это редко бывает. В частности, спецификация ES6 требует, чтобы обещания проверяли значение при каждом вызове resolve , поэтому свертывание цепи невозможно. Обещания в цепочке могут быть разрешены даже с разными значениями (путем создания примерного объекта, который злоупотребляет геттерами, а не в реальной жизни). Вопрос был поднят на esdiscuss, но остается нерешенным.

Поэтому, если вы используете протекающую реализацию, но вам нужна асинхронная рекурсия, тогда вам лучше переключиться на обратные вызовы и использовать отложенный антипаттерн для распространения самого внутреннего результата обещания на единый результат.

[1]: нет официальной терминологии
[2]: ну, они разрешаются друг с другом. Но мы хотим разрешить их с одинаковой ценностью, мы ожидаем, что
[3]: недокументированная детская площадка, проходит aplus. Прочтите код на свой страх и риск: https://github.com/bergus/F-Promise
[4]: также реализовано для Creed в этом запросе на растяжение







promise