Task Discriminants & Arrays

Task Discriminants & Arrays

[Matthew Heaney]

One of the nice things about Ada 95 is that I can pass a task an identifier
by giving the task a discriminant:

task type T (Id : Positive) is
   entry E;
end T;

O : T (1);  

And then the task knows its own identifier by refering to Id.

Now suppose I have a task array:

type Task_Array is array (Positive range <>) of T; -- ???

O : Task_Array;  -- ???

It would be really swell if I could give the task object component of the
array an identifier that is its index position in the array.  Anyone got
any ideas about how to do this?

Is there some other technique for allowing the elaborator to assign an id
to a task object, without using an initialization entry?

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Task Discriminants & Arrays

[Jeff Carter]

Matthew Heaney wrote:
> 
> One of the nice things about Ada 95 is that I can pass a task an identifier
> by giving the task a discriminant:
> 
> task type T (Id : Positive) is
>    entry E;
> end T;
> 
> O : T (1);
> 
> And then the task knows its own identifier by refering to Id.
> 
> Now suppose I have a task array:
> 
> type Task_Array is array (Positive range <>) of T; -- ???
> 
> O : Task_Array;  -- ???
> 
> It would be really swell if I could give the task object component of the
> array an identifier that is its index position in the array.  Anyone got
> any ideas about how to do this?
> 
> Is there some other technique for allowing the elaborator to assign an id
> to a task object, without using an initialization entry?
> 
> --------------------------------------------------------------------
> Matthew Heaney
> Software Development Consultant
> <mailto:matthew_heaney@acm.org>
> (818) 985-1271

As I understand it, task discriminants were intended to eliminate the
"serial bottleneck" that results from having to call an initialization
entry to provide information like this to task instances. However, as
far as I can tell, it simply complicates matters: You have to declare an
access type designating the task type, make your array type an array of
these access types, then allocate the tasks at runtime:

task type T (Id : Positive) is
   entry E;
end T;

type T_Ptr is access all T;

type A is array (Some_Range) of T_Ptr;

O : A;
...
for I in O'range loop
   O (I) := new T (Id => I);
end loop;

This doesn't seem to be any more readable that the 83 equivalent:

task type T is
   entry Init (Id : in Positive);
   entry E;
end T;

type A is array (Some_Range) of T;

O : A;
...
for I in O'range loop
   O (I).Init (Id => I);
end loop;

The use of discriminants may be more efficient and have less of a serial
bottleneck. I'd be interested to know if this is the case, and if so,
how much of an improvement one gains with various compilers.
-- 
Jeff Carter  PGP:1024/440FBE21
Auntie-spam reply to; try ( carter @ innocon . com )
"Now go away, or I shall taunt you a second time."
Monty Python & the Holy Grail

Re: Task Discriminants & Arrays

[Matthew Heaney]

In article <33787506.41C67EA6@spam.innocon.com>, Jeff Carter
<carter@spam.innocon.com> wrote:


>As I understand it, task discriminants were intended to eliminate the
>"serial bottleneck" that results from having to call an initialization
>entry to provide information like this to task instances. However, as
>far as I can tell, it simply complicates matters: You have to declare an
>access type designating the task type, make your array type an array of
>these access types, then allocate the tasks at runtime:

Yeah, I thought of the heap-based solution, but was trying to avoid using
an allocator.  Perhaps you just have to do that.

>The use of discriminants may be more efficient and have less of a serial
>bottleneck. I'd be interested to know if this is the case, and if so,
>how much of an improvement one gains with various compilers.

I think it's true that more entries mean more overhead, because the
run-time executive must monitor activity on each entry queue.  In the case
of an Initialization entry, it means a loss of efficiency because that
entry will never get called more than once.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Task Discriminants & Arrays

[John G. Volan]

Jeff Carter wrote:
> 
> As I understand it, task discriminants were intended to eliminate the
> "serial bottleneck" that results from having to call an initialization
> entry to provide information like this to task instances. However, as
> far as I can tell, it simply complicates matters: You have to declare an
> access type designating the task type, make your array type an array of
> these access types, then allocate the tasks at runtime:
                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

No, not necessarily:

> 
> task type T (Id : Positive) is
>    entry E;
> end T;
> 
> type T_Ptr is access all T;
> 
> type A is array (Some_Range) of T_Ptr;
> 

  T_1 : aliased T (Id => 1);
  T_2 : aliased T (Id => 2);
  T_3 : aliased T (Id => 3);
  ...

  O : constant A :=
    (1 => T_1'Access,
     2 => T_2'Access,
     3 => T_3'Access,
     ... );
     
