efficiency, deep lists

[Ulf Wiger]

On Tue, 2 Oct 2001, Richard Carlsson wrote:

>This was interesting, so I did some benchmarks of my own. The
>results seem to have little variance, and I think they can be
>trusted:

[solid-looking numbers indicating that CPS is not too bad]


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.


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

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