efficiency, deep lists

[Richard Carlsson]

On Tue, 2 Oct 2001, Ulf Wiger wrote:

> What I was getting at was that it appeared as if continuation
> passing style actually led to pretty good performance, but I
> couldn't recall having seen much of it in Erlang.

Precisely. Probably this is because in the dark ages (i.e., up until a
year or two ago), Erlang funs were rather inefficiently implemented; in
particular, a fun application was a lot slower (at least 7-8 times) than
a normal function call, in the early Beam implementations. Today, fun
applications are only ~3 times slower than a local function call (local
calls have also been made faster since then, so this is really quite a
good number). Furthermore, creating a fun value was a bit expensive in
R6 - compared to creating a tuple of comparable size - but in R8, this
is much faster (twice as fast as in R7, actually; too bad I don't have
any figures to compare R6 with R7). Numbers taken from Björn
Gustavsson's home page: http://www.ericsson.com/cslab/~bjorn/.


> The real function I rewrote was not (increment on deep lists),
> but the following (slightly modified to protect the innocent):

So the order of Value elements in the final list was not important?
(Since your new version changes the order to strict left-to-right.
Maybe this was also a bug fix?)

And regarding the names - you can eliminate the get_vals2/2 function by
inlining it in get_values2/1.

	/Richard

> ----------------------------------------------------
> get_values(Keys) when list(Keys) ->
>     lists:foldl(
>       fun(K, Acc) ->
>               get_vals(K) ++ Acc
>       end, [], Keys).
> 
> get_vals(Key) ->
>     [{_, Points}] = ets:lookup(mytab, Key),
>     lists:map(
>       fun({point, Value}) ->
> 	      Value
>       end,
>       Points).
> ----------------------------------------------------
> 
> which I rewrote thus:
> 
> 
> ----------------------------------------------------
> get_values2([Key|Keys]) ->
>    get_vals2(Key, fun() -> get_values2(Keys) end);
> get_values2([]) ->
>    [].
> 
> get_vals2(Key, Cont) ->
>     [{_, Points}] = ets:lookup(mytab, Key),
>     get_values2(Points, Cont).
> 
> get_values2([{point, Value}|Points], Cont) -> 
>     [Value | get_values2(Points, Cont)];
> get_values2([], Cont) ->
>     Cont().
> 
> ----------------------------------------------------
> 
> Here's a helper function that I used to populate a table.
> 
> ----------------------------------------------------
> fill_tab() ->
>     ets:new(mytab, [set, public, named_table]),
>     Ps = lists:seq(1,10),
>     Points = [{point, V} || V <- Ps],
>     lists:foreach(
>       fun(P) ->
> 	      Obj = {P, Points},
> 	      ets:insert(mytab, Obj)
>       end, Ps).
> ----------------------------------------------------
> 
> 
> My version seems to be about 50% faster in a sloppy benchmark.
> 
> In this case, the input is not a deep list, because we don't want
> to read it all onto the heap to begin with. The continuation
> passing style still works fine.
> 
> /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
> 
> 
> 
> 

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