From: jlg@cochiti.lanl.gov (J. Giles)
Subject: Re: Reasons for using C vs. Fortran or vice/versa
Organization: Los Alamos National Laboratory
Distribution: usa
Date: Fri, 13 Nov 1992 19:12:49 GMT

In article <1992Nov13.043250.28205@sbcs.sunysb.edu>, rhorn@csws8.ic.sunysb.edu (Robert Horn) writes:
|> rons@hardy.u.washington.edu (Ronald Schoenberg) writes:
|> >  Fortran arrays are column echelon for a
|> >reason, and C arrays are row echelon slowing down matrix operations
|> >relative to Fortran.     
|> 
|> Wouldn't FORTRAN arrays actually be slower? consider the normal
|> 
|>   for(index = 0; index < kRows; index++) {
|>     for(jndex = 0; jndex < kColumns; jndex++) {
|>       myArray[index][jndex] ...
|>     }
|>   }
|> 
|> one normally accesses matrices in a row major fashion [...]

No.  One normally switches back and forth and accesses arrays in
row-major order, column-major order, sergent-major order, etc. in 
different parts of the program.  Consider the typical matrix multiply: 
at least one of the three arrays (two operands and a result) will
be traversed in each of the two (row- vs. column-major) orders.

Further, striding by constant amount on most machines is equally
fast regardless of whether the stride is one or more than one.

|> [...]                                                  (index changes less
|> often than jndex), so if your array is stored row major, and your cache is
|> nice enough to bring in the words around what you need (since you may well
|> access these as well), [...]

In a cached machine, the choice of order can effect speed.  However, as
I pointed out, the choice of order is more often dictated by what you're
doing.  *AND* if either order is acceptable in you algorithm (as in your 
example above), the *user* is perfectly free to nest the loops in whatever 
order is best - or to declare the arrays with their indices reversed.

|> [...]         Also, the compiler can compute myArray[index] at the top of
|> the loop and use an offset from that to compute the location of the jndexth
|> element.  [...]

Yes, that trick *is* applied to Fortran loops regardless of what 
the stride on the inner loop is - and has been for 30 years.

|> [...]
|> I've always heard that column major matrices were one of the stupidest aspects
|> of FORTRAN.

I've always *known* the choice was arbitrary.  It is somewhat
less than completely irrelevant as a *speed* issue.

Among *bad* choices for array implementation are the idea that 
multidimensional arrays are the same as arrays-of-arrays (and 
choosing a notation which maintains this pretence) and converting 
arrays to raw pointers when passing them as arguments: both properties 
C arrays have.  The *real* array slowdown comes from the fact that 
pointers passed into a procedure as arguments in C are allowed to be 
aliased and little or no optimization can occur when such aliasing 
*might* be present.  Fortran array arguments are (internally)
passed much the same way, but Fortran doesn't allow the arguments
to be aliased - so in Fortran all the usual optimizations can be
applied always.  To be sure, neither language allows the best
solution of allowing the user explicit control over whether 
aliasing is present or not.

-- 
J. Giles
Newsgroups: comp.lang.c