Finding the address of an array element

[Karlos]

One way of creating fast multidimensional lookups (ie without multiplication involved) is to create a table of pointers to pointers. This requires more memory (to hold the pointer table) but then you can get a simple lookup technique.

For example, a dynamic 2D array can be set up as follows

/* create our contiguous block memory for the objects */

size_t i;
size_t numRows = ....;
size_t numCols = ....;

Type* data = 0;
Type** rowPointer = 0;

Type* data = (Type*)malloc(sizeof(Type)*numRows*numCols);

/* create our row lookup */
Type** rowPointer = (Type**)malloc(sizeof(Type*)*numRows);

/* Fill the row lookup table */
for (i=0; i{
    rowPointer = &data[i*numCols];
}

/* Now, the rowPointer table contains the offsets to the start of each 'row' in our main data array, so we can access by lookup without multiplication */

Type* p = (rowPointer[rowIndex])[columnIndex];

The principal drawback of this is that you need to allocate space for the rowPointer table. This is usually a lot smaller than the main data however (each entry is just 4 bytes typically), so you might not worry about this.

[Agafaster]

Personally, I wouldnt bother - you'll only confuse yourself !

stick to 1 or 2 dimensional arrays where the index maths is much easier - if you need more dimensions, have several 1 or 2 d arrays of the same size:

ie:
int x[1000], y[1000], z[1000];

for 3d objects, etc you could use this:

typedef coord struct {int x, y, z };

coord array[1000];

in effect an array of structures.
the coords can then be accessed like this :

px = array[123].x;

etc. or

int curr_ind = 123;
ptr_curr_x = array + curr_ind * sizeof(coord);
ptr_curr_y = array + curr_ind * sizeof(coord) + sizeof(int);
ptr_curr_z = array + curr_ind * sizeof(coord) + 2 * sizeof(int);


This last approach can quite neatly be expanded for any number of dimensions.
why do you need lots of dimensions ? complicated Tensor Analysis ?  :-D

[Karlos]

@AgaFaster

That's fine for statically sized information, but when you have a dynamically allocated multidimensional array of objects (any kind) where each dimension is initialised with a runtime variable you need to get dirty with pointers.

Also, look at your ptr_curr_z expressions etc. These still involve N-1 multiplications per access which can be a serious overhead in critical areas.

[jdiffend]

Off the top of my head I'd say the only simple  :-?  way I can think of to do this is to write a recursive routine where it calls itself to calculate the previous dimension and bases it's calculation off of that which is based on the previous dimension and so on.  It will handle as many dimensions as your stack space will allow for the recursion.  This is also limited by the maximum value your pointer can handle.

You'd need the index within each dimension, the size of that dimension and the sizeof the object you are storing in that nth dimensional array.  They would need to be stored in an array, string, or whatever to be read by the recursive routine.  So, if you want a n dimensional array with each dimension having it's own size you would need an array kinda like this:
//n is number of dimensions
object_position[n] = {27, 2000, ... 100}; // where you have a position within each dimension
dimension_size[n] = {
  {size_n0},
  {size_n1},
  ...
  {size_nn}
}  // where you have the size of each dimension


The dimension size is the return value and the actual pointer is static so offsets are added to it as the calculation goes along.  You pass the recursive routine the the index into the dimension_size array which subtracts one and calls itself until it's zero.  Then calculations start and returns commence.

But that's just off the top of my head.  :-D

[jdiffend]

[jdiffend]

Oh, one more thing.  If you just set up the recursive routine to calculate the offset rather than an actual pointer you just use ArrayBaseAddress + (offset * sizeof(array_element)) to get the actual memory address.

This will actually be faster than doing the calculation in the recursive routine.

The recursive routine is basicly an n to 1 dimensional array index converter.

Hmmmm.... if you typecast it to a 1 dimensional array you could use something more like this to access it:
array1D[offset]

[Sidewinder]

Thank you for all of your help.  I used the offset approach that jdiffend advised and was able to implement a loop to compute the offset and then add it to the base address.  Simply using a bunch of 2D arrays or somthing was not an option because I'm designing a programming langauge and do not wish to impose silly limits on such things when a little time and  thinking could offer a more flexable solution.  Thanks to everyone who helped.  

[samdu]

Am I the only one that feels really stupid after reading this thread?

[jdiffend]

Um... brain fart on my part... no recursion needed.  Just use nested loops.  DU-OH!
(recursion is slower than an iterative approach)

Glad I could help.

[carls]

@samdu
No :-)
I tried to look cool by using the word "pointer" but noone commented my post so I guess I was very wrong :-?

[Sidewinder]

@ everybody

So as not to be contrary here is the routine that I came up with.  No problems yet, but only time will tell.    ;-)

/* number_of_dimensions is an int that holds the number of dimensions of the array (clever eh?), i is the standard counter variable.  address holds the memory location.  The element_values[] array is number_of_dimensions in size and holds the desired position of the element that we wish to address : i.e. (2,4,1,5) .  The max_element_size[] array is also number_of_dimensions in size but it holds the maximum values of each of the dimensions: i.e. (10,10,10,10).

i = number_of_dimensions;
place_value = 1;
address = element_values;
i, element_values, address);
i--;

while (i >= 0)               /* While there are more dimensions to calculate. */
{
   place_value *= max_element_size[i + 1];

   address += element_values * place_value;
   
   i--;
}

address *= type_size;
address += base;

And that's about it.

Cheers.

[FluffyMcDeath]

If you do this often, you may be doing too many multiplications. How about adding another array to keep track of the stride of each dimension, then calculate the values at the time of array creation.

i.e. you add
stride[0] = 1; // single element always is one wide!
for (i=1;i  stride = stride[i-1] * max_element_size[i-1];

// then go through again to mult in the sizeof()
for (i=1;i  stride *= type_size;

//Now you can find your address with
address = base;
for (i = 0; i  address += element_values * stride;

which will save on multiplies as the dimensions grow and ... should compile to better code on G4 with an Altivec aware compiler!!! :-)
 

[Sidewinder]

@ Fluffy

Great idea.  I hadn't considered that.  I think I'll give it a try straight away/