* performance of Generic and strings @ 1999-08-11 0:00 Thomas Rutström 1999-08-11 0:00 ` Marin David Condic ` (2 more replies) 0 siblings, 3 replies; 12+ messages in thread From: Thomas Rutström @ 1999-08-11 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-11 0:00 performance of Generic and strings Thomas Rutström @ 1999-08-11 0:00 ` Marin David Condic 1999-08-11 0:00 ` Robert Dewar 1999-08-11 0:00 ` Robert Dewar 1999-08-11 0:00 ` Michael F. Yoder 2 siblings, 1 reply; 12+ messages in thread From: Marin David Condic @ 1999-08-11 0:00 UTC (permalink / raw) 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/ ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-11 0:00 ` Marin David Condic @ 1999-08-11 0:00 ` Robert Dewar 1999-08-11 0:00 ` Marin David Condic 0 siblings, 1 reply; 12+ messages in thread From: Robert Dewar @ 1999-08-11 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-11 0:00 ` Robert Dewar @ 1999-08-11 0:00 ` Marin David Condic 1999-08-13 0:00 ` Robert Dewar 0 siblings, 1 reply; 12+ messages in thread From: Marin David Condic @ 1999-08-11 0:00 UTC (permalink / raw) 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/ ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-11 0:00 ` Marin David Condic @ 1999-08-13 0:00 ` Robert Dewar 1999-08-13 0:00 ` Martin Dowie ` (2 more replies) 0 siblings, 3 replies; 12+ messages in thread From: Robert Dewar @ 1999-08-13 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-13 0:00 ` Robert Dewar @ 1999-08-13 0:00 ` Martin Dowie 1999-08-14 0:00 ` Robert Dewar 1999-08-13 0:00 ` Richard D Riehle 1999-08-13 0:00 ` Marin David Condic 2 siblings, 1 reply; 12+ messages in thread From: Martin Dowie @ 1999-08-13 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-13 0:00 ` Martin Dowie @ 1999-08-14 0:00 ` Robert Dewar 1999-08-16 0:00 ` Martin Dowie 0 siblings, 1 reply; 12+ messages in thread From: Robert Dewar @ 1999-08-14 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-14 0:00 ` Robert Dewar @ 1999-08-16 0:00 ` Martin Dowie 0 siblings, 0 replies; 12+ messages in thread From: Martin Dowie @ 1999-08-16 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-13 0:00 ` Robert Dewar 1999-08-13 0:00 ` Martin Dowie @ 1999-08-13 0:00 ` Richard D Riehle 1999-08-13 0:00 ` Marin David Condic 2 siblings, 0 replies; 12+ messages in thread From: Richard D Riehle @ 1999-08-13 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-13 0:00 ` Robert Dewar 1999-08-13 0:00 ` Martin Dowie 1999-08-13 0:00 ` Richard D Riehle @ 1999-08-13 0:00 ` Marin David Condic 2 siblings, 0 replies; 12+ messages in thread From: Marin David Condic @ 1999-08-13 0:00 UTC (permalink / raw) 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/ ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-11 0:00 performance of Generic and strings Thomas Rutström 1999-08-11 0:00 ` Marin David Condic @ 1999-08-11 0:00 ` Robert Dewar 1999-08-11 0:00 ` Michael F. Yoder 2 siblings, 0 replies; 12+ messages in thread From: Robert Dewar @ 1999-08-11 0:00 UTC (permalink / raw) > 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: performance of Generic and strings 1999-08-11 0:00 performance of Generic and strings Thomas Rutström 1999-08-11 0:00 ` Marin David Condic 1999-08-11 0:00 ` Robert Dewar @ 1999-08-11 0:00 ` Michael F. Yoder 2 siblings, 0 replies; 12+ messages in thread From: Michael F. Yoder @ 1999-08-11 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~1999-08-16 0:00 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1999-08-11 0:00 performance of Generic and strings Thomas Rutström 1999-08-11 0:00 ` Marin David Condic 1999-08-11 0:00 ` Robert Dewar 1999-08-11 0:00 ` Marin David Condic 1999-08-13 0:00 ` Robert Dewar 1999-08-13 0:00 ` Martin Dowie 1999-08-14 0:00 ` Robert Dewar 1999-08-16 0:00 ` Martin Dowie 1999-08-13 0:00 ` Richard D Riehle 1999-08-13 0:00 ` Marin David Condic 1999-08-11 0:00 ` Robert Dewar 1999-08-11 0:00 ` Michael F. Yoder
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox