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

```