17 December 2009

Playing with Erlang (3): concurrency

In this post I'll show how to write a multithreaded erlang program where each child process will calculate if a given number is a Prime Number (not rocket science, a brute force algorithm will be used).

First this erlang module is called 'prime':

-module(prime).

The method named 'test' with no argument is public
-export([test/0]).

The method named 'start' creates a new thread for the function 'loop'. It returns the ID of this new thread.
start()-> spawn(fun loop/0).

The 'loop' method waits for a message in a child process. When it receives a message matching the pattern '{ _From, {prime,Number},Start }' it invokes the recursive function is_prime and prints the result:
loop()->
receive
{ _From, {prime,Number},Start }->
io:format("result=~p\n Process-ID=~p\n Duration=~p ~n",[
is_prime(2,Number),
self(),
timer:now_diff(now(),Start)/1.0e6
])
;
{_From,_Other} ->
io:format("Booomm~n",[])
end.

The function 'is_prime' is a simple-and-stupid recursive method testing if a number is a prime where we search if the numbers 'Div' lower than 'N' have a modulus of 'Number/Div=0':
is_prime(Div,Number)->
if
Div =:= Number -> {result,{number,Number},{prime,true}};
Number rem Div =:= 0 -> {result,{number,Number},{prime,false}};
true-> is_prime(Div+1,Number)
end.

The method named 'rpc' sends the ID of the current process, the prime number and the current system time to the child process:
rpc(Pid,Request)->
Pid ! { self(), Request , now()}
.

The 'test' method creates a list 'NUMS' of numbers. For each number N in this list the function prime:start is called and it returns a new thread-ID. This Thread-ID is sent with 'N' to the function rpc.
test()->
NUMS=[111, 197951153,197951154,102950143,65537,3,7,8,12],
lists:foreach( fun(N)-> Pid= start(), rpc(Pid,{prime,N}) end, NUMS )
.



Your browser does not support the <CANVAS> element !


All in one, here is the full code:
-module(prime).
-export([test/0]).

start()-> spawn(fun loop/0).

rpc(Pid,Request)->
Pid ! { self(), Request , now()}
.

loop()->
receive
{ _From, {prime,Number},Start }->
io:format("result=~p\n Process-ID=~p\n Duration=~p ~n",[
is_prime(2,Number),
self(),
timer:now_diff(now(),Start)/1.0e6
])
;
{_From,_Other} ->
io:format("Booomm~n",[])
end.

is_prime(Div,Number)->
if
Div =:= Number -> {result,{number,Number},{prime,true}};
Number rem Div =:= 0 -> {result,{number,Number},{prime,false}};
true-> is_prime(Div+1,Number)
end.


test()->
NUMS=[111, 197951153,197951154,102950143,65537,3,7,8,12],
lists:foreach( fun(N)-> Pid= start(), rpc(Pid,{prime,N}) end, NUMS )
.

Compiling:
erlc prime.erl

Running:
erl -noshell -s prime test

Result (as you can see, the biggest prime appears at the end of the list because it took more time for the calculation):
result={result,{number,65537},{prime,true}}
Process-ID=<0.34.0>
Duration=0.006522
result={result,{number,111},{prime,false}}
Process-ID=<0.30.0>
Duration=7.6e-5
result={result,{number,197951154},{prime,false}}
Process-ID=<0.32.0>
Duration=4.57e-4
result={result,{number,3},{prime,true}}
Process-ID=<0.35.0>
Duration=7.25e-4
result={result,{number,7},{prime,true}}
Process-ID=<0.36.0>
Duration=7.23e-4
result={result,{number,8},{prime,false}}
Process-ID=<0.37.0>
Duration=7.22e-4
result={result,{number,12},{prime,false}}
Process-ID=<0.38.0>
Duration=7.2e-4
result={result,{number,102950143},{prime,true}}
Process-ID=<0.33.0>
Duration=8.856508
result={result,{number,197951153},{prime,true}}
Process-ID=<0.31.0>
Duration=49.51542

That's it.
Pierre.

1 comment:

Angel Alvarez said...

Hi

Here my try based on Oneill's
paper: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

% "Genuine" Erathostenes sieve in erlang
% based on http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
% 2009 Angel Alvarez
%

Thsi is a sieve where the cells are processes that are created in a lazy fashion as needed, and avoid duplicate crossing off of multiples.

You can reach me at erlang-questions list...

Regards Angel

-module(multi_erathostenes).
-author("angel at uah.es").
-export([start/1,worker/1]).

-record(cell, {prime,upperbound}).


compare(X,Y) when X > Y -> greater;
compare(X,Y) when X < Y -> smaller;
compare(_,_) -> equal.


worker(#cell{prime=Prime,upperbound=UpperBound} = Cell)->
receive
{test,Number,ParentPID} ->
ParentPID ! ok,
case compare(Number,UpperBound) of
equal ->
%% io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
worker( Cell#cell{upperbound= UpperBound + Prime});
smaller ->
io:format("[last_worker] Found Prime: ~w~n",[Number]),
%% io:format("~w~n",[Prime]),
NextPID =spawn(?MODULE,worker,[#cell{ prime= Number,upperbound=Number*Number}]),
worker(Cell,NextPID)
end;
stop ->
%% io:format("~n",[])
noop
end.

worker(#cell{prime=Prime,upperbound=UpperBound} = Cell,NextPID) ->
receive
{test,Number,ParentPID} ->
ParentPID ! ok,
case compare(Number,UpperBound) of
equal ->
%% io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
worker( Cell#cell{upperbound= UpperBound + Prime},NextPID);
smaller ->
%% io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
NextPID ! {test,Number,self()},
receive
ok -> ok
end,
worker(Cell,NextPID);
greater ->
%% io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
NextPID ! {test,Number,self()},
receive
ok -> ok
end,
worker( Cell#cell{upperbound= UpperBound + Prime},NextPID)
end;
stop ->
NextPID ! stop,
noop
end.

start([N|_StrCommand]) when is_list(N) ->
start(list_to_integer(N));

start(N) ->
OnePID=spawn(?MODULE,worker,[#cell{prime=2,upperbound=4}]),
%% io:format("~w~n",[2]),
cicle(3,N,OnePID).

cicle(Last,Last,Worker) ->
Worker ! stop;
cicle(Current,Last,Worker) ->
Worker ! {test,Current,self()},
receive
ok -> ok
end,
cicle(Current+1,Last,Worker).