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

[Barco You]

I'm struggling to understand ASM code generated by the erlang compiler.

Could you please tell the difference of the asm code between map2  and map3?

{function, *map2*, 3, 12}.
  {label,11}.
    {func_info,{atom,test},{atom,map2},3}.
  {label,12}.
    {test,is_nonempty_list,{f,13},[{x,1}]}.
    {get_list,{x,1},{x,3},{x,4}}.
    {test,is_nonempty_list,{f,11},[{x,2}]}.
    {allocate,3,5}.
    {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}.
    {move,{x,0},{x,3}}.
    {move,{y,1},{x,1}}.
    {move,{y,2},{x,2}}.
    {move,{y,0},{x,0}}.
    {move,{x,3},{y,2}}.
    {trim,2,1}.
    {call,3,{f,12}}.
    {test_heap,2,1}.
    {put_list,{y,0},{x,0},{x,0}}.
    {deallocate,1}.
    return.
  {label,13}.
    {test,is_nil,{f,11},[{x,1}]}.
    {test,is_nil,{f,11},[{x,2}]}.
    {move,nil,{x,0}}.
    return.


{function,* map3*, 3, 15}.
  {label,14}.
    {func_info,{atom,test},{atom,map3},3}.
  {label,15}.
    {test,is_nil,{f,16},[{x,1}]}.
    {test,is_nil,{f,16},[{x,2}]}.
    {move,nil,{x,0}}.
    return.
  {label,16}.
    {move,nil,{x,3}}.
    {call_only,4,{f,18}}.


{function,* map3*, 4, 18}.
  {label,17}.
    {func_info,{atom,test},{atom,map3},4}.
  {label,18}.
    {test,is_nonempty_list,{f,19},[{x,1}]}.
    {get_list,{x,1},{x,4},{x,5}}.
    {test,is_nonempty_list,{f,17},[{x,2}]}.
    {allocate,4,6}.
    {get_list,{x,2},{x,1},{y,3}}.
    {move,{x,0},{x,2}}.
    {move,{x,4},{x,0}}.
    {move,{x,3},{y,0}}.
    {move,{x,2},{y,1}}.
    {move,{x,5},{y,2}}.
    {call_fun,2}.
    {test_heap,2,1}.
    {put_list,{x,0},{y,0},{x,3}}.
    {move,{y,2},{x,1}}.
    {move,{y,3},{x,2}}.
    {move,{y,1},{x,0}}.
    {call_last,4,{f,18},4}.
  {label,19}.
    {test,is_nil,{f,17},[{x,1}]}.
    {test,is_nil,{f,17},[{x,2}]}.
    {move,{x,3},{x,0}}.
    {call_ext_only,1,{extfunc,lists,reverse,1}}.


On Mon, Nov 21, 2011 at 9:35 AM, Jeff Schultz <jws@REDACTED>wrote:

> 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
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111121/2704e559/attachment.htm>