Working with 3D matrices

[Frederic Soustra]

Hi,
I am trying to speed up some work I have to do with a 3D Matrix.

If I am not mistaken, C is row major,
hence the matrix
A of size 2 x 2 x 2
would be stored like this in memory:
A[1][1][1],A[1][2][1],A[2][1][1],A[2][2][2],A[1][1][2],A[1][2][2],A[2][1][2],A[2][2][2]
?
Am I correct, I need to work on Big 3D matrices, and I know that the way
I traverse the matrices counts, which way is fastest? will gcc optimize
this as to minimize the page jumps in memory?
The matrix is declared using malloc so if A is n x n x d then i setup
the matrix this way:

A = (int***) malloc(n*sizeof(int));
for(i = 0;i < n;i++){
A[i] = (int**) malloc(n*sizeof(int));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(d*sizeof(int));
}

Is this a good way to declare the 3d Matrix? and am I traversing it
correctly?

Thank You for the help.

Fred

[Keith Thompson]

Frederic Soustra <Fr**************@sympatico.ca> writes:

I am trying to speed up some work I have to do with a 3D Matrix.

If I am not mistaken, C is row major,
hence the matrix
A of size 2 x 2 x 2
would be stored like this in memory:
A[1][1][1],A[1][2][1],A[2][1][1],A[2][2][2],A[1][1][2],A[1][2][2],A[2][1][2],A[2][2][2]
?
Um, not even close.

First, C arrays are 0-based, not 1-based.

Yes, C arrays are stored in row-major order. For

int A[2][2][2];

the order in memory would be:

A[0][0][0]
A[0][0][1]
A[0][1][0]
A[0][1][1]
A[1][0][0]
A[1][0][1]
A[1][1][0]
A[1][1][1]
Am I correct, I need to work on Big 3D matrices, and I know that the
way I traverse the matrices counts, which way is fastest? will gcc
optimize this as to minimize the page jumps in memory?
Any relationship between the order in which you traverse the array and
performance is implementation-specific; the language says nothing
about it. If you want to know about optimizations performed by gcc,
try one of the gnu.gcc.* newsgroups.
The matrix is declared using malloc so if A is n x n x d then i setup
the matrix this way:

A = (int***) malloc(n*sizeof(int));
for(i = 0;i < n;i++){
A[i] = (int**) malloc(n*sizeof(int));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(d*sizeof(int));
}

Is this a good way to declare the 3d Matrix? and am I traversing it
correctly?

You haven't shown us the declaration of A.

There are several ways to create a 3-dimensional array: an array of
arrays of arrays, an array of arrays of pointers to arrays, and so
forth. What you're doing here doesn't look right. You should never
cast the result of malloc(). If A is an int***, it doesn't make sense
to point it to something of size (n*sizeof(int)).

Read question 6.16 in the C FAQ, at <http://www.c-faq.com/>. Then
read the rest of section 6, then read the rest of the FAQ. If you
still have questions, feel free to come back.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Frederic Soustra]

Keith Thompson wrote:

Frederic Soustra <Fr**************@sympatico.ca> writes:

I am trying to speed up some work I have to do with a 3D Matrix.

If I am not mistaken, C is row major,
hence the matrix
A of size 2 x 2 x 2
would be stored like this in memory:
A[1][1][1],A[1][2][1],A[2][1][1],A[2][2][2],A[1][1][2],A[1][2][2],A[2][1][2],A[2][2][2]
?

Thx, I was still thinking in matlab mode.
Um, not even close.

First, C arrays are 0-based, not 1-based.

Yes, C arrays are stored in row-major order. For

int A[2][2][2];

the order in memory would be:

A[0][0][0]
A[0][0][1]
A[0][1][0]
A[0][1][1]
A[1][0][0]
A[1][0][1]
A[1][1][0]
A[1][1][1]

Am I correct, I need to work on Big 3D matrices, and I know that the
way I traverse the matrices counts, which way is fastest? will gcc
optimize this as to minimize the page jumps in memory?

Any relationship between the order in which you traverse the array and
performance is implementation-specific; the language says nothing
about it. If you want to know about optimizations performed by gcc,
try one of the gnu.gcc.* newsgroups.

The matrix is declared using malloc so if A is n x n x d then i setup
the matrix this way:
A = (int***) malloc(n*sizeof(int));
for(i = 0;i < n;i++){
A[i] = (int**) malloc(n*sizeof(int));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(d*sizeof(int));
}

