Erlang: stackoverflow with recursive function that is not tail call optimized?

Question

Is it possible to get a stackoverflow with a function that is not tail call optimized in Erlang? For example, suppose I have a function like this

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

It would seem like if a large enough list was passed in it would eventually run out of stack space and crash. I tried testing this like so:

> 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

But it never crashes! I tried it with a list of 100,000,000 integers and it took a while to finish but it still never crashed! Questions:

1. Am I testing this correctly?
2. If so, why am I unable to generate a stackoverflow?
3. Is Erlang doing something that prevents stackoverflows from occurring?

Answer 1

You are testing this correctly: your function is indeed not tail-recursive. To find out, you can compile your code using 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.

As a comparison the following tail-recursive version of the function:

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

compiles as:

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

Notice the lack of allocate and the call_only opcode in the tail-recursive version, as opposed to the allocate/call/deallocate/return sequence in the non-recursive function.

You are not getting a stack overflow because the Erlang "stack" is very large. Indeed, stack overflow usually means the processor stack overflowed, as the processor's stack pointer went too far away. Processes traditionally have a limited stack size which can be tuned by interacting with the operating system. See for example POSIX's setrlimit.

However, Erlang execution stack is not the processor stack, as the code is interpreted. Each process has its own stack which can grow as needed by invoking operating system memory allocation functions (typically malloc on Unix).

As a result, your function will not crash as long as malloc calls succeed.

For the record, the actual list L is using the same amount of memory as the stack to process it. Indeed, each element in the list takes two words (the integer value itself, which is boxed as a word as they are small) and the pointer to the next element to the list. Conversely, the stack is grown by two words at each iteration by allocate opcode: one word for CP which is saved by allocate itself and one word as requested (the first parameter of allocate) for the current value.

For 100,000,000 words on a 64-bit VM, the list takes a minimum of 1.5 GB (more as the actual stack is not grown every two words, fortunately). Monitoring and garbaging this is difficult in the shell, as many values remain live. If you spawn a function, you can see the memory usage:

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

As you can see, the memory for the recursive call is not released immediately.