------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "johnvolan@sprintmail.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "These opinions were never defined, so using them " & 
     "would be erroneous...or is that just nondeterministic now? :-) ");
------------------------------------------------------------------------

Re: Task Discriminants & Arrays

[Jeff Carter]

John G. Volan wrote:
> 
> Jeff Carter wrote:
> >
> > As I understand it, task discriminants were intended to eliminate the
> > "serial bottleneck" that results from having to call an initialization
> > entry to provide information like this to task instances. However, as
> > far as I can tell, it simply complicates matters: You have to declare an
> > access type designating the task type, make your array type an array of
> > these access types, then allocate the tasks at runtime:
>                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> 
> No, not necessarily:
> 
> >
> > task type T (Id : Positive) is
> >    entry E;
> > end T;
> >
> > type T_Ptr is access all T;
> >
> > type A is array (Some_Range) of T_Ptr;
> >
> 
>   T_1 : aliased T (Id => 1);
>   T_2 : aliased T (Id => 2);
>   T_3 : aliased T (Id => 3);
>   ...
> 
>   O : constant A :=
>     (1 => T_1'Access,
>      2 => T_2'Access,
>      3 => T_3'Access,
>      ... );
> 

An excellent choice when you have 1E6 of these guys ...
-- 
Jeff Carter  PGP:1024/440FBE21
Auntie-spam reply to; try ( carter @ innocon . com )
"Now go away, or I shall taunt you a second time."
Monty Python & the Holy Grail

Re: Task Discriminants & Arrays

[Robert A Duff]

In article <mheaney-ya023680001305970024550001@news.ni.net>,
Matthew Heaney <mheaney@ni.net> wrote:
>It would be really swell if I could give the task object component of the
>array an identifier that is its index position in the array.  Anyone got
>any ideas about how to do this?

You can give the discriminant a default, which is a function that
increments a counter and returns the new value.  (Horrors!  A function
with a side-effect! ;-))  This will not guarantee that A(I).Id = I,
since the array components are initialized in an arbitrary order.  But
it does guarantee that each task will get a unique Id, which might be
what you want.  Note that the initialization happens before the tasks
are activated, so there's no need to protect the counter from evil
parallel access.

If you really insist that each task's Id be its index, then make it an
array of *pointers* to tasks, and write a loop:

    for I in A'Range loop
        A(I) := new T(Id => I);
    end loop;

Note that this has a slightly different effect -- the tasks are
activated one at a time, rather than in parallel.  So you will probably
want to move any substantial initialization code that appears in the
task's declarative part, down into a block statement.  In your
array-of-tasks example, the activations happen in parallel.  And the
parent task always waits until the activatee's finish executing their
declarative parts.

By the way, if tasks are represented internally as pointers to task
control blocks (could be addresses, or indexes into a table of TCB's),
which is common (in fact, it was pretty much *required*, in Ada 83),
then a compiler can optimize by representing "access T" in the same way
as plain "T".  That is, it is *not* necessary to represent "access T"
with a double indirection -- as a pointer-to-a-pointer-to-a-TCB.  This
is because "=" is not defined on tasks.  I don't know if any compilers
do this optimization -- it's probably not worth the trouble.  I only
mention it because I think it's kind of "neat".

- Bob

Re: Task Discriminants & Arrays

[W. Wesley Groleau (Wes)]

Robert A Duff wrote:
> In article <mheaney-ya023680001305970024550001@news.ni.net>,
> Matthew Heaney <mheaney@ni.net> wrote:
> >It would be really swell if I could give the task object component of the
> >array an identifier that is its index position in the array.  Anyone got
> >any ideas about how to do this?
> 
> You can give the discriminant a default, which is a function that
> increments a counter and returns the new value.  (Horrors!  A function
> with a side-effect! ;-))  This will not guarantee that A(I).Id = I,
> since the array components are initialized in an arbitrary order.  But
> it does guarantee that each task will get a unique Id, which might be
> what you want.  

Is it not true that I can read the ID of each task?  

function "<" ( Left, Right : Discriminated_Task ) return Boolean is
begin
  return Left.ID < Right.ID;
end "<"

