From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f891f,eac70c5fad02d925 X-Google-Attributes: gidf891f,public X-Google-Thread: 1094ba,c6e2c9477ddee2a6 X-Google-Attributes: gid1094ba,public X-Google-Thread: 103376,eac70c5fad02d925 X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) Subject: Re: Concerning subscript bounds checks Date: 1996/06/27 Message-ID: <4qtgfi$hfa@goanna.cs.rmit.EDU.AU> X-Deja-AN: 162333205 references: <4qdj3e$btf@goanna.cs.rmit.EDU.AU> <4ql9eq$hdt@goanna.cs.rmit.EDU.AU> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.ada,comp.lang.misc,comp.lang.fortran nntp-posting-user: ok Date: 1996-06-27T00:00:00+00:00 List-Id: clodius@hotspec.lanl.gov (William Clodius) writes: >In article <4ql9eq$hdt@goanna.cs.rmit.EDU.AU> ok@goanna.cs.rmit.EDU.AU >(Richard A. O'Keefe) writes: > I call that a _good_ result. (The 4 subscripts that aren't quite so > obvious are executed with low frequency, and only the upper bound is > not obviously safe.) >But the comparison is not complete as it is done only one way. Er, *what* comparison? Nowhere did I state or imply that Ada was *better* than Fortran. All I stated, and all I meant to imply, was that - in an algorithm whose original coding DID NOT HAVE ADA IN MIND - it fell out quite naturally - that almost all of the subscripts in the Ada version - OBVIOUSLY don't need checking - using only local information >Did you check to see what an equivalent algorithm >would do on the original F77 code? How would it do if rewritten in >F90 stle? There are two difficulties with doing this kind of thing in Fortran. (1) My Ada procedure is generic, mainly because I wanted it to be valid Ada 83, and that was the only way to pass a function. But having done that, it was possible to have a generic formal array type as well. generic type Coord is digits <>; type Index is (<>); type Point is array (Index) of Coord; type Value is digits <>; with function Funct(X: in Point) return Value; procedure Nelder_Mead( Start : in Point; Step : in Point; DevMin : in Value; Konvge : in Positive; Kcount : in Natural; Ncalls : out Natural; Nrestarts: out Natural; Xmin : out Point; Ymin : out Value; Good : out Boolean ); This means that if the Index bounds happen to be static, the Ada compiler can know what they are when generating code for an instance of the body. The Fortran version starts out like this: SUBROUTINE NELMIN(FN, N, START, XMIN, YNEWLO, REQMIN, STEP, * KONVGE, KCOUNT, ICOUNT, NUMRES, IFAULT) REAL FN INTEGER N REAL START(N) REAL XMIN(N) REAL YNEWLO REAL REQMIN REAL STEP(N) INTEGER KONVGE INTEGER KCOUNT INTEGER ICOUNT INTEGER NUMRES INTEGER IFAULT In F77, I cannot declare a local array of the same size as XMIN. (One Nelder-Mead subroutine I've seen handled that by assuming that N <= 20 and using fixed-size local arrays; another required the caller to pass workspace.) In F90, I can. (2) The loop control variables in Fortran, whether F77 or F90, are not tied to the array bounds. They are INTEGER, not Index. Point (2) is not actually a difficulty for the obvious algorithm, in which (scalar) variables start out with with the empty set as their possible interval, and the set is expanded as necessary. The key point is that the form of the Ada loop makes it _obvbious_ without any data flow analysis at all that a subscript is safe. If you have P: array (Simplex_Range) of Point; Pstar, Pbar: Point; ... for I in Point'Range loop PStar(I) := PBar(I) + (P(Hi)(I) - PBar(I)) * (-Reflection); -- # # # # end loop; then it is obvious that each of the flagged subscripts is safe. These particular subscripts, of course, would vanish entirely in APL, PL/I, or Fortran 90: PSTAR = PBAR + (P(Hi,*) - PBAR)*(-REFLECTION); /*PL/I*/ Now, I _already_ eliminated a lot of these from my count, because I wrote some inline subprograms to do special bits of vector arithmetic. Point (1) _is_ a significant difference between Ada and Fortran 90. In this particular example, it doesn't matter so much, because the simple rule "if a subscript is a loop identifier and the range of the loop identifier is the same as the range of that subscript, then no subscript check is needed" works very well. This is what I mean by the check being local. The Fortran equivalent would be "in A(...,I,...) where A was declared to have dimensions (...,L:U,...) and the definition of I that is live at this point is from DO[]I = L,U, no subscript check is needed for I." In the two Fortran versions, - the version with fixed size local arrays would need a smart compiler to notice that "IF (N .GT. 20)" the subroutine exits at once, so that it can assume N <= 20 elsewhere. - the version with workspace provided by the caller needs _two_ size parameters, N and N1 (= N+1), and the compiler doesn't _know_ that N1 = N+1 (because it isn't told, and in F77, cannot be told). A Fortran 90 version would not have these problems. Just to go over the main point one more time, I was *not* saying that Ada is *better* than anything else, only that even the simplest of local- information-only rules is *good* for Ada numeric code. For what it's worth, here are some times: -- Original Fortran results on a 36-bit DEC-2060 -- Function NCalls NRestarts Value of Min Time -- 1 177 0 1.67E-9 T1 msec -- 2 266 0 4.03E-9 230-T1 msec -- 3 230 0 2.79E-9 T2 msec -- 4 712 14 5.75E-14 640-T2 msec -- My Fortran results on a 32-bit SPARC -- Function NCalls NRestarts Value of Min Time -- 1 177 0 1.0E-9 0.43 msec -- 2 213 0 2.0E-8 0.88 msec -- 3 230 0 6.3E-9 1.1 msec -- 4 666 13 7.1E-14 5.8 msec -- Compiled with "f77 -native -fast -stackvar -O3" -- My Ada results on a 32-bit SPARC -- Function NCalls NRestarts Value of Min Time -- 1 177 0 1.79E-9 0.40 msec -- 2 213 0 1.98E-8 0.94 msec -- 3 231 0 3.24E-9 2.3 msec -- 4 736 17 9.54E-14 6.9 msec -- Compiled with "gnatmake -cargs -gnatp -O3 -Wall" The SPARC results were obtained on a SPARCstation-10 (sunm4) running Solaris 2.5, f77 SC4.0, gnat 3.04, gcc 2.7.2. Oddly enough, it was much easier to rewrite the Fortran code to Ada than to re_type_ the Fortran code and get it working. It was only when I noticed the "-XlistE" flag in Sun's f77 that I made any progress with the Fortran version. Static checking helps a _lot_. Why the big difference for function 4? I've no idea. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.