elementos - addeventlistener javascript

Construyendo una cadena de promesa recursivamente en javascript-consideraciones de memoria

Question

En esta respuesta , una cadena de promesa se construye recursivamente.

Simplificado ligeramente, tenemos:

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
}

Presumiblemente, esto daría lugar a una pila de llamadas y una cadena de promesa, es decir, "profunda" y "amplia".

Anticiparía un pico de memoria más grande que realizar una recursión o construir una cadena de promesa solo.

• ¿Es esto así?
• ¿Alguien ha considerado los problemas de memoria de construir una cadena de esta manera?
• ¿El consumo de memoria diferiría entre las bibliotecas prometidas?

Answer 1

una pila de llamadas y una cadena de promesa, es decir, "profunda" y "amplia".

En realidad no. No hay una cadena de promesa aquí tal como la conocemos por doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).… (que es lo que Promise.each o Promise.reduce podrían hacer para ejecutar secuencialmente los controladores si se escribiera de esta manera).

Lo que estamos enfrentando aquí es una cadena de resolución ¹ : lo que sucede al final, cuando se cumple el caso base de la recursión, es algo así como Promise.resolve(Promise.resolve(Promise.resolve(…))) . Esto es solo "profundo", no "ancho", si quieres llamarlo así.

Anticiparía un pico de memoria más grande que realizar una recursión o construir una cadena de promesa solo.

No es un pico en realidad. Lentamente, con el tiempo, construirá una gran cantidad de promesas que se resuelven con la más interna, todas representando el mismo resultado. Cuando, al final de su tarea, se cumple la condición y la promesa más interna se resuelve con un valor real, todas estas promesas deben resolverse con el mismo valor. Eso terminaría con un costo de O(n) para subir por la cadena de resolución (si se implementa ingenuamente, esto incluso podría hacerse recursivamente y causar un desbordamiento de la pila). Después de eso, todas las promesas, excepto las más externas, pueden convertirse en basura recolectada.

En contraste, una cadena de promesa construida por algo como

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

mostraría una espiga, asignando n objetos de promesa al mismo tiempo, y luego los resolvería lentamente uno por uno, recogiendo basura de los anteriores hasta que solo la promesa final establecida esté viva.

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

¿Es esto así?

No necesariamente. Como se dijo anteriormente, todas las promesas en ese volumen se resuelven finalmente con el mismo valor ² , por lo que todo lo que necesitaríamos es almacenar la promesa más externa e interna al mismo tiempo. Todas las promesas intermedias pueden ser recolectadas de basura lo antes posible, y queremos ejecutar esta recursión en un espacio y tiempo constantes.

De hecho, esta construcción recursiva es totalmente necesaria para los bucles asíncronos con una condición dinámica (sin un número fijo de pasos), realmente no se puede evitar. En Haskell, donde esto se usa todo el tiempo para la mónada IO , se implementa una optimización solo por este caso. Es muy similar a la recursividad de llamadas de cola , que los compiladores eliminan habitualmente.

¿Alguien ha considerado los problemas de memoria de construir una cadena de esta manera?

Si. Esto se discutió en promises / aplus, por ejemplo, aunque todavía no hay resultados.

Muchas bibliotecas de promesa admiten ayudantes de iteración para evitar el pico de la promesa y then cadenas, como los métodos de map y de Bluebird.

Mi propia biblioteca prometedora ^3,4 presenta cadenas de resolución sin introducir memoria o sobrecarga de tiempo de ejecución. Cuando una promesa adopta otra (incluso si aún está pendiente), se vuelven indistinguibles, y las promesas intermedias ya no se mencionan en ninguna parte.

¿El consumo de memoria diferiría entre las bibliotecas prometidas?

Si. Si bien este caso puede optimizarse, rara vez lo es. Específicamente, la especificación ES6 requiere Promesas para inspeccionar el valor en cada llamada de resolve , por lo que no es posible colapsar la cadena. Las promesas en la cadena podrían incluso resolverse con diferentes valores (construyendo un objeto de ejemplo que abusa de los captadores, no en la vida real). El problema se planteó en esdiscuss, pero sigue sin resolverse.

Entonces, si usa una implementación con fugas, pero necesita una recursión asincrónica, entonces es mejor volver a las devoluciones de llamada y usar el antipatrón diferido para propagar el resultado de la promesa más interna a una sola promesa de resultado.

_{[1]: sin terminología oficial
[2]: bueno, se resuelven entre sí. Pero queremos resolverlos con el mismo valor, esperamos que
[3]: parque infantil indocumentado, pasa aplus. Lea el código bajo su propio riesgo: https://github.com/bergus/F-Promise
[4]: también implementado para Creed en esta solicitud de extracción}

Answer 2

Acabo de encontrar un truco que puede ayudar a resolver el problema: no hagas recursiones en el último, sino hazlo en la última catch , ya que la catch está fuera de la cadena de resolución. Usando su ejemplo, sería así:

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
}

Answer 3

