Re: Efficient Sequential Access to Arrays

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

On Tuesday, 17 July 2012 10:01:59 UTC+1, Dmitry A. Kazakov  wrote:
> On Mon, 16 Jul 2012 23:40:21 -0700 (PDT), Keean Schupke wrote:
> 
> > The real problem is that each element needs to be addressed spatially (say
> > as a 2D grid) so that all 4 direct, and 4 diagonal neighbours can be
> > quickly found (using indexed-addressing), another is that we need to be
> > able to tell if any two elements are in the same group (using disjoint-set
> > union-find), and another is that we need to be able to iterate through all
> > the members of a group given any element in that group.
> > 
> > If there is a faster data structure that meets all those requirements, then I am listening.
> 
> Depends on details.
> 
> k-d trees might be worth looking.
> 
> Less known are "pyramid" structures (used in image processing, filtering,
> compression).
> 
> For image segmenting, e.g. by area growing (8th-neighbourhood), one
> sometimes uses recursive elements permutations like (1,1) (1,2) (2,1) (2,2)
> (1,3) (1,4) (2,3) (2,4). That allows to perform segmenting in strictly
> consequent order visiting each pixel once. I remember it was popular in
> PDP-11 days when integer multiplication was indeed expensive.
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de


A tree structure is going to be slower than an array for the spatial lookup part. Indexing is faster than links (I think you said so yourself). So why suggesting a linked structure to replace the array?

One reason we use links to represent the groups is that by using a cirular list we can join two groups together very quickly using an exchange. If X is any element from the first circular list, and Y any element from the second circular list we can join the two into a single circular list by doing:

T := X.Next; X.Next = Y.Next; Y.Next := T; -- or Swap(X.Next, Y.Next)

And yes, joining groups is the most frequent operation on the groups, so copying one group into the other using arrays is slower.

So 2D spatial indexing (array structure) is optimal for spatial lookup. Circular lists between element is optimal for joining groups. The link to the canonical element from the eager-union algorithm is optimal for lookup dominated disjoint set.

So you can see the data structure is already optimal for the operations frequently required. It is an array of elements that contain a next element pointer to implement a circular linked list and a canonical element pointer to identify the sub-set.

So we have the algorithm, and the data structure, which is optimal from an analytical perspective. Some observations:

- The data structure and algorithm is optimal from a machine operation perspective (if we consider the relative speeds of the machine code operations)

- If the language cannot encode this structure, it cannot get the fastest performance as the language cannot be faster than the machine code operations.

- I may have misdirected people by looking at the loop behaviour of index optimisation. In my tests it is just as fast as pointer arithmetic. The real problem is that we need to combine the circular linked list into the array and allow addressing of neighbours from the resulting pointer dereference.

All this is fine, the problem in Ada is this:

- When we lookup an element spatially by index, and then iterate through the subset members (following the next links) we lose the ability to index spatially from the next element.

- If we instead store the index of the next element instead of the link, it is slower because we have to use a relative addressing mode instead of an absolute one.

- The compiler cannot use any optimisation of the array indexing because the index comes from main-memory. It is not stepping through in sequence so it cannot use strength reduction. There is no point in reading compiler documentation, this is beyond any current optimisation technology to do this, and no amount of shuffling the code about will change this.

- doing a division to convert the address of the next node back into an index to address the neighbours does not make any sense as division is slower than multiplication.

- The conclusion is the optimal way to do this is to access the neighbours by using the 'access' stored in the next pointer, and calculate the memory location of the neighbours by address arithmetic.

- We need to package this into an ADT to hide all the address stuff so it can be unit tested and validated in isolation from the rest of the application.


Does that make sense?


Cheers,
Keean.