-- write Bob Duff's ID function to ensure that all IDs are in A'Range 
-- instantiate your favorite sort with the "<" above and Matt's array.
-- declare the array, then sort it.
-- result:  A(I).ID = I  for all  I in A'Range

----------------------------------------------------------------------
    Wes Groleau, Hughes Defense Communications, Fort Wayne, IN USA
Senior Software Engineer - AFATDS                  Tool-smith Wanna-be

  w w g r o l  at  p s e u l t 0 1  dot  f w  dot  h a c  dot  c o m

     SPAM should be sent to   I.want.one@mailbombs.for.idiots.org
 If you don't want to pay $500 (see 47 USC 227), don't send it here.
----------------------------------------------------------------------

Re: Task Discriminants & Arrays

[Mats Weber]

W. Wesley Groleau (Wes) wrote:
> -- write Bob Duff's ID function to ensure that all IDs are in A'Range
> -- instantiate your favorite sort with the "<" above and Matt's array.
> -- declare the array, then sort it.
> -- result:  A(I).ID = I  for all  I in A'Range

You can't sort it because task types are limited and you can't move them
in the array (no assignment). So you have to use access types and thus
allocate the tasks one by one, or sort an array of pointers that point
to the original array, which messes up the program quite a bit.

Re: Task Discriminants & Arrays

[Robert A Duff]

In article <3379C86F.352@this.message>,
W. Wesley Groleau (Wes) <see.signature@this.message> wrote:
>Is it not true that I can read the ID of each task?  

You can read them.

>function "<" ( Left, Right : Discriminated_Task ) return Boolean is
>begin
>  return Left.ID < Right.ID;
>end "<"
>
>-- write Bob Duff's ID function to ensure that all IDs are in A'Range 
>-- instantiate your favorite sort with the "<" above and Matt's array.
>-- declare the array, then sort it.
>-- result:  A(I).ID = I  for all  I in A'Range

But you can't move the tasks around -- they're limited.  You could move
pointers to tasks around, but if you're willing to use pointers, you
might as well use allocators, and assign the id's you want.  I suppose
you could have an array of tasks, and an array of pointers to tasks, and
sort the latter (and hide the former from clients).  The only advantage
I can see to that is that it allows parallel activation of the tasks.

- Bob

Re: Task Discriminants & Arrays

[John G. Volan]

Robert A Duff wrote:

> I suppose
> you could have an array of tasks, and an array of pointers to tasks, and
> sort the latter (and hide the former from clients).  The only advantage
> I can see to that is that it allows parallel activation of the tasks.

An interesting suggestion. We could have something like:

  task type Process_Type
    (Process_Id : Process_Id_Type := Get_New_Process_Id)
     -- Note: We have to make sure this function is already
     -- elaborated at this point; probably needs to be in another
     -- package
  is
    ...
  end Process_Type;

  type Process_Access_Type is access all Process_Type;

  type Process_Array_Type is
    array (Process_Index_Type range <>) of aliased Process_Type;
    -- Note: Process_Index_Type does not necessarily have to be
    -- the same as Process_Id_Type.  In fact, they probably should
    -- be different to avoid confusing the id of a process with its
    -- arbitrary location in such an array, which won't necessarily
    -- be the same.

  type Process_Access_Array_Type is
    array (Process_Id_Type range <>) of Process_Access_Type;

  procedure Find_Process_Id_Bounds
    (Process_Array      : in     Process_Array_Type;
     Minimum_Process_Id :    out Process_Id_Type;
     Maximum_Process_Id :    out Process_Id_Type)
  is
    ...
  begin
    ... -- left as an exercise for the reader
  end Find_Process_Id_Bounds;

  function Get_Process_Access_Array
    (Process_Array : access Process_Array_Type)
     return Process_Access_Array_Type
  is
    Minimum_Process_Id, Maximum_Process_Id : Process_Id_Type;
  begin
    Find_Process_Id_Bounds
      (Process_Array.all, Minimum_Process_Id, Maximum_Process_Id);
    declare
      Process_Access_Array : Process_Access_Array_Type
        (Minimum_Process_Id .. Maximum_Process_Id);
    begin
      for Process_Index in Process_Array'Range loop
        declare
          Process : constant Process_Access_Type :=
            Process_Array(Process_Index)'Access;
        begin
          Process_Access_Array(Process.Process_Id) := Process;
        end;
      end loop;
      return Process_Access_Array;
    end;
  end Get_Process_Access_Array;