Este patrón de promesa generará una cadena recursiva. Por lo tanto, cada resolve () creará un nuevo marco de pila (con sus propios datos), utilizando algo de memoria. Esto significa que una gran cantidad de funciones encadenadas que utilizan este patrón prometedor pueden producir errores de desbordamiento de pila.

Para ilustrar esto, usaré una pequeña biblioteca de promesas llamada Sequence , que he escrito. Se basa en la recursividad para lograr la ejecución secuencial de funciones encadenadas:

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

La secuencia funciona muy bien para cadenas pequeñas / medianas, en el rango de 0-500 funciones. Sin embargo, en aproximadamente 600 cadenas, la secuencia comienza a degradarse y a generar errores de desbordamiento de la pila.

La conclusión es: actualmente , las bibliotecas de promesas basadas en recursión son más adecuadas para cadenas de funciones más pequeñas / medianas, mientras que las implementaciones de promesas basadas en reducciones son adecuadas para todos los casos, incluidas las cadenas más grandes.

Esto, por supuesto, no significa que las promesas basadas en la recursividad sean malas. Solo necesitamos usarlos teniendo en cuenta sus limitaciones. Además, es raro que necesite encadenar tantas llamadas (> = 500) a través de promesas. Normalmente me encuentro usándolos para configuraciones asíncronas que utilizan mucho ajax. Pero incluso si los casos más complejos no he visto una situación con más de 15 cadenas.

En otros comentarios...

Estas estadísticas se recuperaron de las pruebas realizadas con otra de mis bibliotecas, provisnr , que captura el número logrado de llamadas a funciones dentro de un intervalo de tiempo determinado.

Answer 4

Para complementar las impresionantes respuestas existentes, me gustaría ilustrar la expresión, que es el resultado de una recursión asincrónica. En aras de la simplicidad, uso una función simple que calcula el poder de una base y exponente dados. El caso recursivo y base son equivalentes a los del ejemplo del 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}

Con la ayuda de algunos pasos de sustitución, la porción recursiva se puede reemplazar. Tenga en cuenta que esta expresión se puede evaluar en su 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}

Interpretación:

1. Con la new Promise(res => setTimeout(res, 0, 8)) se invoca al ejecutor inmediatamente y ejecuta un cálculo sin bloqueo (imitado con setTimeout ). Luego se devuelve una Promise inestable. Esto es equivalente a doSomethingAsync() del ejemplo del OP.
2. Una devolución de llamada de resolución se asocia con esta Promise través de .then(... Nota: El cuerpo de esta devolución de llamada se sustituyó con el cuerpo de powerp .
3. El punto 2) se repite y se construye una estructura de controlador anidada hasta que se alcanza el caso base de la recursividad. El caso base devuelve una Promise resuelta con 1 .
4. La estructura anidada del controlador se "desenrolla" llamando a la devolución de llamada asociada correspondientemente.

¿Por qué la estructura generada está anidada y no encadenada? Debido a que el caso recursivo dentro de los controladores de then les impide devolver un valor hasta que se alcanza el caso base.

¿Cómo puede funcionar esto sin una pila? Las devoluciones de llamada asociadas forman una "cadena", que une las micrototas sucesivas del bucle de eventos principal.

Answer 5

Descargo de responsabilidad: la optimización prematura es mala, la forma real de conocer las diferencias de rendimiento es comparar su código , y no debe preocuparse por esto (solo he tenido que hacerlo una vez y he usado promesas para al menos 100 proyectos) .

¿Es esto así?

Sí , las promesas tendrían que "recordar" lo que están siguiendo, si haces esto por 10000 promesas, tendrías una cadena de promesas larga de 10000, si no lo haces, entonces no lo harás (por ejemplo, con recurrencia) - Esto es cierto para cualquier control de flujo de colas.

Si tiene que hacer un seguimiento de 10000 cosas adicionales (las operaciones), entonces necesita guardar memoria y eso lleva tiempo, si ese número es un millón, puede que no sea viable. Esto varía entre bibliotecas.

¿Alguien ha considerado los problemas de memoria de construir una cadena de esta manera?

Por supuesto, este es un gran problema, y ​​un caso de uso para usar algo como Promise.each en bibliotecas como bluebird y then encadenar.

Personalmente, tuve en mi código para evitar este estilo para una aplicación rápida que atraviesa todos los archivos en una VM una vez, pero en la gran mayoría de los casos no es un problema.

¿El consumo de memoria diferiría entre las bibliotecas prometidas?

Si mucho. Por ejemplo, bluebird 3.0 no asignará una cola adicional si detecta que una operación de promesa ya es asíncrona (por ejemplo, si comienza con un Promise.delay) y solo ejecutará cosas sincrónicamente (porque las garantías asíncronas ya están preservadas).

Esto significa que lo que reclamé en mi respuesta a la primera pregunta no siempre es cierto (pero es cierto en el caso de uso habitual) :) Las promesas nativas nunca podrán hacerlo a menos que se brinde soporte interno.

Por otra parte, no es sorprendente, ya que las bibliotecas prometedoras difieren en órdenes de magnitud entre sí.