Pelles C forum

C language => Tips & tricks => Topic started by: JohnF on August 19, 2014, 08:21:59 PM

Title: Accessing 2D arrays
Post by: JohnF on August 19, 2014, 08:21:59 PM

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

Code: [Select]

#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

Title: Re: Accessing 2D arrays
Post by: jj2007 on August 19, 2014, 09:08:52 PM

error #2048: Undeclared identifier 'array'.

Title: Re: Accessing 2D arrays
Post by: JohnF on August 20, 2014, 06:48:20 AM

Sorry.

Code: [Select]

#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

Title: Re: Accessing 2D arrays
Post by: czerny on August 20, 2014, 09:13:14 AM

I have those values (without optimization):

2921
94

use this

Code: [Select]

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! :-(

Title: Re: Accessing 2D arrays
Post by: JohnF on August 20, 2014, 09:39:26 AM

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

Title: Re: Accessing 2D arrays
Post by: neo313 on August 20, 2014, 11:25:19 AM

Quote from: JohnF on August 20, 2014, 09:39:26 AM

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]

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

Title: Re: Accessing 2D arrays
Post by: JohnF on August 21, 2014, 06:51:10 AM

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

John