Performance considerations in 3D arrays

[Jon Rea]

Im a relatively new coder and am still learning the best way to do thigs
- and I have always been told the best way to learn is by writing
testing code and measuring, Could anyone shed some light on why my
'MyArray[,,]' test is so much faster? Id really like to know!

What is the best method for creating and accessing 2D, 3D and nD arrays?

Cheers Guys
Jon Rea

Application Output

WindowsXP:
Sum: 251437500.000000
Sum: 251437500.000000
Array3D test Took 30 seconds
Sum: 251437500.000000
Sum: 251437500.000000
MyArray[] test Took 30 seconds
Sum: 251437500.000000
Sum: 251437500.000000
MyArray[] (V2) test Took 29 seconds
Sum: 251437500.000000
Sum: 251437500.000000
MyArray[,,] test Took 11 seconds

Linux (RH9):
Sum: 251437500.000000
Sum: 251437500.000000
Array3D test Took 20 seconds
Sum: 251437500.000000
Sum: 251437500.000000
MyArray[] test Took 20 seconds
Sum: 251437500.000000
Sum: 251437500.000000
MyArray[] (V2) test Took 22 seconds
Sum: 251437500.000000
Sum: 251437500.000000
MyArray[,,] test Took 6 seconds

Application Code
#include <iostream>
#include <stdio.h>
#include <tchar.h>
#include <time.h>

#include "tntjama/tnt_array3d.h"

using namespace TNT;

int _tmain(int argc, _TCHAR* argv[])
{
int count1 = 15;
int count2 = 100;

int M = 150;
int N = 150;
int P = 150;

time_t starttime = time( NULL );
for( int r = 0; r < count1; r++ )
{
Array3D< double > A(M,N,P);

for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
A[j][k] = (double)k; /* initalize
array values */

for( int q = 0; q < count2; q++ )
{
double sum = 0.0;
for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
sum += A[j][k]; /* calc sum */
if( r == 0 && (q == 0 || q == 15) ) printf("Sum: %lf\n",sum);
}
}
printf("Array3D test Took %d seconds\n",(int)(time(NULL) - starttime));

starttime = time( NULL );
int T = M*M;
for( int r = 0; r < count1; r++ )
{
double *A = new double[M*N*P];

for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
A[(T*i)+(N*j)+k] = (double)k; /*
initalize array values */

for( int q = 0; q < count2; q++ )
{
double sum = 0.0;
for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
sum += A[(T*i)+(N*j)+k]; /* calc sum */
if( r == 0 && (q == 0 || q == 15) ) printf("Sum: %lf\n",sum);
}

delete[] A;
}
printf("MyArray[] test Took %d seconds\n",(int)(time(NULL) -
starttime));

starttime = time( NULL );
T = M*M;
int indexRoot1, indexRoot2;
for( int r = 0; r < count1; r++ )
{
double *A = new double[M*N*P];

for (int i=0; i < M; i++)
{
indexRoot1 = (T*i);
for (int j=0; j < N; j++)
{
indexRoot2 = indexRoot1 + (N*j);
for (int k=0; k < P; k++)
{
A[indexRoot2+k] = (double)k; /*
initalize array values */
}
}
}

for( int q = 0; q < count2; q++ )
{
double sum = 0.0;
int indexRoot1, indexRoot2;
for (int i=0; i < M; i++)
{
indexRoot1 = (T*i);
for (int j=0; j < N; j++)
{
indexRoot2 = indexRoot1 + (N*j);
for (int k=0; k < P; k++)
{
sum += A[indexRoot2+k]; /* calc sum */
}
}
}
if( r == 0 && (q == 0 || q == 15) ) printf("Sum: %lf\n",sum);
}

delete[] A;
}
printf("MyArray[] (V2) test Took %d seconds\n",(int)(time(NULL) -
starttime));

starttime = time( NULL );
for( int r = 0; r < count1; r++ )
{
double *A = new double[M,N,P];

for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
A[i,j,k] = (double)k; /* initalize
array values */

for( int q = 0; q < count2; q++ )
{
double sum = 0.0;
for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
sum += A[i,j,k]; /* calc sum */
if( r == 0 && (q == 0 || q == 15) ) printf("Sum: %lf\n",sum);
}

delete[] A;
}
printf("MyArray[,,] test Took %d seconds\n",(int)(time(NULL) -
starttime));

return 0;
}

 

[jmoy]

Im a relatively new coder and am still learning the best way to do thigs
- and I have always been told the best way to learn is by writing
testing code and measuring, Could anyone shed some light on why my
'MyArray[,,]' test is so much faster? Id really like to know!

...
starttime = time( NULL );
for( int r = 0; r < count1; r++ )
{
double *A = new double[M,N,P];

for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
A[i,j,k] = (double)k; /* initalize
array values */

for( int q = 0; q < count2; q++ )
{
double sum = 0.0;
for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
sum += A[i,j,k]; /* calc sum */
if( r == 0 && (q == 0 || q == 15) ) printf("Sum: %lf\n",sum);
}

delete[] A;
}
printf("MyArray[,,] test Took %d seconds\n",(int)(time(NULL) -
starttime));

double *A = new double[M,N,P]

is not the correct syntax to declare a three-dimensional array in C++.
In fact there is no way to define a three dimensional array whose
second and third dimensions are not known at compile time. In the case
of your particular program you can define M, N, P as 'const int' rather
than 'int' and define A as
double A[M][N][P];
and access the (i,j,k) element at A[j][k]

In C++ comma is a binary operator whose value equals that of the second
operand so double[M,N,P] is just the same as double[P] and A[i,j,k] is
the same as A[k]. The sum turns out right in your program because of
the special pattern you use for initializing A. Set its (i,j,k)th
element to something that depends of all the subscripts, say i*j*k, to
see the difference.

 

[Stuart Golodetz]

Im a relatively new coder and am still learning the best way to do thigs
- and I have always been told the best way to learn is by writing
testing code and measuring, Could anyone shed some light on why my
'MyArray[,,]' test is so much faster? Id really like to know!

...
starttime = time( NULL );
for( int r = 0; r < count1; r++ )
{
double *A = new double[M,N,P];

for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
A[i,j,k] = (double)k; /* initalize
array values */

for( int q = 0; q < count2; q++ )
{
double sum = 0.0;
for (int i=0; i < M; i++)
for (int j=0; j < N; j++)
for (int k=0; k < P; k++)
sum += A[i,j,k]; /* calc sum */
if( r == 0 && (q == 0 || q == 15) ) printf("Sum:
%lf\n",sum);
}

delete[] A;
}
printf("MyArray[,,] test Took %d seconds\n",(int)(time(NULL) -
starttime));

double *A = new double[M,N,P]

is not the correct syntax to declare a three-dimensional array in C++.
In fact there is no way to define a three dimensional array whose
second and third dimensions are not known at compile time.

Well, not as such perhaps, but you can (inadvisedly) do:

double ***A = new double**[M];
for(int i=0; i<M; ++i)
{
A = new double*[N];
for(int j=0; j<N; ++j)
{
A[j] = new double[P];
}
}

etc.

I wouldn't recommend it though (it's a bit on the long-winded side).

Stu

In the case
of your particular program you can define M, N, P as 'const int' rather
than 'int' and define A as
double A[M][N][P];
and access the (i,j,k) element at A[j][k]

In C++ comma is a binary operator whose value equals that of the second
operand so double[M,N,P] is just the same as double[P] and A[i,j,k] is
the same as A[k]. The sum turns out right in your program because of
the special pattern you use for initializing A. Set its (i,j,k)th
element to something that depends of all the subscripts, say i*j*k, to
see the difference.