Reading Notes #3: Ring Benchmark

I have been working my way through Joe Armstrong's Programming in Erlang. One of the exercises in chapter 8 is to write a "ring benchmark" in Erlang and any other language, compare the results and publish them.

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

Here are my benchmarks written in Erlang and Python respectively. I have presumed that the author meant sending messages synchronously; i.e. a message has to go around the whole ring before the next can be sent.

The Erlang version was easy to write. After all the language is designed to use a processes and messages paradigm of programming. Here is the source code:
-module(pring). %% %% Exported Functions %% -export([run/2]). -ifdef(debug). -define(DEBUG(Format, Args), io:format(Format, Args)). -else. -define(DEBUG(Format, Args), void). -endif. %% %% API Functions %% run(N, M) when is_integer(N), is_integer(M), N > 0, M > 0 -> time_it(fun() -> start(N, M) end). %% %% Local Functions %% time_it(F) when is_function(F) -> statistics(runtime), statistics(wall_clock), Result = F(), {_, CPUTime} = statistics(runtime), {_, ElapsedTime} = statistics(wall_clock), {Result, CPUTime/1000, ElapsedTime/1000}. start(N, M) when is_integer(N), is_integer(M), N > 0, M > 0 -> This = self(), First = spawn(fun() -> loop(This, This) end), ?DEBUG("Creating ~p for N = ~p~n", [First, N]), Last = create(First, First, N - 1), First ! {realign, First, Last}, First ! {relay, message, M, This}, receive {done, message} -> N * M end. create(First, Previous, N) when is_pid(First), is_pid(Previous), is_integer(N), N > 0 -> Pid = spawn(fun() -> loop(First, Previous) end), ?DEBUG("Creating ~p for N = ~p~n", [Pid, N]), create(First, Pid, N - 1); create(First, Previous, 0) when is_pid(First), is_pid(Previous) -> Previous. send_relay_message(Target, Message, M, ReportBack) when is_pid(Target), is_integer(M), is_pid(ReportBack) -> ?DEBUG("~p => ~p (M = ~p) ~n", [self(), Target, M + 1]), Target ! {relay, Message, M, ReportBack}. loop(First, Previous) when is_pid(First), is_pid(Previous) -> This = self(), receive {realign, NewFirst, NewPrevious} when is_pid(NewFirst), is_pid(NewPrevious) -> ?DEBUG("I am ~p Realigning: First ~p to ~p, Previous ~p to ~p~n", [This, First, NewFirst, Previous, NewPrevious]), loop(NewFirst, NewPrevious); {relay, Message, M, ReportBack} when is_integer(M), is_pid(ReportBack), This =:= First, M > 0 -> send_relay_message(Previous, Message, M - 1, ReportBack), loop(First, Previous); {relay, Message, M, ReportBack} when is_integer(M), is_pid(ReportBack), This =:= First, M =:= 0 -> ?DEBUG("I am ~p All rounds of relay over~n", [This]), ReportBack ! {done, Message}, void; {relay, Message, M, ReportBack} when is_integer(M), is_pid(ReportBack), This =/= First, M > 0 -> send_relay_message(Previous, Message, M, ReportBack), loop(First, Previous); {relay, Message, M, ReportBack} when is_integer(M), is_pid(ReportBack), This =/= First, M =:= 0 -> send_relay_message(Previous, Message, M, ReportBack), void; _Other -> ?DEBUG("I am ~p I don't understand ~p~n", [This, _Other]), loop(First, Previous) end.
I wrote the "other programming language" version in Python. The benchmark code makes use of Python's multiprocessing module (available in version 2.6 and above). Since I couldn't find any Erlang-style way to directly send a message to a process I chose to use a set of Queue objects to accomplish message passing. Each process has access to two queues - an "in" queue to receive messages and an "out" queue to relay them to the next process in the ring. Each process' "out" queue serves as the "in" for the next. After constructing N - 1 processes, a "plug" process is created to complete the process ring.
from multiprocessing import Process, Pipe, Queue import os, sys, argparse, time def create(first, target, in_queue, n): if n == 0: return in_queue out_queue = Queue() process = Process(target = target, args = (first, in_queue, out_queue,)) process.start() return create(first, target, out_queue, n - 1) def send_relay_message(queue, message, m, sender): queue.put(('relay', message, m,)) def loop(first, in_queue, out_queue): this = os.getpid() while True: input_data = in_queue.get() message_type = input_data[0] if message_type == 'realign': new_first = input_data[1] first = new_first elif message_type == 'relay': (message, m) = input_data[1:] if (this == first) and (m > 0): send_relay_message(out_queue, message, m - 1, this) elif (this == first) and (m == 0): return elif (this != first) and (m > 0): send_relay_message(out_queue, message, m, this) elif (this != first) and (m == 0): send_relay_message(out_queue, message, m, this) return else: print "I am %s. I do not understand %s" % (this, input_data) if __name__ == '__main__': parser = argparse.ArgumentParser(description = 'Run an N * M ring benchmark.') parser.add_argument('-n', '--processes', help ='Number of Processes') parser.add_argument('-m', '--messages', help = 'Number of Messages') args = parser.parse_args(sys.argv[1:] or []) n, m = map(int, (args.processes, args.messages)) start = time.time() this = os.getpid() first_in_queue = Queue() first_out_queue = Queue() first = Process(target = loop, args = [this, first_in_queue, first_out_queue]) first.start() last_out_queue = create(first.pid, loop, first_out_queue, n - 2) plug = Process(target = loop, args = [first, last_out_queue, first_in_queue]) plug.start() first_in_queue.put(('realign', first.pid)) first_in_queue.put(('relay', 'hello', m)) first.join() plug.join() end = time.time() print (end - start)
I am not entirely convinced that Python's processes are the equivalent of Erlang ones. Certainly threads are not the answer given their use of shared memory. Perhaps the difficulty in creating lightweight, shared-nothing processes in other languages is what the author wanted to illustrate using the example.

The results are shown below. The program was executed on a machine with a dual core Pentium, 2GB memory and running Ubuntu Jaunty.

Please note that:

• I could not increase the number of Python processes to the order of 1000 (10^3). When I tried to do this the program crashed with a number of errors.
• I got a curious QueueFeederThread exception when I executed the process for N = 100, M = 10000.

N	M	N * M	(Wall) Time in seconds
			Erlang	Python
10	10	10^2	0.0	0.0732
10	100	10^3	0.003	0.1795
100	100	10^4	0.036	2.3976
100	1000	10^5	0.242	12.2252
1000	1000	10^6	1.877	-
1000	10000	10^7	18.593	-
10000	10000	10^8	197.477	-

Reading Notes #2: Passing functions as arguments to higher order functions

Does Erlang allow you to pass functions (not "funs" or anonymous functions) as arguments to higher order functions? I was under the impression that it doesn't. To find out I tweeted a question about the same. After looking at the answers I decided to rephrase the question with the help of a concrete example. Here it goes:

Step 1: Define a function add_one in a module named test.
% test.erl -module(test). -export([add_one/1]). add_one(X) -> X + 1.
Step 2: Start the erlang shell and try to use this function.
1> c(test). {ok,test} 2> test:add_one(2). 3 3> lists:map(test:add_one, [1, 2, 3]). * 1: illegal expression 4> lists:map(fun(X) -> test:add_one(X) end, [1, 2, 3]). [2,3,4] 5> lists:map(fun(X) -> X + 1 end, [1, 2, 3]). [2,3,4] 6>
As you can see I have tried three different combinations. Line #3 shows a call to the higher order function lists:map passing in the qualified name of the add_one function as first argument. The shell throws an error.

In Line #4 I wrap test:add_one inside a fun and it works.

In Line #5 I replicate the code of add_one inside an anonymous fun and everything works fine.

Contrast this with say, Python.

Definition:
def add_one(x): return x + 1
Usage:
>>> from test import add_one >>> map(add_one, [1, 2, 3]) [2, 3, 4] >>>
Now I'll repeat the question: Does Erlang allow you to pass functions (not "funs" or anonymous functions) as arguments to higher order functions? Or am I missing something?

Please share your thoughts in the comments.

Update #1:
Got an answer. There is a way to do it. It still involves using the fun keyword. 1> c(test). {ok,test} 2> lists:map(fun test:add_one/1, [1, 2, 3]). [2,3,4] 3>
Update #2:
Got another answer which does *not* use fun. The syntax is just a little different. Thanks to Justin Sheehy. 1> c(test). {ok,test} 2> lists:map({test,add_one}, [1, 2, 3]). [2,3,4] 3>

Reading Notes #1

I have been reading Joe Armstrong's paper "Making reliable distributed systems in the presence of software errors" and making notes as I go. In chapter 3 the author gives examples of how Erlang handles higher order functions. One of them is a "generator" function.
1> Adder = fun(X) -> fun(Y) -> X + Y end end. #Fun<erl_eval.5.123085357> 2> Adder10 = Adder(10). #Fun<erl_eval.5.123085357> 3> Adder(10). 15
Line 1 defines an Adder that returns another function with X bound to the input to Adder. In line 2 we create a specific adder - in this case a function that adds 10 to its input. I think line 3 was meant to show how the specific adder created in line 2 could be invoked. If Adder10 were to be called with 5 as argument it would return 15. Instead Adder is invoked again and the result shown is not correct as Adder(10) would return a generator, not 15. I think the snippet can be modified thus:
1> Adder = fun(X) -> fun(Y) -> X + Y end end. #Fun<erl_eval.6.49591080> 2> Adder10 = Adder(10). #Fun<erl_eval.6.49591080> 3> Adder10(5). 15