On Fri, May 20, 2011 at 07:47:15AM -0400, Frédéric Trottier-Hébert wrote:
> I would dare say that tail recursion is not exactly important in this example.
>
> In both cases, you basically end up creating a list, which will hold all the values of all messages. In one case, you will be creating a list of N elements to be carried on the stack, in the other case, you'll be having a stack that is about the size of N elements.
>
> In the first case, you also have to reverse the list, in the other, you don't. It's not really a big deal IMO to use a call that is not tail recursive when what you are doing is building a list that is in the same order as the items happen. If you look into the stdlib, you'll see that the lists:map/2 function is (or was? haven't looked in a few versions) implemented in a non tail recursive manner. When you think of it, it kind of makes sense too; you give a list of the same size as before, in the right order, for similar speeds, and you'll be avoiding a call to a BIF (reverse/1) on top of it.
Messen ist wissen
-- von Siemens
To measure is to know
But it is fun to speculate (to elaborate on the conclusion above).
Body recursion:
For every message, build it on the heap, push the message
handle on the stack (1 word), call yourself meaning push the
return address (1 word). If we run out of stack + heap that are
in the same memory block (in the current implementation) do a
garbage collect that will increase the free space.
When the loop is ended we pop one stack frame at the time
(1+1 words) and build one list cons cell (2 words). The result
is built while we return and requires no garbage collections
since the pops from the stack match what's built on the heap.
Tail recursion:
For every message, build it on the heap, build one list cons
cell (2 words) on the heap and loop to yourself. Garbage
collect just like above. Practically equivalent to the
body recursive variant but build all on the heap and
nothing on the stack.
When the loop is ended, do the lists:reverse/1 to build the
result. A new list is built on the heap requiring the same
size as the old list, and the reversed list becomes garbage.
So, tail recursion should require a top memory consumption of
2 * size(MsgList) words more than body recursion. This will
cause extra garbage collection. Also the lists:reverse/1 is
extra work that the body recursive variant avoids.
In this case I speculate body recursion wins.
In some other implementation where heap and stack are not in
the same memory block the situation changes. I know of no
such implementation yet. In the Erjang prototype stack space
is limited so all body recursion should be avoided. That
might be an unacceptable limitation since it impacts so
hard at body recursion.
>
> Now, in the case when you're building a list in a different order or where you basically create more data than necessary by avoiding recursion (ex.: a tail recursive fibonacci vs. a non tail recursive fibonacci), then tail recursion should be chosen, but I see nothing wrong with the flush/0 implementation of Kannan.
>
> --
> Fred Hébert
>
http://www.erlang-solutions.com>
>
>
> On 2011-05-20, at 06:50 AM, Vance Shipley wrote:
>
> > Kannan,
> >
> > No, it is not tail recursive. This is:
> >
> > %% @spec() -> [term()]
> > %%
> > flush() ->
> > flush([]).
> >
> > %% @hidden
> > flush(Msgs) ->
> > receive
> > Msg ->
> > flush([Msg | Msgs]);
> > after 17 ->
> > Msgs
> > end.
> >
> > On Fri, May 20, 2011 at 03:45:19PM +0530, Kannan wrote:
> > } Is the following list construction an efficient one?
> > }
> > } flush() ->
> > } receive
> > } Msg ->
> > } [Msg|flush()]
> > } after 17 ->
> > } []
> > } end.
> >
> > --
> > -Vance
> > _______________________________________________
> > erlang-questions mailing list
> >
[hidden email]
> >
http://erlang.org/mailman/listinfo/erlang-questions>
> _______________________________________________
> erlang-questions mailing list
>
[hidden email]
>
http://erlang.org/mailman/listinfo/erlang-questions--
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Locked
