[Shootout-list] ring of processes

[Bengt Kleberg]

This is a multi-part message in MIME format.
--------------070100050605070604050501
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Brent Fulgham wrote:
> On 2004-10-02 10:30:04 -0700 Aaron Denney <wnoise@ofb.net> wrote:
> 
>> I have a first draft of this in Haskell.  It wasn't clear from the
>> description exactly what the master process is supposed to after sending
>> the first two messages off, and I don't fully understand what the erlang
>> versions do, so I've had it replicate what the slave processes do:
>> relay 10 high-priority messages, then 1 low priority messages, 10 times.
> 
> 
> Bengt will have to weigh in with the correct answer, but based on a 
> quick look at
> the Erlang code the first process sends the high priority message to the 

i hope that it will not come as a big surprise if i have been rethinking 
the ring test in the light of the possible solutions offered by other 
languages?

would it be possible to have a (belated) discussion about the ring? not 
what it does, but what it should do? it might mean that a lot of code 
that has been painstakingly created will have to change, so i am not 
mandating a change, just asking if it is possible.


now, to start the discussion: i would like to test how well a language 
can handle sys5 message passing ipc. i think it is a good thing (tm) 
and, despite the clunky-ness in the original implimentation, worth using.


the first (major) problem with the ring is that we have a fixed number 
of processes. it will mean that the process creation time is the only 
thing we are measuring until n gets big enough. this is not something i 
am happy with. my current idea is to use a process to message ratio that 
will assure that we are timeing the messages. in erlang we need more 
than 100 messages for each process to reach a linear corelation between 
the number of messages and the time.
other languages might need more messages.
i suggest we use a ratio of 128 messages to each process, until another 
language show us that we need to change it upwards.
in the test we create n number of process and send 128*n messages.

problem number two (minor) is the fact that we have two messages sent 
out from the master processes, but only count down 1. (i do that 
anyway). this is a little confusing and i suggest we count down with the 
number of processes sent.

then we have this here comment from the haskell code:
  - bit of data has to have someplace to go.  This is implemented by
  - giving each processes a rendezvous point (MVar a), telling
  - each where to send, and where to receive.  In this light, the "check
  - sender" is a bit silly, as the sender can only be the process that
  - also has a reference.
since the sender id is an important part of sys5 ipc (imho) i need to 
change the ring so that the sender is no longer silly. my suggestion is 
to send in both direction of the ring. this way the processes need to 
check from where the message comes to be able to send it onwards in the 
right direction.

Raymond Racine wrote:
 > I am not clear on the ring of process test.
...deleted
 > This is how the description reads to me.  But it seems odd.  Can someone
 > clarify the test?

the test is odd. i can try to clearify it. there are 3 concepts with 
sys5 ipc that i think are important and want to have in this test.

1 we can select which input we want
2 we can identify who sent the input to us
3 the sender should not block when sending to us, even if we are 
neglecting to read incomeing messages.


i am trying to devise a test that will force, or at least hobble 
alternatives to, this kind of behaviour. at the same time the test is 
supposed to make sense, ie how it does things should be sensible(*).

with the 3 items above in mind i will try and explain some of the odd 
bits of this test.

the hi/low pri messages are supposed to handle point 1 and 3.
point 3 by sending low prio messages that are ignored we try to make 
sure that the sender does not block.
point 1 by selecting hi pri messages first.

point 2 was missing, but i am proposing (far) above to add it by sending 
in both directions of the ring.


Aaron Denney wrote:
...deleted
 > Should I go ahead and post an updated Haskell version that does this?
 >

please wait a little until we can agree upon what we want. as opposed to 
what i have done. the latter is not what i want :-)


(*)the most sensible idea (to do with hi/low pri messages) was the 
suggestion that we should stop treating low prio messages if a high prio 
message turns up. this is a good thing (tm).


i have a alternative version of ring in erlang included. for those that 
think erlang is difficult i could do one in mzscheme this evening. would 
that help?


bengt

--------------070100050605070604050501
Content-Type: text/plain;
 name="ring.erl"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="ring.erl"

