[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