Re: Task Discriminants & Arrays

["John G. Volan" <johnvolan@sprintmail.com>]

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? :-) ");
------------------------------------------------------------------------