efficiency, deep lists

[Chandrashekhar Mullaparthi]

I actually like my style which yields even better results. And it has the
added benefit of being tail recursive and more readable. I'm sorry Uffe if
you were trying to make some other point. But my results seem to indicate
that incr2 is the most expensive. But then timer:tc gives a wide range of
results. But the pattern is the same.

3> timer:tc(continuation, incr1, [List]).
{300,[2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8|...]}

4> timer:tc(continuation, incr2, [List]).
{530,[2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8|...]}

5> timer:tc(continuation, incr3, [List]).
{370,[2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8|...]}

6> timer:tc(continuation, incr4, [List]).
{297,[2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8|...]}

7> timer:tc(continuation, myinc, [List]).
{209,[2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8|...]}

%%------------------------------

myinc(List) ->
    lists:reverse(myinc(List, [])).
myinc([H|T], Acc) ->
    myinc(T, myinc2(H, Acc));
myinc([], Acc) ->
    Acc.

myinc2([H|T], Acc) ->
    myinc2(T, [H+1|Acc]);
myinc2([], Acc) -> Acc.

%%---------------------------------

cheers,
Chandru

> -----Original Message-----
> From: Ulf Wiger [mailto:etxuwig@REDACTED]
> Sent: 2 October 2001 10:53
> To: erlang-questions@REDACTED
> Subject: efficiency, deep lists
> 
> 
> 
> Hi,
> 
> I've been playing around with continuation passing style when 
> processing lists of lists. It does seem to be a bit cheaper than
> the alternative styles. If funs are optimized in R8, it should be
> even more so.
> 
> 
> Example:
> 
> I wrote four different ways to increment all elements in a list
> of lists of integers (lists:duplicate(50, lists:seq(1,50)).
> 
> The outcome on my machine was as follows:
> 
> - incr1/1: 964 us
> - incr2/1: 814 us
> - incr3/1: 951 us
> - incr4/1: 914 us
> 
> 
> The winner, albeit by a hair, was:
> 
> incr2([H|T]) ->
>    incr22(H, fun() -> incr2(T) end);
> incr2([]) ->
>    [].
> 
> incr22([H|T], F) ->
>    [H+1|incr22(T, F)];
> incr22([], F) ->
>    F().
> 
> 
> So, question to the community. Does this style of programming
> strike you as offensive, or do you kind of like it?
> 
> Personally, I feel that the other contenders only come close
> because ++ has been optimized in C, so I kind of like the
> continuation passing style because it is cheap by design.  ;-)
> 
> /Uffe
> ****************************
> 
> -module(continuation).
> -author('etxuwig@REDACTED').
> 
> -compile(export_all).
> 
> mk_list() ->
>     lists:duplicate(50, lists:seq(1,10)).
> 
> incr1([H|T]) when list(H) ->
>     incr11(H) ++ incr1(T);
> incr1([]) ->
>     [].
> 
> incr11([H|T]) ->
>     [H+1|incr11(T)];
> incr11([]) ->
>     [].
> 
> incr2([H|T]) when list(H) ->
>     incr22(H, fun() -> incr2(T) end);
> incr2([]) ->
>     [].
> 
> incr22([H|T], F) ->
>     [H+1|incr22(T, F)];
> incr22([], F) ->
>     F().
> 
> incr3(List) ->
>     lists:foldl(
>       fun(L, Acc) ->
> 	      incr11(L) ++ Acc
>       end, [], List).
> 
> incr4(List) ->
>     incr11(lists:concat(List)).
> 
> 
> 
> -- 
> 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
> 



NOTICE AND DISCLAIMER:
This email (including attachments) is confidential.  If you have received
this email in error please notify the sender immediately and delete this
email from your system without copying or disseminating it or placing any
reliance upon its contents.  We cannot accept liability for any breaches of
confidence arising through use of email.  Any opinions expressed in this
email (including attachments) are those of the author and do not necessarily
reflect our opinions.  We will not accept responsibility for any commitments
made by our employees outside the scope of our business.  We do not warrant
the accuracy or completeness of such information.