Re: Efficient Sequential Access to Arrays

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Mon, 16 Jul 2012 03:16:09 -0700 (PDT), Keean Schupke wrote:

> On Monday, 16 July 2012 08:47:01 UTC+1, Dmitry A. Kazakov  wrote:
>> On Sun, 15 Jul 2012 13:03:12 -0700 (PDT), Keean Schupke wrote:
>> 
>> Absolute figures tell little. How big is the relative difference?
> 
> About 25% (30k with indexing, 40k with relative addressing)

Which itself looks like a problem. It takes no less than 25% of overall
performance for mere shuffling data in a task unrelated to stuff like
recoding etc. This looks wrong to me. I would look for a better
algorithm/structure.

>> Loop optimization is a tricky issue. I suspect that tiny variations of code
>> may turn it on or off. You should read GCC documentation on that subject to
>> see what is possible on which machines.
> 
> It appears GCC is unable to optimise the indexing away when the index is
> dynamic (relies on IO or PRNG for example).

You should read its documentation in order to be able to say. Consequent
indexing could be optimized as addition to the register-stored base.

>> How much operations do you have per array element? If you do basically only
>> indexing then there must be something wrong with the algorithm. Otherwise,
>> say one multiplication per 100 instructions, is nothing, especially when
>> memory access (a very slow thing) is involved.
> 
> The algorithm is highly optimised, and has been developed over several
> years. The choice of data structures is pretty good,

It does not look good when indexing takes more than 25%.

> Highly optimised code can still have good structure, using inlining and
> generics code can be elegant and fast.

Code using generics/templates is never elegant nor fast, but that is an
off-topic.

> There is nothing wrong in design terms with a forward-iterator, in fact it
> is better design from a generic point of view to expose the minimal set of
> methods to efficiently implement the required algorithm.

This is only necessary when the class of the container type is wider than
just arrays, e.g. includes other structures like lists.

If you have performance problems with arrays, which are built-in and
subject of tailored optimization, you cannot expect situation improved by
puzzling the compiler with more abstract types. That could only disable
optimization.

> To see elegant and efficient code constructed in this way see Stepanov's
> "Elements of Programming".

I am not a STL fan. 

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de