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.2 required=5.0 tests=BAYES_00,INVALID_MSGID, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,b4731a3b5d591abd X-Google-Attributes: gid103376,public From: "John G. Volan" Subject: Re: Task Discriminants & Arrays Date: 1997/05/16 Message-ID: <337CE7E2.7B33@sprintmail.com>#1/1 X-Deja-AN: 242888633 References: <3379C86F.352@this.message> <337B09C9.62BB@sprintmail.com> Reply-To: johnvolan@sprintmail.com Newsgroups: comp.lang.ada Date: 1997-05-16T00:00:00+00:00 List-Id: 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? :-) "); ------------------------------------------------------------------------