Re: Efficient Sequential Access to Arrays

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

I have re-implemented the code to use array indexing, but with the improvements I made in the profile-guided thread. The indexed code does not use 'access' variables at all, but uses 'renames' and 'in out' functions (from Ada-2012), except for the one function discussed below.

Current performance is:

Relative Addressing code 57,000 simulations per second
Array Indexing code 42,000 simulations per second

So the relative addressing code is 36% faster. I have some ideas to improve the array indexed version, as the element size is no longer a power of two that may be having some affect. I can also pack the data structure tighter as I think I can fit it in 16 bytes now I only have to store two 16bit indexes instead of two 64bit addresses. 

In rewriting this code I came across the following issue, that I have not yet found a totally satisfactory solution to. I have an ADT representing the disjoint set, but the element stored in it is limited and I cannot return it from a function. I have several options:

1) throw away structured programming and make everything happen in one package directly on the array, hurting readability, understandability, maintainability and losing the ability to separately test and validate the code.

2) make the array part of the public interface for the package, breaking encapsulation and the ability to separately test and validate the code.

3) return an access, however to avoid an access level violation I have to pass an access to the ADT into this function instead of the ADT itself.

Ignoring performance which is the best way to structure this? Is there another way I have missed?


Cheers,
Keean.