(MM#2 algorithm)-module(c8p2m_t2).
-export([c8_ping/2,c8_loop/1,c8_cntrl/1
]).
%%-----------------------------* start CREATE the RING *-----------------------------------------------
c8_ping(N,M) when is_integer(N), is_integer(M), N > 1, M > 1 ->
Max = erlang:system_info(process_limit),
StartP = spawn(?MODULE, c8_cntrl, [[self(), M]]), %%--- START process pid of the RING
case (N > Max) of
true ->
EndP = c8_for(2, Max, StartP); %%--- END process pid of the RING
false ->
EndP = c8_for(2, N, StartP) %%--- END process pid of the RING
end,
StartP ! EndP, %%--- Initiate the ping process
io:format(" Max number of processes:~p/Ring size:~p/Number of circles:~p~n", [Max,N,M]),
io:format(" Total message count:~p~n", [N*M]).
%%-----------------------------* end CREATE the RING *-------------------------------------------------
%%-----------------------------* start Regular RING PROCESS *------------------------------------------
c8_loop(NextP)->
receive
{ping,M}->
if
M > 0 ->
NextP ! {ping,M}, %%--- ping the message to the next process!
c8_loop(NextP);
true ->
NextP ! {ping,0} %%--- ping to the next process to die!
end
end.
%%-----------------------------* end Regular RING PROCESS *--------------------------------------------
%%-----------------------------* start Control RING PROCESS *------------------------------------------
c8_cntrl([NextP,M])->
receive
{ping,Cnt} ->
if
Cnt > 0 -> %%--- Start next circle if Cnt > 0!
NextP ! {ping,Cnt-1}, %%--- ping to the next process!
c8_cntrl([NextP,Cnt-1]);
true ->
{_,E_time} = statistics(wall_clock), %%--- calculate ping the ring stats!
io:format(" Total elapsed time: ~p seconds~n", [E_time/1000]),
NextP ! {ping,0} %%--- ping the next process to die!
end;
EndP ->
statistics(wall_clock), %%--- Start elapsed time measurements
EndP ! {ping,M}, %%--- Start the first ping!
c8_cntrl([EndP,M-1]) %%--- FIRST time: close the RING (StartP <-> EndP)!
%% REPLACE Erlang Shell Pid (the start
%% of the ring) served as a placeholder.
end.
%%-----------------------------* end Control RING PROCESS *--------------------------------------------
%%-----------------------------* start HELPER FUNCTIONS *----------------------------------------------
c8_for(N, N, P) -> P;
c8_for(I, N, P) ->
c8_for(I+1, N, spawn(?MODULE, c8_loop, [P])).
%%-----------------------------* end HELPER FUNCTIONS *------------------------------------------------
Sunday, May 3, 2009
Programming Erlang - Exercise 8.11.2 MM#1 Code
(MM#1 algorithm)-module(c8p2m_t1).
-export([c8_ping/2,c8_loop/1
]).
%%-----------------------------* CREATE the RING *--------------------------------------------------------
c8_ping(N,M) when is_integer(N), is_integer(M), N > 1 ->
Max = erlang:system_info(process_limit),
TotalMsgCnt = N*M,
StartP = spawn(?MODULE, c8_loop, [[self(), TotalMsgCnt]]), %%--- START process pid of the RING
case (N > Max) of
true ->
EndP = c8_for(1, Max, StartP, TotalMsgCnt ); %%--- END process pid of the RING
false ->
EndP = c8_for(1, N, StartP, TotalMsgCnt) %%--- END process pid of the RING
end,
StartP ! EndP, %%--- Initiate the ping process
io:format(" Max number of processes: ~p / Ring size: ~p processes / Number of circles: ~p~n", [Max,N,M]).
%%-----------------------------* CREATE the RING *--------------------------------------------------------
%%-----------------------------* RING PROCESS *-----------------------------------------------------------
c8_loop([NextPid,TotalMsgCount])->
receive
{ping,CurrentMsgCount}-> %%--- Circle the RING until the total message count is reached!
case (CurrentMsgCount+1) > TotalMsgCount of
true ->
{_,E_time} = statistics(wall_clock),
io:format(" Circling \"ping\" ~p times from process to process in the ring took ~p seconds~n", [CurrentMsgCount, E_time/1000]),
io:format(" Average ping message elapsed time:~p in miliseconds~n", [E_time/CurrentMsgCount]),
NextPid ! die; %%--- housekeeping - start killing all ring processes!
false ->
NextPid ! {ping,CurrentMsgCount+1} %%--- ping the message to the next process in the ring!
end,
c8_loop([NextPid,TotalMsgCount]);
die -> %%--- kill the ring process!
case erlang:is_process_alive(NextPid) of
true ->
NextPid ! die,
c8_flush_buff(),
void;
false ->
c8_flush_buff(),
void,
io:format("* Housekeeping complete: ALL processes assigned to the ring are destroyed! * ~n"),
io:format("__________________________________________________________________________________________~n")
end;
EndP -> %%--- FIRST time to close the RING: link StartP with EndP !
statistics(wall_clock), %%--- Start elapsed time measurements
EndP ! {ping,1}, %%--- Start the first ping around the ring!
c8_loop([EndP,TotalMsgCount])
end.
%%-----------------------------* RING PROCESS *-----------------------------------------------------------
%%-----------------------------* start HELPER FUNCTIONS *-------------------------------------------------
c8_for(N, N, P, _TotalMsgCnt) -> P;
c8_for(I, N, P, _TotalMsgCnt) -> c8_for(I+1, N, spawn(?MODULE, c8_loop, [[P,_TotalMsgCnt]]), _TotalMsgCnt).
c8_flush_buff()->
receive
_Any ->
c8_flush_buff()
after 0 ->
true
end.
%%-----------------------------* end HELPER FUNCTIONS *---------------------------------------------------
-export([c8_ping/2,c8_loop/1
]).
%%-----------------------------* CREATE the RING *--------------------------------------------------------
c8_ping(N,M) when is_integer(N), is_integer(M), N > 1 ->
Max = erlang:system_info(process_limit),
TotalMsgCnt = N*M,
StartP = spawn(?MODULE, c8_loop, [[self(), TotalMsgCnt]]), %%--- START process pid of the RING
case (N > Max) of
true ->
EndP = c8_for(1, Max, StartP, TotalMsgCnt ); %%--- END process pid of the RING
false ->
EndP = c8_for(1, N, StartP, TotalMsgCnt) %%--- END process pid of the RING
end,
StartP ! EndP, %%--- Initiate the ping process
io:format(" Max number of processes: ~p / Ring size: ~p processes / Number of circles: ~p~n", [Max,N,M]).
%%-----------------------------* CREATE the RING *--------------------------------------------------------
%%-----------------------------* RING PROCESS *-----------------------------------------------------------
c8_loop([NextPid,TotalMsgCount])->
receive
{ping,CurrentMsgCount}-> %%--- Circle the RING until the total message count is reached!
case (CurrentMsgCount+1) > TotalMsgCount of
true ->
{_,E_time} = statistics(wall_clock),
io:format(" Circling \"ping\" ~p times from process to process in the ring took ~p seconds~n", [CurrentMsgCount, E_time/1000]),
io:format(" Average ping message elapsed time:~p in miliseconds~n", [E_time/CurrentMsgCount]),
NextPid ! die; %%--- housekeeping - start killing all ring processes!
false ->
NextPid ! {ping,CurrentMsgCount+1} %%--- ping the message to the next process in the ring!
end,
c8_loop([NextPid,TotalMsgCount]);
die -> %%--- kill the ring process!
case erlang:is_process_alive(NextPid) of
true ->
NextPid ! die,
c8_flush_buff(),
void;
false ->
c8_flush_buff(),
void,
io:format("* Housekeeping complete: ALL processes assigned to the ring are destroyed! * ~n"),
io:format("__________________________________________________________________________________________~n")
end;
EndP -> %%--- FIRST time to close the RING: link StartP with EndP !
statistics(wall_clock), %%--- Start elapsed time measurements
EndP ! {ping,1}, %%--- Start the first ping around the ring!
c8_loop([EndP,TotalMsgCount])
end.
%%-----------------------------* RING PROCESS *-----------------------------------------------------------
%%-----------------------------* start HELPER FUNCTIONS *-------------------------------------------------
c8_for(N, N, P, _TotalMsgCnt) -> P;
c8_for(I, N, P, _TotalMsgCnt) -> c8_for(I+1, N, spawn(?MODULE, c8_loop, [[P,_TotalMsgCnt]]), _TotalMsgCnt).
c8_flush_buff()->
receive
_Any ->
c8_flush_buff()
after 0 ->
true
end.
%%-----------------------------* end HELPER FUNCTIONS *---------------------------------------------------
Programming Erlang - Exercise 8.11.2 NV Code
(NV algorithm)
-module(c8p2_t).
-export([start/2]).
start(Rounds, Size) ->
Ring = ring(Size-1, self()), %% Set up a ring of Size-1, because self() will participate.
statistics(wall_clock),
Ring ! {ping, Rounds}, %% Send the ping into the ring.
main(Ring), %% Put myself into the ring.
{_, Elapsed} = statistics(wall_clock),
io:format("Rounds: ~p / Ring size: ~p. Ringing ~p messages took ~p seconds~n", [Rounds,Size,Rounds * Size, Elapsed/1000]),
io:format("Avg ping message elapsed time: ~p miliseconds.~n", [Elapsed/(Rounds*Size)]).
%% Create a ring of specified size. Boss is the start of the ring.
ring(1, Boss) ->
spawn(fun() -> proc(1, Boss) end);
ring(N, Boss) ->
spawn(fun() -> proc(N, ring(N-1, Boss)) end).
%% Proc is a process in the ring. N is its number in the ring, Next is the next process.
proc(N, Next) ->
receive {ping, M} -> %% M is the message number.
Next ! {ping, M}, %% Propagate the message.
if
M > 1 -> proc(N, Next); %% Expect more messages.
true -> ready %% We're done.
end
end.
%% Main is similar to proc, but decrements the message number.
%% Returns when all messages have been sent.
main(Next) ->
receive
{ping, M} ->
if
M > 1 ->
Next ! {ping, M-1},
main(Next);
true -> ready
end
end.
-module(c8p2_t).
-export([start/2]).
start(Rounds, Size) ->
Ring = ring(Size-1, self()), %% Set up a ring of Size-1, because self() will participate.
statistics(wall_clock),
Ring ! {ping, Rounds}, %% Send the ping into the ring.
main(Ring), %% Put myself into the ring.
{_, Elapsed} = statistics(wall_clock),
io:format("Rounds: ~p / Ring size: ~p. Ringing ~p messages took ~p seconds~n", [Rounds,Size,Rounds * Size, Elapsed/1000]),
io:format("Avg ping message elapsed time: ~p miliseconds.~n", [Elapsed/(Rounds*Size)]).
%% Create a ring of specified size. Boss is the start of the ring.
ring(1, Boss) ->
spawn(fun() -> proc(1, Boss) end);
ring(N, Boss) ->
spawn(fun() -> proc(N, ring(N-1, Boss)) end).
%% Proc is a process in the ring. N is its number in the ring, Next is the next process.
proc(N, Next) ->
receive {ping, M} -> %% M is the message number.
Next ! {ping, M}, %% Propagate the message.
if
M > 1 -> proc(N, Next); %% Expect more messages.
true -> ready %% We're done.
end
end.
%% Main is similar to proc, but decrements the message number.
%% Returns when all messages have been sent.
main(Next) ->
receive
{ping, M} ->
if
M > 1 ->
Next ! {ping, M-1},
main(Next);
true -> ready
end
end.
Programming Erlang - Exercise 8.11.2 Benchmark Statistics
Programming Erlang - Chapter 8 Problems: BENCHMARK results
My contribution to the discussion for Programming Erlang - Chapter 8 Problems
( http://forums.pragprog.com/forums/27/topics/311 ).
Not very long ago, having some spare time, I decided to read the intriguing Joe Armstrong’s book and, after a long time, I started to do some programming completing book’s exercises. As Joe said, programming is in fact experimental discipline and without trying to do some programming one can’t understand the potential of some programming language. Why I choose Erlang I really don’t know. I stumbled on the Pragmatic Bookshelf website and I was attracted to the apparently elegant programming language and decided to give it a try. Getting more involved I completed the Chapter 8 Exercises. The result was MM#1 program ( “c8p2m_t1” ), my first version of the solution.
As I’m a kind of picky guy I started with the precise definition of a ring abstraction; according to my understanding a ring is an abstraction which is created by linking the N parallel processes so that each process is aware ONLY of its successor. Additionally, each ring process should have the quite precisely known and well defined functionality, fully controlled and created by a programmer. I have the opinion that it is not mandatory to create a ring, as the abstraction, from N IDENTICAL parallel processes (like in my first version of the code – MM#1) but for me it was the easiest way to solve the Problem 2. Following Joe’s advice to write a blog about test results, I was looking for the other published solutions, of other people who were following Joe’s advice and wanted to share their experience. That is how I spotted discussion in the Pragmatic Bookshelf website and started to analyze and compare posted solutions with my own solution to the problem, presented here as MM#1 (“c8p2m_t1”).
First solution (by Christopher Atkins) does not correctly ping the message around the ring (“Caller” in the loop/1 seems to be always Erlang shell Pid and ping doesn’t circle around the created ring of N spawned processes).
The second solution (by Nico Verwer) correctly ping a message around the ring, but the ring is not created in compliance with my definition of a ring abstraction. N-1 identical parallel processes [represented by the proc()] are linked to the control function main() [almost identical to the proc()in functionality], running as a part of the Erlang Shell, representing the ring start process in the Nico’s code. The choice of parallel processors linked in a ring is a question of freedom but, there is one important difference in Nico’s choice for the control process, violating my definition of a ring abstraction, and, according to my opinion, that represents a valid objection that Nico’s code did NOT create a valid ring abstraction. To be more specific, the Erlang Shell is a process, running in parallel with other spawned processes, but, with significantly more hidden functionality than other N-1 parallel processes. The main() function in the shell is just a small part of that complex process, enveloping quite a few system processes [ i() provides more information in that respect]. In that respect the Erlang Shell is NOT controlled by the programmer and from my point of view, can NOT be a part of the ring abstraction, which should be completely created by the programmer.
On the other side, Nico’s code gave me the idea that I can create the second version of the code MM#2 ( “c8p2m_t2” ) where I created one asymmetrical process, which has the control role in the ring.
I decided to test the efficiency of three different solutions ( Nico’s code: NV, MM#1 and MM#2) under the same controlled conditions.
Environment:
AMD Turion(tm) 64 , 1590 MHz Mobile Technology ML-28, 2GB Memory
MS XP Home Edition SP-3 with standard convoluted MS mixture of OS services with disabled internet connection, antivirus and other startup programs and Erlang (BEAM) emulator version 5.6.5.
Each experiment is using the same number of ping messages, doubling the ring size and dividing in half the number of circles in each measurement (except in the last case because of limitations regarding the max number of parallel processes).
My contribution to the discussion for Programming Erlang - Chapter 8 Problems
( http://forums.pragprog.com/forums/27/topics/311 ).
Not very long ago, having some spare time, I decided to read the intriguing Joe Armstrong’s book and, after a long time, I started to do some programming completing book’s exercises. As Joe said, programming is in fact experimental discipline and without trying to do some programming one can’t understand the potential of some programming language. Why I choose Erlang I really don’t know. I stumbled on the Pragmatic Bookshelf website and I was attracted to the apparently elegant programming language and decided to give it a try. Getting more involved I completed the Chapter 8 Exercises. The result was MM#1 program ( “c8p2m_t1” ), my first version of the solution.
As I’m a kind of picky guy I started with the precise definition of a ring abstraction; according to my understanding a ring is an abstraction which is created by linking the N parallel processes so that each process is aware ONLY of its successor. Additionally, each ring process should have the quite precisely known and well defined functionality, fully controlled and created by a programmer. I have the opinion that it is not mandatory to create a ring, as the abstraction, from N IDENTICAL parallel processes (like in my first version of the code – MM#1) but for me it was the easiest way to solve the Problem 2. Following Joe’s advice to write a blog about test results, I was looking for the other published solutions, of other people who were following Joe’s advice and wanted to share their experience. That is how I spotted discussion in the Pragmatic Bookshelf website and started to analyze and compare posted solutions with my own solution to the problem, presented here as MM#1 (“c8p2m_t1”).
First solution (by Christopher Atkins) does not correctly ping the message around the ring (“Caller” in the loop/1 seems to be always Erlang shell Pid and ping doesn’t circle around the created ring of N spawned processes).
The second solution (by Nico Verwer) correctly ping a message around the ring, but the ring is not created in compliance with my definition of a ring abstraction. N-1 identical parallel processes [represented by the proc()] are linked to the control function main() [almost identical to the proc()in functionality], running as a part of the Erlang Shell, representing the ring start process in the Nico’s code. The choice of parallel processors linked in a ring is a question of freedom but, there is one important difference in Nico’s choice for the control process, violating my definition of a ring abstraction, and, according to my opinion, that represents a valid objection that Nico’s code did NOT create a valid ring abstraction. To be more specific, the Erlang Shell is a process, running in parallel with other spawned processes, but, with significantly more hidden functionality than other N-1 parallel processes. The main() function in the shell is just a small part of that complex process, enveloping quite a few system processes [ i() provides more information in that respect]. In that respect the Erlang Shell is NOT controlled by the programmer and from my point of view, can NOT be a part of the ring abstraction, which should be completely created by the programmer.
On the other side, Nico’s code gave me the idea that I can create the second version of the code MM#2 ( “c8p2m_t2” ) where I created one asymmetrical process, which has the control role in the ring.
I decided to test the efficiency of three different solutions ( Nico’s code: NV, MM#1 and MM#2) under the same controlled conditions.
Environment:
AMD Turion(tm) 64 , 1590 MHz Mobile Technology ML-28, 2GB Memory
MS XP Home Edition SP-3 with standard convoluted MS mixture of OS services with disabled internet connection, antivirus and other startup programs and Erlang (BEAM) emulator version 5.6.5.
Each experiment is using the same number of ping messages, doubling the ring size and dividing in half the number of circles in each measurement (except in the last case because of limitations regarding the max number of parallel processes).
The representative metrics is the measured average ping message elapsed time!
The graphical results are represented in this chart:
The graphical results are represented in this chart:
Discussion of results:
The code MM#2 is showing the best results, almost 10% better than the next contender NV. The MM#1 is showing the worst results, 20% worse than NV. If we analyze the code then we can see that the main difference between the MM#2 and NV on one side, and the MM#1 on the other side, is the fact that the algorithms in the first group (MM#2 and NV) don’t perform same number of arithmetic operations (increasing the counter representing the current number of executed pings and corresponding tests to decide when to stop pinging) as the MM#1 algorithm. In the former case, this number is the number of circles where in the later case, it is the total number of pings; a difference between the MM#2 and NV, and 10% greater efficiency of the MM#2 algorithm is probably due to the difference between created control process in MM#2 case vs. Erlang shell hidden processing and its hidden overhead (the control process in the NV case). These results are increasing my preference toward the precise definition of a ring abstraction. On the other side, algorithm in the MM#1 has its advantage in its flexibility to implement a change in the behavior of the ring abstraction. Each ring process in MM#1 is and can be the control process, what is not the case in MM#2 and NV algorithms. If, for example, we want to change the program to stop after arbitrary number of ping messages, it’s easy to do that in the MM#1 case. It would be a challenge to implement that change in behavior in the MM#2 and NV, because the algorithm in these cases does not depend on a ring size, what is on the other side the main reason why these algorithms are “more efficient”. As the “efficiency” can be improved other ways (creation of the ring abstraction over independent nodes …..), and we still measure the efficiency with the average transaction response time, the clear advantage of independent “intelligent” components of a ring abstraction in MM#1 becomes attractive advantage.
Tuesday, April 21, 2009
In Search of Lost Time
Chanson d'Automne
Les saglots longs
Des violons
De l'automne
Blessent mon couer
D'une langeur
Monotone.
Tout suffocant
Et blême, quand
Sonne l'heure,
Je me souviens
Des jours anciens
Et je pleure.
Et je m'e vais
Au vent mauvais
Qui m'emporte
Deçà, delà,
Pareil à la
Feuille morte.
(Paul Verlaine)
Always rushing in the previous 25+ years of my professional life I had barely a chance to slow down and really understand what is the real meaning of these words I knew of for a long time.
"We call the time we spend doing productive but yet, it is the time we
are not doing that gives birth to our best ideas." (Tao, 11)
Michael
Les saglots longs
Des violons
De l'automne
Blessent mon couer
D'une langeur
Monotone.
Tout suffocant
Et blême, quand
Sonne l'heure,
Je me souviens
Des jours anciens
Et je pleure.
Et je m'e vais
Au vent mauvais
Qui m'emporte
Deçà, delà,
Pareil à la
Feuille morte.
(Paul Verlaine)
Always rushing in the previous 25+ years of my professional life I had barely a chance to slow down and really understand what is the real meaning of these words I knew of for a long time.
"We call the time we spend doing productive but yet, it is the time we
are not doing that gives birth to our best ideas." (Tao, 11)
At last I had the opportunity to reflect over these words and finally understand the meaning:
In the area of my professional activity, I wanted to learn something new and different form my routine job for some time (Project Management) and that is how my Erlang adventure came about; this way I will bring back the glimpse of time when I could choose to do only things I considered to be interesting and challenging.
Michael
Subscribe to:
Posts (Atom)
