Erlang, Termite and a Blog

In his soon-to-be-published book, Joe Armstrong proposes the following exercise:

Write a ring benchmark. Create N processes in a ring. Send a message round the ring M times. So that a total of N * M messages get sent. Time how long this takes for different values of N and M.

and he adds

Write a similar program in some other programming language you are familiar with. Compare the results. Write a Blog and publish the results on the Internet!

Since i happen to be learning Erlang and, besides, know of another programming language providing Erlang-like primitives, i thought i’d take Joe’s bait and give you a little taste of how Erlang feels to a newcomer.

This is my implementation of the ring in Erlang. If you’re an Erlang hacker, be prepared to be scared: this is my first longer-than-ten-lines program–but, please, do not hesitate to criticize it as deserved!.

-module(ring).
-export([make_ring/2]).

make_ring(N, M) -> spawn(fun() -> sender(N, M) end).

sender(N, M) ->
    FirstPid = self(),
    NextPid = spawn(fun() -> tunnel(N, 2, FirstPid) end),
    statistics(runtime),
    statistics(wall_clock),
    do_times(M, 0, fun(I) -> NextPid ! I end),
    NextPid ! done,
    receive done -> done end,
    {_, Time1} = statistics(runtime),
    {_, Time2} = statistics(wall_clock),
    U1 = Time1 * 1000,
    U2 = Time2 * 1000,
    io:format("Total time=~p (~p) microseconds~n", [U1, U2]).

do_times(N, N, _) -> done;
do_times(N, J, Fun) -> Fun(J), do_times(N, J+1, Fun).

tunnel(N, N, FirstPid) -> tunnel(FirstPid);
tunnel(N, J, FirstPid) -> 
     tunnel(spawn(fun() -> tunnel(N, J+1, FirstPid) end)).

tunnel(Pid) ->
    receive
        done -> Pid ! done;
        Any -> Pid ! Any, tunnel(Pid)
    end.

Here you can see some of Erlang’s niceties: first class, anonymous functions (using the fun() -> [body] end lambda constructor); function definition by cases (a la Haskell: guards are also admitted) and pattern matching; message mailboxes using receive (also using pattern matching) and the send operator !; easy process creation with spawn; and the pretty no-frills but extremely convenient module system (one would write ring:make_ring(A,B) to call our ring launcher: the Erlang shell will find and load the ring module as long as the file is in the load path). You may also have noticed that there is no variable mutations, or that lower case atoms (like done) are automatically interpreted as symbols. Tuples also make an appearance: they are constructed using braces (as in {_, Time1}) and you assign values to its components, again, by pattern matching. And, oh, those tail recursive calls to tunnel and do_times are properly optimized by the Erlang interpreter.

Although the above is just a subset of the language’s features, it’s enough to show why i like Erlang: it reminds me of Scheme in many ways, while borrowing some interesting bits from ML languages and even Prolog. On top of it, it fulfills Alan Perlis desideratum on programming languages: it changes the way you think, as recently noticed by one of my favourite bloggers. (It is also worth mentioning that Erlang comes charged with a pretty nice library, excellently documented, that has recently gained a slick search interface.)

But back to Joe’s problem. As it happens, there’s ‘one other language i’m familiar with’ (Scheme) that provides and Erlang-like library (Gambit‘s Termite), and rewriting the program was a breeze:

(define (make-ring n m) (spawn (lambda () (sender n m))))

(define (sender n m)
  (define (display-time msg start end)
    (display (list msg (- end start)))
    (newline))
  (let* ((fist-pid (self))
         (next-pid (spawn (lambda () (tunnel n 2 fist-pid))))
         (rt (real-time))
         (ct (cpu-time)))
    (let loop ((m m))
      (cond ((= 0 m)
             (! next-pid 'done)
             (recv ('done
                    (let ((nct (cpu-time))
                          (nrt (real-time)))
                      (display-time "CPU time: " ct nct)
                      (display-time "Real time: " rt nrt)))))
            (else (! next-pid m)
                  (loop (- m 1)))))))

(define (tunnel n j first-pid)
  (cond ((= n j) (send-recv first-pid))
        (else (send-recv (spawn (lambda () 
                                   (tunnel n (+ 1 j) first-pid)))))))

(define (send-recv pid)
  (recv
   ('done (! pid 'done))
   (x (! pid x) (send-recv pid))))

If you’re a Schemer, you’ll readily understand the code above, which uses the same primitives as Erlang: !, recv (since receive is taken in Gambit) and spawn.

What about the comparison? Well, i love Scheme and, to my biased eyes, Gambit’s version is more beautiful. So let’s move to something that is not in the eye of the beholder: speed. Running ring:make_ring(5000, 1000) in my laptop gives the following output:

Total time=970000 (1520000) microseconds

while typing (make-ring 5000 1000) at the Gambit’s interpreter prompt yields:

CPU time: 19.442507999999997 secs
Real time: 19.780327081680298 secs

So, the Scheme interpreter is about 20 times slower than the Erlang interpreter (the factor seems to be more or less constant when you change the number of processes or messages sent). But Gambit has a secret weapon: it’s a Scheme to C compiler (why, it’s actually called Gambit-C!). So I compiled my program and ran it, with the following result:

CPU time: 2.3031090000000005 secs
Real time: 2.3484270572662354 secs

