Optimizing a high-traffic function in XNA

Question

I have a function that's called hundreds of thousands of times per update, and i need to optimize it. Now, i generally follow the "don't optimize too soon" rule but this is a critical function that virtually all of my code's time is spent in, so anything you can suggest would help. I'm also not that familiar with any sort of tips and tricks that can be used to optimize XNA or c# code. Can you help me?

if (linearPosition.Y < _min.Y || linearPosition.Y > _max.Y)// the nonlinear space commisioned doesn't cover it so that's the behavior i want, same case with next line
{
    return linearPosition;
}
if (linearPosition.X < _min.X || linearPosition.X > _max.X)
{
    return linearPosition;
}
PositionData[] fourNearestPoints = new PositionData[4] 
{
    new PositionData {distance = float.MaxValue},
    new PositionData {distance = float.MaxValue},
    new PositionData {distance = float.MaxValue},
    new PositionData {distance = float.MaxValue}
};

for (int x = 0; x < _restPositions.GetLength(0); x++)
{
    for (int y = 0; y < _restPositions.GetLength(1); y++)
    {
        PositionData temp = new PositionData
        {
            indexX = x,
            indexY = y,
            value = _restPositions[x,y],
            distance = (linearPosition - _restPositions[x,y]).Length()
        };
        if (temp.distance < fourNearestPoints[0].distance)
        {
            fourNearestPoints[3] = fourNearestPoints[2];
            fourNearestPoints[2] = fourNearestPoints[1];
            fourNearestPoints[1] = fourNearestPoints[0];
            fourNearestPoints[0] = temp;
        }
    }
}
Vector2 averageRestVector = new Vector2((fourNearestPoints[0].value.X +
    fourNearestPoints[1].value.X +
    fourNearestPoints[2].value.X +
    fourNearestPoints[3].value.X) / 4,
    (fourNearestPoints[0].value.Y +
    fourNearestPoints[1].value.Y +
    fourNearestPoints[2].value.Y +
    fourNearestPoints[3].value.Y) / 4);
Vector2 averageDeformedVector = new Vector2((_deformedPositions[fourNearestPoints[0].indexX, fourNearestPoints[0].indexY].X +
    _deformedPositions[fourNearestPoints[1].indexX, fourNearestPoints[1].indexY].X +
    _deformedPositions[fourNearestPoints[2].indexX, fourNearestPoints[2].indexY].X +
    _deformedPositions[fourNearestPoints[3].indexX, fourNearestPoints[3].indexY].X) / 4,
    (_deformedPositions[fourNearestPoints[0].indexX, fourNearestPoints[0].indexY].Y +
    _deformedPositions[fourNearestPoints[1].indexX, fourNearestPoints[1].indexY].Y +
    _deformedPositions[fourNearestPoints[2].indexX, fourNearestPoints[2].indexY].Y +
    _deformedPositions[fourNearestPoints[3].indexX, fourNearestPoints[3].indexY].Y) / 4);

Vector2 displacement = averageDeformedVector - averageRestVector;
return linearPosition + displacement;

Answer 1

The first thing I'd try is losing the fourNearestPoints array... Perhaps using just 4 variables for the 4 nearest locations. You always treat this by constant index, so this should be a simple change, especially if you name like the array index:

PositionData fourNearestPoints_0 = ...,
             fourNearestPoints_1 = ...,
             fourNearestPoints_2 = ...,
             fourNearestPoints_3 = ...;

---

The next thing I'd look at is the _restPositions usage; I don't know if GetLength (in this use) will be optimized out, so I would try pre-caching that. In a linear array, .Length is optimized (in the full CLR, at least) - but not GetLength AFAIK:

int width = _restPositions.GetLength(0), height = _restPositions.GetLength(1);
for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)

---

Also; what is PositionData? A struct or a class? I would be tempted to try this as both - making sure it is immutable, and passing in the data via the constructor to make the IL slimmer:

PositionData temp = new PositionData(x, y, _restPositions[x,y],
        (linearPosition - _restPositions[x,y]).Length());

---

In the following, you are doing some work that is discarded most of the time:

    PositionData temp = new PositionData
    {
        indexX = x,
        indexY = y,
        value = _restPositions[x,y],
        distance = (linearPosition - _restPositions[x,y]).Length()
    };
    if (temp.distance < fourNearestPoints[0].distance)
    {
        fourNearestPoints[3] = fourNearestPoints[2];
        fourNearestPoints[2] = fourNearestPoints[1];
        fourNearestPoints[1] = fourNearestPoints[0];
        fourNearestPoints[0] = temp;
    }

I would do:

var distance = (linearPosition - _restPositions[x,y]).Length();
if (distance < fourNearestPoints_0.distance) {
    fourNearestPoints_3 = fourNearestPoints_2;
    fourNearestPoints_2 = fourNearestPoints_1;
    fourNearestPoints_1 = fourNearestPoints_0;
    fourNearestPoints_0 = new PositionData(x, y, _restPositions[x,y], distance);
}

---

I'm also interested in that that distance=... line; there is a lot there that we can't see that might need more work - the - operator, and the Length() method.

---

Am I right in assuming that Length() involves a square-root? (expensive) You could avoid this by working in square distances instead. You might need to make this explicit with a square-length method that doesn't take the root, and compare square lengths throughout, but you can save lots of CPU cycles. This is available as LengthSquared().

Answer 2

For one thing, try using a one-dimensional array instead of a rectangular array for _restPositions - the CLR is optimised for zero-based one-dimensional arrays. Just keep an index into the array, and increment it on each iteration:

int index = 0;
// I'm assuming you can pass in width and height separately
for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)
    {
        PositionData temp = new PositionData
        {
            indexX = x,
            indexY = y,
            value = _restPositions[index],
            distance = (linearPosition - _restPositions[index]).Length()
        };
        if (temp.distance < fourNearestPoints[0].distance)
        {
            fourNearestPoints[3] = fourNearestPoints[2];
            fourNearestPoints[2] = fourNearestPoints[1];
            fourNearestPoints[1] = fourNearestPoints[0];
            fourNearestPoints[0] = temp;
        }
        index++;
    }
}

If you could make a constructor to PositionData which took appropriate values instead of having separate property setters, that might help too.

You're also indexing into fourNearestPoints several times - any reason not to just use four local variables? It won't do much, but you never know...