2D array indexing very slow

  • Thread starter Thread starter Tristan
  • Start date Start date
T

Tristan

In C# why is:

int[] myArray = new int[5000,5000];

for (int y = 0; y < 5000; y++)
{
for (int x = 0; x < 5000; x++)
{
myArray[x, y] = 1;
}
}

So slow!!!

I think It's the indexing into the array which is causing
performance hits in my application but why? Either this
or am I simply using too big an array to expect a
quick operation?

If it's a problem with C# is there a way around this?

Many thanks.

Tristan.
 
(e-mail address removed) (Tristan) wrote in
In C# why is:

int[] myArray = new int[5000,5000];

for (int y = 0; y < 5000; y++)
{
for (int x = 0; x < 5000; x++)
{
myArray[x, y] = 1;
}
}

So slow!!!

I think It's the indexing into the array which is causing
performance hits in my application but why? Either this
or am I simply using too big an array to expect a
quick operation?

If it's a problem with C# is there a way around this?

Many thanks.

Tristan.
Click to expand...

i always use the following code (which is quite fast btw. although it
doesn't do anything else than mapping the 2 dimensional addressing mode
on linear addressing):

int xsize = 5000;
int ysize = 5000;
int[] myArray = new int[xsize*ysize];

for(int y=0; y<ysize; y++)
for(int x=0; x<xsize; x++)
myArray[y*xsize + x] = 1;

greets
Peter

--
------ooo---OOO---ooo------

Peter Koen - www.kema.at
MCAD MCDBA
CAI/RS CASE/RS IAT

------ooo---OOO---ooo------
 
Peter's reduces it by a factor of 10 when i tried it out! I used:

private void button1_Click(object sender, System.EventArgs e)
{
DateTime start = DateTime.Now;
/*int[,] myArray = new int[5000,5000];

for (int y = 0; y < 5000; y++)
{
for (int x = 0; x < 5000; x++)
{
myArray[x, y] = 1;
}
}*/
int xsize = 5000;
int ysize = 5000;
int[] myArray = new int[xsize*ysize];

for(int y=0; y<ysize; y++)
for(int x=0; x<xsize; x++)
myArray[y*xsize + x] = 1;
DateTime end = DateTime.Now;

MessageBox.Show(end.Ticks - start.Ticks +"");

}

Peter Koen said:
(e-mail address removed) (Tristan) wrote in
In C# why is:

int[] myArray = new int[5000,5000];

for (int y = 0; y < 5000; y++)
{
for (int x = 0; x < 5000; x++)
{
myArray[x, y] = 1;
}
}

So slow!!!

I think It's the indexing into the array which is causing
performance hits in my application but why? Either this
or am I simply using too big an array to expect a
quick operation?

If it's a problem with C# is there a way around this?

Many thanks.

Tristan.
Click to expand...

i always use the following code (which is quite fast btw. although it
doesn't do anything else than mapping the 2 dimensional addressing mode
on linear addressing):

int xsize = 5000;
int ysize = 5000;
int[] myArray = new int[xsize*ysize];

for(int y=0; y<ysize; y++)
for(int x=0; x<xsize; x++)
myArray[y*xsize + x] = 1;

greets
Peter

--
------ooo---OOO---ooo------

Peter Koen - www.kema.at
MCAD MCDBA
CAI/RS CASE/RS IAT

------ooo---OOO---ooo------
Click to expand...
 
Chris Small said:
Peter's reduces it by a factor of 10 when i tried it out! I used:

private void button1_Click(object sender, System.EventArgs e)
{
DateTime start = DateTime.Now;
/*int[,] myArray = new int[5000,5000];

for (int y = 0; y < 5000; y++)
{
for (int x = 0; x < 5000; x++)
{
myArray[x, y] = 1;
}
}*/
int xsize = 5000;
int ysize = 5000;
int[] myArray = new int[xsize*ysize];

for(int y=0; y<ysize; y++)
for(int x=0; x<xsize; x++)
myArray[y*xsize + x] = 1;
DateTime end = DateTime.Now;

MessageBox.Show(end.Ticks - start.Ticks +"");

}
Click to expand...

(I've never understood why people are obsessed with using GUIs for no
good reason... See http://www.pobox.com/~skeet/csharp/benchmark.html
for a simple benchmarking framework.)

Anyway, there's a very good reason why Peter's code is so much faster
than the original, and it's mostly *not* because of the 2D array. It's
because of locality of reference. The 1D version is going through the
memory in one pass, byte by byte. The 2D version is skipping through
the array, the first byte then the 5001st, then the 10001st, etc, then
back to the second byte, etc.

Benchmarking the 2D version which does the same as the 1D version in
terms of ordering, it's far, far closer - less than a factor of 2
difference, which is much less likely to be a significant factor in
real world apps where values in memory tend to actually be *used*.
 
Back
Top