Re: Efficient Sequential Access to Arrays

[Keean Schupke <keean.schupke@googlemail.com>]

On Wednesday, 25 July 2012 08:09:09 UTC+1, Niklas Holsti  wrote:
> On 12-07-24 19:00 , robin vowels wrote:
> > On Monday, 23 July 2012 03:34:26 UTC+10, Niklas Holsti  wrote:
> >> On 12-07-22 19:21 , Florian Weimer wrote:
> >> > * Keean Schupke:
> >> >
> >> >> So assuming we need this level of performance, what would be the
> >> >> best (and most idiomatic Ada) way to package this type of usage
> >> >> pattern as an abstract datatype?
> >> >
> >> > You should look at compiler dumps to figure out why the strength
> >> > reduction optimization does not kick in.
> >> >
> >>
> >> As I understand it, the program is accessing A(I,J), where A is a 2D
> >> array, and also accessing A(I+1,J), A(I,J+1), and the other neighbours
> >> of A(I,J), eight in all.
> >>
> >> I,J are indices that are *not* traversed in sequential order, but in
> >> some scattered order.
> >>
> >> Computing the address of A(I,J) involves multiplications of J and I with
> >> the size of an array element and the size of an array row, respectively.
> >> The problem seems to be that the results of these multiplications are
> >> not reused in computing the address of A(I+1,J) etc.
> >>
> >> If the index constraints (or at least the row length) of A are static
> >> (compile-time) constants, and the address of A(I,J) has been computed,
> >> and c1 and c2 are some other compile-time constants (-1, 0, +1 in this
> >> program), then the address of A(I+c1,J+c2) can be computed by adding a
> >> static offset to the address of A(I,J). This is what happens when A(I,J)
> >> and the neighbours are accessed through a C pointer, or when Keean uses
> >> address arithmetic explicitly in the Ada program. The question is why
> >> the Ada compiler is not doing this optimization.
> >>
> >> As I understand it, "strength reduction" is a loop optimization where an
> >> expression of the form C*i, with "i" the loop index, is replaced by a
> >> new variable that is incremented by C on each loop iteration. But in
> >> Keean's program the indices I,J are not loop indices, nor linearly
> >> related to loop indices.
> >>
> >> The optimization that would be required here is to replace (X+C)*F by
> >> X*F+C*F, when C and F are static constants and X*F has already been
> >> computed and is available. This would replace the multiplication by an
> >> addition of a static constant. I've never seen this special kind of
> >> optimization proposed or described.
> >
> > I think that it's a standard optimisation.
> 
> I'm willing to be convinced of that. But it seems that GNAT/GCC is not 
> performing this optimization in Keean's program.
> 
> > For the PL/I optimising compiler for the CDC Cyber (c. 1980),
> > multiplication was eliminated for matrix elements
> > by using a table of offsets into each row.
> > Thus, double subscripting reduced to simple addition.
> 
> That sounds like a specific choice of code generation for arrays, rather 
> than a general optimization.
> 
> Keean could simulate this code by defining the array as a 
> one-dimensional array of one-dimensional arrays (rows), which would 
> replace the row-length multiplication by an additional indexing.
> 
> >> (We are of course (I believe) assuming that index range checks are
> >> turned off.)
> >
> > Index range checks should be left on.
> 
> Sure, in general. But here the OP (Keean) is trying to beat the 
> performance of C++ that uses pointers without index checks. Enabling 
> index checks in the Ada code would probably (in this case, where the 
> algorithm has scatterered indexing of the array) slow it by an amount 
> that swamps the effect of the multiplication optimization.
> 
> -- 
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
>        .      @       .

On the specific point of array index checking, if you can statically prove the algorithm using the array will never use an out of range index, there is no need to run-time index check.

If we generate a random number between one and N, and then lookup the Nth element, we do not need to range check as the number is by definition in range. If the type system can carry such proofs (for example using range types in Ada) so you have:


subtype Idx is Integer range 1 .. 10;
type Arr is array (Idx) of Integer;  
function Random returns Idx;
A : Arr;
A(Random); -- as the random number is already in the range there needs to be no range checks on the array lookup.


I don't know how good the compiler is at doing this?

There are times when the programmer can guarantee that the output of a function will be within range due to extensive unit testing and validation.


I wonder, is there a way to get the compiler (GNAT) to issue a warning when it has to insert a range check?


Cheers,
Keean.