And then in the client application code:

  package Jeff_Carters_Million_Processes is

    Process_Array : aliased Process_Array_Type (1 .. 1E6);
    -- Wham!! ... all activated at once

    Process_Access_Array : constant Process_Access_Array_Type :=
      Get_Process_Access_Array (Process_Array'Access);

    -- Deciding whether and how to hide either or both of these
    -- arrays is left as an exercise for the reader.

  end Jeff_Carters_Million_Processes;

:-) :-) :-)


------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "johnvolan@sprintmail.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "These opinions were never defined, so using them " & 
     "would be erroneous...or is that just nondeterministic now? :-) ");
------------------------------------------------------------------------

Re: Task Discriminants & Arrays

[Robert A Duff]

In article <337B09C9.62BB@sprintmail.com>,
John G. Volan <johnvolan@sprintmail.com> wrote:
>  task type Process_Type
>    (Process_Id : Process_Id_Type := Get_New_Process_Id)
>     -- Note: We have to make sure this function is already
>     -- elaborated at this point; probably needs to be in another
>     -- package

Not at *this* point.  Just before you create any objects of this type.

>  is
>    ...
>  end Process_Type;
>
>  type Process_Access_Type is access all Process_Type;
>
>  type Process_Array_Type is
>    array (Process_Index_Type range <>) of aliased Process_Type;
>    -- Note: Process_Index_Type does not necessarily have to be
>    -- the same as Process_Id_Type.  In fact, they probably should
>    -- be different to avoid confusing the id of a process with its
>    -- arbitrary location in such an array, which won't necessarily
>    -- be the same.

Good point.

>    Process_Array : aliased Process_Array_Type (1 .. 1E6);
>    -- Wham!! ... all activated at once

Yeah, right.  A million tasks.

>...
>  end Jeff_Carters_Million_Processes;
>
>:-) :-) :-)

Sorry, I don't get it.  Are you saying "this is a mess"?  Yeah, it is.
Shrug.

- Bob

Re: Task Discriminants & Arrays

[John G. Volan]

Robert A Duff wrote:
> 
> >...
> >  end Jeff_Carters_Million_Processes;
> >
> >:-) :-) :-)
> 
> Sorry, I don't get it.  Are you saying "this is a mess"?  Yeah, it is.
> Shrug.

No, no! I think this is a great solution!  I wasn't smiling at your
idea, I was smiling because I think that this handily meets a challenge
Jeff Carter raised.  Let me clarify:

We've been struggling with how to meet all of the following goals:

(1) We want to have a collection of tasks that are all activated at the
same time.  In other words, we want to avoid allocating the tasks
individually on the heap.

(2) We want to be able to index individual tasks in the collection by
unique id numbers.

(3) We want to provide each task with its unique id number (so that it
can be used in the task body for whatever purpose), but without having
to synchronize with the task via an entry call.

Meeting goal 1 is simple: just declare an array of tasks.

Meeting goal 3 is a little tricky, but doable: We can give a task an id
number via a discriminant, without need for synchronization. We can
guarantee this is a unique identifier by default-initializing the
discriminant with a function that has an incrementing side-effect (i.e.,
your earlier suggestion).

Meeting goal 2 now becomes a problem. How can you make sure that a given
task is indexed by its id number?  Well, you can't, not with a simple
array of tasks.  But what you _can_ do is have an array pointers to the
tasks, and index the _pointers_ by id.

Jeff Carter made the statement that this means you have to sequentially
allocate the tasks on the heap (in a for loop). But this would fail goal
1.

I countered that having an array of pointers doesn't necessarily mean
the tasks are on the heap: I showed an example where I declared a bunch
of _aliased_ tasks in the same scope (satsifying goal 1). In that
example, I did some simplistic things: I manually constrained each
task's id discriminant to a different (static) value, and then afterward
manually applied 'Access to each aliased task, wrote out an aggregate
expression by hand, and initialize a constant array of general access to
task indexed by id.

Jeff Carter took one look at all the manual work I was doing, and
flippantly said "An excellent choice when you have 1E6 of these guys
..."  Talk about throwing down the gauntlet! :-)

Well, I took that as a challenge, but then your suggestion inspired a
solution:  Declare an aliased array of aliased tasks with arbitrary
index, using your side-effect-function-discriminant trick.  Don't worry
about where each task winds up in that array. Then create the array of
task pointers indexed by id.

