Frage Erstellen einer Versprechenskette rekursiv in JavaScript - Speicherüberlegungen


Im diese Antwort, eine Versprechenskette wird rekursiv aufgebaut.

Vereinfacht haben wir:

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
}

Vermutlich würde dies zu einem Call-Stack führen und eine Versprechenskette - dh "tief" und "weit".

Ich würde einen größeren Speicherverlust erwarten, als entweder eine Rekursion durchzuführen oder eine Versprechenskette alleine aufzubauen.

  • Ist das so?
  • Hat jemand die Speicherprobleme des Aufbaus einer Kette auf diese Weise betrachtet?
  • Wäre der Speicherverbrauch zwischen Prometh-Bibliotheken unterschiedlich?

46
2018-04-28 17:21


Ursprung


Antworten:


ein Callstack und eine Versprechenskette - also "tief" und "weit".

Nicht wirklich. Es gibt keine Verheißungskette hier, wie wir sie kennen doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).… (welches ist was Promise.each oder Promise.reduce könnte tun, um Handler sequentiell auszuführen, wenn es auf diese Weise geschrieben wurde).

Was wir hier sehen, ist ein Kette auflösen1 - was am Ende passiert, wenn der Grundfall der Rekursion erfüllt ist, ist etwas wie Promise.resolve(Promise.resolve(Promise.resolve(…))). Das ist nur "tief", nicht "breit", wenn man es so nennen will.

Ich würde einen größeren Speicherverlust erwarten, als entweder eine Rekursion durchzuführen oder eine Versprechenskette alleine aufzubauen.

Eigentlich kein Spike. Sie würden langsam, im Laufe der Zeit, einen Großteil der Versprechen aufbauen, die mit dem innersten gelöst werden und alle das gleiche Ergebnis darstellen. Wenn am Ende Ihrer Aufgabe die Bedingung erfüllt ist und das innerste Versprechen mit einem tatsächlichen Wert gelöst wird, sollten alle diese Versprechen mit demselben Wert aufgelöst werden. Das würde enden O(n) Kosten für die Aufwärtsbewegung der Auflösungskette (wenn diese naiv implementiert wird, könnte dies sogar rekursiv erfolgen und einen Stapelüberlauf verursachen). Danach können alle Versprechungen außer dem äußersten zu Müll gesammelt werden.

Im Gegensatz dazu ist eine Versprechenskette, die von etwas wie gebaut wird

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

würde eine Spitze zeigen, Zuteilung n Verspreche gleichzeitig Objekte und löse sie dann langsam nacheinander auf, indem du die vorherigen sammelst, bis nur noch das besagte Endversprechen lebendig ist.

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

Ist das so?

Nicht unbedingt. Wie oben gesagt, sind alle Versprechen in dieser Masse am Ende mit demselben Wert gelöst2Alles, was wir brauchen würden, ist, das äußerste und innerste Versprechen gleichzeitig zu speichern. Alle Zwischenversprechungen können so schnell wie möglich auf Müllbasis gesammelt werden, und wir wollen diese Rekursion in konstantem Raum und konstanter Zeit ablaufen lassen.

Tatsächlich ist dieses rekursive Konstrukt völlig notwendig für asynchrone Schleifen mit einer dynamischen Bedingung (keine feste Anzahl von Schritten), können Sie es nicht wirklich vermeiden. In Haskell, wo dies die ganze Zeit für die IO Monade, eine Optimierung für sie ist nur in diesem Fall implementiert. Es ist sehr ähnlich zu Tail Call Rekursion, die routinemäßig von Compilern eliminiert wird.

Hat jemand die Speicherprobleme des Aufbaus einer Kette auf diese Weise betrachtet?

Ja. Das war diskutiert bei Versprechungen / aplus zum Beispiel, obwohl noch kein Ergebnis.

Viele Promise-Bibliotheken unterstützen Iterations-Helfer, um die Versprechen zu vermeiden then Ketten, wie Bluebirds each und mapMethoden.

