I'm struggling to understand ASM code generated by the erlang compiler.<div><br></div><div>Could you please tell the difference of the asm code between map2 and map3?</div><div><br></div><div><div>{function, <b>map2</b>, 3, 12}.</div>
<div> {label,11}.</div><div> {func_info,{atom,test},{atom,map2},3}.</div><div> {label,12}.</div><div> {test,is_nonempty_list,{f,13},[{x,1}]}.</div><div> {get_list,{x,1},{x,3},{x,4}}.</div><div> {test,is_nonempty_list,{f,11},[{x,2}]}.</div>
<div> {allocate,3,5}.</div><div> {get_list,{x,2},{x,1},{y,2}}.</div><div> {move,{x,0},{x,2}}.</div><div> {move,{x,3},{x,0}}.</div><div> {move,{x,2},{y,0}}.</div><div> {move,{x,4},{y,1}}.</div><div> {call_fun,2}.</div>
<div> {move,{x,0},{x,3}}.</div><div> {move,{y,1},{x,1}}.</div><div> {move,{y,2},{x,2}}.</div><div> {move,{y,0},{x,0}}.</div><div> {move,{x,3},{y,2}}.</div><div> {trim,2,1}.</div><div> {call,3,{f,12}}.</div>
<div> {test_heap,2,1}.</div><div> {put_list,{y,0},{x,0},{x,0}}.</div><div> {deallocate,1}.</div><div> return.</div><div> {label,13}.</div><div> {test,is_nil,{f,11},[{x,1}]}.</div><div> {test,is_nil,{f,11},[{x,2}]}.</div>
<div> {move,nil,{x,0}}.</div><div> return.</div><div><br></div><div><br></div><div>{function,<b> map3</b>, 3, 15}.</div><div> {label,14}.</div><div> {func_info,{atom,test},{atom,map3},3}.</div><div> {label,15}.</div>
<div> {test,is_nil,{f,16},[{x,1}]}.</div><div> {test,is_nil,{f,16},[{x,2}]}.</div><div> {move,nil,{x,0}}.</div><div> return.</div><div> {label,16}.</div><div> {move,nil,{x,3}}.</div><div> {call_only,4,{f,18}}.</div>
<div><br></div><div><br></div><div>{function,<b> map3</b>, 4, 18}.</div><div> {label,17}.</div><div> {func_info,{atom,test},{atom,map3},4}.</div><div> {label,18}.</div><div> {test,is_nonempty_list,{f,19},[{x,1}]}.</div>
<div> {get_list,{x,1},{x,4},{x,5}}.</div><div> {test,is_nonempty_list,{f,17},[{x,2}]}.</div><div> {allocate,4,6}.</div><div> {get_list,{x,2},{x,1},{y,3}}.</div><div> {move,{x,0},{x,2}}.</div><div> {move,{x,4},{x,0}}.</div>
<div> {move,{x,3},{y,0}}.</div><div> {move,{x,2},{y,1}}.</div><div> {move,{x,5},{y,2}}.</div><div> {call_fun,2}.</div><div> {test_heap,2,1}.</div><div> {put_list,{x,0},{y,0},{x,3}}.</div><div> {move,{y,2},{x,1}}.</div>
<div> {move,{y,3},{x,2}}.</div><div> {move,{y,1},{x,0}}.</div><div> {call_last,4,{f,18},4}.</div><div> {label,19}.</div><div> {test,is_nil,{f,17},[{x,1}]}.</div><div> {test,is_nil,{f,17},[{x,2}]}.</div><div>
{move,{x,3},{x,0}}.</div><div> {call_ext_only,1,{extfunc,lists,reverse,1}}.</div><div><br></div><br><div class="gmail_quote">On Mon, Nov 21, 2011 at 9:35 AM, Jeff Schultz <span dir="ltr"><<a href="mailto:jws@csse.unimelb.edu.au">jws@csse.unimelb.edu.au</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">On Fri, Nov 18, 2011 at 11:37:24AM +0400, Dmitry Demeshchuk wrote:<br>
> Okay, I admit, this isn't an "honest" tail-recursed function, since a<br>
> list concatenation operator is going to be called at the end. However,<br>
> Erlang compiler optimizes such cases and converts them to<br>
> tail-recursive:<br>
> <a href="http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive" target="_blank">http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive</a><br>
<br>
</div>Not really. Here's what R14B compiles your map2/3 to (with my<br>
comments added):<br>
<div class="im"><br>
{function, map2, 3, 2}.<br>
{label,1}.<br>
</div> {func_info,{atom,map2},{atom,map2},3}.<br>
<div class="im"> {label,2}.<br>
{test,is_nonempty_list,{f,3},[{x,1}]}.<br>
{get_list,{x,1},{x,3},{x,4}}.<br>
{test,is_nonempty_list,{f,1},[{x,2}]}.<br>
</div> {allocate,3,5}. % allocate stack frame<br>
<div class="im"> {get_list,{x,2},{x,1},{y,2}}.<br>
{move,{x,0},{x,2}}.<br>
{move,{x,3},{x,0}}.<br>
{move,{x,2},{y,0}}.<br>
{move,{x,4},{y,1}}.<br>
</div> {call_fun,2}. % Fun(H1, H2)<br>
{move,{x,0},{x,3}}. % could be reordered<br>
<div class="im"> {move,{y,1},{x,1}}.<br>
{move,{y,2},{x,2}}.<br>
{move,{y,0},{x,0}}.<br>
</div> {move,{x,3},{y,2}}. % cute<br>
{trim,2,1}. % trim the stack frame<br>
{call,3,{f,2}}. % map2(Fun, T1, T2)<br>
<div class="im"> {test_heap,2,1}.<br>
{put_list,{y,0},{x,0},{x,0}}.<br>
</div> {deallocate,1}. % deallocate stack frame<br>
<div class="im"> return.<br>
{label,3}.<br>
{test,is_nil,{f,1},[{x,1}]}.<br>
{test,is_nil,{f,1},[{x,2}]}.<br>
{move,nil,{x,0}}.<br>
return.<br>
<br>
</div>So if T1 and T2 have length N, you get a peak stack use of N frames.<br>
Unless the VM does some clever transformation when it loads this code,<br>
of course.<br>
<br>
In this case, the stack frame is able to be trimmed to 1 entry before<br>
the recursion, so it quite possibly ends up taking a similar amount of<br>
space to the intermediate list produced by the usual tail recursion<br>
transformation.<br>
<br>
This may actually be better than Erlang tail recursion followed by<br>
reverse/2 because it avoids garbage collecting the intermediate list<br>
produced by the usual tail recursion transformation. Whether this<br>
ends up as a net speed gain as well is something one would have to<br>
measure.<br>
<br>
(The trim instruction seems weird. I'm curious about why it was done<br>
this way.)<br>
<span class="HOEnZb"><font color="#888888"><br>
<br>
Jeff Schultz<br>
</font></span><div class="HOEnZb"><div class="h5">_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</div></div></blockquote></div><br></div>