Ottimizzazione di chiamata di coda Node.js: possibile o no?

Question

Mi piace JavaScript finora e ho deciso di utilizzare Node.js come mio motore in parte a causa di this, che afferma che Node.js offre TCO. Tuttavia, quando si tenta di eseguire questo (ovviamente coda di chiamata) codice con Node.js, provoca un overflow dello stack:

function foo(x) { 
    if (x == 1) { 
     return 1; 
    } 
    else { 
     return foo(x-1); 
    } 
} 

foo(100000); 

Ora, ho fatto qualche ricerca e ho trovato this. Qui, sembra dire che dovrei scrivere in questo modo:

function* foo(x) { 
    if (x == 1) { 
     return 1; 
    } 
    else { 
     yield foo(x-1); 
    } 
} 

foo(100000); 

Tuttavia, questo mi dà errori di sintassi. Ho provato varie permutazioni di esso, ma in tutti i casi, Node.js sembra scontento di qualcosa.

In sostanza, mi piacerebbe sapere quanto segue:

1. fa o non fare Node.js TCO?
2. Come funziona questa magica cosa yield in Node.js?

Answer 1

Ci sono due domande piuttosto-distinte qui:

• fa o non fare Node.js TCO?
• Come funziona questa funzione di rendimento magico in Node.js?

fa o non fa Node.js fare TCO?

TL; DR: Non più, come del Nodo 8.x. Ha funzionato per un po ', dietro una bandiera o un'altra, ma al momento della stesura di questo documento (novembre 2017) non funziona più perché il motore JavaScript V8 sottostante che utilizza non supporta più il TCO. Vedi this answer per ulteriori informazioni.

Dettagli:

ottimizzazione Tail-call (TCO) è una richiesta part of the ES2015 ("ES6") specification. Quindi supportarlo non è, direttamente, una cosa NodeJS, è qualcosa che il motore JavaScript V8 utilizzato da NodeJS deve supportare.

A partire dal nodo 8.x, V8 non supporta TCO, nemmeno dietro a un flag. Potrebbe fare (di nuovo) ad un certo punto nel futuro; vedi this answer per ulteriori informazioni.

Nodo 7,10 fino a 6.5.0 almeno (i miei appunti dicono 6.2, ma non è d'accordo node.green) supportati TCO dietro una bandiera (--harmony in 6.6.0 e fino, --harmony_tailcalls prima) solo in modalità rigorosa.

Se si desidera controllare l'installazione, ecco le prove node.green usi (accertarsi di utilizzare il flag se si sta utilizzando una versione rilevante):

function direct() { 
    "use strict"; 
    return (function f(n){ 
     if (n <= 0) { 
     return "foo"; 
     } 
     return f(n - 1); 
    }(1e6)) === "foo"; 
} 

function mutual() { 
    "use strict"; 
    function f(n){ 
     if (n <= 0) { 
     return "foo"; 
     } 
     return g(n - 1); 
    } 
    function g(n){ 
     if (n <= 0) { 
     return "bar"; 
     } 
     return f(n - 1); 
    } 
    return f(1e6) === "foo" && f(1e6+1) === "bar"; 
} 

console.log(direct()); 
console.log(mutual()); 

 
$ # Only certain versions of Node, notably not 8.x or (currently) 9.x; see above 
$ node --harmony tco.js 
true 
true 

Come funziona questo magico lavoro yield funziona in Node.js?

Questa è un'altra cosa ES2015 ("funzioni generatore"), quindi è ancora una volta che V8 deve implementare. È completamente implementato nella versione di V8 nel Nodo 6.6.0 (ed è stato utilizzato per diverse versioni) e non è dietro alcun flag.

Le funzioni del generatore (quelle scritte con function* e yield) funzionano bloccando e restituendo un iteratore che cattura il loro stato e può essere utilizzato per continuare il loro stato in un'occasione successiva. Alex Rauschmeyer ha un articolo approfondito su di loro here.

Ecco un esempio di utilizzo del iteratore restituito dalla funzione del generatore in modo esplicito, ma di solito non lo farà e vedremo perché in un attimo:

"use strict"; 
function* counter(from, to) { 
    let n = from; 
    do { 
     yield n; 
    } 
    while (++n < to); 
} 

let it = counter(0, 5); 
for (let state = it.next(); !state.done; state = it.next()) { 
    console.log(state.value); 
} 

che ha questa uscita:

 
0 
1 
2 
3 
4 

Ecco come funziona:

• Quando chiamiamo counter (let it = counter(0, 5);), lo stato interno iniziale della chiamata a counter viene inizializzato e viene immediatamente restituito un iteratore; nessuno del codice effettivo in counter viene eseguito (ancora).
• La chiamata it.next() esegue il codice in counter tramite la prima dichiarazione yield. A quel punto, counter sospende e memorizza il suo stato interno. it.next() restituisce un oggetto stato con un flag done e uno value. Se il flag done è false, il valore value corrisponde al valore restituito dall'istruzione yield.
• Ogni chiamata a it.next() anticipa lo stato all'interno di counter al successivo yield.
• Quando una chiamata a it.next() rende counter finitura e ritorno, l'oggetto stato che ha ottenere indietro done insieme al true e value impostato al valore di ritorno di counter.

Avendo variabili per l'iteratore e l'oggetto di stato ed effettuare chiamate a it.next() e l'accesso alle proprietà done e value è tutto boilerplate che (di solito) si mette di mezzo di ciò che stiamo cercando di fare, in modo ES2015 fornisce la nuova dichiarazione for-of che ci rimbocca tutto e ci dà solo ogni valore. Ecco che lo stesso codice di cui sopra scritto con for-of:

"use strict"; 
function* counter(from, to) { 
    let n = from; 
    do { 
     yield n; 
    } 
    while (++n < to); 
} 

for (let v of counter(0, 5)) { 
    console.log(v); 
} 

v corrisponde a state.value nel nostro esempio precedente, con for-of facendo tutte le chiamate e it.next()done controlli per noi.

Answer 2

node.js supporta infine il TCO dal 2016, version 6.2.0.

Deve essere eseguito con i flag --use-strict --harmony-tailcalls affinché TCO funzioni.

Answer 3

risposta più concisa ... come della sua data di applicazione, come detto ...

funziona TCO. Non è a prova di proiettile, ma è molto dignitoso. Ecco il fattoriale (7000000,1).

>node --harmony-tailcalls -e "'use strict';function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(7000000,1))" 
Infinity 

E qui è senza TCO.

>node -e "'use strict';function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(15669,1))" 
[eval]:1 
function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(15669,1)) 
    ^

RangeError: Maximum call stack size exceeded 
at f ([eval]:1:11) 
at f ([eval]:1:32) 
at f ([eval]:1:32) 
at ... 

Tuttavia, fa tutto fino a 15668.

Per quanto riguarda la resa, vedere altre risposte. Probabilmente dovrebbe essere una domanda separata.

Answer 4

6.2.0 - con 'use strict' e '--harmony_tailcalls'

lavora con piccoli ricorsioni coda ottimizzata di 10000 (come in questione), ma fallisce la funzione stessa chiamate 99999999999999 volte.

7.2.0 con 'use strict' e '--harmony'

bandiera funziona senza problemi e rapidamente anche con 99999999999999 chiamate.