What I was trying to add to this was the fact that you don't really have
to "sort" the pointer array, you can construct it _already_ sorted. All
you have to do is traverse the array of tasks, take the 'Access of each,
and stick it directly into the slot indexed by the task's id.

Hmm, long-forgotten memories of my old algorithms class are floating up
from my subconscious ... is what I described known as a "radix sort"?
Bottom line, you don't need some O(N log N) sort to achieve this, it's
purely O(N).

------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "johnvolan@sprintmail.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "These opinions were never defined, so using them " & 
     "would be erroneous...or is that just nondeterministic now? :-) ");
------------------------------------------------------------------------

Re: Task Discriminants & Arrays

[John G. Volan]

Sorry, I should have added the following:

John G. Volan wrote:
> 
> Robert A Duff wrote:
>
> > Sorry, I don't get it.  Are you saying "this is a mess"?  Yeah, it is.
> > Shrug.
> 
> No, no! I think this is a great solution!

Of course, you should wrap a nice abstraction around this.  All that a
user should have to know is that there are these tasks and they are
accessible by id number:

  package Processes is

    type Process_Id_Type is range ...;

    function Get_New_Process_Id return Process_Id_Type;

    task type Process_Type
      (Process_Id : Process_Id_Type := Get_New_Process_Id)
    is
      ...
    end Process_Type;

    type Process_Access_Type is access all Process_Type;

    function Get_Process
      (Process_Id : in Process_Id)
       return Process_Access_Type;

    -- Note to clients: To get access to a Process_Type task, call
    -- Get_Process. DO NOT declare any Process_Type tasks
    -- of your own; this will result in Constraint_Error.
    -- Elaboration of this package already results in the creation
    -- of one task for each value in Process_Id_Type.

  end Processes;

------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "johnvolan@sprintmail.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "These opinions were never defined, so using them " & 
     "would be erroneous...or is that just nondeterministic now? :-) ");
------------------------------------------------------------------------

Re: Task Discriminants & Arrays

[Matthew Heaney]

In article <337B09C9.62BB@sprintmail.com>, johnvolan@sprintmail.com wrote:


>An interesting suggestion. We could have something like:
>
>  task type Process_Type
>    (Process_Id : Process_Id_Type := Get_New_Process_Id)
>     -- Note: We have to make sure this function is already
>     -- elaborated at this point; probably needs to be in another
>     -- package

No.  The rule that a procedure body is a "later declarative item" went away
in Ada 95:

declare
   Index : Natural := 0;

   function Get_New_Process_Id return Positive is
   begin
      Index := Index + 1;
      return Index;
   end;

   task type T (Id : Positive := Get_New_Process_Id) is
      entry E;
   end T;

   type TA is array (Positive range 1 .. 10) of T;

   O : TA;
...

This kind of application is precisely why the rule went away.  No more
Program_Error!

However, as Bob pointed out, this doesn't guarantee that O(I).Id = I.

Perhaps in Ada 0X we can add loop expressions (sort of like what you have
in Fortran).  That would allow more initializations at the point of
declaration of an object, instead of having to defer the initialization to
the executable region (e.g. the begin part of the body) because the
initialization requires a loop.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Task Discriminants & Arrays

[John G. Volan]

Matthew Heaney wrote:
> 
> In article <337B09C9.62BB@sprintmail.com>, johnvolan@sprintmail.com wrote:
> 
> >An interesting suggestion. We could have something like:
> >
> >  task type Process_Type
> >    (Process_Id : Process_Id_Type := Get_New_Process_Id)
> >     -- Note: We have to make sure this function is already
> >     -- elaborated at this point; probably needs to be in another
> >     -- package
> 
> No.  The rule that a procedure body is a "later declarative item" went away
> in Ada 95:

Yes, that's true. Having the full body of Get_New_Process_Id earlier in
the same declarative region would do the trick.

However, my intention was for the code in my sketch to go into a
package, rather than just a local block.  Parts of my example belonged
in the package spec, parts in the body, but I admit that wasn't clear. 
(I was typing pretty fast...)  Under those circumstances, I don't
believe Get_New_Process_Id could be another function spec declared in
the same package spec with Process_Type.

------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "johnvolan@sprintmail.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "These opinions were never defined, so using them " & 
     "would be erroneous...or is that just nondeterministic now? :-) ");
------------------------------------------------------------------------