Re: Concerning subscript bounds checks

[ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe)]

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.