From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,ad4585f2971e47c5 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news3.google.com!feeder.news-service.com!216.196.110.142.MISMATCH!border3.nntp.ams.giganews.com!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.bt.com!news.bt.com.POSTED!not-for-mail NNTP-Posting-Date: Mon, 21 Feb 2011 06:49:34 -0600 From: Brian Drummond Newsgroups: comp.lang.ada Subject: Re: Need some light on using Ada or not Date: Mon, 21 Feb 2011 12:52:24 +0000 Reply-To: brian@shapes.demon.co.uk Message-ID: <6nm4m6h6il8j02l9b11qkjsg3k2cjhjul8@4ax.com> References: <4d5ef836$0$23753$14726298@news.sunsite.dk> <7ibvl6tn4os3njo3p4kek9kop44nke3n7t@4ax.com> <4d5fd57d$0$6992$9b4e6d93@newsspool4.arcor-online.net> <4D617036.4080902@obry.net> X-Newsreader: Forte Agent 1.7/32.534 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Usenet-Provider: http://www.giganews.com X-AuthenticatedUsername: NoAuthUser X-Trace: sv3-PnXJCWXbZ90jctKa9anLK3OnlvI3Yv/DhTtxHgHS1EmmGoJb3oeOqz73enzcTc7PX/reFTLC6EPAoqk!+Z/zNLUUQDD1nRQqj93OXl4t8H5+lwaJG/+ohxQgM27ZB6Wu1SS5jqHYpl/9WJreHwhN47L+iHOG!sFc= X-Complaints-To: abuse@btinternet.com X-DMCA-Complaints-To: abuse@btinternet.com X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 7516 Xref: g2news2.google.com comp.lang.ada:18488 Date: 2011-02-21T12:52:24+00:00 List-Id: On Sun, 20 Feb 2011 22:47:05 +0000, Simon Wright wrote: >Brian Drummond 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;