# [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

{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

```