performance of Generic and strings

performance of Generic and strings

[Thomas Rutström]

Hi

Is there anyone who can tell me exactly what it is that makes generic
procedures so slow compared to non-generic procedures? 

I am also interested in techniques that will speed up the use of strings
in Ada?

	thanks in advance
		.thomas

Re: performance of Generic and strings

[Michael F. Yoder]

Thomas Rutstr�m wrote:
> 
> Hi
> 
> Is there anyone who can tell me exactly what it is that makes generic
> procedures so slow compared to non-generic procedures?
> 
> I am also interested in techniques that will speed up the use of strings
> in Ada?
> 
>         thanks in advance
>                 .thomas

I'm virtually certain that these problems are specific to particular
implementations, and aren't inherent to Ada in general.  For example, I
know there is at least one implementation of Ada.Strings.Unbounded and
Ada.Strings.Wide_Unbounded with truly gruesome performance problems, but
the problem isn't inherent to the semantics of the packages.  (To be
fair to them, I should note that my co-workers and I made exactly the
same error when we implemented variable-length string handling in Pascal
at one of my old companies.  But we fixed it.)

In all likelihood you will need to state which implementation you're
using, and what you're trying to do.
-- 
Michael F. Yoder

Unscientific man is beset by a deplorable desire to have been right.
The scientist is distinguished by a desire to *be* right. -- W.V. Quine

Re: performance of Generic and strings

[Marin David Condic]

Thomas Rutstr�m wrote:

> Hi
>
> Is there anyone who can tell me exactly what it is that makes generic
> procedures so slow compared to non-generic procedures?
>
> I am also interested in techniques that will speed up the use of strings
> in Ada?

The first question is: What compiler/version and processor/operating-system
are you working with? There should be nothing that makes generic procedures
inherently *substantially* slower than non-generic procedures so it would
help to identify the implementation.

Generally, an implementation would require one more layer of indirection in
references to things which are generic sort of like the extra layer of
indirection implied by object oriented stuff. (A tag lookup prior to jumping
to a subroutine, for example.) Granted, this is overhead, but we've used
generic procedures in hard real-time apps and have not found them to be
excessively slow. It also depends on exactly what you are doing. Some
generic parameters may impose less overhead than others. Could you post an
example of a generic parameter list that is causing you trouble?

There are three kinds of strings in Ada. The base level "primitive" strings
for which appendix A.4.3 provides a package of manipulation routines under
the name Ada.Strings.Fixed. These strings should be as fast as any other
language's strings given that they are a simple array implementation. Of
course, your compiler may have supplied a poor implementation of the package
Ada.Strings.Fixed, which could account for slow speed. The next type of
strings are defined in the package Ada.Strings.Bounded in A.4.4. This
variety of string should be based on a fixed size allocation and should also
perform at speeds similar to the Fixed string. You pay some space penalty
for semi-dynamic behavior, but not much time overhead. The third type of
string is the Unbounded string defined in A.4.5, Ada.Strings.Unbounded.
These will require some form of dynamic allocation as strings grow and
shrink. They provide far more convenient behavior at the expense of possible
wasted space and time overhead. Again, there may be performance problems
because of your particular implementation, so it will help to post your
environment and possibly some code fragments which you think are performing
poorly.

Another thing you might do is look for a compiler option that turns off
range checks on the code you believe is running too slow. This is like
performing on a high wire without a net, but once you've got confidence in
the correctness of your code, it will be less risky. You can also use the
pragma Suppress within your code to turn off a variety of checks which may
be slowing the code down. (See ARM 11.5)

Hope this helps.

MDC
--
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
***To reply, remove "bogon" from the domain name.***

Visit my web page at: http://www.mcondic.com/

Re: performance of Generic and strings

[Robert Dewar]

> Is there anyone who can tell me exactly what it is that makes
> generic procedures so slow compared to non-generic procedures?

No, there is no one who can tell you this, because it simply
is not true. In most implementations of Ada, generics are done
by inline expansion, so there is absolutely NO time efficiency
penalty for making a procedure generic, none at all!

So you are really asking another question entirely, which is
something like

why is generic procedure BLA slower than non-generic procedure
JUNK.

We need to know BLA and JUNK to answer this :-)


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

Re: performance of Generic and strings

[Robert Dewar]

In article <37B18AB6.BBAEF44A@pwfl.com>,
  e108678@pwflcom wrote:
> Generally, an implementation would require one more layer of
indirection in
> references to things which are generic sort of like the extra
layer of
> indirection implied by object oriented stuff. (A tag lookup
prior to jumping
> to a subroutine, for example.) Granted, this is overhead


There is no such overhead in typical implementations of
generics, so it is not clear what you are talking about.

If you are using an implementation that shares generic bodies,
then indeed there are time penalties, but most (nearly all?)
Ada 95 compilers handle generics with full "macro type"
inline expansion, so there are no penalties at all. This is
most certainly true of GNAT.

Of course if you PROGRAM a level of indirection, e.g. passing
a procedure pointer to the generic subprogram, you get extra
overhead, but you would get exactly the same overhead passing
the same procedure pointer to a non-generic version of the
subprogram.


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

Re: performance of Generic and strings

[Marin David Condic]

Robert Dewar wrote:

> There is no such overhead in typical implementations of
> generics, so it is not clear what you are talking about.
>

My understanding was that there are two ways to implement generics - one
was macro-like expansion and the other was via some sort of "profile"
information which could make the code common, but change the behavior
for each generic instance. (For example, keeping pointers to
subprograms, size information for various data types, etc. and the
generated code operates using the profile info when calling subprograms,
moving data, etc.)

Clearly, a code expansion technique would pose no time penalty -
provided the compiler did not do some different form of code generation
when it went to compile generics vs standard stuff. (I believe we've had
examples of this in earlier Ada compilers.) There is, however, an
obvious space penalty as well as a serious verification issue to this
technique.

Given that Thomas was originally complaining of a speed penalty, I
suppose I was presuming his compiler must be using an implementation
technique that would account for this. 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. :-)

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.
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. It
also greatly reduces verification problems, which is a tremendous
concern around here.

MDC
--
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
***To reply, remove "bogon" from the domain name.***

Visit my web page at: http://www.mcondic.com/

Re: performance of Generic and strings

[Richard D Riehle]

In article <7ovq7d$km$1@nnrp1.deja.com>,
	Robert Dewar <dewar@gnat.com> wrote:

>
>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 :-)

Also, ask Terry Dunbar.  The TLD compiler used for some of the
communication satellite software on a 1750A required a code
sharing model.  There is a consequent trade-off between time and
memory.  On a 1750A, there is little of either, but certainly more
of time than memory.   Yes, I know about the MMU, but the MMU cannot
be used on most satellites.  Takes too much real-estate and draws
too much power.  

I wonder what kind of model Terry will use for Ada 95.  I heard he would use
GNAT, but that would run counter to the model of his Ada 83 design.  Anyone
heard from Terry lately?   

Richard Riehle
richard@adaworks.com
http://www.adaworks.com

Re: performance of Generic and strings

[Robert Dewar]

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.

Re: performance of Generic and strings

[Marin David Condic]

Robert Dewar wrote:

>
> > 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).
>

The problem is not so much a technical one as it is a procedural and
managerial one. If you go to the trouble of verifying a normal
subprogram by running the code with a variety of test cases, this takes
a fair amount of time and money. From one release to the next, so long
as that module has not been touched, you can presume the verification to
remain valid. (Yes, we can always generate scenarios where the calls
change and something that didn't blow up, now does, but that's more of
an integration issue.) You'd very much like to do the same thing with a
generic, but in an expansion situation, it generates a whole new set of
bits every time it is instantiated and you now have to do something to
demonstrate that this new set of bits is correct. Seeing that the code
didn't change from one release to another tells you very nearly nothing
about the validity of your prior verification efforts. Whereas if the
code is shared (difficult as that may be) you have one set of bits which
you can run a verification suite on and - to the extent that your test
scenario is useful - you can feel comfortable that no change in the
source module means that this verification remains valid.

Of course a lot depends on how serious you need to treat the issue of
verification. :-) And we can always throw in the monkey wrench of
observing that with some compilers, given the same source code, a
different set of bits may be generated depending on execution conditions
at the time. That *really* makes our configuration management people
lose sleep at night! :-)

Thanks for the useful info on what compilers do with generics.

MDC
--
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
***To reply, remove "bogon" from the domain name.***

Visit my web page at: http://www.mcondic.com/

Re: performance of Generic and strings

[Martin Dowie]

Rational can do either and you can specify which either via switches
(environment variables) or a (non-standard) pragma. the default set is
for macro expansions. and they advise that trying to use shared bodies
may result in inefficient code.

Robert Dewar wrote:

> 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.

Re: performance of Generic and strings

[Robert Dewar]

In article <37B4335E.7A69258B@dowie-cs.demon.co.uk>,
  Martin Dowie <martin@dowie-cs.demon.co.uk> wrote:
> Rational can do either and you can specify which either via
switches
> (environment variables) or a (non-standard) pragma. the
default set is
> for macro expansions. and they advise that trying to use
shared bodies
> may result in inefficient code.

I trust you are referring to the new Ada 95 Rational technology
here (certainly the Ada 83 Rational technology did do generic
sharing). If Rational allowes full generic sharing in Ada 95,
it is certainly not suprising that they warn that shared bodies
may cause inefficient code :-)


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

Re: performance of Generic and strings

[Martin Dowie]

depends what you mean by 'new' ;-) - we've been using this version of
Apex for about a year, and indeed the old Ada83 R1000 we used all those
years ago, didn't offer this (or at least i never came across it in the
manuals!).

Robert Dewar wrote:

> In article <37B4335E.7A69258B@dowie-cs.demon.co.uk>,
>   Martin Dowie <martin@dowie-cs.demon.co.uk> wrote:
> > Rational can do either and you can specify which either via
> switches
> > (environment variables) or a (non-standard) pragma. the
> default set is
> > for macro expansions. and they advise that trying to use
> shared bodies
> > may result in inefficient code.
>
> I trust you are referring to the new Ada 95 Rational technology
> here (certainly the Ada 83 Rational technology did do generic
> sharing). If Rational allowes full generic sharing in Ada 95,
> it is certainly not suprising that they warn that shared bodies
> may cause inefficient code :-)
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.