[erlang-questions] about tail-recursive

Pierpaolo Bernardi olopierpa@REDACTED
Wed Apr 16 12:23:57 CEST 2008


On 16 Apr 2008 11:27:48 +0200, Bjorn Gustavsson <bjorn@REDACTED> wrote:

>  The tail-recursive version would not consume any stack, but it would have to
>  build a list in reverse order, which it would have to reverse by calling lists:reverse/1.
>  The stack space and the list consumes exactly the same amount of memory (in R12B).
>
>  See
>
>  http://www.erlang.org/doc/efficiency_guide/myths.html#2.3

BTW, the efficiency guide says:

"It depends. On Solaris/Sparc, the body-recursive function seems to be
slightly faster, even for lists with very many elements. On the x86
architecture, tail-recursion was up to about 30 percent faster."

In this case I found lists:map to be slightly faster than my tail recursive
map on a pentium M760 (centrino, single core, 2Ghz, slow bus)

Any explanation?

Cheers
P.

======

Eshell V5.6.2  (abort with ^G)

33> testmap:test(1000000).
{{stdlib,94000},{tailrec,172000}}
34> testmap:test(1000000).
{{stdlib,203000},{tailrec,282000}}
35> testmap:test(1000000).
{{stdlib,141000},{tailrec,187000}}
36> testmap:test(1000000).
{{stdlib,125000},{tailrec,156000}}
37> testmap:test(1000000).
{{stdlib,141000},{tailrec,156000}}

Code:
====

-module(testmap).

-compile(export_all).

%% A tail recursive version of map
trmap(Fun, List) ->
    trmap(Fun, List, []).

trmap(_Fun, [], Acc) ->
    lists:reverse(Acc);
trmap(Fun, [A|Z], Acc) ->
    trmap(Fun, Z, [Fun(A)|Acc]).

test(N) ->
    List = lists:duplicate(N, foo),
    T0 = now(),
    _List1 = lists:map(fun(X)-> X end, List),
    T1 = now(),
    _List2 = trmap(fun(X)-> X end, List),
    T2 = now(),
    { { stdlib, timer:now_diff(T1, T0)},
      { tailrec, timer:now_diff(T2, T1)}
     }.

%% EOF



More information about the erlang-questions mailing list