How to move fast around a 2D array

[jehugaleahsa]

Hello:

I have a List<T[]> where the internal arrays are of a fixed size.

I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:

public struct Position
{
Position(int x, int y) { X = x; Y = y; }
int X { get; set; }
int Y { get; set; }
}

private Position Advance(Position pos, int distance)
{
// creates new position that is distance positions forward in the
array
}

I am currently implementing this method like this:

private Position Advance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZE, offset %
FIXED_ARRAY_SIZE);
}

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

Thanks,
Travis

 

[Sergey Zyuzin]

Hello:

I have a List<T[]> where the internal arrays are of a fixed size.

I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:

public struct Position
{
š š Position(int x, int y) { X = x; Y = y; }
š š int X { get; set; }
š š int Y { get; set; }

}

private Position Advance(Position pos, int distance)
{
š š // creates new position that is distance positions forward in the
array

}

I am currently implementing this method like this:

private Position Advance(Position pos, int distance)
{
š š int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
š š return new Position(offset / FIXED_ARRAY_SIZE, offset %
FIXED_ARRAY_SIZE);

}

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

Thanks,
Travis

Hi Travis,
This might be a bit faster, assuming distance is positive. I removed
multiplication, added one 'if' instead
and in half cases two additional additions are performed.
However I didn't profile it.

int Y = pos.Y + offset % FIXED_ARRAY_SIZE;
if (Y >= FIXED_ARRAY_SIZE)
{
return new Position(pos.X + offset / FIXED_ARRAY_SIZE + 1, Y -
FIXED_ARRAY_SIZE);
}
else
{
return new Position(pos.X + offset / FIXED_ARRAY_SIZE, Y);
}

HTH,
Sergey

 

[Alun Harford]

Hello:

I have a List<T[]> where the internal arrays are of a fixed size.

I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:

public struct Position
{
Position(int x, int y) { X = x; Y = y; }
int X { get; set; }
int Y { get; set; }
}

private Position Advance(Position pos, int distance)
{
// creates new position that is distance positions forward in the
array
}

I am currently implementing this method like this:

private Position Advance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZE, offset %
FIXED_ARRAY_SIZE);
}

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

Well if you *must* keep the same data structure (I would have thought a
List<int> would be more appropriate given what you have to do here...)

If you know that distance will normally be small, you can do

private Position Advance(Position pos, int distance)
{
if(pos.X + distance >= 0 && pos.X + distance < FIXED_ARRAY_SIZE)
{
return new Position(pos.Y, pos.X + distance);
}
else
{
//Your code
}
}

Another option would be (and you could do both if you need it *really*
fast but less readable):

Dictionary<int, Position> lookup = new Dictionary<int, Position>();
private Position Advance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
Position p;
if(lookup.TryGetValue(offset, out p))
{
return p;
}
int y = offset / FIXED_ARRAY_SIZE;
for(int i = 0; i < FIXED_ARRAY_SIZE; i++)
{
lookup.Add(y + i, new Position(y, i));
}
return new Position(p, offset % FIXED_ARRAY_SIZE);
}

Or you can bit fiddle, depending on the value of FIXED_ARRAY_SIZE.

Alun Harford

 

[Steve Gerrard]

I am currently implementing this method like this:

private Position Advance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZE, offset %
FIXED_ARRAY_SIZE);
}

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

How do you know it is the math? I would bet that the math is plenty fast, and
that it is the creation of new Position instances that is the bottleneck. If you
just return a new position with the same values as the passed one (for testing
only, obviously), is it much faster, or does the profiler show it to be just as
busy?

 

[jehugaleahsa]

How do you know it is the math? I would bet that the math is plenty fast, and
that it is the creation of new Position instances that is the bottleneck. If you
just return a new position with the same values as the passed one (for testing
only, obviously), is it much faster, or does the profiler show it to be just as
busy?- Hide quoted text -

- Show quoted text -

The profiler indicates that the majority of the time is spent in
DivRem; that is how I know. It doesn't seem to care much about the
multiplication.

 

[jehugaleahsa]

Hello:

I have a List<T[]> where the internal arrays are of a fixed size.

I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:

public struct Position
{
    Position(int x, int y) { X = x; Y = y; }
    int X { get; set; }
    int Y { get; set; }
}

private Position Advance(Position pos, int distance)
{
    // creates new position that is distance positions forward in the
array
}

I am currently implementing this method like this:

private Position Advance(Position pos, int distance)
{
    int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
    return new Position(offset / FIXED_ARRAY_SIZE, offset %
FIXED_ARRAY_SIZE);
}

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

Well if you *must* keep the same data structure (I would have thought a
List<int> would be more appropriate given what you have to do here...)

