Re: Efficient Sequential Access to Arrays

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

On Sunday, 22 July 2012 19:41:29 UTC+1, Florian Weimer  wrote:
> * Keean Schupke:
> 
> > What is the best way to do that? The program uses extensive inlining
> > and optimisation, so individual functions are hard to find in the
> > output. By the time its compiled its about a single 32k function.
> 
> -gnatG shows you Ada-like code which is passed to the compiler
> middle-end, and -fdump-tree-all writes files showing the results of
> individual passes.

At the moment my conclusion is with the current state of the compiler, you cannot match the performance of the relative addressing version of this algorithm with indexed addressing. 

Maybe compiler technology will improve (but that's not useful right now), and maybe there's a better algorithm (but I don't know what it is).

So for the moment it looks like I am going to stick with the relative addressing as the solution that best addresses the project goals.

It seems that for simple cases the belief that the compiler can optimise array indexing to be just as fast as pointer arithmetic is true, but it does not appear to be the case for all algorithms. Certainly I seem to have one of the cases where it is not true. As all the most common operations are supported by the data structures I am using in O(1) time, I don't hold out much hope of finding a faster algorithm more suited to indexed addressing.


Cheers,
Keean.