Velocity Reviews > Working with 3D matrices

# Working with 3D matrices

Frederic Soustra
Guest
Posts: n/a

 01-30-2006
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
Guest
Posts: n/a

 01-30-2006
Frederic Soustra <(E-Mail Removed)> 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) http://www.velocityreviews.com/forums/(E-Mail Removed) <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
Guest
Posts: n/a

 01-30-2006
Keith Thompson wrote:
> Frederic Soustra <(E-Mail Removed)> 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

Thanks a lot.

Fred

=?ISO-8859-1?Q?Sch=FCle_Daniel?=
Guest
Posts: n/a

 01-30-2006
[...]

>>> 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

=?ISO-8859-1?Q?Sch=FCle_Daniel?=
Guest
Posts: n/a

 01-30-2006
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
Guest
Posts: n/a

 01-31-2006
In article <m2pDf.1905\$(E-Mail Removed)> Frederic Soustra <(E-Mail Removed)> 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, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/