robert....@erlang-solutions.com
31/03/2011 19:40 |
|
carlsson...@gmail.com
01/04/2011 10:46 |
|
So if (from the docs) list comprehension become :
'lc^0'([E|Tail], Expr) -> [Expr(E)|'lc^0'(Tail, Expr)]; 'lc^0'([], _Expr) -> [].
E-mail communication cannot be guaranteed to be timely secure, error or virus-free._______________________________________________
Thanks for your reply. The following part of the docs actually shows that it does do the non-return optimisation:-) tho you answer also make me question all my carefully crafted non-body recursive functions with reverses too !
James
On 1 Apr 2011, at 20:08, Richard Carlsson wrote:
> On 2011-04-01 19:24, James Churchman wrote:
>> So if (from the docs) list comprehension become :
>>
>> 'lc^0'([E|Tail], Expr) -> [Expr(E)|'lc^0'(Tail, Expr)];
>> 'lc^0'([], _Expr) -> [].
>>
>> then, what happens when Expr contains references to other variables in
>> the original scope? (eg not E ) it says Expr used to be a Fun, but now
>> it's not, so in this case is it a Fun, or does it increase the arty of
>> the generated lc^0 function for each of the extra referenced vars?
>
> Essentially, yes, it increases the arity. First, the list comprehension becomes a local function in Core Erlang (with access to the variables in scope). The local function is then lifted out to become a normal function with additional parameters before it gets translated to BEAM.
>
>> Also keen to know the body recursive "cost", and why it avoids using
>> list reverse in the case when a list is required to be returned :-)
>
> A body recursive translation is simpler, and is generally faster for short lists (the majority of list comprehensions runs on lists shorter than 100 elements, in my experience at least, and the break-even point for tail recursion plus reverse is somewhere above 100 elements).
>
> Even for quite long lists, a body recursive function is typically not much worse than a tail recursive solution with a reverse at the end, so there's no reason to change the behaviour and make it worse for short lists. Hence, the current implementation never produces a list in reverse order, and it never needs to reverse anything at the end.
>
> If the compiler knows that the result (which is always a list) won't be used at all, it could generate code more similar to lists:foreach() instead, but I don't think that's done currently.
>
> /Richard
There used to be a more noticeable difference between
body recursion and tail recursion before the R12B release,
because body recursion would usually use more memory.
In R12B and later releases, the tail-recursive and
body-recursive variants of a function generally use the
same amount of memory and executes roughly in the
same time. See:
http://www.erlang.org/doc/efficiency_guide/myths.html#id58884
>> If the compiler knows that the result (which is always a list) won't be used at all, it could generate code more similar to lists:foreach() instead, but I don't think that's done currently.
It's done. See:
http://www.erlang.org/doc/efficiency_guide/listHandling.html#id61285
--
Björn Gustavsson, Erlang/OTP, Ericsson AB