[erlang-questions] Efficiency of a list construction

[Raimo Niskanen]

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
> > erlang-questions@REDACTED
> > http://erlang.org/mailman/listinfo/erlang-questions
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB