Re: Need some light on using Ada or not

[Brian Drummond <brian_drummond@btconnect.com>]

On Sun, 20 Feb 2011 22:47:05 +0000, Simon Wright <simon@pushface.org> wrote:

>Brian Drummond <brian_drummond@btconnect.com> writes:
>
>> the 100% overhead (on this test case) imposed by the pthread library
>> (which I think is how Gnat implements its tasking)
>
>Here (Mac OS X, GCC 4.6.0 x86_64 experimental), I tried modifying the
>Ada code to use the same tasking (threading) structure as the C GNU GCC
>#5 version. Result (I only checked with parameter 16):
>
>C:           real 5.1 user 9.0
>GNAT (orig): real 6.0 user 5.8
>GNAT (mod):  real 5.3 user 9.4
>
>(the 'user' value, which is what time(1) reports, is apparently the
>total CPU time, while the 'real' time is the elapsed time; this machine
>has 2 cores, both it seems running at about 90% in the test).

So again, there is an overhead (maybe 80%) imposed by tasking, and significant
improvements won't appear until >2 processors.

I can't be sure I'm reading the C correctly, but it looks as if it's creating a
new pthread (task) for each depth step, similar to my first attempt.

I have now decoupled the number of tasks from the problem, to simplify
experiments with different numbers of tasks, and improve load balancing.
It runs approx. 4x as fast with 4 or 8 tasks as it does with 1 task (on a 4-core
machine!), therefore only about 2x as fast as it does without tasking.

As this is my first experiment with tasking, comments are welcome (and I'd be
interested to see your version). If people think this is worth submitting to the
shootout, I'll go ahead.

- Brian

----------------------------------------------------------------
-- BinaryTrees
--
-- Ada 95 (GNAT)
--
-- Contributed by Jim Rogers
-- Tasking experiment : Brian Drummond
----------------------------------------------------------------
with Treenodes; use Treenodes;
with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Command_Line; use Ada.Command_Line;
with Ada.Characters.Latin_1; use Ada.Characters.Latin_1;

procedure Binarytrees_tasking is
   -- Change "CPUs" to control number of tasks created
   CPUs : constant Positive := 8;
   BlockSize : Positive;
   Min_Depth : constant Positive := 4;
   N : Natural := 1;
   Stretch_Tree : TreeNode;
   Long_Lived_Tree : TreeNode;
   Max_Depth : Positive;
   Stretch_Depth : Positive;
   Iteration : Positive;
   Iterations : Positive;
   Sum : Integer;
   Check : Integer;
   Depth : Natural;

   task type check_this_depth is
      entry Start(Iteration, Size : Positive; To_Depth :in Natural);
      entry Complete(Result : out Integer);
   end check_this_depth;

   task body check_this_depth is
      Check : Integer;
      Sum : Integer;
      Depth : Natural;
      First : Positive;
      Last : Positive;
      Short_Lived_Tree_1 : TreeNode;
      Short_Lived_Tree_2 : TreeNode;

   begin
      loop
         select
            accept Start(Iteration, Size : Positive; To_Depth :in Natural) do
               First := Iteration;
               Last := Iteration + Size - 1;
               Depth := To_Depth;
            end Start;
            Check := 0;
            for I in First .. Last loop
               Short_Lived_Tree_1 := Bottom_Up_Tree(Item => I, Depth => Depth);
               Short_Lived_Tree_2 := Bottom_Up_Tree(Item =>-I, Depth => Depth);
               Item_Check(Short_Lived_Tree_1, Sum);
               Check := Check + Sum;
               Item_Check(Short_Lived_Tree_2, Sum);
               Check := Check + Sum;
            end loop;
            accept Complete(Result : out Integer) do
               Result := Check;
            end Complete;
         or
            Terminate;
         end select;
      end loop;
   end check_this_depth;

   subtype Task_Count is positive range 1 .. CPUs;	
   Tasks : array (Task_Count) of check_this_depth;

begin
   if Argument_Count > 0 then
      N := Positive'Value(Argument(1));
   end if;
   Max_Depth := Positive'Max(Min_Depth + 2, N);
   Stretch_Depth := Max_Depth + 1;
   Stretch_Tree := Bottom_Up_Tree(0, Stretch_Depth);
   Item_Check(Stretch_Tree, Check);
   Put("stretch tree of depth ");
   Put(Item => Stretch_Depth, Width => 1);
   Put(Ht & " check: ");
   Put(Item => Check, Width => 1);
   New_Line;
   
   Long_Lived_Tree := Bottom_Up_Tree(0, Max_Depth);
   
   Depth := Min_Depth;
   while Depth <= Max_Depth loop
      Iterations := 2**(Max_Depth - Depth + Min_Depth);
      Check := 0;

-- Setup tasking parameters for reasonable task granularity
-- Too large and we can't balance CPU loads
-- Too small and we waste time in task switches
-- Not very critical - anything more complex is probably a waste of effort
      
      BlockSize := 2**10;
      if Iterations < BlockSize * CPUs then
         BlockSize := 1;
      end if;
  
-- Check that Iterations is a multiple of Blocksize * CPUs
-- Error out otherwise (dealing with remainder is trivial but tedious)
      Pragma Assert(Iterations mod( BlockSize * CPUs) = 0, 
                            "Iteration count not supported!");

      -- for I in 1..Iterations loop  
      Iteration := 1;   
      while Iteration <= Iterations loop
         for j in Task_Count loop
            Tasks(j).Start(Iteration, Blocksize, Depth);
            Iteration := Iteration + BlockSize;
         end loop;
         for j in Task_Count loop
            Tasks(j).Complete(Sum);
            Check := Check + Sum;
         end loop;
      end loop;
      Put(Item => Iterations * 2, Width => 0);
      Put(Ht & " trees of depth ");
      Put(Item => Depth, Width => 0);
      Put(Ht & " check: ");
      Put(Item => Check, Width => 0);
      New_Line;
      Depth := Depth + 2;
   end loop;
   Put("long lived tree of depth ");
   Put(Item => Max_Depth, Width => 0);
   Put(Ht & " check: ");
   Item_Check(Long_Lived_Tree, Check);
   Put(Item => Check, Width => 0);
   New_Line;
end BinaryTrees_tasking;