Erlang: stackoverflow với chức năng đệ quy mà không phải là đuôi gọi tối ưu hóa?

Question

Có thể nhận một stackoverflow với một hàm không phải là đuôi gọi tối ưu hóa trong Erlang? Ví dụ, giả sử tôi có một chức năng như thế này

sum_list([],Acc) -> 
    Acc; 
sum_list([Head|Tail],Acc) -> 
    Head + sum_list(Tail, Acc). 

Có vẻ như nếu một danh sách đủ lớn đã được thông qua trong đó cuối cùng sẽ chạy ra khỏi ngăn xếp không gian và sụp đổ. Tôi đã thử nghiệm thử nghiệm này như vậy:

> L = lists:seq(1, 10000000). 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29|...] 
> sum_test:sum_list(L, 0). 
50000005000000 

Nhưng nó không bao giờ gặp sự cố! Tôi đã thử nó với một danh sách 100.000.000 số nguyên và phải mất một lúc để hoàn thành nhưng nó vẫn chưa bao giờ bị rơi! Câu hỏi:

1. Tôi có kiểm tra chính xác không?
2. Nếu có, tại sao tôi không thể tạo luồng ngăn xếp?
3. Erlang có đang làm điều gì đó ngăn chặn tình trạng tràn ngăn xếp xảy ra không?

Answer 1

Bạn đang thử nghiệm chính xác: chức năng của bạn thực sự không phải là đệ quy đuôi. Để tìm hiểu, bạn có thể biên dịch mã của mình bằng cách sử dụng erlc -S <erlang source file>.

{function, sum_list, 2, 2}. 
    {label,1}. 
    {func_info,{atom,so},{atom,sum_list},2}. 
    {label,2}. 
    {test,is_nonempty_list,{f,3},[{x,0}]}. 
    {allocate,1,2}. 
    {get_list,{x,0},{y,0},{x,0}}. 
    {call,2,{f,2}}. 
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}. 
    {deallocate,1}. 
    return. 
    {label,3}. 
    {test,is_nil,{f,1},[{x,0}]}. 
    {move,{x,1},{x,0}}. 
    return. 

Như một sự so sánh các phiên bản đuôi-đệ quy sau của hàm:

tail_sum_list([],Acc) -> 
    Acc; 
tail_sum_list([Head|Tail],Acc) -> 
    tail_sum_list(Tail, Head + Acc). 

biên dịch như:

{function, tail_sum_list, 2, 5}. 
    {label,4}. 
    {func_info,{atom,so},{atom,tail_sum_list},2}. 
    {label,5}. 
    {test,is_nonempty_list,{f,6},[{x,0}]}. 
    {get_list,{x,0},{x,2},{x,3}}. 
    {gc_bif,'+',{f,0},4,[{x,2},{x,1}],{x,1}}. 
    {move,{x,3},{x,0}}. 
    {call_only,2,{f,5}}. 
    {label,6}. 
    {test,is_nil,{f,4},[{x,0}]}. 
    {move,{x,1},{x,0}}. 
    return. 

Thông báo việc thiếu allocate và call_only opcode trong mòn đuôi phiên bản đệ quy, trái ngược với allocate/call/deallocate/return chuỗi trong hàm không đệ quy.

Bạn không bị tràn ngăn xếp vì ngăn xếp Erlang "rất lớn. Thật vậy, tràn ngăn xếp thường có nghĩa là ngăn xếp bộ xử lý tràn, vì con trỏ ngăn xếp của bộ xử lý đã đi quá xa. Quy trình theo truyền thống có kích thước ngăn xếp hạn chế có thể được điều chỉnh bằng cách tương tác với hệ điều hành. Xem ví dụ của POSIX setrlimit.

Tuy nhiên, Erlang thực hiện chồng là không bộ vi xử lý ngăn xếp, vì mã được giải thích. Mỗi quá trình có ngăn xếp riêng của nó có thể phát triển khi cần thiết bằng cách gọi các hàm phân bổ bộ nhớ hệ điều hành (thường là malloc trên Unix).

Do đó, chức năng của bạn sẽ không bị lỗi miễn là malloc cuộc gọi thành công.

Để lưu nội dung, danh sách thực tế L đang sử dụng cùng một lượng bộ nhớ như ngăn xếp để xử lý. Thật vậy, mỗi phần tử trong danh sách có hai từ (chính giá trị số nguyên, được đóng thành một từ khi chúng nhỏ) và con trỏ đến phần tử tiếp theo trong danh sách. Ngược lại, ngăn xếp được phát triển bởi hai từ tại mỗi lần lặp bằng mã vạch allocate: một từ cho CP được tự lưu bởi allocate và một từ theo yêu cầu (thông số đầu tiên là allocate) cho giá trị hiện tại.

Đối với 100.000.000 từ trên máy ảo 64 bit, danh sách mất tối thiểu 1,5 GB (nhiều hơn khi chồng thực tế không được phát triển hai từ, may mắn thay). Việc giám sát và thu dọn này rất khó trong vỏ, vì nhiều giá trị vẫn còn tồn tại. Nếu bạn sinh ra một hàm, bạn có thể thấy mức sử dụng bộ nhớ:

spawn(fun() -> 
    io:format("~p\n", [erlang:memory()]), 
    L = lists:seq(1, 100000000), 
    io:format("~p\n", [erlang:memory()]), 
    sum_test:sum_list(L, 0), 
    io:format("~p\n", [erlang:memory()]) 
end). 

Như bạn thấy, bộ nhớ cho cuộc gọi đệ quy không được giải phóng ngay lập tức.