Row Major versus Column Major Initialization

Row Major versus Column Major Initialization

Post by Rance Horto » Tue, 04 Apr 2000 04:00:00



Hello All,

Here is the row major initialization:

#define ASIZE 4096
long int A[ASIZE][ASIZE];

void main()
{
 double Duration;
 clock_t Start, Finish;

 int nI,
  nJ,
  nN;

 Start = clock();
 for(nN = 0;nN < 100; nN++)
      for(nI = 0;nI < ASIZE; nI++)             --Row major initialization
           for(nJ = 0; nJ < ASIZE;nJ++)
                A[nI][nJ];

 Finish = clock();

 Duration = (double)(Finish-Start)/CLOCKS_PER_SEC;

 cout << "\tDuration = " << Duration << endl;

Quote:}--end Row major init

for column major just switch the above two for loops like so:
for(nJ = 0; nJ < ASIZE;nJ++)
    for(nI = 0;nI < ASIZE; nI++)             --Column major initialization
           A[nI][nJ];

Im working in Visual Studio 6.0 on Win NT 4.0 sp5

My question is this ..... why is the column major initialization every bit as fast as the Row major?
I expected the Row Major to blow the doors off of the column major.

Can someone provide an answer?

Rance

 
 
 

Row Major versus Column Major Initialization

Post by Rance Horto » Tue, 04 Apr 2000 04:00:00


Scratch my Post.....

someone was smart enough to point out that it helps to supply a value to my two d array.... and yes i feel pretty special for overlooking that little detail.......

and all is now right in the world....

Rance

 
 
 

Row Major versus Column Major Initialization

Post by E. Robert Tisdal » Wed, 05 Apr 2000 04:00:00



> Hello All, Here is the row major initialization: #define ASIZE 4096
> long int A[ASIZE][ASIZE]; void main()
> {
>  double Duration;
>  clock_t Start, Finish;  int nI,
>   nJ,
>   nN;  Start = clock();
>  for(nN = 0;nN < 100; nN++)
>       for(nI = 0;nI < ASIZE; nI++)             --Row major initialization
>            for(nJ = 0; nJ < ASIZE;nJ++)
>                 A[nI][nJ];  Finish = clock();  Duration =
> (double)(Finish-Start)/CLOCKS_PER_SEC;
>  cout << "\tDuration = " << Duration << endl;
> }--end Row major init  for column major just switch the above two for loops
> like so:for(nJ = 0; nJ < ASIZE;nJ++)
>     for(nI = 0;nI < ASIZE; nI++)             --Column major initialization
>            A[nI][nJ];  Im working in Visual Studio 6.0 on Win NT 4.0 sp5 My
> question is this ..... why is the column major initialization every bit as
> fast as the Row major?I expected the Row Major to blow the doors off of the
> column major. Can someone provide an answer?

You twit!

Neither of your nested loops initialize anything.
Your compiler didn't write any code for either of them.

 
 
 

Row Major versus Column Major Initialization

Post by Ron Natali » Wed, 05 Apr 2000 04:00:00



> Hello All,
> ?
> Here is the row major initialization:
> ?
> #define ASIZE 4096
> long int A[ASIZE][ASIZE];
> ?
> void main()

Please get used to declaring main as int, as is required by the language.

Quote:> My question is this ..... why is the column major initialization every bit as fast as the Row major?
> I expected the Row Major to blow the doors off of the column major.

First off you'll have to explain why you thought it would be.

Second, any optimizing compiler worht a dang isn't even going to access A since you don't
do anything with the value (and in many cases might be smart enough to ditch the loops entirely).
You're most likely testing *NOTHING*.

Try doing it again  using the value for something (assign it or add it to anther variable).

 
 
 

Row Major versus Column Major Initialization

Post by Aare » Thu, 06 Apr 2000 04:00:00


Quote:> Here is the row major initialization:

> #define ASIZE 4096
> long int A[ASIZE][ASIZE];

> void main()
> {
>  double Duration;
>  clock_t Start, Finish;

>  int nI,
>   nJ,
>   nN;

>  Start = clock();
>  for(nN = 0;nN < 100; nN++)
>       for(nI = 0;nI < ASIZE; nI++)             --Row major
> initialization
>            for(nJ = 0; nJ < ASIZE;nJ++)
>                 A[nI][nJ];

>  Finish = clock();

>  Duration = (double)(Finish-Start)/CLOCKS_PER_SEC;

>  cout << "\tDuration = " << Duration << endl;
> }--end Row major init

> for column major just switch the above two for loops like so:
> for(nJ = 0; nJ < ASIZE;nJ++)
>     for(nI = 0;nI < ASIZE; nI++)             --Column major
> initialization
>            A[nI][nJ];

> Im working in Visual Studio 6.0 on Win NT 4.0 sp5

> My question is this ..... why is the column major initialization every
> bit as fast as the Row major?
> I expected the Row Major to blow the doors off of the column major.

Hopefully this answer is more helpful than those saying A[][] not used
at all. The example is simple enough to get the idea, not for someone to
compile it and check the assembly output.

Strength reduction optimization phase could introduce temporary A
pointer and perform loop as follows:

for (long int * Aptr = A; Aptr < &A[ASIZE][ASIZE]; Aptr++)
        *Aptr = something;

This optimization is possible if the something initializer is not
depending on row and column indexes and these indexes are not used
inside the loop. But even if this optimization is not possible (like
A[i][j] = i * j; initialization), then row-by-row iteration can be
optimized with pointer to row instead of indexing, so even

for (int i = 0; i < ASIZE; i++)
        for (int j = 0; j < ASIZE; j++)
                A[i][j] = i * j;

might be optimized into

long int * Aptr = A;
for (int i = 0; i < ASIZE; i++)
        for (int j = 0; j < ASIZE; j++)
                *Aptr++ = i * j;

P.S. Leave this optimization to the compiler, unless you write another
core for distributed.net key search :)