Optimization of list comprehensions?

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

Optimization of list comprehensions?

David Gould

I really like list comprehensions, they seem so, declarative. I am tempted
to use them everywhere ;-)

But, what does the compiler do with them?

Does it generate better code for a list comprehension than for using
lists:map()?

Is it able to detect when a listcomp is used for its side effects alone and
not build the result? For example, is:

 [io:format('~s~n', [Item]) | Item <- Items].

more or less effcient than:

 lists:foreach(fun(Item) -> io:format('~s~n', [Item])) end, Items).

Oh yeah, is it better or worse style?

-dg

--
David Gould                                                 dg
SuSE, Inc.,  580 2cd St. #210,  Oakland, CA 94607          510.628.3380
You left them alone in a room with a penguin?!  Mr Gates, your men are
already dead.


Reply | Threaded
Open this post in threaded view
|

Optimization of list comprehensions?

Richard Carlsson-4

On Mon, 5 Feb 2001, David Gould wrote:

> I really like list comprehensions, they seem so, declarative. I am
> tempted to use them everywhere ;-)
>
> But, what does the compiler do with them?
>
> Does it generate better code for a list comprehension than for using
> lists:map()?

Up until now, list comprehensions have not been efficiently compiled, but
as of the coming R8 release they will be as efficient as the hand-coded
versions, i.e.:

        do(Xs) -> [foo(X) || X <- Xs].

will be as quick as:

        do([X | Xs]) ->?[foo(X) | do(Xs)];
        do([]) -> [].

And in fact, there is some potential for generating even better code for
list comprehensions than for explicitly recursive functions.

> Is it able to detect when a listcomp is used for its side effects
> alone and not build the result? For example, is:
>
>  [io:format('~s~n', [Item]) | Item <- Items].
>
> more or less effcient than:
>
>  lists:foreach(fun(Item) -> io:format('~s~n', [Item])) end, Items).

It could be done, but don't expect it to happen any time soon. (Actually,
that sort of optimisation - a form of specialisation - applies to other
code as well, not only list comprehensions.)

> Oh yeah, is it better or worse style?

I'd say the "foreach" version is better style in this case, since it is
less obvious to the eye (even if it is actually the case) that the calls
will be executed in the expected order in the list comprehension version.

        /Richard Carlsson


Richard Carlsson (richardc)   (This space intentionally left blank.)
E-mail: Richard.Carlsson WWW: http://www.csd.uu.se/~richardc/



Reply | Threaded
Open this post in threaded view
|

Optimization of list comprehensions?

Ulf Wiger-4
In reply to this post by David Gould



On Mon, 5 Feb 2001, David Gould wrote:

>I really like list comprehensions, they seem so, declarative. I am
>tempted to use them everywhere ;-)

Yes, they're nice.


>But, what does the compiler do with them?
>
>Does it generate better code for a list comprehension than for using
>lists:map()?

Essentially, the list comprehension becomes a lists:map().


You can check for yourself by using the 'E' compiler option.
Here's an example:

*********************** lctest.erl

-module(lctest).
-author('etxuwig').

%%-compile(export_all).
-export([lc1/1,
         lc2/2]).


lc1(List) ->
    [foo(X) ||
        X <- List,
        X > 17].

lc2(List1, List2) ->
    [foo({X, Y}) ||
        X <- List1,
        Y <- List2,
        X > Y].

foo(X) -> X.


***********************

erlc -E lctest.erl


*********************** lctest.E


-author(['etxuwig']).

lc1(List) ->
    begin
        %0 = % fun-info:
{78720207,[['%0','%1','X'],['%0','%1'],['%0']],[]}
             fun ([X|%1],%0) ->
                     if
                         X > 17 ->
                             [foo(X)|%0(%1,%0)];
                         true ->
                             %0(%1,%0)
                     end;
                 ([_|%1],%0) ->
                     %0(%1,%0);
                 ([],%0) ->
                     [] end,
        %0(List,%0)
    end.

lc2(List1,List2) ->
    begin
        %2 = % fun-info:
{123483443,[['%2','%3','X'],['%2','%3'],['%2']],['List2
']}
             fun ([X|%3],%2) ->
                     begin
                         %4 = % fun-info:
{38130919,[['%4','%5','Y'],['%4','%5']
,['%4']],['%2','%3','X']}
                              fun ([Y|%5],%4) ->
                                      if
                                          X > Y ->
                                              [foo({X,Y})|%4(%5,%4)];
                                          true ->
                                              %4(%5,%4)
                                      end;
                                  ([_|%5],%4) ->
                                      %4(%5,%4);
                                  ([],%4) ->
                                      %2(%3,%2) end,
                         %4(List2,%4)
                     end;
                 ([_|%3],%2) ->
                     %2(%3,%2);
                 ([],%2) ->
                     [] end,
        %2(List1,%2)
    end.

foo(X) ->
    X.

module_info() ->
    [].

module_info(_) ->
    [].





>Is it able to detect when a listcomp is used for its side effects
>alone and not build the result?

I don't recall seeing anything like that in the compiler
(but I will admit I don't understand the compiler well enough to be
sure.)



>Oh yeah, is it better or worse style?


Personally, I try to avoid using list comprehensions when I really
don't care about the result, since lists:foreach/2 makes that point
very clearly.

/Uffe
--
Ulf Wiger                                    tfn: +46  8 719 81 95
Senior System Architect                      mob: +46 70 519 81 95
Strategic Product & System Management    ATM Multiservice Networks
Data Backbone & Optical Services Division      Ericsson Telecom AB



Reply | Threaded
Open this post in threaded view
|

Optimization of list comprehensions?

Robert Virding-4
In reply to this post by David Gould
David Gould <dg> writes:
>
>I really like list comprehensions, they seem so, declarative. I am tempted
>to use them everywhere ;-)
>
>But, what does the compiler do with them?
>
>Does it generate better code for a list comprehension than for using
>lists:map()?

The current (R7) compiler does a reasonable job with and the code is
comaprable to using lists:map.  The new R8 compiler will do a better
job, but it very much depends on what you do in the lc/map which is the
faster.  Lc's shouldn't be slower.

>Is it able to detect when a listcomp is used for its side effects alone and
>not build the result? For example, is:
>
> [io:format('~s~n', [Item]) | Item <- Items].
>
>more or less effcient than:
>
> lists:foreach(fun(Item) -> io:format('~s~n', [Item])) end, Items).
>
>Oh yeah, is it better or worse style?

The compiler does not detect if a comprehension is used for side effects
alone.  It is, however, definitely much worse style not to use
lists:foreach or lists:map where appropriate.  lists:foreach explicitly
says "do this for each element and throw away the result" while
comprehensions say "take elements from generators, filter out unwanted
cases and build list of values like this".

You should always try and be clear.  Anyway we are looking at how to
optimise calls to useful functions in the standard libraries, like
lists:map and lists:foreach.

        Robert

--
Robert Virding                          Tel: +46 (0)8 545 55 017
Alteon Web Systems                      Email: rv
S:t Eriksgatan 44                       WWW: http://www.bluetail.com/~rv
SE-112 34 Stockholm, SWEDEN
"Folk s?ger att jag inte bryr mig om n?gonting, men det skiter jag i".