Tuesday, January 19, 2010

Erlang process mailbox performance

I came across this performance issue in Erlang while doing the pattern matching against the mailbox [a.k.a. selective message processing]. Here is the orignal code:

-module (perf).

-export( [start/0] ).

start() ->
S = erlang:now(),
Pids = spawn_n(fun test/1, 10000, []),
E = erlang:now(),
io:format( "Total time: ~p~n", [timer:now_diff(E, S)/1000] ).

spawn_n(_F, 0, Acc) -> Acc;
spawn_n(F, N, Acc) ->
Me = self(),
Pid = spawn(fun() -> F(Me) end),
spawn_n(F, N-1, [Pid|Acc]).

test(Pid) -> Pid ! {self(), ok}.

wait([]) -> ok;
wait([Pid|Pids]) ->
receive {Pid, ok} -> ok end,

Run time for perf:start() was 1.3 seconds

Erlang (BEAM) emulator version 5.6.5 [source] [smp:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.6.5 (abort with ^G)
1> perf:start().
Total time: 1368.038

Now I changed wait(Pids) to wait(lists:reverse(Pids)). After this change, run time for perf:start() was 83 milliseconds.

1> perf:start().
Total time: 83.037

15x improvement just by changing the way mailbox scan is done.

Little things like this are usually overlooked and the language is blamed for the performance issues.


ciprian.craciun@gmail.com said...

The issue you are describing in related to the following:
* as you start the processes, they get scheduled in the order they're started; thus the first one starts and sends a message, then the second one, etc.;
* as you start processes you accumulate them in reverse order;
* thus when you do a receive you're actually waiting for the last process to send you a message, and so you postpone the other messages that have already been received;
* in the second case (where you reverse the accumulating list), you wait for the first process to send, then you wait for the second, etc.; thus you receive messages in "parallel" as the workers are scheduled;

So the performance penalty you observe is justified.

Dude Mangalore said...

Thanx for the comments...

You are right.. This is the exact point I wanted to make here. I have heard some people saying Erlang is slow.. and it turned out that they found it slow because they were not using it in the right way..

One more thing here to note is that, the time complexity of first method is O(N + (N-1) + (N-2)....+1). In the 2nd method, the time complexity is reduced to O(N).

Book Promotion