Is this a good way to declare the 3d Matrix? and am I traversing it
correctly?

You haven't shown us the declaration of A.

There are several ways to create a 3-dimensional array: an array of
arrays of arrays, an array of arrays of pointers to arrays, and so
forth. What you're doing here doesn't look right. You should never
cast the result of malloc(). If A is an int***, it doesn't make sense
to point it to something of size (n*sizeof(int)).

Read question 6.16 in the C FAQ, at <http://www.c-faq.com/>. Then
read the rest of section 6, then read the rest of the FAQ. If you
still have questions, feel free to come back.

Thank you for pointing me to the FAQ,
so according to the FAQ this is a correct setup for the 3D Matrix:

int*** A = (int***) malloc(n*sizeof(int**));
for(i = 0;i < n;i++){
A[i] = (int**) malloc(n*sizeof(int*));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(d*sizeof(int));
}
and if I read your example of how it is stored in memory then,
it is completely inneficient to build the matrix this way if i am
traversing it in the following manner:
for(l = 0; l < d; l++){
for(i = 0;i <n;i++){
for(j = 0;j < n;j++){
/* do stuff with A[i][j][l]
}
}
}

Again correct me if I am wrong:
If I traverse this matrix using l, then i then j as the indices then my
declaration should look like this:
int*** A = (int***) malloc(d*sizeof(int**));
for(i = 0;i < d;i++){
A[i] = (int**) malloc(n*sizeof(int*));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(n*sizeof(int));
}
Again thank you for pointing me to Q6.16, I had gone through the others
but had not seen 6.16.

Thanks a lot.

Fred

[Schüle Daniel]

[...]

The matrix is declared using malloc so if A is n x n x d then i setup
the matrix this way:
A = (int***) malloc(n*sizeof(int));
as Keith pointed out, never cast return of malloc
are you using C++ compiler?
if so then replace malloc with new
for(i = 0;i < n;i++){
A[i] = (int**) malloc(n*sizeof(int));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(d*sizeof(int));
}

here the same
and if I read your example of how it is stored in memory then,
it is completely inneficient to build the matrix this way if i am
traversing it in the following manner:
for(l = 0; l < d; l++){
for(i = 0;i <n;i++){
for(j = 0;j < n;j++){
/* do stuff with A[i][j][l]
}
}
}

just as idea, you could do

int dim1, dim2, dim3;
int * large = malloc(sizeof(int) * dim1*dim2*dim3);

inline int access_large(int i, int j, int k)
{ return large + i*dim2*dim3 + j*dim3 + k; }

you can also provide DEBUG_ARRAY mode and check the ranges
whether i,j,k are valid

Regards, Daniel

[Schüle Daniel]

const int dim1 = 10, dim2 = 20, dim3 = 5;
int * large = malloc(sizeof(int) * dim1*dim2*dim3);

inline int * access_large(int i, int j, int k)
{ return large + i*dim2*dim3 + j*dim3 + k; }

*acces_large(0,0,0) = 10;
int xyz = *acces_large(0,0,0);

[Dik T. Winter]

In article <m2*******************@news20.bellglobal.com> Frederic Soustra <Fr**************@sympatico.ca> writes:

Thank you for pointing me to the FAQ,
so according to the FAQ this is a correct setup for the 3D Matrix:

int*** A = (int***) malloc(n*sizeof(int**));
for(i = 0;i < n;i++){
A[i] = (int**) malloc(n*sizeof(int*));
for(j = 0;j < n;j++)
A[i][j] = (int*) malloc(d*sizeof(int));
}
This is not a three-dimensional array. A three-dimensional array would
have the type "array of array of array of int". Your array has type
"array of pointer to array of pointer to array of int".
and if I read your example of how it is stored in memory then,
It is completely irrelevant. In the above example (with n = 2) you
can not be sure that A[0][0][1] is followed by A[0][1][0].
it is completely inneficient to build the matrix this way if i am
traversing it in the following manner:
for(l = 0; l < d; l++){
for(i = 0;i <n;i++){
for(j = 0;j < n;j++){
/* do stuff with A[i][j][l]
}
}
}

With your definition it is indeed extremely inefficient. When you
have a true 3-dimensional array it may be inefficient, but that
depends on how the cache of your processor works.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/