[erlang-questions] [erlang-question] How to comprehend two lists synchronously?

Jeff Schultz jws@REDACTED
Mon Nov 21 02:35:02 CET 2011


On Fri, Nov 18, 2011 at 11:37:24AM +0400, Dmitry Demeshchuk wrote:
> Okay, I admit, this isn't an "honest" tail-recursed function, since a
> list concatenation operator is going to be called at the end. However,
> Erlang compiler optimizes such cases and converts them to
> tail-recursive:
> http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive

Not really.  Here's what R14B compiles your map2/3 to (with my
comments added):

{function, map2, 3, 2}.
  {label,1}.
    {func_info,{atom,map2},{atom,map2},3}.
  {label,2}.
    {test,is_nonempty_list,{f,3},[{x,1}]}.
    {get_list,{x,1},{x,3},{x,4}}.
    {test,is_nonempty_list,{f,1},[{x,2}]}.
    {allocate,3,5}.		% allocate stack frame
    {get_list,{x,2},{x,1},{y,2}}.
    {move,{x,0},{x,2}}.
    {move,{x,3},{x,0}}.
    {move,{x,2},{y,0}}.
    {move,{x,4},{y,1}}.
    {call_fun,2}.		% Fun(H1, H2)
    {move,{x,0},{x,3}}.		% could be reordered
    {move,{y,1},{x,1}}.
    {move,{y,2},{x,2}}.
    {move,{y,0},{x,0}}.
    {move,{x,3},{y,2}}.		% cute
    {trim,2,1}.			% trim the stack frame
    {call,3,{f,2}}.		% map2(Fun, T1, T2)
    {test_heap,2,1}.
    {put_list,{y,0},{x,0},{x,0}}.
    {deallocate,1}.		% deallocate stack frame
    return.
  {label,3}.
    {test,is_nil,{f,1},[{x,1}]}.
    {test,is_nil,{f,1},[{x,2}]}.
    {move,nil,{x,0}}.
    return.

So if T1 and T2 have length N, you get a peak stack use of N frames.
Unless the VM does some clever transformation when it loads this code,
of course.

In this case, the stack frame is able to be trimmed to 1 entry before
the recursion, so it quite possibly ends up taking a similar amount of
space to the intermediate list produced by the usual tail recursion
transformation.

This may actually be better than Erlang tail recursion followed by
reverse/2 because it avoids garbage collecting the intermediate list
produced by the usual tail recursion transformation.  Whether this
ends up as a net speed gain as well is something one would have to
measure.

(The trim instruction seems weird.  I'm curious about why it was done
this way.)


    Jeff Schultz



More information about the erlang-questions mailing list