Slow access to array

rudo32

Hi I'am programming matrix product and I have problem with accessing to array. Its too slow. I use VC++ 6 (win32 console app) This is only example: #define N 1000 int M1[1000]; int M2[1000]; int M3[1000]; int a,b,c; //fill M1,M2,M3,a,b,c for (j=0;j<N;j++) for (i=0;i<N;i++) for (k=0;k<N;k++) M3[1]=M1[1]*M2[1]; // no indexing just 1 this takes about 6 sec. for (j=0;j<N;j++) for (i=0;i<N;i++) for (k=0;k<N;k++) a=b*c; this takes 0.01 sec. :confused: Can somebody tell me how to do it faster ? Don't worry,I know how to do matrix product. This example just describe slow access to array's elements. I also tried something with asm block, but for (j=0;j<N;j++) for (i=0;i<N;i++) for (k=0;k<N;k++) __asm mov ax,1 this takes about 8 sec. -- modified at 6:27 Sunday 9th October, 2005

Jose Lamas Rios

Some questions: rudo32 wrote: for (j=0;j<N;j++) for (i=0;i<N;i++) for (k=0;k<N;k++) M3[1]=M1[1]*M2[1]; this takes about 6 sec. Was the use of 1 as the index in all arrays, and not using neither i, j, or k intentional? What are M1, M2, and M3? Are they simple arrays (i.e., as in int M1[1000]), STL vectors, MFC's CArrays, or what? rudo32 wrote: for (j=0;j<N;j++) for (i=0;i<N;i++) for (k=0;k<N;k++) a=b*c; this takes 0.01 sec. What are a, b, and c? The optimizer might be clever enough not to generate the triple loop and generate all of the above as equivalent to

if (N > 0)
a = b*c;

-- jlr http://jlamas.blogspot.com/[^]

Rage_bla

Are you sure you mean: M3[1]=M1[1]*M2[1]; and not something like: M3[k]=M1[i]*M2[j]; If you were really talking about the first I can't see how it would be possible to be any slower/different than the second example you posted. If you really ment M3[k]=M1[i]*M2[j] read on: First, compile with optimizations turned on. It that doesn't work try using pointers: for (pj = &j[0]; pj < &j[1000] ; pj++) for (pi = &i[0]; pi < &i[1000] ; pi++) for (pk = &k[0]; pk < &k[1000] ; pk++) *pk=(*pi)*(pj); Smart compilers might do this for you automaticaly. H. -- modified at 20:31 Saturday 8th October, 2005

John R Shaw

Frist: Not enought information. Second: Do not use i++, unless your are using built in types. Use ++i by default, unless you have a good reason not to. If it is not a built in type, that alone will slow every thing down. Third: You need to rewrite the question with a little more detail. It does not matter what the results where in the 6 seconcd test, because according to what you gave us (j,i,k) are ignored. INTP Every thing is relative...

rudo32

For realley matrix product I will must to use more then one loop. for(int j=0;j<N;j++) { for(int i=0;i<N;i++) { fSum=0; for(int k=0;k<N;k++) fSum+=M1[N*j+k]*M2[N*k+i]; M[j*N+i]=fSum; } }

rudo32

Rage_bla wrote: for (pj = &j[0]; pj < &j[1000] ; pj++) for (pi = &i[0]; pi < &i[1000] ; pi++) for (pk = &k[0]; pk < &k[1000] ; pk++) *pk=(*pi)*(pj); Your code is much more slower. If pj is *int, then pj++ is much more slower then j++;

rudo32

I added some information.

John R Shaw

Ok!:doh: You added more information that adds nothing to solving the problem. a, b, and c are naturley faster, becuase they are not arrays that have to be indexed; matter of fact, they are just hanging in space with no defined value (they're global so they're probaly 0). An index of 1 is still an index. If it takes 6 seconds to process arrays of a mere 1000 elements, then there is something else going on. Still not enough information! P.S. It's 6:55 AM sunday mourning here, good night (or good morning). INTP Every thing is relative...

rudo32

So, what else information do you want to know ? Because I want to know, how to write code with fast access to array's elements. I've got simple linear array of integers. Matrix product is n^3 problem. Can I handle array memory faster then array[i] ? Or some compiler switches for pointers ... The aim of my programme is matrix inversion and part which is consumes the most of time, is matrix product. ... right now we have 3:00 pm, so good afternoon; -- modified at 9:14 Sunday 9th October, 2005

Rage_bla

int main(int argc, char* argv[]) { DWORD beg = GetTickCount(); int i,j,k; for (j=0;j

rudo32

Try this. This is matrix product. int M1[1000*1000]; int M2[1000*1000]; int M3[1000*1000]; for(j=0;j

Rage_bla

Use "Ignore HTML tags in this message" when posting becouse half of your code is missing ;)

John R Shaw

Sorry!:-O It was way passed my bed time, you did provide enough imformation. The order in which the calculation are done matters: (VC6.0, optimizations: maximum speed, Compiled for release)

#define MATRIX_SIZE 1000
int M1[MATRIX_SIZE];
int M2[MATRIX_SIZE];
int M3[MATRIX_SIZE];
/////////////////////////////////
void matrix_speed_test() // AVARAGE TIME: 2.16 seconds
{
int j, i, k;
for( j=0;j<MATRIX_SIZE;++j )
for( i=0;i<MATRIX_SIZE;++i )
for( k=0;k<MATRIX_SIZE;++k )
M3[j] = M1[i] * M2[k];
}

/////////////////////////////////
void matrix_speed_test2() // AVARAGE TIME: 0.61 seconds
{
int j, i, k;
int m1,m2;
for( j=0;j<MATRIX_SIZE;++j )
{
m1 = M1[j];
for( i=0;i<MATRIX_SIZE;++i )
{
m2 = M2[i];
for( k=0;k<MATRIX_SIZE;++k )
M3[k] = m1 * m2;
}
}
}

/////////////////////////////////
void matrix_speed_test3() // AVARAGE TIME: 1.91 seconds
{
int j, i, k;
int m1;
for( j=0;j<MATRIX_SIZE;++j )
{
for( i=0;i<MATRIX_SIZE;++i )
{
m1 = M1[i];
for( k=0;k<MATRIX_SIZE;++k )
M3[j] = m1 * M2[k];
}
}
}

As you can see, rearanging the code to change where the indexing occurs can greatly increase the speed. I tried a few other ways, but they still avaraged 2.17 seconds. I hope that helps! P.S. Sorry for the delay, I am usualy only online when reasearching. INTP Every thing is relative...