Iteration over lists

[Bjorn Gustavsson]

Your benchmark is not fair.

What you call recursion is in fact iteration expressed as tail-recursion.
Naturally it is faster.

Real recursion would look this:

recursion([H | T]) ->
    [integer_to_list(H) | recursion(T)];
recursion([]) -> [].

A list comprehension will in fact be translated to the exact same
code a the function above.

I did my own measurements, comparing my revised recursion/1 function to
your other functions (except mapping/1). I used my own framework for
benchmarking, found at my home page (http://www.erlang.se/~bjorn).
The actual code can be found at the end of this email.

I used R10B-10.

Name         Relative time
----         -------------

recursion    1.00
listcompr    1.01
revrecursion 1.12
mapfun       1.14

My framework is careful to run each new benchmark in fresh process.
Did you run each test in a new process? If not, differences in heap sizes
will seriously bias the results.

As can been seen, recursion and list comprehension are about the same.
(Since the generated code is the same, the differences are due to random
fluctuations; actually, sometimes they both ended up at 1.0.)

Using tail-recursion and then reversing is somewhat slower than either
recursion or list comprehensions. My list size was 6000. I expect that
if the lists are really huge, revrecursion will win.

Using lists:map/2 and a fun is slightly slower than recursing directly
because of the overhead of calling the fun.


Note that in older versions of OTP, list comprenhensions used to be
implemented in terms of funs. That is no longer the case. Also, funs
were much slower in older versions of OTP.

Conclusions:

1) If you can get away with producing a list with elements reversed,
   an iterative function using tail-recursion is fastest.

2) Otherwise, if your lists are up to say 10000 elements, use a list
   comprehension and be happy.  :-)

3) If your lists are larger than that, you should do some measurements
   and see if maybe tail-recursion followed by a lists:reverse/1 might
   be faster.

/Bjorn

Emil Öberg (LN/EAB) <emil.oberg@REDACTED> writes:

>  Hi.
> 
> Sitting here doing some profiling on our system and started to wonder about the performance of recursion/map/list comprehensions. Made a small test program just to compare them and got some (to me at least) surprising results. Lists:map() is nearly twice as slow as recursion, even when list is reversed, and list comprehension is even slower! Could anyone explain this? It is kind of disturbing to be forced to use messy recursion just because your code is time-critical.
> 

-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB

-module(listify_bm).
-export([benchmarks/0,
	 recursion/1,
	 revrecursion/1,
	 mapfun/1,
	 listcompr/1]).

benchmarks() ->
    {1500,
     [recursion,
      revrecursion,
      mapfun,
      listcompr]}.

recursion(Iter) ->
    recursion_1(Iter, make_list()).

recursion_1(0, _) -> ok;
recursion_1(Iter, L) ->
    recursion_2(L),
    recursion_1(Iter-1, L).

recursion_2([H | T]) ->
    [integer_to_list(H) | recursion_2(T)];
recursion_2([]) -> [].

revrecursion(Iter) ->
    revrecursion_1(Iter, make_list()).

revrecursion_1(0, _) -> ok;
revrecursion_1(Iter, L) ->
    revrecursion_2(L, []),
    revrecursion_1(Iter-1, L).

revrecursion_2([H | T], Acc) ->
    revrecursion_2(T, [integer_to_list(H) | Acc]);
revrecursion_2([], Acc) -> 
    lists:reverse(Acc).

mapfun(Iter) ->
    mapfun_1(Iter, make_list()).

mapfun_1(0, _) -> ok;
mapfun_1(Iter, L) ->
    mapfun_2(L),
    mapfun_1(Iter-1, L).

mapfun_2(L) ->
    lists:map(fun erlang:integer_to_list/1, L).

listcompr(Iter) ->
    listcompr_1(Iter, make_list()).

listcompr_1(0, _) -> ok;
listcompr_1(Iter, L) ->
    listcompr_2(L),
    listcompr_1(Iter-1, L).

listcompr_2(L) ->
    [erlang:integer_to_list(X) || X <- L].

make_list() ->
    lists:seq(1, 6000).