8

是否可以使用未在 Erlang 中优化尾调用的函数获得 stackoverflow？例如，假设我有这样的功能

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

看起来如果传入一个足够大的列表，它最终会耗尽堆栈空间并崩溃。我试过这样测试：

> 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

但它永远不会崩溃！我尝试了一个包含 100,000,000 个整数的列表，它花了一段时间才完成，但它仍然没有崩溃！问题：

  1. 我是否正确测试了这个？
  2. 如果是这样，为什么我无法生成stackoverflow？
  3. Erlang 是否正在做一些防止堆栈溢出发生的事情？
4

1 回答 1

12

您正在正确地对此进行测试：您的函数确实不是尾递归的。要找出答案，您可以使用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.

作为比较，以下函数的尾递归版本：

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

编译为：

{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.

注意尾递归版本中缺少allocate和操作码，与非递归函数中的 /// 序列相反。call_onlyallocatecalldeallocatereturn

你没有得到堆栈溢出，因为 Erlang 的“堆栈”非常大。实际上，堆栈溢出通常意味着处理器堆栈溢出，因为处理器的堆栈指针离得太远了。进程传统上具有有限的堆栈大小，可以通过与操作系统交互来调整。参见例如 POSIX 的setrlimit。

但是，Erlang 执行堆栈不是处理器堆栈，因为代码是被解释的。每个进程都有自己的堆栈，可以通过调用操作系统内存分配函数（通常是 Unix 上的malloc ）按需增长。

因此，只要malloc调用成功，您的函数就不会崩溃。

为了记录，实际列表L使用与堆栈相同数量的内存来处理它。实际上，列表中的每个元素都包含两个单词（整数值本身，因为它们很小，所以被装箱为一个单词）和指向列表下一个元素的指针。相反，堆栈在操作码的每次迭代中增长两个字allocate：一个字CP由allocate自身保存，一个字根据请求（的第一个参数allocate）用于当前值。

对于 64 位 VM 上的 100,000,000 个字，该列表至少需要 1.5 GB（幸运的是，实际堆栈不是每两个字增长一次）。在 shell 中监控和垃圾处理是很困难的，因为许多值仍然存在。如果你生成一个函数，你可以看到内存使用情况：

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).

如您所见，递归调用的内存不会立即释放。

于 2014-11-20T08:43:00.360 回答