Re: What is a Display ? (was: Subverting 'Access for Sub-programs)

[Robert Dewar <robert_dewar@my-deja.com>]

In article <t7907pbwwc.fsf@calumny.jyacc.com>,
  Hyman Rosen <hymie@prolifics.com> wrote:

> kilgallen@eisner.decus.org (Larry Kilgallen) writes:
> > What is a Display ?
>
> Since such access
> tends to be rare, static links are probably better.

Well this is arguable, and in my experience it is not unusual
for Ada programs to violate this rule.

But more to the point, consider the following categories:

1. Calls to global procedures not containing nested procedures
2. Calls to global procedures containing nested procedures
3. Calls to nested procedures not containing nested procedures
4. Calls to nested procedures containing nested procedures

For static links, 1,2 involve no overhead on the call, but 3,4
do require the overhead of setting up the static link.

For displays 1,3 involve no overhead on the call, but 2,4 do
require the overhead of updating the display.

Now obviously if you have no nested procedures, then you are in
case 1 all the time, and neither approach causes any overhead.

If you have nested procedures, the question is which is better.
I think it is clear that displays come off better -- why? Well
for displays we only pay overhead on a call to a procedure that
contains nested procedures, but in such cases, almost surely
there will be significantly more calls to leaves (i.e. to the
nested procedures), than to the procedure containing them. But
in the static link case, you pay for calls to ALL non-global
subprograms.

This analysis does not however include the impact of general
procedure pointers without the ADa 95 restrictions. In that
case, you would find displays so much less efficient for the
case of calling subprograms via an access pointer, that you
would almost surely choose static links.

With the rules of Ada 95, which are carefully designed so that
this extra impact on display implementations does not occur, it
is probably the case that a per-task display represents the most
efficient handling of non-local references.

Consider for example, a not uncommon case, where you have a
large procedure that contains a large number of nested
procedures (e.g. look at Analyze_Attribute in the GNAT sources).

There is one call to Analyze_Attribute (that would involve call
overhead for the display case, but not for the static link case)

But then when the analysis call makes a sequence of calls to
the nested procedures, which often call one another, the display
approach would have zero overhead for all such calls, whereas
the static link case would have to update the link on each call.

Robert Dewar


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.