Re: Efficient Sequential Access to Arrays

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

On Sunday, 15 July 2012 21:03:12 UTC+1, Keean Schupke  wrote:
> On Sunday, 15 July 2012 20:48:35 UTC+1, Dmitry A. Kazakov  wrote:
> > On Sun, 15 Jul 2012 11:40:08 -0700 (PDT), Keean Schupke wrote:
> > 
> > > However in order to achieve this performance I needed to rework the arrays
> > > as the use of Indexes was too slow.
> > 
> > You have to measure it in order to know. Write two variants and compare
> > their performance.
> 
> Have done, the difference is about 10k simulations per second.
> 
> > 
> > > An example of this is lets say we are
> > > accessing element 5 from array A "A(5)" this requires a multiplication to
> > > access (base_address + index * record_size).
> > 
> > It does not, because 5 is constant.
> 
> Obviously the index is not actually a constant but the result of selecting a random element in the list. The multiplication is necessary for finding this first element, but the operations on relative elements (+/-1, +/-2 etc) can use addition with a pointer, not so with an index.
> 
> > 
> > > To access the neighbour A(6)
> > > also requires a multiplication. Accessing the array sequentially requires
> > > a multiplication per step. 
> > 
> > That depends on loop optimizations. I would expect GCC to optimize access
> > to array elements per the loop's index.
> 
> It does not seem to, I'll see if I can post some assembly.
> 
> > 
> > > So assuming we need this level of performance, what would be the best (and
> > > most idiomatic Ada)
> > 
> > Indexing is unlikely to have a significant (>5%) influence on overall
> > performance. Usually it is other things.
> 
> It seems to have an significant influence in the benchmarks I have run and has a particular influence when sequentially accessing elements.
> 
> > 
> > > way to package this type of usage pattern as an
> > > abstract datatype?
> > 
> > Array of aliased elements, to ensure elements independently addressable.
> 
> Yes, the type itself will need to have aliased elements, but I was assuming this would be hidden in a package as an ADT, and would expose an indexed-iterator that has '+' and '-' operations on the iterator (not just a forward or bidirectional iterator).
> 
> 
> Cheers,
> Keean.


So, looking at some test code, with simple loop bounds (say the range of the array or other constants) the whole loop gets optimised and unrolled. However this is not the case with more complex bounds (like random numbers needed in the monte-carlo simulation).  So with the following Ada code:


for J in S .. E loop
    Y := Y + X(J).Z;
end loop;


Where S and E are random numbers in the index range of the array and where S < E, and the array is an array of records (in this case 28 bytes long) containing the integer Z.


imul   $0x1c,%r9,%r10
add    0x48(%rsp,%r10,1),%edi


So you can see the multiplication is executed for every iteration.


Cheers,
Keean.