Re: Efficient Sequential Access to Arrays

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

On Sunday, 22 July 2012 18:34:26 UTC+1, 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.
> 
> (We are of course (I believe) assuming that index range checks are 
> turned off.)
> 
> -- 
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
>        .      @       .

That's some of it, the other part is that sometimes the 'scattered order' is from following a linked list between elements. So A1(I, J) is computed from a PRNG, and we access A1(I, J) and may access all or none of A1(I, J-1), A1(I-1, J), A1(I+1, J), A1(I, J+1) and all or none of A1(I-1, J-1), A1(I+1, J-1), A1(I-1, J+1), A1(I+1, J+1). We may also access the 'canonical' element of the subset A* which in the fast code is a link and the neighbours addresses calculated from the link address, and all the elements in the subset (A2, A3, .. AN) and each of their horizontal and vertical neighbours.

So with the relative addressing code, stepping through the subset is dereference link, add constant[+/- row_size * element_size] and constant[+/- element_size] to access the neighbours, then dereference next link etc. The size of the array are generic parameters, so I presume the constants get pre-calculated at elaboration time.

With the indexed version, it is storing the index of the canonical element of the subset, and the index of the next element in the subset instead of the address.

Does that help determine if it is going to be possible to get better performance from the array indexed version?


Cheers,
Keean.