Re: Efficient Sequential Access to Arrays

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

On Sunday, 22 July 2012 11:09:44 UTC+1, (unknown)  wrote:
> On Monday, 16 July 2012 04:40:08 UTC+10, Keean Schupke  wrote:
> 
> > However in order to achieve this performance I needed to rework the arrays as the use of Indexes was too slow. 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). To access the neighbour A(6) also requires a multiplication. Accessing the array sequentially requires a multiplication per step.
> 
> Have you tried turning on high optimisation?


Yes this is compiled with

test: test.adb
	rm -f *.gcda
	gnatmake -march=native -O3 -fprofile-generate -ftest-coverage -gnatp -gnatn test -bargs -shared -cargs -fdata-sections -ffunction-sections -largs -Wl,--gc-sections
	./test
	touch test.adb
	gnatmake -march=native -O3 -fprofile-use -gnatp -gnatn test -bargs -shared -cargs -fdata-sections -ffunction-sections -largs -Wl,--gc-sections


> 
> If you are accessing elements sequentially,
> the optimiser will probably not do multiplications,
> but instead access successive elements by means of additions.


It is difficult to say if lack of this optimisation is the cause of the slowness.

What does seem to be the case is that storing the index of the next element of a linked list is slower than storing the address.


> 
> Other factors may be relevant:
> 1. For example, if the size of a
>    record is small-ish, the compiler may use shifts and/or
>    adds/subtracts instead of multiplications.
> 
> 2. The hardware multiplier may be one of the fast kind,
>    in which case the time is negligible.


The target (achieved by the relative addressing code) is 57,000 simulations per second. Currently the fastest version using array indexing is 42,000 simulations per second. 36% is too big a difference to ignore, and this is a real world problem not a benchmark. So I am looking for ideas to improve the array indexing version. 

I am not sure what is the cause of the speed difference, it may not be the actual array index lookup time, but a consequence of using array lookup where the other version uses direct addressing (pointer dereference with no offset).


Cheers,
Keean.