I have heard that doing a 2D array lookup is slower than doing a 1D array lookup, and 3D array lookup is slower than 2D, and so on. It seems to me that a 2D array lookup should be the same as two 1D array lookups, and a 3D array lookup should be the same as three 1D array lookups, but people seem to think 3D array lookups are REALLY slow. So what is the truth here? Here is why I think a 2D array lookup should be the same as two 1D array lookups. Let''s say I have two arrays: int b1[10], b2[10];. I make another array: int * a[2]; a[0] = b1; a[1] = b2; Now I should be able to do a 2D array lookup like: int i = a[1][5]; However, shouldn''t this be the same as doing two 1D array lookups? I''m just doing two 1D array lookups.

I thought that even a 1D array lookup required a multiply (unless it is an array of bytes). Since an int is 4 bytes (usually), to lookup in int a[10], it has to do *(a + (i * 4)).

Another issue is, how smart is the compiler? I hear a lot of people recommend to just do it the most straightforward way, avoid all of the pointer stuff, and let the compiler convert it to that method if that will be faster.

With all of the "real" stuff that your game is probably doing--graphics, sound, physics, etc, etc--you should NOT be worrying about whether a[10][10] or a[100] is faster.

Worrying about optimizing the least important 1% of your code is simply wasted effort. You''d be better off trying to get more speed out of your rendering loop. (If you even need any, most computers are fast enough that you don''t care.)

And the multiply-by-four for integers is built in to the processor. AFAIK it takes no more time than a ''normal'' lookup

Multi dimentional array access DOES require multiple multiplies - compared to SINGLE dimention lookups - but this is completely unavoidable ... cause you have to do the multiply sometime ... the only thing you can optimize is when ... the the user wants to get item [3] [2] on a chess board ... someone has to do the mutliple to figure out that this really is item index [26] (3 * 8 + 2).

also, when the array is declared all at once it is faster, not slower, than when the arrays are built using pointers to arrays ... in which case they use multiple multiplies AND a pointer dereference per dimension.

int a1[20];
int a2[20][20];
int a2b[20*20];
int a3[20][20][20];
int a3b[20*20*20];

when you use a2b[index];

the compiler does something like: *(a2b + (index * 4))

when you use a2[x][y];

the compiler does something like:

*(a2b + (x * 80) + (y * 4))

so the [ + x * 80 ] is the extra work ... BUT this work is actually DOING SOME FUNCTION that you need, it''s comverting a number from a logical domain (rows / column) to a physical domain (single dimentional address space) ... if you try to use a2b you will find YOU writing the equivelent code to solve the problem ... so it''s NOT an optimization, it''s a functional change.

also, smart compilers do optimize out that multiply in loops - it''s just standard variable computation hoisting ... if the compiler can see that for a given inner loop a certain computation is contanst, it compute it once, prior to the loop ...

so this:

// assume this might be a nested loop - variable x is already set ... outside this code ...
for(int y=0; y<20; ++y)
cout << a2[x][y];

if the compiler cannot or does not optimze this (such as in debug mode) - then EVERY time inside the loop, the [+ x * 80] code will be done ...

but most (all I know of) modern compilers can optimize this so that the [x * 80] part is done before the loop, and is simple added in each time ... - and most compilers can go even farther and precompute the [a2 + (x * 80)] part, so inside the loop the code is JUST this:

*(precomputedSum + (y * 4))

EXACTLY the same as a one dimentional array.

quote:Original post by Anonymous Poster
With all of the "real" stuff that your game is probably doing...

Ahem... My program is a chess program, so...

quote:graphics

No graphics.

quote:sound

No sound.

quote:physics

No physics.

quote:etc, etc

Aha! You hit on one. Enhanced Transposition Cutoffs (ETC)! A decent tree searching pruning technique.

quote:you should NOT be worrying about whether a[10][10] or a[100] is faster.

Worrying about optimizing the least important 1% of your code is simply wasted effort. You''d be better off trying to get more speed out of your rendering loop. (If you even need any, most computers are fast enough that you don''t care.)

The chess board is an array. The piece lists are 2D arrays or 3D arrays, depending upon which I choose. A chess program will spend almost all of its time scanning one of these arrays (board or piece lists).

If there is a detectable difference between using a 2D array or a 3D array for piece lists, I''d like to know that. I''ll be accessing and scanning these quite a bit.

I was just thinking about one time when I turned a 2D array lookup into a single bitwise OR. Instead of doing this: a[x][y];, I did this: a[x|y];. I just modifed the values that x and y contained so it would work.

If the size of each dimension of the array was a power of two, I imagine if I wanted to take the time, I could do this for a 3D array also, right? a[x|y|z];?