Weird problem with recursion and tasks

Weird problem with recursion and tasks

[christopher.orihuela]

I was implementing a concurrent version of QuickSort (each half in a
different task) when I realized that sometimes the recursive task
didn't execute.
¿Could anybody tell me why for values of MaxI > 4 I allways get a
higer count of A in the following program? Thanks.


With Ada.Text_IO;
Use Ada.Text_IO;

Procedure My_Proc is

   protected type Counter is
      Procedure IncA;
      Procedure IncB;
      Procedure ShowCounts;
   private
      A, B: Natural := 0;
   end Counter;

   protected body Counter is
      Procedure IncA is
      begin
         A := A+1;
      end IncA;
      Procedure IncB is
      begin
         B := B+1;
      end IncB;
      Procedure ShowCounts is
      begin
         Put_Line("A: " & Integer'Image(A));
         Put_Line("B: " & Integer'Image(B));
      end ShowCounts;
   end Counter;

   MyCounter : Counter;

   Procedure Recursive (I : Natural; MaxI : Natural) is
   begin

      if (I >= MaxI) then
           return;
      end if;

      MyCounter.IncA;
      MyCounter.IncA;
      declare
         Task My_Recursive_Task;
         Task Body My_Recursive_Task is
         begin
            Recursive(I+1, MaxI);
            MyCounter.IncB;
         end My_Recursive_Task;

      begin
         Recursive(I+1, MaxI);
         MyCounter.IncB;
      end;
   end Recursive;
   
begin
   Recursive (1, 6);
   MyCounter.ShowCounts;
end My_Proc;

Re: Weird problem with recursion and tasks

[Gautier]

christopher.orihuela@gmail.com:

> I was implementing a concurrent version of QuickSort (each half in a
> different task) when I realized that sometimes the recursive task
> didn't execute.
> �Could anybody tell me why for values of MaxI > 4 I allways get a
> higer count of A in the following program? Thanks.

The behaviour seems to depend on the compiler...
- With ObjectAda 7.2.2 SE I always get, in debug or release mode:
A:  62
B:  62
- With GNAT GPL 2006 I usually get the same, but also sometimes
A:  62
B:  57
or even down to
A:  60
B:  49
Here my competencies stop, I'm not a specialist in tasks & Co.
Then, is it your compiler or something missing in the code - I cannot decide...
HTH
______________________________________________________________
Gautier         -- http://www.mysunrise.ch/users/gdm/index.htm
Ada programming -- http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!

Re: Weird problem with recursion and tasks

[Dmitry A. Kazakov]

On 2 Dec 2006 19:21:14 -0800, christopher.orihuela@gmail.com wrote:

> I was implementing a concurrent version of QuickSort (each half in a
> different task) when I realized that sometimes the recursive task
> didn't execute.
> �Could anybody tell me why for values of MaxI > 4 I allways get a
> higer count of A in the following program? Thanks.

It looks like a compiler bug to me (GNAT 3.15p, Windows). If we added a few
put_lines:

With Ada.Text_IO, Ada.Strings.Fixed;
Use  Ada.Text_IO, Ada.Strings.Fixed;

Procedure My_Proc is

   protected type Counter is
      Procedure IncA;
      Procedure IncB;
      Procedure ShowCounts;
   private
      A, B: Natural := 0;
   end Counter;

   protected body Counter is
      Procedure IncA is
      begin
         A := A+1;
      end IncA;
      Procedure IncB is
      begin
         B := B+1;
      end IncB;
      Procedure ShowCounts is
      begin
         Put_Line("A: " & Integer'Image(A));
         Put_Line("B: " & Integer'Image(B));
      end ShowCounts;
   end Counter;

   MyCounter : Counter;

   Procedure Recursive (I : Natural; MaxI : Natural) is
   begin

      if (I >= MaxI) then
           return;
      end if;

      MyCounter.IncA;
      MyCounter.IncA;

      declare
         task My_Recursive_Task;
         task body My_Recursive_Task is
         begin
            Put_Line(I * " " & "Start task");
            Recursive(I+1, MaxI);
            MyCounter.IncB;
            Put_Line(I * " " & "Stop task");
         end My_Recursive_Task;

      begin
         Recursive(I+1, MaxI);
         MyCounter.IncB;
      end;

   end Recursive;
   
begin
   Recursive (1, 5);
   MyCounter.ShowCounts;
end My_Proc;

we would see that starting with MaxI=4 and higher some of My_Recursive_Task
are not awaited for termination by their masters, when the task object gets
out of scope. I see it in breach with ARM 7.6.1(4).

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Weird problem with recursion and tasks

[Matthew Heaney]

"christopher.orihuela@gmail.com" <christopher.orihuela@gmail.com> writes:

>    protected body Counter is
>       Procedure ShowCounts is
>       begin
>          Put_Line("A: " & Integer'Image(A));
>          Put_Line("B: " & Integer'Image(B));
>       end ShowCounts;
>    end Counter;


Ada.Text_IO.Put_Line is a "potentially-blocking operation" so you should not
call it from a protected operation; be aware that Program_Error might get
raised here.  (Ada 2005 has a new feature whereby you can request the compiler
to detect that a potentially-blocking call was made and raise that exception.)

Re: Weird problem with recursion and tasks

[Craig Carey <research@ijs.co.nz>]

Matthew Heaney wrote:
...
> Ada.Text_IO.Put_Line is a "potentially-blocking operation" so you should not

It would be that when the procedure recurses, it creates a new thread.
The thread of the procedure and the thread that it creates run in
parallel.

I write at a cafe since the nzsis.govt.nz was editing and deleting my
private
e-mail - viciously censoring, actually deleting. I killed my e-mail
address
at research@ijs.co.nz. I was perfectly blocked from using 56 k access
by
the SIS, since about 8 August 2006. Here there is deliberate
overbilling: a
plague of fraudulent demands for cash, and that is what happens when NZ
implements the strategic goal of opposing train bombing: serious fraud.

Craig Carey, computer.org.nz.

Re: Weird problem with recursion and tasks

[christopher.orihuela]

Thank you for your replies. I will consider it a compiler bug, then :)

Re: Weird problem with recursion and tasks

[christopher.orihuela]

well, if anybody ever has the same problem, someone else found a
workaround: using pointers to objects task declared at an equal or
higher level than the procedure that launches them.

Re: Weird problem with recursion and tasks

[Georg Bauhaus]

On Mon, 2006-12-04 at 12:09 -0800, christopher.orihuela@gmail.com wrote:
> well, if anybody ever has the same problem, someone else found a
> workaround: using pointers to objects task declared at an equal or
> higher level than the procedure that launches them.

Does this mean we shouldn't use Ada the way it was designed
when using GNAT?


 -- Georg 

Re: Weird problem with recursion and tasks

[Dmitry A. Kazakov]

On Tue, 05 Dec 2006 12:38:49 +0100, Georg Bauhaus wrote:

> On Mon, 2006-12-04 at 12:09 -0800, christopher.orihuela@gmail.com wrote:
>> well, if anybody ever has the same problem, someone else found a
>> workaround: using pointers to objects task declared at an equal or
>> higher level than the procedure that launches them.
> 
> Does this mean we shouldn't use Ada the way it was designed
> when using GNAT?

Was it a rhetorical question? I like to answer those! (:-)) Yes, we
shouldn't, because there is pretty little choice for people outside large
firms. Because even in a large firm you have first to convince management
to buy licenses. GNAT de facto is a monopolist on the market which isn't a
market at all...

So either you fix your program or you do the compiler. [Rhetorically] What
would you choose?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Weird problem with recursion and tasks

[Ludovic Brenta]

christopher.orihuela@gmail.com wote:
> Thank you for your replies. I will consider it a compiler bug, then :)

What version of the compiler? On what platform?

If you're using gnat 3.15p, please file a bug in the Debian bug
database, even if you don't use Debian. That way, the bug and its
workaround become public, documented and searchable.

See http://bugs.debian.org

Use package "gnat".

-- 
Ludovic Brenta.

Re: Weird problem with recursion and tasks

[Georg Bauhaus]

On Tue, 2006-12-05 at 04:03 -0800, Ludovic Brenta wrote:

> If you're using gnat 3.15p, please file a bug in the Debian bug
> database, even if you don't use Debian. That way, the bug and its
> workaround become public, documented and searchable.

Will it be possible to have a big warning next to "workaround"?
This way people might feel a need to add a comment line next
to the workaround in normal code.

Re: Weird problem with recursion and tasks

[Ludovic Brenta]

Georg Bauhaus wote:
> On Tue, 2006-12-05 at 04:03 -0800, Ludovic Brenta wrote:
>
> > If you're using gnat 3.15p, please file a bug in the Debian bug
> > database, even if you don't use Debian. That way, the bug and its
> > workaround become public, documented and searchable.
>
> Will it be possible to have a big warning next to "workaround"?
> This way people might feel a need to add a comment line next
> to the workaround in normal code.

Yes. Since every bug is a mailing list, anyone can reply to the bug
and add their comments. See for example

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=48538;archive=yes

-- 
Ludovic Brenta.

Re: Weird problem with recursion and tasks

[christopher.orihuela]

> What version of the compiler? On what platform?

GNAT GPL 2006 (20060522-34) for windows.

But the behaviour is the same under linux.

Re: Weird problem with recursion and tasks

[christopher.orihuela]

I opened a bug report for GCC (
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30078 ).