Re: Composing tasks and protected objects

[Robert A Duff <bobduff@shell01.TheWorld.com>]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> news:wcchde4dyv4.fsf@shell01.TheWorld.com...
> > Florian Weimer <fw@deneb.enyo.de> writes:
> >
> > > * Robert A. Duff:
> > > > The multi-way call feature was rejected primarily due to perceived
> > > > difficulty of implementation, or perceived difficulty of *efficient*
> > > > implementation.  I did not agree with that argument.
> > >
> > > I could understand that argument if this language feature caused
> > > uniform overhead on all protected operations, even if it isn't used
> > > anywhere in the program.  Is this really the case?
> >
> > I think I could implement multi-ways calls in such a way that there is
> > zero or near-zero overhead for the currently-allowed features (plain
> > calls, timed/conditional calls).  But I have not proven that by doing
> > so!
> 
> The UI teams of the Ada 9X effort were asked to write reports on this
> feature. None of them came up with an efficient implementation. Their
> reports are still around somewhere (use the search engine to look in the
> AdaIC archives - archive.adaic.com).

It's easy to believe that multi-way call is infeasible to implement in
an existing Ada 83 compiler.  And we certainly cannot blame an Ada 83
implementor for not taking into account language requirements that did
not exist until 10 years after they did their design!

And of course a language revision needs to take into account difficulty
of implementation on *existing* compilers.

For example, in Ada 83, one could assume that a task can only be on one
entry queue at a time.  And it was reasonable for Ada 83 implementers to
take advantage of that assumption by putting the queue links in the TCB.
For multi-way calls, you have to switch to thinking about each entry
call (represented by a stack-allocated object) being separately on an
entry queue, rather than the *task* itself being on the queue.  And that
might require a rather daunting rewrite of an existing Ada 83
implementation.

However, my claim was that it is possible to implement multi-way calls
with near-zero distributed overhead, in a *from scratch*
implementation.

Note that there may already be a tiny bit of distributed overhead:
simple entry calls pay some cost because of the mere existence of timed
entry calls, even if timed entry calls are not used, because you have to
worry about the potential race condition if the time-out happens at
nearly the same time as the entry being triggered.  I claim (without
proof ;-)) that the distributed overhead of multi-way calls can be
hidden in the same overhead necessary for timed calls.

> > Inefficiency is never a good reason to leave a feature out of a
> > language.  What matters is distributed overhead (i.e. when a feature
> > causes inefficiency when you *don't* use it).
> 
> I think that most of the possible efficient implementations did so by having
> distributed overhead. But it was a long, long time ago, so I don't remember
> the details anymore.
> 
> But I do remember that one of the major issues was that the people who were
> pushing for the feature were hard-real-time types with strict timing
> requirements. No one had an implementation that could meet those sorts of
> requirements (polling seemed to be required).

I don't think polling is required (in a from-scratch design, where the
designer knows the requirement for multi-way call ahead of time).

>... Having a feature that cannot
> be efficicient enough for the customers is silly.

I don't really buy that argument.  If the requirement is to wait upon
multiple entry calls, and that feature is not available, then
programmers will have to implement it themselves.  If it's inherently
inefficient, then so be it -- they need that functionality, and that's
that.  It's unlikely that programmers will be able to implement that
functionality more efficiently than Ada implementers.

> > There's also the issue that the implementation experiments done during
> > the Ada 9X process were done on *existing* implementations, which were
> > designed with the requirements of Ada 83 in mind.  Adding a feature to
> > an existing implementation is sometimes a lot harder than implementing
> > it in a from-scratch design where the designer knows the requirements
> 
> Possibly. I have to wonder if there wouldn't be too many conflicting
> requirements to make that possible. The "Bob" language without task entries
> would clearly make it easier to allow other sorts of things (although I
> can't quite figure out how it would work). A clear sheet of paper helps
> things in every dimension -- but that isn't going to happen for Ada, as
> compatibility is important.

Yes -- compatibility is important.

- Bob