Fortran vs. C for numerical work (SUMMARY)

[Dan Bernstein]

In article <7200 at lanl.gov> ttw at lanl.gov (Tony Warnock) writes:
>     With respect to speed, almost all machines that I have used during
>     the last 25 or so years have had faster multiplications than
>     memory accesses.

Hmmm. What machines do you use? In my experience (mostly mainframes and
supers, some micros, and only recently a bit with minis) local memory
access is up to several times as fast as integer multiplication. (I
don't like this situation; converting to floating point just to multiply
quickly on a Cray seems rather silly.)

> Most computations access an array along one of its
>     dimensions, holding the others constant.

Yes, but just because you use pointers doesn't mean you have to give up
the advantages of flat arrays.

> There is also no storage overhead
>     associated with keeping arrays of pointers. For multi-dimensional
>     problems, this overhead could be quite large.

I assume you meant ``there is storage overhead...'' That's true, but
it's really not a problem. If you have a 5 by 5 by 2 by 3 by 15 array,
can you begrudge space for thirty pointers so that you save 5% of your
computation time? Thought so. Even if you set up pointers within
pointers for every dimension, you can do it so that the pointer space
is 1/N of the array space, where N is the widest single dimension.

>     Anyway, Dan's answer points out the performance differences in the
>     array versus pointer access stuff. Personally I just don't user
>     pointers much because my problems don't call for them. If I had to
>     access multi-dimensional arrays in random fashion very often, the
>     pointer solution might be acceptable.

But you really do access random spots in arrays; it's a rare problem
that always starts from the top left corner of every matrix. Take a
typical pivot-based algorithm, for instance: you're dealing with
essentially random rows at each step.

> How does one set up a pointer array
>     for allowing easy access along each dimension (for example in a
>     typical 5-dimensional array)?

You keep pointers to the top of each 4-dimensional hyperplane in the
array. You can get some of the benefit of this from storing integer
indexes, but you still lose at least an addition per array sweep, more
for higher-dimensional arrays if you store more pointers. Since the
sweeps run 20x faster on (e.g.) a Convex, the extra computation outside
each sweep becomes noticeable.

---Dan