Iteration over lists

[Emil Öberg (LN/EAB)]

 That's a strange statement. There's nothing 'fair' when choosing implementation. 
 Of course I implement recursive functions as tail recursion if possible, with reverse() if the order of the list is important.
 The thing is that by using map or list comprehension you provide more information that the compiler could use to optimize the code (you know that you are iterating elements in a list). Apparently this information is ignored by the compiler and the constructs are only syntactic sugar (no flames, I know that readability is important, but in this case that doesn't give the customer more bang for the bucks). 
I was also informed that map() is implemented in a beam, not in erts, so this explains why it is slower. But still there is list comprehension. Since tail recursion is so much faster, why isn't list comprehension implemented as such, and why isn't map()? As it is now I will have to recommend designers not to use map() and absolutely not list comprehension on large lists.

	/Emil 

-----Original Message-----
From: Bjorn Gustavsson [mailto:bjorn@REDACTED] 
Sent: den 17 mars 2006 11:21
To: Emil Öberg (LN/EAB)
Cc: erlang-questions@REDACTED
Subject: Re: Iteration over lists

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