Tail Call Optimization – Erlang

Surprised to see that Erlang can be run as a script. But here, we are not going to see about escript but to test whether Erlang does the Tail call optimization or not. If it does, how much performance are we gaining on it? I’ve taken the factorial example given in the above escript page.

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname factorial -mnesia debug verbose
main([String]) ->
    try
        N = list_to_integer(String),
        F = fac(N),
        io:format("factorial ~w = ~w\n", [N,F])
    catch
        _:_ ->
            usage()
    end;
main(_) ->
    usage().

usage() ->
    io:format("usage: factorial integer\n"),
    halt(1).

fac(0) -> 1;
fac(N) -> N * fac(N-1).

And, based on that script, amending a few lines, I’ve written a tail-call-optimized version of the script factorial_tco

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname factorial_tco -mnesia debug verbose
main([String]) ->
    try
        N = list_to_integer(String),
        F = fac(N),
        io:format("factorial_tco ~w = ~w\n", [N,F])
    catch
        _:_ ->
            usage()
    end;
main(_) ->
    usage().

usage() ->
    io:format("usage: factorial_tco integer\n"),
    halt(1).

fac1(0, Acc) -> Acc;
fac1(N, Acc) -> fac1(N - 1, N * Acc).

fac(N) -> fac1(N, 1).

Using the following Perl snippet, I tested both the versions.

use Time::HiRes qw(time);
use feature qw(say);

my $t1 = time; `escript ./factorial     100000 > /dev/null`; my $t2 = time;
say "factorial     ran in ", $t2 - $t1, " seconds";

my $t3 = time; `escript ./factorial_tco 100000 > /dev/null`; my $t4 = time;
say "factorial_tco ran in ", $t4 - $t3, " seconds";

The first script takes just above 39 seconds and the second script takes just above 37 seconds. Gaining 2 seconds in calculating a factorial(100000) doesn’t look like a big difference but it looks like tail-call-optimization is being carried out by Erlang.

Cheers!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s