Re: performance of Generic and strings

[Robert Dewar <dewar@gnat.com>]

In article <37B1B634.543D131D@pwfl.com>,
  e108678@pwflcom wrote:
> I have also been informed by
> other experts in the Ada compilation field that there are
certain
> language issues involved with the macro expansion technique
which make
> the profile technique more attractive. (I won't name names,
not wishing
> to draw anyone unwillingly into the fray, but feel free to
leap to my
> defense here. :-)

You have been informed exactly wrong (or misunderstood :-)
It is FAR FAR easier to do macro expansion, and indeed the
design of Ada 95 pretty much assumes macro expansion for
specs. Bodies can be shared, but general sharing of bodies
is VERY VERY tricky, ask Randy Burkhardt :-)

> As to which is more commonly used? Not being a compiler vendor
myself,
> I'll defer to those who make it their business to know the
market.

GNAT certainly uses macro expansion, so does Intermetrics (and
hence Greenhills, Aonix, SHARC and any other Ada 95 compiler
using the Intermetrics front end.

Rational used to do code sharing in Ada 83, but I am pretty
sure the new Rational technology uses macro expansion.

I am not aware of any validated Ada 95 compiler that does NOT
do macro expansion (counter examples welcome to be posted :-)

> However, between the two, I think I'd rather have
instantiation done
> with some sort of profile information rather than expansion.
While
> normally, I'd come down on the side of speed, in this
instance, I'd
> prefer the space savings as long as the time penalty was
minimal.

The time penalty is not at all minimual. Many simple things
have to be done by passing thunks. In practice the best you
can do is to share some simple cases of generics, but then
you might fall afoul of the Digital patent. Full general
sharing imposes a very significant penalty. For example,
what do you do with a digits formal? Do everything in
double precision? Well, apart from the obvious time penalty,
that's not quite right for special cases like
Unchecked_Conversion and 'Machine. So you have to pass
thunks for these operations. Consider integer, and things
get worse. To use 64-bits for all integer operations is
far too expensive on some machines.

Dan Eilers (Irvine) has suggested significant additions in
the language to make more sharing of generics feasible, since
he is interested in doing sharing, but considers the language
in its current form simply too hostile to efficient sharing
(i.e. the time penalty is just too great).

Note other annoying areas are exceptions, where exceptions must
be unique in different instantiations, and obscure programs can
tell the difference. There are many many other gotcha's in
implementing general shared generics.

Note that shared generics will cause a space *penalty* if
a generic is instantiated only once, a common occurrence in
many programs.

Note also that the space penalty is quite small if a generic is
designed so that most common code is in a non-generic helper
unit (see implementation of Integer_IO in GNAT for an example
of this approach, or Direct_IO).

> It
> also greatly reduces verification problems, which is a
> tremendous concern around here.

I am not at all sure that it reduces verification problems.
Obviously if you are doing only one instantiation, it greatly
increases the problems, because the code is so much more
complex, and will rely on a lot of indirect subprogram calls,
for the thunks, always a big worry for verification environments
(some verification protocols simply prohibit indirect calls
completely).

For macro instantiation, you do have to repeat the verification
for each instance, but the work to be done is far easier,
because you do the verification only for the particular instance
of the actuals, instead of having to verify the generic for all
possible instantiations.

Indeed in the HRG discussions, some felt that generics could
ONLY be considered verifiable if instances were NOT shared.

We decided early on in GNAT to provide only the macro
substitution approach. There is in fact nothing in the GNAT
technology that makes it hard to do generic code sharing. It
is neither easier nor harder in GNAT than it would be in any
other environment. We had anticipated concerns about this
approach, but so far it has not been a major issue.

I will say that in general we see people being far more
concerned about space than time, so I can easily see that
there might be environments in which the overhead of sharing
would be a good trade off for the saved space. However, I
suspect that sharing of generic bodies is hard enough in Ada 95
than it may never get done in the GNAT environment (at least by
ACT), we have lots of other things to do before that.

I must say I am very surprised that anyone in the Ada compiler
community would claim it is easier to do sharing than macro
expansion, given that the difficulties of generic sharing are
positively notorious :-)

Robert Dewar
Ada Core Technologies


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