Efficiency of a list construction

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Efficiency of a list construction

Theepan
Hi

Is the following list construction an efficient one?

flush() ->
    receive
Msg ->
   [Msg|flush()]
    after 17 ->
   []
    end.



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Vance Shipley
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
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Paul Barry
Interesting response.

I'm currently working my way through both Joe's book and
Francesco/Simon's.  As this is Erlang, I'm reading the two books in
parallel (of course).

Both books talk about the efficiency of tail recursion over direct
recursion with a bit of talk about how the run-time may optimize for
code that isn't tail recursive to improve its performance.  The
suggestion seems to be that in older versions of the run-time, tail
recursion won hands down, but that nowadays this may not always be the
case.  Is there an update on this?

Of course, Joe's book suggests that the only way to *really* know is
to measure (good advice).  Using "timer:tc" (as described on page 107
of the Francesco/Simon book) might be a good place to start.

Regards.

Paul.


On 20 May 2011 11:50, Vance Shipley <[hidden email]> 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
>



--
Paul Barry, w: http://paulbarry.itcarlow.ie, e: [hidden email]
Lecturer, Computer Networking: Institute of Technology, Carlow, Ireland.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Ulf Wiger

On 20 May 2011, at 13:08, Paul Barry wrote:

Both books talk about the efficiency of tail recursion over direct
recursion with a bit of talk about how the run-time may optimize for
code that isn't tail recursive to improve its performance.  The
suggestion seems to be that in older versions of the run-time, tail
recursion won hands down, but that nowadays this may not always be the
case.  Is there an update on this?

The Erlang/OTP Efficiency Guide is the most up-to-date document on the matter.

E.g. Chapter 5.4  - Why you should not worry about recursive lists functions


BR,
Ulf W

Ulf Wiger, CTO, Erlang Solutions, Ltd.




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Theepan
In reply to this post by Vance Shipley

I saw this function in gen_sctp_SUITE.erl :-(


On Fri, May 20, 2011 at 4:20 PM, Vance Shipley <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Ladislav Lenart
In reply to this post by Paul Barry
Hello.

I would like to point out that the two implementations are not
exactly the same because the tail recursive version returns
messages in the reverse order as opposed to the original
(non-tail recursive version), which does preserve the order
of received messages. The equivalent tail-recursive implementation
would be:

%% @spec() ->  [term()]
flush() ->
flush([]).

%% @hidden
flush(Msgs) ->
     receive
         Msg ->
             flush([Msg | Msgs]);
     after 17 ->
         lists:reverse(Msgs)    % added call to lists:reverse/1
     end.


However if the order is important I would use the original
non-tail recursive version. For example lists:map/2 uses
non-tail recursive approach as well.


Ladislav Lenart


On 20.5.2011 13:08, Paul Barry wrote:

> Interesting response.
>
> I'm currently working my way through both Joe's book and
> Francesco/Simon's.  As this is Erlang, I'm reading the two books in
> parallel (of course).
>
> Both books talk about the efficiency of tail recursion over direct
> recursion with a bit of talk about how the run-time may optimize for
> code that isn't tail recursive to improve its performance.  The
> suggestion seems to be that in older versions of the run-time, tail
> recursion won hands down, but that nowadays this may not always be the
> case.  Is there an update on this?
>
> Of course, Joe's book suggests that the only way to *really* know is
> to measure (good advice).  Using "timer:tc" (as described on page 107
> of the Francesco/Simon book) might be a good place to start.
>
> Regards.
>
> Paul.
>
>
> On 20 May 2011 11:50, Vance Shipley<[hidden email]>  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
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Vance Shipley
In reply to this post by Ulf Wiger
Old habits die hard.

On Fri, May 20, 2011 at 01:11:58PM +0200, Ulf Wiger wrote:
}  E.g. Chapter 5.4  - Why you should not worry about recursive lists functions
}  
}  http://www.erlang.org/doc/efficiency_guide/listHandling.html#id64754

--
        -Vance
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Frédéric Trottier-Hébert
In reply to this post by Vance Shipley
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.

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
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Pierpaolo Bernardi
In reply to this post by Vance Shipley
On Fri, May 20, 2011 at 12:50, Vance Shipley <[hidden email]> 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.

However, this returns a reversed list, w.r.t.

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

P.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Raimo Niskanen-2
In reply to this post by Frédéric Trottier-Hébert
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
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Ulf Wiger

On 20 May 2011, at 14:38, Raimo Niskanen wrote:

> In the Erjang prototype stack space
> is limited so all body recursion should be avoided.

In all fairness to Erjang, it actually handles most cases of body recursion quite well. The times I've seen it blow up, it was always in pretty-printing a binary (a deeply-body-recursive function).

BR,
Ulf

Ulf Wiger, CTO, Erlang Solutions, Ltd.
http://erlang-solutions.com



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Efficiency of a list construction

Richard A. O'Keefe-2
In reply to this post by Raimo Niskanen-2
Consider

        map(F, [X|Xs]) -> [F(X) | map(F, Xs)];
        map(_, []    ) -> [].

By the classical definition, this is not tail recursive.
The Prolog equivalent, however, _is_.

The reason the Prolog version is tail recursive is that it
can build a data structure with a hole in it [F(X) | Hole]
and pass the hole:

        map(F, [X|Xs], &Result) =>
            *Result := [F(X) | Hole],
            map(F, Xs, &Hole);
        map(F, [], &Result) =>
            *Result := [].

And this would be safe even in Erlang because nobody (other
than the garbage collector) can ever see the hole.
This extended version of "tail recursion" applies when there
the last expression that the call occurs in is a data structure
construction.

The existing Erlang system *doesn't* support extended tail
recursion, largely for the sake of the garbage collector.
But it could, without any change to the source language
or its semantics.


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions