Re: Pointer Arithmetic (was: Wanted: Ada STL....)

[adam@irvine.com]

In article <36B78CDD.1372@lanl.gov>,
  William Clodius <wclodius@lanl.gov> wrote:

> For most machines in use the most efficient implementations of arrays is
> as a single contiguous block that is accessed by mapping indices
> directly to the equivalent pointer operations. (The exceptions are more
> easilly mapped to arrays and not to pointers.) It is true that mapping
> involving an index other than the most rapidly varying one can be
> thought of as involving a multiplication, but the same is true of the
> equivalent pointer arithmetic. In both cases the same functionality can
> be obtained by adding a (n easilly determined)  finite integer to the
> current memory index. The analysis for the compiler to do this is so
> simple, I would not be surprized if Ada Lovelace discussed it for
> Babage's machine in the 1800s.  Any compiler that does not perform that
> analysis is broken.
>
> It is sometimes thought that because it is relatively easy for the
> programmer to move some of the pointer arithmetic outside the loop, that
> pointer arithmetic is more efficient, but the algorithms necessary to
> perform that motion by the compiler have been available since the first
> Fortran compiler, ca. 1957. Any compiler that does not perform that
> analysis is a toy and not a professional system. It is more likely that
> a programmer will not perform the necessary analysis for the pointers,
> than that a compiler will not perform the analysis.

I'm not quite following everything you say.  I agree that if you're using
the index variable inside a FOR loop, it should be easy for the compiler to
optimize the index operations so that no multiplication is used, e.g.

    for I in Arr'range loop
        Do_Something_With (Arr (I));
    end loop;

But what if the operation of stepping through the array isn't so neatly
packaged?  Note that while I was talking about stepping through an array,
I never said anything about this stepping taking place inside a single loop.
It's certainly conceivable (if you have a package that declares
an iterator, for example) that the index manipulation might not even be
handled within the same subprogram call.  You might have to provide a
routine that steps to the next element of the array, then saves the index
in a global variable or an object's "work area" before the subprogram exits,
and then use the saved index the next time the subprogram is called.  It
seems to me that it would be a lot harder for a compiler to perform the
analysis required to determine that the index should be implemented with
pointer arithmetic.  Granted, when a program starts getting this complex,
it's hard for me to come up with a real-life example where the few nanoseconds
saved by avoiding multiplications would really make a difference.

				-- Adam

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own