Accessing 2D arrays

[JohnF]

Run this and the Tip will be clear. I was not aware of it, maybe I should have been.

Code Select Expand


#include <windows.h>
#include <stdio.h>

int _cdecl main(void)
{
int i, j;
long t, t1;

t = GetTickCount();

for (j = 0; j < 10000; j++)
for (i = 0; i < 2000; i++)
array[i][j] = 0.0;

t1 = GetTickCount();
printf("%d\n", t1-t);

t = GetTickCount();

for (i = 0; i < 2000; i++)
for (j = 0; j < 10000; j++)
array[i][j] = 0.0;

t1 = GetTickCount();
printf("%d\n", t1-t);

return 0;
}


John

[jj2007]

error #2048: Undeclared identifier 'array'.

[JohnF]

Sorry.

Code Select Expand


#include <windows.h>
#include <stdio.h>
#define SIZE 4000
float array[SIZE][SIZE];
int _cdecl main(void)
{
int i, j;
long t, t1;

t = GetTickCount();

for (j = 0; j < SIZE; j++)
for (i = 0; i < SIZE; i++)
array[i][j] = 0.0;

t1 = GetTickCount();
printf("%d\n", t1-t);

t = GetTickCount();

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
array[i][j] = 0.0;

t1 = GetTickCount();
printf("%d\n", t1-t);

return 0;
}


John

[czerny]

I have those values (without optimization):

2921
94

use this

Code Select Expand

printf("%d %d %d\n",t,t1,t1-t);
and I get

3586718 3589625 2907
3592609 3595546 2937

very strange!

Edit: Not strange at all! I have not seen the difference between the two loops in first place.
So I have copied the first loop over the second, getting ... the same! :-(

[JohnF]

The point I was making is the fact that the two sets of loops have very different timings.

I leave it to the reader to understand why.

John

[neo313]

The point I was making is the fact that the two sets of loops have very different timings.

I leave it to the reader to understand why.

John

Code Select Expand


for (j = 0; j < SIZE; j++)
for (i = 0; i < SIZE; i++)
array[i][j] = 0.0;

for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
array[i][j] = 0.0;


It is a simple trick relying that the reader will not notice that the variables i and j are effectively switched when used in array.

The first array is being read all over the place messing with the cpu cache.

http://stackoverflow.com/questions/16699247/what-is-cache-friendly-code

[JohnF]

It's not a trick, it's a tip.

John