NO

Author Topic: Accessing 2D arrays  (Read 2809 times)

JohnF

  • Guest
Accessing 2D arrays
« 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

Offline jj2007

  • Member
  • *
  • Posts: 506
Re: Accessing 2D arrays
« Reply #1 on: August 19, 2014, 09:08:52 pm »
error #2048: Undeclared identifier 'array'.

JohnF

  • Guest
Re: Accessing 2D arrays
« Reply #2 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

czerny

  • Guest
Re: Accessing 2D arrays
« Reply #3 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! :-(
« Last Edit: August 20, 2014, 12:11:29 pm by czerny »

JohnF

  • Guest
Re: Accessing 2D arrays
« Reply #4 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


neo313

  • Guest
Re: Accessing 2D arrays
« Reply #5 on: August 20, 2014, 11:25:19 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
« Last Edit: August 20, 2014, 11:28:25 am by neo313 »

JohnF

  • Guest
Re: Accessing 2D arrays
« Reply #6 on: August 21, 2014, 06:51:10 am »
It's not a trick, it's a tip.

John