Tối ưu hóa cuộc gọi đuôi Node.js: có thể hay không?

Question

Tôi thích JavaScript cho đến nay và quyết định sử dụng Node.js làm động cơ của tôi một phần vì this, tuyên bố rằng Node.js cung cấp TCO. Tuy nhiên, khi tôi cố gắng chạy này (rõ ràng là đuôi-gọi điện thoại) mã với Node.js, nó gây ra một chồng tràn:

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

foo(100000); 

Bây giờ, tôi đã làm một số đào, và tôi thấy this. Ở đây, có vẻ như tôi phải viết như sau:

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

foo(100000); 

Tuy nhiên, điều này mang lại cho tôi lỗi cú pháp. Tôi đã thử các hoán vị khác nhau của nó, nhưng trong mọi trường hợp, Node.js có vẻ không hài lòng với một cái gì đó.

Về cơ bản, tôi muốn biết những điều sau:

1. Liệu hoặc không Node.js làm TCO?
2. Điều này hoạt động như thế nào với công việc ma thuật yield trong Node.js?

Answer 1

Có hai câu hỏi khá-biệt ở đây:

• Liệu hoặc không Node.js làm TCO?
• Điều năng suất huyền diệu này hoạt động như thế nào trong Node.js?

Có hay không Node.js làm TCO?

TL; DR: Không nữa, tính đến Node 8.x. Nó đã làm trong một thời gian, sau một lá cờ hay cách khác, nhưng khi viết bài này (tháng 11 năm 2017) nó không còn nữa bởi vì động cơ V8 JavaScript cơ bản mà nó sử dụng không hỗ trợ TCO nữa. Xem this answer để biết thêm về điều đó.

chi tiết:

Tail-gọi tối ưu hóa (TCO) là một đòi hỏi part of the ES2015 ("ES6") specification. Vì vậy, hỗ trợ nó không phải là, trực tiếp, một điều NodeJS, đó là một cái gì đó động cơ V8 V8 mà NodeJS sử dụng cần phải hỗ trợ.

Kể từ nút 8.x, V8 không hỗ trợ TCO, thậm chí không phải sau cờ. Nó có thể làm (một lần nữa) tại một số điểm trong tương lai; xem this answer để biết thêm về điều đó.

Nút 7.10 xuống còn 6.5.0 ít nhất (ghi chú của tôi nói 6.2, nhưng node.green không đồng ý) đã hỗ trợ TCO phía sau cờ (--harmony trong 6.6.0 trở lên, --harmony_tailcalls trước đó) ở chế độ nghiêm ngặt.

Nếu bạn muốn kiểm tra cài đặt của bạn, sau đây là các bài kiểm tra node.green sử dụng (hãy chắc chắn để sử dụng cờ nếu bạn đang sử dụng một phiên bản có liên quan):

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 

như thế nào Điều này làm việc yield ma thuật trong Node.js?

Đây là một điều ES2015 khác ("chức năng máy phát"), vì vậy một lần nữa đó là thứ mà V8 phải triển khai. Nó hoàn toàn được thực hiện trong phiên bản V8 trong Node 6.6.0 (và đã được cho một số phiên bản) và không phải là đằng sau bất kỳ cờ.

Chức năng của máy phát điện (được viết bằng function* và sử dụng yield) hoạt động bằng cách có thể dừng và trả lại một trình lặp ghi lại trạng thái của chúng và có thể được sử dụng để tiếp tục trạng thái của chúng trong một dịp tiếp theo. Alex Rauschmeyer có một bài viết chuyên sâu về chúng here.

Dưới đây là một ví dụ của việc sử dụng các iterator được trả về bởi các chức năng máy phát điện một cách rõ ràng, nhưng bạn thường sẽ không làm điều đó và chúng ta sẽ thấy lý do tại sao trong một thời điểm:

"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); 
} 

Đó có sản lượng này:

 
0 
1 
2 
3 
4 

Sau đây là cách hoạt động:

• Khi chúng ta gọi là counter (let it = counter(0, 5);), trạng thái nội bộ ban đầu của lệnh gọi tới counter được khởi tạo và chúng tôi ngay lập tức lấy lại trình lặp; không có mã thực tế nào trong số counter chạy (chưa).
• Gọi it.next() chạy mã trong counter thông qua câu lệnh yield đầu tiên. Tại thời điểm đó, counter tạm dừng và lưu trữ trạng thái nội bộ của nó. it.next() trả về đối tượng trạng thái có cờ done và value. Nếu cờ done là false, thì value là giá trị được tạo bởi tuyên bố yield.
• Mỗi cuộc gọi đến it.next() tiến hành trạng thái bên trong counter sang yield tiếp theo.
• Khi có cuộc gọi đến it.next() làm counter kết thúc và trở lại, đối tượng trạng thái chúng ta nhận lại có done thiết lập để true và value thiết lập để giá trị trả về của counter.

Có biến cho iterator và đối tượng trạng thái và thực hiện cuộc gọi đến it.next() và truy cập vào done và value tính là tất cả soạn sẵn đó (thường) được theo cách của những gì chúng ta đang cố gắng làm, vì vậy ES2015 cung cấp tuyên bố mới for-of cho phép tất cả chúng tôi mang lại cho chúng tôi và chỉ cung cấp cho chúng tôi từng giá trị. Dưới đây là mã cùng viết ở trên với 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 tương ứng với state.value trong ví dụ trước đó của chúng tôi, với for-of làm tất cả các cuộc gọi và it.next()done kiểm tra đối với chúng tôi.

Answer 2

node.js cuối cùng cũng hỗ trợ TCO kể từ 2016.05.17, version 6.2.0.

Cần phải thực thi với các cờ --use-strict --harmony-tailcalls để TCO hoạt động.

Answer 3

Câu trả lời ngắn gọn hơn ... kể từ ngày thực hiện, như đã đề cập ...

TCO hoạt động. Nó không phải là chống đạn, nhưng nó rất phong nha. Đây là Factorial (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 

Và ở đây không có 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 ... 

Mặc dù vậy, mọi thứ vẫn hoạt động với 15668.

Về sản lượng, hãy xem các câu trả lời khác. Có lẽ nên là một câu hỏi riêng biệt.

Answer 4

6.2.0 - với 'sử dụng nghiêm ngặt' và '--harmony_tailcalls'

công trình chỉ với recursions đuôi được tối ưu hóa nhỏ của 10000 (như trong câu hỏi), nhưng thất bại chức năng tự gọi mình 99999999999999 lần.

7.2.0 với 'sử dụng nghiêm ngặt' và '--harmony'

cờ làm việc liên tục và nhanh chóng ngay cả với 99999999999999 cuộc gọi.