efficiency, deep lists

Ulf Wiger etxuwig@REDACTED
Tue Oct 2 17:40:07 CEST 2001

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

[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) ->
      fun(K, Acc) ->
              get_vals(K) ++ Acc
      end, [], Keys).

get_vals(Key) ->
    [{_, Points}] = ets:lookup(mytab, Key),
      fun({point, Value}) ->

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


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],
      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.

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