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

Björn Gustavsson bgustavsson@REDACTED
Mon Nov 21 09:55:53 CET 2011


On 11/21/11, Jeff Schultz <jws@REDACTED> wrote:

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

It doesn't.

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

Actually, "{trim,2,1}" means that two stack entries will be trimmed
and one stack entry will remain. The number of remaining stack
entries is only there to simplify the hipe compiler; it will not be used
at run-time by BEAM.

This function will use the same amount of space (two words) as
the tail-recursive version.

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

Yes, it must be measured in every individual case. In general, both
versions run with roughly the same speed. Depending on hardware
archictecture (CPU, cache), heap size, typical list size, and probably
other factors, the tail recursive or body recursive function could be
fastest.

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

Mainly backward compatibility. It would have been very difficult to do
stack trimming in the traditional way without breaking backward
compatibility. Unfortunately the return address is stored at the
wrong end of the stack frame from the point of view of stack
trimming, but too much depend on it.

-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB



More information about the erlang-questions mailing list