If you know that distance will normally be small, you can do

private Position Advance(Position pos, int distance)
{
    if(pos.X + distance >= 0 && pos.X + distance < FIXED_ARRAY_SIZE)
    {
       return new Position(pos.Y, pos.X + distance);
    }
    else
    {
       //Your code
    }

}

Another option would be (and you could do both if you need it *really*
fast but less readable):

Dictionary<int, Position> lookup = new Dictionary<int, Position>();
private Position Advance(Position pos, int distance)
{
    int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
    Position p;
    if(lookup.TryGetValue(offset, out p))
    {
       return p;
    }
    int y = offset / FIXED_ARRAY_SIZE;
    for(int i = 0; i < FIXED_ARRAY_SIZE; i++)
    {
       lookup.Add(y + i, new Position(y, i));
    }
    return new Position(p, offset % FIXED_ARRAY_SIZE);

}

Or you can bit fiddle, depending on the value of FIXED_ARRAY_SIZE.

Alun Harford- Hide quoted text -

- Show quoted text -

I could also use a int[][]. If there is a faster way of moving around
it, I would gladly do the additional memory managment.

 

[Steve Gerrard]

The profiler indicates that the majority of the time is spent in
DivRem; that is how I know. It doesn't seem to care much about the
multiplication.

It may show the line that contains DivRem, but that line also creates a new
Position.

Consider these two versions of Advance:

private Position Advance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZE, offset % FIXED_ARRAY_SIZE);
}

private void JustAdvance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
pos.X = offset/FIXED_ARRAY_SIZE;
pos.Y = offset % FIXED_ARRAY_SIZE;
}

If I call each of these 1 million times in a loop, I get the following times:
Advance (creates a new Position each time): 0.469 secs
JustAdvance (does the math and stores result): 0.078 secs

It is spending about 16% of the time doing math, and 84% of the time creating a
new Position.

 

[jehugaleahsa]

It may show the line that contains DivRem, but that line also creates a new
Position.

Consider these two versions of Advance:

private Position Advance(Position pos, int distance)
{
 int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
 return new Position(offset / FIXED_ARRAY_SIZE, offset % FIXED_ARRAY_SIZE);

}

private void JustAdvance(Position pos, int distance)
{
 int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
 pos.X = offset/FIXED_ARRAY_SIZE;
 pos.Y = offset % FIXED_ARRAY_SIZE;

}

If I call each of these 1 million times in a loop, I get the following times:
    Advance (creates a new Position each time): 0.469 secs
    JustAdvance (does the math and stores result): 0.078 secs

It is spending about 16% of the time doing math, and 84% of the time creating a
new Position.

Say you were right, then why does creating a simple class like
Position take so long? Is it a paging issue?

 

[henon]

On Feb 17, 11:40 pm, "(e-mail address removed)" <[email protected]>
wrote:
[...]

Say you were right, then why does creating a simple class like
Position take so long? Is it a paging issue?

probably because every call to "new" starts the garbage collector. one
should always try to avoid many news in complex algorithmic code by
preallocation or using value types instead of reference types.

-- henon
______
http://www.eqqon.com/index.php/User:Henon

 

