[erlang-questions] Please suggest why these repeated timings increase

Isaac Gouy <>
Sat Aug 27 20:17:59 CEST 2011


Here's a tiny (somewhat silly) program - a circle of processes, removed one at a time until there's only one left.

I expect there's a simple explanation - I expect I've done something basic wrong - but repeatedly creating and reducing such a circle of processes seems to slowdown, and I'd like to understand why.

There doesn't seem to be any accumulation of zombie processes, so I'm a little puzzled what else might be going on.



$ /usr/local/src/otp_src_R14B02/bin/erlc josephus.erl

$ /usr/local/src/otp_src_R14B02/bin/erl -noshell -run josephus main

943157
2219531
3490628
4814178
6334408
7419798
8615281
9778484
11364821
12440720


-module(josephus).
-export([main/0,soldier/3,timedloop/1]).

soldier( PreviousPid, NextPid, Id ) ->
   receive
      {MainPid,countoff,Kth,K} -> 
         countoff(PreviousPid,NextPid,Id,MainPid,Kth,K);
         
      {set_previous,Pid} ->
         soldier(Pid,NextPid,Id);

      {set_next,Pid} ->
         soldier(PreviousPid,Pid,Id)
   end.


countoff( Previous, Next, Id, MainPid, Kth, K ) when Kth == K -> 
   MainPid ! {details,[Id,Previous,self(),Next]},
   if 
      Previous == self() -> 
         MainPid ! {countoff_ack,Id};

      true -> 
         Previous ! {set_next,Next},
         Next ! {set_previous,Previous},
         Next ! {MainPid,countoff,Kth,1}
   end;

countoff( Previous, Next, Id, MainPid, Kth, K ) ->    
   Next ! {MainPid,countoff,Kth,K+1},
   soldier(Previous,Next,Id).


ring(N) -> 
   ring(N,1,nil,[]).

ring(N,I,P,L) when I =< N -> 
   Pid = spawn(josephus,soldier,[P,nil,I]),
   ring(N,I+1,Pid,[Pid|L]);

ring(_,_,Last,L) ->    
   First = ring_set_next(nil,L),  
   Last ! {set_next,First},
   First ! {set_previous,Last},
   First.
 
ring_set_next(Last,[]) -> Last;
ring_set_next(P,[Pid|T]) -> 
   Pid ! {set_next,P},
   ring_set_next(Pid,T).


countoffSoldiers(N,Kth) ->
   Soldier = ring(N),
   %Soldier ! {self(),countoff,Kth,1}, % standard Josephus problem
   Soldier ! {self(),countoff,Kth,Kth},
   receive {countoff_ack,I} -> I end.

 
%-----------------------------------------------------------------------------

timedloop(0) -> ok;
timedloop(N) ->
    countoffSoldiers(40,3),
    timedloop(N-1).

repeat(_,0) -> ok;
repeat(N, Repeat) ->
    {MicroSecs,I} = timer:tc(josephus,timedloop,[N]),
    io:format("~w~n",[MicroSecs]),
    repeat(N,Repeat-1).

main() ->
    repeat(1000,10),
    halt(0).



More information about the erlang-questions mailing list