Re: Matrix Multiplication

["William B. Clodius" <wclodius@lanl.gov>]

Ted Dennison wrote:
> 
> In article <3857E220.26AE90BB@lanl.gov>,
>   "William B. Clodius" <wclodius@lanl.gov> wrote:
> > numerics question where the types are determined statically and
> > generally map to the equivalent hardware operations. In this case a
> > common performance difference between languages is the extent to which
> > the language can rely on local analyses for its optimizations, which
> > in turn mostly depends on the aliasing properties of entities in the
> > language, which in turn is most strongly influenced by the properties
> > of the arguments to procedures. In this case Ada has relatively loose
> > rules compared to some other languages, e.g., C/C++, but stronger
> > rules than Fortran, so that Ada is in principle harder to optimize
> > than Fortran. However, the difference between Fortran and Ada in this
> 
> That is a fairly accurate principle. So why did I end up finding so many
> "Ada could do better situations"? You may ask. Well there are two issues
> you missed in the above:
>   1)  In general, the more information a compiler has about the possible
> values of objects, the better it can optimize. That gives strongly typed
> languages an advantage. You may turn off the runtime checking, but the
> compiler can still assume the values will never exceed that range for
> code generation purposes.
> 
> For instance, a big issue is how much information about the possible
> values of the iteration variables the compiler has access to. The
> ability of an Ada developer to constrain his index types using subtypes
> potentially gives the compiler a trememdous boost here.

Yes it is a win, but I don't know how big a win it is compared to the
requirement in both Ada and Fortran that indexing outside the visible
indices of the array is illegal. I would expect that in the vast
majority of cases, both assumptions are equivalent. Of course what I
expect might not be what I would find.

> 
>   2)  You ignore non-local optimization issues. That's fair enough. But
> in their quest for more speed, researchers are delving into non-local
> optimizations. Ada's strong typing drasticly reduces the possible access
> paths the optimizer has to worry about for a location or value. Also, a
> lot of the language was written to allow compilers leeway in optimizing.
> For example, users aren't allowed to make assumptions about the
> parameter passing method used for subroutines except in certain
> situations. Generally the more information and freedom a compiler has at
> its disposal, the easier it will be for it to optimize.

I did not discuss non-local optimization issues, but one of your
arguments in favor of such optimizations for Ada, "users aren't allowed
to make assumptions about the parameter passing method used for
subroutines except in certain situations" is even more an argument in
favor of Fortran, which allows even fewer assumptions. That is precisely
what I meant by Ada having even stronger aliasing rules than Fortran for
arguments to its procedures. If I remember correctly, Ada requires
either copy-in/copy-out or call by reference semantics by the compiler
(without specifying the choice made) in most contexts, while Fortran
requires that code allow either copy-in/copy-out or call by reference
implementation, but does not require that the actual implementation be
consistent with either semantics, i.e. at arbitrary points in the
procedure arguments can be copied-in/copied-out without synchronizing
with other copy-ins/copy-outs. The other argument about strong typing is
not a strong argument against Fortran, as by almost any definition
Fortran is strongly typed (albeit some aspects of its typing are error
prone, e.g., implicit typing).

A better argument might be that Ada has better dataflow control
constructs than Fortran 77 and 66 (and in some aspects better than
Fortran 90, though WHERE and the more recent FORALL have their
advantages), but I don't know how strong an argument that is given that
reputedly most compilers use intermediate forms that replace those
constructs by their unstructured equivalents.

One reason I did not bring up non-local optimization is that for some
languages important cases of such optimizations are known to be NP hard
in the general case, e.g., C argument aliasing in the absence of C99's
restrict. I do not know how pertinent that is for Ada vs Fortran.

An additional problem in this discussion is that some compilers may have
a switch that in effect implements: this code has additional semantics
not specified by the standard. 

> <snip>