Meine eigene Versprechens-Bibliothek3,4 bietet Ketten auflösen, ohne Speicher- oder Laufzeitaufwand einzuführen. Wenn ein Versprechen ein anderes annimmt (selbst wenn es noch aussteht), werden sie ununterscheidbar und Zwischenversprechen werden nirgendwo mehr erwähnt.

Wäre der Speicherverbrauch zwischen Prometh-Bibliotheken unterschiedlich?

Ja. Während dieser Fall optimiert werden kann, ist es selten. Insbesondere erfordert die ES6-Spezifikation Promises, den Wert bei jedem zu überprüfen resolve Rufen Sie an, so dass die Kette nicht kollabieren kann. Die Versprechen in der Kette könnten sogar mit unterschiedlichen Werten aufgelöst werden (indem ein Beispielobjekt konstruiert wird, das Getter missbraucht, nicht im wirklichen Leben). Das Thema wurde auf esdiscuss erhoben aber bleibt ungelöst.

Wenn Sie also eine undichte Implementierung verwenden, aber eine asynchrone Rekursion benötigen, wechseln Sie besser zurück zu Callbacks und verwenden Sie die latentes Antipattern das innerste Versprechensergebnis zu einem einzigen Ergebnisversprechen zu propagieren.

[1]: keine offizielle Terminologie
[2]: Nun, sie sind miteinander gelöst. Aber wir wollen um sie mit dem gleichen Wert zu lösen, wir erwarten von Das
[3]: undokumentierter Spielplatz, Pässe aplus. Lesen Sie den Code auf eigene Gefahr: https://github.com/bergus/F-Promise
[4]: auch für Creed in implementiert diese Pull-Anfrage


37
2018-04-28 23:23



Haftungsausschluss: vorzeitige Optimierung ist schlecht, der wahre Weg, über Leistungsunterschiede zu erfahren, ist benchmarken Sie Ihren Codeund du solltest dir darüber keine Sorgen machen (ich musste es nur einmal tun und ich habe Versprechen für mindestens 100 Projekte benutzt).

Ist das so?

Ja, die Versprechen müssten sich "erinnern" an was sie folgen, wenn du dies für 10000 Versprechen machst, hättest du eine 10000 lange Versprechens-Kette, wenn du es nicht tust, dann wirst du nicht (zum Beispiel mit Rekursion) - Dies gilt für jede Warteschlangenflusssteuerung.

Wenn Sie 10000 zusätzliche Dinge (die Operationen) verfolgen müssen, dann müssen Sie den Speicher für sie behalten und das braucht Zeit, wenn diese Zahl eine Million ist, ist es möglicherweise nicht lebensfähig. Dies variiert zwischen Bibliotheken.

Hat jemand die Speicherprobleme des Aufbaus einer Kette auf diese Weise betrachtet?

Natürlich ist dies ein großes Problem und ein Anwendungsfall für die Verwendung von etwas wie Promise.each in Bibliotheken wie Bluebird over thenfähige Verkettung.

Ich hatte persönlich in meinem Code, diesen Stil für eine schnelle App zu vermeiden, die alle Dateien in einer VM einmal durchläuft - aber in den allermeisten Fällen ist es kein Problem.

Wäre der Speicherverbrauch zwischen Prometh-Bibliotheken unterschiedlich?

Ja, sehr. Beispielsweise wird bluebird 3.0 keine zusätzliche Warteschlange zuweisen, wenn es feststellt, dass eine Zusageoperation bereits asynchron ist (z. B. wenn es mit einem Promise.delay beginnt) und nur synchron ausgeführt wird (weil die Async-Garantien bereits erhalten sind).

Das bedeutet, dass das, was ich in meiner Antwort auf die erste Frage behauptet habe, nicht immer wahr ist (aber im regulären Anwendungsfall wahr ist) :) Native Versprechungen werden niemals dazu in der Lage sein, es sei denn, interne Unterstützung wird bereitgestellt.

Andererseits ist es nicht verwunderlich, da sich die Versprechungsbibliotheken um Größenordnungen voneinander unterscheiden.


15
2018-04-28 17:27



Ich habe gerade einen Hack herausgebracht, der bei der Lösung des Problems helfen könnte: Wiederhole keine Rekursion thenmach es lieber im letzten catch, schon seit catch ist außerhalb der Auflösungskette. Mit Ihrem Beispiel wäre es so:

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
}

3
2018-04-14 06:34



Um die großartigen existierenden Antworten zu ergänzen, möchte ich den Ausdruck illustrieren, der das Ergebnis einer solchen asynchronen Rekursion ist. Der Einfachheit halber verwende ich eine einfache Funktion, die die Potenz einer gegebenen Basis und eines gegebenen Exponenten berechnet. Der rekursive und der Basisfall entsprechen denen des Beispiels des 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}

Mit Hilfe einiger Substitutionsschritte kann der rekursive Teil ersetzt werden. Bitte beachten Sie, dass dieser Ausdruck in Ihrem Browser ausgewertet werden kann:

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

Deutung:

  1. Mit new Promise(res => setTimeout(res, 0, 8)) Der Executor wird sofort aufgerufen und führt eine nicht bclockende Berechnung aus (imitiert mit setTimeout). Dann ein Unruhestifter Promise ist zurück gekommen. Dies ist äquivalent mit doSomethingAsync() des Beispiels des OP.
  2. Ein Auflösungsrückruf ist damit verbunden Promise über .then(.... Hinweis: Der Text dieses Rückrufs wurde durch den Text ersetzt powerp.
  3. Punkt 2) wird wiederholt und verschachtelt then Die Handlerstruktur wird aufgebaut, bis der Basisfall der Rekursion erreicht ist. Der Basisfall gibt a zurück Promise aufgelöst mit 1.
  4. Das verschachtelte then Handler-Struktur wird "abgewickelt", indem der zugehörige Callback entsprechend aufgerufen wird.

Warum ist die generierte Struktur verschachtelt und nicht verkettet? Weil der rekursive Fall innerhalb der then Handler verhindern, dass sie einen Wert zurückgeben, bis der Basisfall erreicht ist.

Wie kann das ohne einen Stapel funktionieren? Die zugehörigen Rückrufe bilden eine "Kette", die die aufeinanderfolgenden Mikrotasks der Hauptereignisschleife überbrückt.


1
2017-07-12 14:34



Dieses Zusicherungsmuster erzeugt eine rekursive Kette. So erstellt jeder resolve () einen neuen Stack-Frame (mit seinen eigenen Daten), der etwas Speicher verwendet. Dies bedeutet, dass eine große Anzahl von verketteten Funktionen, die dieses Zusicherungsmuster verwenden, Stapelüberlauffehler erzeugen kann.

Um das zu veranschaulichen, benutze ich ein winziges Versprechens-Bibliothek namens Sequencewas ich geschrieben habe. Es beruht auf Rekursion, um eine sequenzielle Ausführung für verkettete Funktionen zu erreichen:

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

Sequence funktioniert hervorragend für kleine bis mittelgroße Ketten im Bereich von 0-500 Funktionen. Bei ungefähr 600 Ketten beginnt die Sequenz jedoch, sich zu verschlechtern und erzeugt häufig Stapelüberlauffehler.

Das Endergebnis ist: zur ZeitRekursionsbasierte Versprechungsbibliotheken sind eher für kleinere / mittlere Funktionsketten geeignet, während reduktionsbasierte Versprechungsimplementierungen für alle Fälle, einschließlich größerer Ketten, in Ordnung sind.

Dies bedeutet natürlich nicht, dass Rekursionsbasierte Versprechen schlecht sind. Wir müssen sie nur im Hinblick auf ihre Einschränkungen verwenden. Außerdem ist es selten, dass Sie diese vielen Aufrufe (> = 500) über Versprechungen verketten müssen. Ich benutze sie normalerweise für asynchrone Konfigurationen, die stark Ajax verwenden. Aber selbst in den komplexesten Fällen habe ich keine Situation mit mehr als 15 Ketten gesehen.

Als Randnotiz...

Diese Statistiken wurden aus Tests abgerufen, die mit einer anderen meiner Bibliotheken durchgeführt wurden - provisnr - die die erreichte Anzahl von Funktionsaufrufen innerhalb eines bestimmten Zeitintervalls erfasst.


0
2017-07-23 17:17