Fortran vs. C, and noalias: old postings, new data

[Thomas M. Breuel]

In article <221 at validgh.com> dgh at validgh.com (David G. Hough on validgh) quotes
the following facts:

   --> some benchmarcks showing that C versions of linpack run somewhat
       slower on Sun4's that FORTRAN versions]

   --> noalias may be non-negotiable, but it may be non-negligible, as I found 
       out somewhat to my surprise this week.

   --> unrolling of loops may not be as profitable in C as it is in FORTRAN:

   daxpy(n,da,dx,dy)
   double *dx,*dy,da;
   {
	   int i;
	   for(i=0;i<n;i++) dy[i]=dy[i]+da*dx[i];
   }

   dx[i+1] cannot be loaded before dy[i] is stored because dy might
   be aliased to dx+1

   --> X3J11 seems to be reluctant to include a noalias declaration
       in C

   --> if something isn't done soon, vendors will go their own way

These are important issues to be addressed by the community of
numerical C programmers who want to get out the last bit of
efficiency.

Embracing the FORTRAN notion of "noalias" is, however, probably not
the right thing to do. Many C programmers, including myself, feel
that insuring absence of aliasing is a great burden in a language
that encourages the construction of highly linked data structures.

Traditionally, some of the effects of a "noalias" construct in C have
been gotten by the introduction of explicit temporaries. This is a
tradeoff between the inconvenience of having to do a certain amount
of CSE by hand and having to worry about avoiding aliasing.

Hand optimizations of this form are completely portable, and they
are only needed in critical sections of the code. Traditionally,
C programmers have never even expected the compiler to perform
any kind of CSE.

With more modern CPU's, certain kinds of optimizations cannot
be done by hand anymore. Loop unrolling is one example. The
noalias assumption certainly solves a lot of these problems with
one simple concept. However, I feel that it is the wrong
abstraction.

For example, in the loop given above, you don't really care about the
fact that dx and dy are not aliased. In fact, if they pointed at the same
array, the code would make perfect sense. What you really want to state
to the optimizer is the fact that there are no sequential dependencies
in this loop.

A clean way of doing this is by providing a separate looping construct
with special semantics. For example, you could add a "parallel"
construct, which carries with it the implicit assumption that there
are no sequential dependencies among the loop body, or a "vectorloop"
construct, which carries with it the implicit assumption that all
sequential dependencies are lexically apparent to the compiler (a kind
of "noalias" assumption for loop bodies).

Another way of avoiding the problem of aliasing in C completely is
to make sure that all assignments are to locations such that the
compiler can determine statically that they are not aliased. This
is actually a common programming practice. For example, in the above
loop, you could have written:

   #include <malloc.h>
   double *daxpy(n,da,dx,dy)
   double *dx,*dy,da;
   {
	   int i;
           double *result=malloc(n*sizeof(double));
	   for(i=0;i<n;i++) result[i]=dy[i]+da*dx[i];
	   return result;
   }

If you think about it, this is somewhat dual to the fact that
in FORTRAN you may have to copy one of the argument arrays
in order to make sure that the aliasing restriction is satisfied.
You may quibble that that occurs less frequently--but I think
that depends on your programming style.

Writing code like the above does actually not necessarily carry much
overhead compared to the code written under the "noalias" assumption,
and while in C, you have to worry about freeing "result" explicitly
later, in C++ all that can be taken care of automatically as well.

In summary, I think providing a specialized looping construct in C and
C++ that declares absent or limited sequential dependencies is
preferable to introducing a "noalias" construct. With it, and with
techniques that C programmers have been accustomed to for a long time,
it should be possible to write numerical code that compiles as efficiently
as FORTRAN, probably even on vector architectures. The language
that you get will have a very different flavor from FORTRAN for numerical
programming, but that's OK.

Adding a general notion of "noalias" to a language with lots of
pointers and nested data structures would probably lead to chaos, and
I anticipate that once FORTRAN 90 programmers start using dynamic
allocation and pointers heavily, they will discover that it can
be difficult to ensure absence of aliasing.

							Thomas.

PS: I actually am not convinced that in the loop example that dgh
gave, aliasing is actually even responsible for inhibiting the loop
unrolling or the optimization of the unrolled loop on a Sun4.
Certainly, the arguments he gave in his original posting weren't
sufficient to support that assertion. But there are architectures
where assuming absence of sequential dependencies is, of course, a big
win.