efficiency, deep lists

Ulf Wiger <>
Tue Oct 2 11:52:43 CEST 2001


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('').

-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




More information about the erlang-questions mailing list