-module(ring).
-export([main/0, main/1]).

-define( WORK_HARD, 10).
-define( MESSAGES_PER_PROCESS, 128).


main() -> main(['2']).
main([Arg1]) ->
	Number_of_Processes = atom_to_integer( Arg1 ),
	Number_of_Messages = Number_of_Processes * ?MESSAGES_PER_PROCESS,
	Last_Message = ring( Number_of_Processes, Number_of_Messages, the_ring ),
	io:fwrite( "~w~n", [Last_Message] ),
	erlang:halt().


atom_to_integer( Atom ) ->
	erlang:list_to_integer(erlang:atom_to_list(Atom)).


ring( N, Number_of_Messages, Message ) ->
	First_Pid = erlang:self(),
	Second_Pid = erlang:spawn( fun() -> init_process(N, First_Pid, First_Pid) end ),
	send_high_and_low_prio( Second_Pid, {First_Pid, Message} ),	% 2 messages
	receive	% get hold of last pid, before main loop
	{Last_Pid, New} ->
		send_high_and_low_prio( Last_Pid, {First_Pid, New} ),	% another 2 messages
		first_process_loop( Number_of_Messages-4, New, First_Pid, Second_Pid, Last_Pid)
	end.


init_process( 0, Previous_Pid, First_Pid ) ->
	loop( Previous_Pid,  erlang:self(), First_Pid, ?WORK_HARD );
init_process( N,  Previous_Pid, First_Pid ) ->
	My_Pid = erlang:self(),
	Next_Pid = erlang:spawn( fun() -> init_process(N-1, My_Pid, First_Pid) end ),
	loop( Previous_Pid,  My_Pid, Next_Pid, ?WORK_HARD ).


% process loop for those in the ring
loop( Previous_Pid, My_Pid, Next_Pid, 0 ) ->	% hard work done
	receive
	low_priority_message ->	% get low prio messages
		loop( Previous_Pid, My_Pid, Next_Pid, 0 );
	{Previous_Pid, Message} ->
		send_high_and_low_prio( Next_Pid, {My_Pid, Message} ),
		loop( Previous_Pid,  My_Pid, Next_Pid, ?WORK_HARD );	% start hard work
	{Next_Pid, Message} ->
		send_high_and_low_prio( Previous_Pid, {My_Pid, Message} ),
		loop( Previous_Pid,  My_Pid, Next_Pid, ?WORK_HARD )	% start hard work
	end;
loop( Previous_Pid, My_Pid, Next_Pid, Work ) ->	% allow only high prio messages
	receive
	{Previous_Pid, Message} ->
		send_high_and_low_prio( Next_Pid, {My_Pid, Message} ),
		loop( Previous_Pid, My_Pid, Next_Pid, Work - 1 );
	{Next_Pid, Message} ->
		send_high_and_low_prio( Previous_Pid, {My_Pid, Message} ),
		loop( Previous_Pid, My_Pid, Next_Pid, Work - 1 )
	end.


% the controlling process loop
% at N = 0 we stop, returning the last input
first_process_loop( 0, Input, _My_Pid, _Second_Pid, _Last_Pid) ->
	Input;
first_process_loop( N, Input, My_Pid, Second_Pid, Last_Pid) ->
	receive
	low_priority_message ->	% just ignore low prio. we send with each high prio
		first_process_loop( N, Input, My_Pid, Second_Pid, Last_Pid);
	{Second_Pid, New} ->	% from beginning of ring. send to end
		send_high_and_low_prio( Last_Pid, {My_Pid, New} ),
		first_process_loop( N-2, New, My_Pid, Second_Pid, Last_Pid);
	{Last_Pid, New} ->	% from end of ring. send to beginning
		send_high_and_low_prio( Second_Pid, {My_Pid, New} ),
		first_process_loop( N-2, New, My_Pid, Second_Pid, Last_Pid)
	end.


send_high_and_low_prio( Pid, Message ) ->
	Pid ! Message,
	Pid ! low_priority_message.

--------------070100050605070604050501--