Construindo uma cadeia de promises recursivamente em javascript – considerações de memory

Nesta resposta , uma cadeia de promise é construída recursivamente.

Simplificado, temos:

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 } 

Presumivelmente, isso daria origem a uma pilha de chamadas e uma cadeia de promise – ou seja, “profunda” e “ampla”.

Eu anteciparia um pico de memory maior do que executar uma recursion ou construir uma cadeia de promises sozinha.

  • Isso é assim?
  • Alguém considerou os problemas de memory de construir uma cadeia dessa maneira?
  • O consumo de memory diferiria entre as promises?

    uma pilha de chamadas e uma cadeia de promises – ou seja, “profunda” e “ampla”.

    Na verdade não. Não há cadeia de promises aqui como a conhecemos de doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).… (Que é o que Promise.each ou Promise.reduce pode fazer para executar sequencialmente manipuladores se ele foi escrito dessa maneira).

    O que estamos enfrentando aqui é uma cadeia de resolução 1 – o que acontece no final, quando o caso base da recursion é encontrado, é algo como Promise.resolve(Promise.resolve(Promise.resolve(…))) . Isso é apenas “profundo”, não “amplo”, se você quiser chamá-lo assim.

    Eu anteciparia um pico de memory maior do que executar uma recursion ou construir uma cadeia de promises sozinha.

    Não é um pico na verdade. Você lentamente, com o tempo, construiria uma porção de promises que são resolvidas com o mais interno, todas representando o mesmo resultado. Quando, no final de sua tarefa, a condição é satisfeita e a promise mais interna é resolvida com um valor real, todas essas promises devem ser resolvidas com o mesmo valor. Isso resultaria em O(n) custo para subir a cadeia de soluções (se implementado ingenuamente, isso pode até ser feito recursivamente e causar um estouro de pilha). Depois disso, todas as promises, exceto as mais externas, podem se tornar lixo coletado.

    Em contraste, uma cadeia de promises que é construída por algo como

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

    mostraria um pico, alocando n objects de promise ao mesmo tempo, e então os resolveria um por um lentamente, coletando os anteriores até que apenas a promise de término estabelecida estivesse viva.

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

    Isso é assim?

    Não necessariamente. Como dito acima, todas as promises nesse volume são no final resolvidas com o mesmo valor 2 , então tudo o que precisamos é armazenar a promise mais externa e a mais íntima de uma só vez. Todas as promises intermediárias podem se tornar lixo coletadas assim que possível, e queremos executar essa recursion em espaço e tempo constantes.

    Na verdade, essa construção recursiva é totalmente necessária for loops asynchronouss com uma condição dinâmica (nenhum número fixo de etapas), você não pode realmente evitá-la. Em Haskell, onde isso é usado o tempo todo para a mônada IO , uma otimização para ela é implementada apenas por causa desse caso. É muito semelhante à recursion de chamada de cauda , que é rotineiramente eliminada pelos compiladores.

    Alguém considerou os problemas de memory de construir uma cadeia dessa maneira?

    Sim. Isto foi discutido em promises / aplus por exemplo, embora sem resultado ainda.

    Muitas bibliotecas prometem apoiar os ajudantes de iteração para evitar o pico de promises, then cadeias, como os methods de each map da Bluebird.

    Minha própria biblioteca de promises 3,4 apresenta cadeias de resolução sem introduzir memory ou sobrecarga de tempo de execução. Quando uma promise adota outra (mesmo que ainda esteja pendente), ela se torna indistinguível e as promises intermediárias não são mais referenciadas em lugar algum.

    O consumo de memory diferiria entre as promises?

    Sim. Embora esse caso possa ser otimizado, raramente é. Especificamente, a especificação ES6 exige que a Promises inspecione o valor em todas as chamadas de resolve , portanto, o recolhimento da cadeia não é possível. As promises na cadeia podem até ser resolvidas com valores diferentes (construindo um object de exemplo que abuse de getters, não na vida real). A questão foi levantada em discussão, mas continua sem solução.

    Portanto, se você usar uma implementação com vazamento, mas precisar de recursion assíncrona, será melhor alternar de volta para os retornos de chamada e usar o antipadrão de destino para propagar o resultado da promise mais interna para uma única promise de resultado.

    [1]: sem terminologia oficial
    [2]: bem, eles são resolvidos uns com os outros. Mas queremos resolvê-los com o mesmo valor, esperamos que
    [3]: playground indocumentado, passa por aplus. Leia o código por sua própria conta e risco: https://github.com/bergus/F-Promise
    [4]: também implementado para o Creed neste pedido pull

    Aviso: a otimização prematura é ruim, a maneira real de descobrir as diferenças de desempenho é fazer um benchmark do seu código , e você não deve se preocupar com isso (eu tive que usar apenas uma vez e usei promises para pelo menos 100 projetos) .

    Isso é assim?

    Sim , as promises teriam que “lembrar” o que estão seguindo, se você fizer isso por 10.000 promises, você terá uma cadeia de 10000 promises longas, se não fizer isso, você não fará (por exemplo, com recursion) – isto é verdade para qualquer controle de stream de enfileiramento.

    Se você tem que manter o controle de 10000 coisas extras (as operações), então você precisa manter a memory para isso e isso leva tempo, se esse número for um milhão, pode não ser viável. Isso varia entre bibliotecas.

    Alguém considerou os problemas de memory de construir uma cadeia dessa maneira?

    Claro, isso é um grande problema, e um caso de uso para usar algo como Promise.each em bibliotecas como bluebird sobre encadeamento.

    Eu pessoalmente tive em meu código para evitar esse estilo para um aplicativo rápido que atravessa todos os arquivos em uma VM uma vez – mas na grande maioria dos casos é um problema não.

    O consumo de memory diferiria entre as promises?

    Sim, muito. Por exemplo, o bluebird 3.0 não alocará uma fila extra se detectar que uma operação de promise já é assíncrona (por exemplo, se iniciar com um Promise.delay) e apenas executará as coisas de forma síncrona (porque as garantias assíncronas já foram preservadas).

    Isso significa que o que eu reivindiquei na minha resposta à primeira pergunta nem sempre é verdade (mas é verdade no caso de uso regular) 🙂 Promessas nativas nunca poderão fazer isso a menos que o suporte interno seja fornecido.

    Então, novamente – não é nenhuma surpresa, uma vez que as bibliotecas prometem diferem por ordem de magnitude umas das outras.

    Eu acabei de sair de um hack que pode ajudar a resolver o problema: não faça recursion no último, em vez disso, faça-o na última catch , já que o catch está fora da cadeia de resolução. Usando o seu exemplo, seria assim:

     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 } 

    Para complementar as respostas impressionantes existentes, gostaria de ilustrar a expressão, que é o resultado de tal recursion assíncrona. Por uma questão de simplicidade, uso uma function simples que calcula o poder de uma determinada base e expoente. O caso recursivo e base são equivalentes aos do exemplo do 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} 

    Com a ajuda de algumas etapas de substituição, a parte recursiva pode ser substituída. Por favor, note que esta expressão pode ser avaliada no seu navegador:

     // 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} 

    Interpretação:

    1. Com o new Promise(res => setTimeout(res, 0, 8)) o executor é chamado imediatamente e executa um cálculo sem bllocking (imitado com setTimeout ). Então uma Promise não resolvida é devolvida. Isso é equivalente a doSomethingAsync() do exemplo do OP.
    2. Um callback de resolução está associado a este Promise via .then(... Nota: O corpo deste retorno de chamada foi substituído pelo corpo do powerp .
    3. O ponto 2) é repetido e uma estrutura de manipulador aninhada é criada até que o caso base da recursion seja atingido. O caso base retorna um Promise resolvido com 1 .
    4. A estrutura de manipulador aninhada é “desenrolada” chamando o retorno de chamada associado correspondentemente.

    Por que a estrutura gerada está aninhada e não está encadeada? Porque o caso recursivo dentro dos manipuladores then impede de retornar um valor até que o caso base seja atingido.

    Como isso pode funcionar sem uma pilha? Os retornos de chamada associados formam uma “cadeia”, que faz a ponte entre as sucessivas microtasks do loop de events principal.

    Este padrão de promise irá gerar uma cadeia recursiva. Assim, cada resolve () criará um novo quadro de pilha (com seus próprios dados), utilizando alguma memory. Isso significa que um grande número de funções encadeadas usando esse padrão de promise pode gerar erros de estouro de pilha.

    Para ilustrar isso, usarei uma minúscula biblioteca promissória chamada Sequence , que eu escrevi. Ele se baseia na recursion para obter execução sequencial para funções encadeadas:

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

    Seqüência funciona muito bem para pequenas / médias cadeias de tamanho, na faixa de 0-500 funções. No entanto, em cerca de 600 cadeias, a sequência começa a degradar e a gerar erros de estouro de pilha com frequência.

    A linha inferior é: atualmente , as bibliotecas promissoras baseadas em recursion são mais adequadas para cadeias de funções menores / médias, enquanto as implementações de promise baseadas em redução são aceitáveis ​​para todos os casos, incluindo cadeias maiores.

    Isso obviamente não significa que promises baseadas em recursion sejam ruins. Nós só precisamos usá-los com suas limitações em mente. Além disso, é raro que você precise encadear tantas chamadas (> = 500) através de promises. Eu normalmente me encontro usando-os para configurações assíncronas que utilizam fortemente ajax. Mas mesmo se os casos mais complexos não vi uma situação com mais de 15 cadeias.

    Em uma nota lateral …

    Essas statistics foram recuperadas de testes realizados com outra de minhas bibliotecas – provisnr – que captura o número de chamadas de function alcançadas dentro de um determinado intervalo de tempo.