[Jon Skeet [C# MVP]]

probably because every call to "new" starts the garbage collector. one
should always try to avoid many news in complex algorithmic code by
preallocation or using value types instead of reference types.

Position is already a struct according to the first post.

Jon

 

[Jon Skeet [C# MVP]]

If I call each of these 1 million times in a loop, I get the following times:
Advance (creates a new Position each time): 0.469 secs
JustAdvance (does the math and stores result): 0.078 secs

It is spending about 16% of the time doing math, and 84% of the time creating a
new Position.

Could you post a short but complete benchmarking program to
demonstrate this? It would be interesting to tweak it.

Jon

 

[Steve Gerrard]

Could you post a short but complete benchmarking program to
demonstrate this? It would be interesting to tweak it.

Jon

Sure.

public struct Position
{
public int X , Y ;
public Position(int x, int y) { X = x; Y = y; }
}

const int FIXED_ARRAY_SIZE = 1000;
const int LOOP_COUNT = 1000000;
Position test = new Position(0,0);

private void button1_Click(object sender, System.EventArgs e)
{
int x;
TimeSpan t;
DateTime start, finish;

start = DateTime.Now;
for (x = 0; x < LOOP_COUNT; x++)
{
test=Advance(test,1);
}
finish = DateTime.Now;
t = finish-start;
System.Diagnostics.Debug.WriteLine(t.TotalSeconds.ToString("#,0.000"));

start = DateTime.Now;
for (x = 0; x < LOOP_COUNT; x++)
{
JustAdvance(test,1);
}
finish = DateTime.Now;
t = finish-start;
System.Diagnostics.Debug.WriteLine(t.TotalSeconds.ToString("#,0.000"));
}

private Position Advance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZE, offset %
FIXED_ARRAY_SIZE);
}

private void JustAdvance(Position pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZE + pos.Y + distance;
pos.X = offset/FIXED_ARRAY_SIZE;
pos.Y = offset % FIXED_ARRAY_SIZE;
}

 

[Jon Skeet [C# MVP]]

Sure.

I converted your bits into a genuinely complete application, and it
shows very different results:


using System;
using System.Diagnostics;

public struct Position
{
public int X , Y ;
public Position(int x, int y) { X = x; Y = y; }
}

class Test
{
const int FixedArraySize = 1000;
const int LoopCount = 100000000;

static void Main()
{
Position pos = new Position(0, 0);

Stopwatch sw = Stopwatch.StartNew();
for (int x = 0; x < LoopCount; x++)
{
pos = Advance(pos, 1);
}
sw.Stop();
Console.WriteLine ("Advance: {0}",
(int)sw.ElapsedMilliseconds);

sw = Stopwatch.StartNew();
for (int x = 0; x < LoopCount; x++)
{
JustAdvance(pos,1);
}
sw.Stop();
Console.WriteLine ("JustAdvance: {0}",
(int)sw.ElapsedMilliseconds);
}

static Position Advance(Position pos, int distance)
{
int offset = pos.X * FixedArraySize + pos.Y + distance;
return new Position(offset / FixedArraySize,
offset % FixedArraySize);
}

static void JustAdvance(Position pos, int distance)
{
int offset = pos.X * FixedArraySize + pos.Y + distance;
pos.X = offset/FixedArraySize;
pos.Y = offset % FixedArraySize;
}
}

Results:
Advance: 6912
JustAdvance: 5103

Note that that's doing 100 million iterations in between 5 and 7
seconds. That seems rather different to your call to Advance, although
JustAdvance seems the same order of magnitude on my box as yours.

What does the above code display on your box?

 

[Peter Duniho]

On Feb 17, 11:40 pm, "(e-mail address removed)" <[email protected]>
wrote:
[...]

Say you were right, then why does creating a simple class like
Position take so long? Is it a paging issue?

probably because every call to "new" starts the garbage collector.

Huh?

AFAIK, this is _not_ true. The GC runs only as necessary. Instantiating
a new object does not cause it to run every time.

So even if Position were a reference type, instantiating it wouldn't
necessarily cause the GC to run.

Pete

 

[jehugaleahsa]

Switching between struct and class has made little difference, in my
case. I am a little stuck on how I am to reduce creating new objects.
I am still not sure that is my problem.

Thanks for you input. I'll keep digging.

 

[Steve Gerrard]

Results:
Advance: 6912
JustAdvance: 5103

Note that that's doing 100 million iterations in between 5 and 7
seconds. That seems rather different to your call to Advance, although
JustAdvance seems the same order of magnitude on my box as yours.

What does the above code display on your box?

Short answer:
Advance: 8984
JustAdvance: 5187

What I noticed was that

Position pos = new Position(0, 0);

is in Main() in your code, meaning it is a local stack variable. If I move that
line into the button1_click method in my scraggly code, instead of the result of
469 vs 78 milliseconds that I first posted, I get 93 vs 68 milliseconds, or if I
run it 100 million times, 9281 vs 6875.

So, despite the fact that my post was done with Net 1.1 code (home machine is
out of date), and the flaky button1_click approach that you grimaced at, the
main difference seems to be where the Position variable is - heap or stack. I am
surprised it makes so much difference, I must say.

 

[Peter Duniho]

Switching between struct and class has made little difference, in my
case. I am a little stuck on how I am to reduce creating new objects.
I am still not sure that is my problem.

Sorry if my reply to the other post misled you into thinking I was
suggesting it was. That wasn't my intent.

In fact, I haven't done any serious performance testing, but everything
I've read suggests that in .NET, allocations are extremely fast, and that
even garbage collecting short-lived objects (which, as I understand it,
probably won't happen as long as you've got lots of memory left and your
own code is busy doing constant work) is not very time-consuming.

Of course, if you're using a struct you're not really creating a new
object anyway, so that wouldn't be the problem even if allocations were in
fact expensive.

Thanks for you input. I'll keep digging.

I may have missed it, but have you been able to post a
concise-but-complete code sample that reliably demonstrates the problem?

In this case, I would say that that would mean a console application that
includes timings and shows how much time it takes to do some specific
amount of work, along with your own statement with respect to how much
time you expect or want that work to take.

Pete