The interpreted Erlang code is still more than twice quicker than the compiled C code. Not bad: the more i look at that Erlang program, the more beautiful it looks!

Of course, this is just a toy benchmark which says nearly nothing about the real performance of either Erlang or Termite. I just thought it could be a way of whetting your appetite and get you started in these to systems that i’m just discovering. Googling for Erlang and Termite will direct you to several recent blog entries discussing them and helping you to join the fun, but, lest you miss it, let me recommend this Termite mini-tutorial by Marc Feeley.

And again, if you discover any of the silly things i could do better in the programs above, please leave a comment: i’m just learning!

About these ads

14 Responses to “Erlang, Termite and a Blog”

  1. Serguey Zefirov Says:

    While comparing different languages for high-level hardware modelling I was required to create a benchmark code for similar problem.

    I was writing on Haskell against our Erlang competitor. And it was real royal pain.

    Just because Haskell refuses to execute such a useless code. All my execution times was 0.0 seconds. ;)

  2. Alaric Snell-Pym Says:

    What I wonder is where the speed difference comes from. Some profiling would be good :-)

    Issues I’d expect are:

    1) I bet the Erlang networking primitives have been fine-tuned for performance in ways that Termite’s haven’t

    2) Being a pure functional language, Erlang can probably perform garbage collection more efficiently than Scheme

    3) I don’t know much about Erlang implementation details, but it’d be interesting to see how much this is a matter of ‘better implementation’ versus ‘inherent limitations of the language’. Because if it’s the former rather than the latter, it means the Bigloo folks need to do some work to catch up, and the Erlang source might be full of useful ideas for them. But if it’s the latter, then it might actually influence the long-term choice of languages…

  3. schemeway Says:

    Nice post!

    Add the following lines at the beginning of the Scheme program and you will get another factor of 2 speedup.

    (declare
    (standard-bindings)
    (fixum)
    (block)
    (not safe))

  4. Kimmy Says:

    How about testing against a Lua version?

  5. Ben Kavanagh Says:

    Here is a slightly different implementation. Where a master node sends one message and the message traverses M times without having to manage each round. I think it’s more in the spirit of the problem definition.

    -module(ring).
    -export([go/2]).

    go(N, M) ->
    FPid = spawn(fun() -> initfirst() end),
    SPid = spawn(fun() -> initrest(N, 2, M, FPid) end),
    register(master, self()),
    FPid ! {start, SPid, M, hello},
    wait_done(FPid).

    wait_done(FPid) ->
    receive
    {finished, FPid} -> unregister(master)
    end.

    initfirst() ->
    receive
    {start, NextP, M, Msg} ->
    NextP ! {Msg},
    loop(M, NextP, self())
    end.

    initrest(N, N, M, FPid) -> loop (M, FPid, FPid);
    initrest(N, J, M, FPid) ->
    NextId = spawn(fun()->initrest(N, J+1, M, FPid) end),
    loop (M, NextId, FPid).

    loop(M, NextP, FPid) when M > 0 ->
    receive
    {Msg} ->
    NextP!{Msg}
    end,
    loop(M-1, NextP, FPid);
    loop(0, _, FPid) when FPid == self() -> master!{finished, self()};
    loop(0, _, _) -> true.

  6. jao Says:

    schemeway: maybe i’m missing something, but adding your suggested declaration to the top of the file and recompiling has virtually no effect on the run times…

  7. Me Says:

    Ok, and so you don’t cheat, do this with multiple CPUs or on multiple machines, so the message actually has to leave the process (OS process, not Erlang process). I’d like to know how the numbers are in that case.

    Otherwise, it’s not really fair towards platforms that use OS threads, because OS threads have clear disadvantages, but allow sharing the load over multiple CPUs.

  8. jao Says:

    Me: FWIW, the tests above ran on a Core Duo, and both Erlang and Gambit (both interpreted and compiled) are using both CPUs (I’ve checked).

  9. Top Posts « WordPress.com Says:

    […] Erlang, Termite and a Blog In his soon-to-be-published book, Joe Armstrong proposes the following exercise: […]

  10. links for 2007-05-16 « Bloggitation Says:

    […] Erlang, Termite and a Blog (tags: erlang programming scheme) […]

  11. iWantToKeepAnon Says:

    @Evoreal Team,

    Care to back that up w/ code? It is certainly possible, even likely. But you need to do it w/ processes (not threads). And you need to define message passing. Using shared memory or mapped memory probably doesn’t count. TCP/IP is probably a must using ASN.1 or UBF over XML is prefered.

    Write us up some code and show us the results! Then show us the number of lines of code you wrote including the ASN.1 or UBF functions. Then compare the time and effort it took. Take the ratio of you LOCs vs. 31 in ring.erl.

    Turing proved that any problem solved in 1 language can be solved in another (or something like that) … but it doesn’t mean you *should* solve certain problems in YOUR language. There is a freedom of choice.

  12. indian Says:

    in his soon-to-be-published book, joe armstrong proposes the following exercise:.
    how about testing against a lua version.
    Erlang, Termite and a Blog « programming musings
    « three questionsa personal note »erlang, termite and a blog


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

Follow

Get every new post delivered to your Inbox.

Join 42 other followers

%d bloggers like this: