Doubt-Efficiecy of 3D arrays

[chella mani]

hi all,

I am developing a tool for scientific application which must be time
and memory efficient,my tool uses 1D,2D and 3D arrays. Is it a good
practice to use 3D arrays in applications or I should use convert my
3D arrays to 1D arrays for efficiency.
Thanks in advance,
Chella mani

[Tim Prince]

"chella mani" <ch********@gma il.com> wrote in message
news:90******** *************** ***@posting.goo gle.com...

hi all,

I am developing a tool for scientific application which must be time
and memory efficient,my tool uses 1D,2D and 3D arrays. Is it a good
practice to use 3D arrays in applications or I should use convert my
3D arrays to 1D arrays for efficiency.

If you can avoid repeated non-sequential access to your data by copying them
over to another array, that should improve efficiency. For example, matrix
multiply should go faster if one of the operands is transposed, in order to
use dot products with stride 1. It needn't be written as a 1D array.
Making your program obscure could ruin the efficiency of your development.

[Flash Gordon]

On Mon, 20 Sep 2004 06:34:03 GMT
"Tim Prince" <tp*****@nospam computer.org> wrote:

"chella mani" <ch********@gma il.com> wrote in message
news:90******** *************** ***@posting.goo gle.com...

hi all,

I am developing a tool for scientific application which must be time
and memory efficient,my tool uses 1D,2D and 3D arrays. Is it a good
practice to use 3D arrays in applications or I should use convert my
3D arrays to 1D arrays for efficiency. If you can avoid repeated non-sequential access to your data by
copying them over to another array, that should improve efficiency.

Actually, it is very dependant on the compiler and processor. A compiler
is likely to convert a 3D to a calculated pointer access. Then it can do
strength reduction of multiplication to repeated addition if you are
looping over the array (and yes, I have seen compiler documentation
listing this as one of the optimisations) and so you are down to what
you would have had if you had implemented it as a 1D array.
For example, matrix multiply should go faster if one of the operands
is transposed, in order to use dot products with stride 1. It needn't
be written as a 1D array.
Making your program obscure could ruin the efficiency of your
development.

Agreed. Write your code to be understandable otherwise it will be hell
trying to get something that works.

For something like this I would first worry about writing an algorithms
document detailing all the algorithms and the optimisations to the
algorithms. The only low level optimisation I would do is making sure
that for nested loops to scan the 2D and 3D arrays are ordered such that
it is just stepping through memory where possible. I.e. (if I'm not
going mad)

double a[5][5][5];
int x,y,z;
for (x=0; x<5; x++) {
for (y=0; y<5; y++) {
for (z=0; z<5; z++) {
/* Do stuff with a[x][y][z] */
}
}
}

However, what's fastest for your particular implementation is OT here.
--
Flash Gordon
Sometimes I think shooting would be far too good for some people.
Although my email address says spam, it is real and I read it.

[SM Ryan]

ch********@gmai l.com (chella mani) wrote:
# hi all,
#
# I am developing a tool for scientific application which must be time
# and memory efficient,my tool uses 1D,2D and 3D arrays. Is it a good
# practice to use 3D arrays in applications or I should use convert my
# 3D arrays to 1D arrays for efficiency.

Whether you use A[i][j][k] or A[i*m*n+j*n+k], you're still using three dimensional
arrays. If your model doesn't permit abstraction to higher order features, but must
be some variant if three dimensional celluar automata, then it is what it is. Then the
best you can get is to access the elements to minimise page faults and cache trashing.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
There are subtler ways of badgering a witness.

[Felipe Magno de Almeida]

chella mani wrote:

hi all,

I am developing a tool for scientific application which must be time
and memory efficient,my tool uses 1D,2D and 3D arrays. Is it a good
practice to use 3D arrays in applications or I should use convert my
3D arrays to 1D arrays for efficiency.
Thanks in advance,
Chella mani

make your code readable, and let the optimization to the compiler, if
you REALLY want optimization, then use assembly, but even in assembly it
is very difficult to make it faster than the compiled code.

--
Felipe Magno de Almeida
UIN: 2113442
email: felipe.almeida@ ic unicamp br, felipe.m.almeid a@gmail com
I am a C, modern C++, MFC, ODBC, Windows Services, MAPI developer
from synergy, and Computer Science student from State
University of Campinas(UNICAM P).
To know more about:
Unicamp: http://www.ic.unicamp.br
Synergy: http://www.synergy.com.br
current work: http://www.mintercept.com

[Derrick Coetzee]

chella mani wrote:

Is it a good practice to use 3D arrays in applications or I should use convert my
3D arrays to 1D arrays for efficiency.

On platforms with a data cache, it may be benficial to lay out your
array elements such that your loops traverse the elements in linear
order in memory, or at least do so more often. You may also want to
produce similar versions of a function to operate on both dynamic and
static arrays. If this is likely to be a concern, my personal
recommendation is this, supposing your array has dimensions m, n, p:
* define, dynamically allocate, or pass in a 1D array of size m*n*p
holding the elements
* define a "local" macro specific to that array taking three arguments
which performs the address calculation in the standard way (by "local"
macro, I mean #undef it at the end of the function, to avoid name
collisions later)
* get the algorithm working
* first, try rearranging loops to get better cache performance
* if this fails, fiddle with the macros until you get good performance

Here's an example of 2-operand destructive matrix addition with
fixed-size matrices:

#define M 20
#define N 50
#define P 100

void matrixAdd(int* arg_a, int* arg_b) {
#define a(i,j,k) (arg_a[(i)*N*P + (j)*P + (k)])
#define b(i,j,k) (arg_b[(i)*N*P + (j)*P + (k)])
int i,j,k;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
for(k=0; k<P; k++)
a(i,j,k) += b(i,j,k);
#undef b
#undef a
}

Now with dynamic-sized:

void matrixAdd(int* arg_a, int* arg_b, int m, int n, int p) {
#define a(i,j,k) (arg_a[(i)*n*p + (j)*p + (k)])
#define b(i,j,k) (arg_b[(i)*n*p + (j)*p + (k)])
int i,j,k;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
for(k=0; k<p; k++)
a(i,j,k) += b(i,j,k);
#undef b
#undef a
}

As macros go these are pretty safe - no reevaluation. Just watch out for
macro redefinitions and make sure your address calculations are actually
one-to-one.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.