在XNA中优化高流量函数

Question

在XNA中优化高流量函数

4

我有一个函数，在每次更新时调用数十万次，我需要对其进行优化。通常情况下，我遵循“不要过早优化”的原则，但这是一个关键的函数，几乎所有代码的时间都花在了这里，因此您能提供的任何建议都会有所帮助。我对优化XNA或C#代码的任何技巧也不太熟悉。你能帮我吗？

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;

- RCIX

请参见更新的答案，不要每次创建“temp”。 - Marc Gravell

添加了一个关于LengthSquared的注释。 - Marc Gravell

另外，我认为你的代码有漏洞...如果我们测试的点不是最近的，而是比如说第二近的，会发生什么？你可能需要进行3次距离测试，分别对_1、_2、_3进行测试。 - Marc Gravell

我将变量distance初始化为float.MaxValue，然后只有在距离小于列表中第一个项目（我假设它是最接近的）时才对变量进行洗牌（丢弃最后一个并将每个变量向上移动一个项目）。因此，在任何给定时间，列表中的第三个项目只有在比列表中的第四个项目更接近但比第二个项目更远时才能到达那里。 - RCIX

这里有一个额外的想法；我想知道你是否可以在最大距离周围建立一个盒子（即一个半径为最近点_3的距离（包括sqrt）的正方形）。然后，您可以通过它们的x/y排除候选点。每当您找到一个新的nearestPoint_3时，您需要维护该框（使其更小）。 - Marc Gravell

如果你需要一个例子，请告诉我。 - Marc Gravell

2个回答

2

首先，尝试使用一维数组而不是矩形数组来存储_restPositions - CLR 优化了零基础的一维数组。只需保持对数组的索引，并在每次迭代时递增它：

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++;
    }
}

如果您可以创建一个构造函数来接收适当的值，而不是使用单独的属性设置器来创建PositionData，那么这可能会有所帮助。

您还多次索引到fourNearestPoints - 有没有什么原因不只使用四个本地变量？这不会有太大的影响，但你永远不知道...

- Jon Skeet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marc Gravell · Accepted Answer

我建议你先尝试放弃使用fourNearestPoints数组... 可以考虑使用4个变量来表示4个最近的位置。因为你总是通过固定的索引来处理它，所以这应该是一个简单的改变，特别是如果你像数组索引一样命名变量：

第一个尝试是失去fourNearestPoints数组...也许只使用4个变量来表示4个最近的位置。你总是通过常数索引来处理这个问题，所以这应该是一个简单的改变，特别是如果你像数组索引一样命名变量:

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

接下来我会关注 _restPositions 的使用；我不确定在这种情况下 GetLength 是否会被优化，所以我会尝试预先缓存它。在线性数组中，.Length 是经过优化的（至少在完整的CLR中）- 但是我认为 GetLength 并没有：

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

此外，“PositionData”是什么？是一个“struct”还是一个“class”？我会尝试将其作为两者来使用-确保它是不可变的，并通过构造函数传递数据，以使IL更加简洁：

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

在接下来的工作中，大部分时间你正在处理被废弃的任务：

    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;
    }

我会做：

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);
}

我对那个distance=...行也很感兴趣；有很多我们看不到的东西可能需要更多的工作——减号运算符和Length()方法。

我猜Length()涉及平方根？（昂贵的）你可以通过使用平方距离来避免这种情况。你可能需要使用一个不带根的平方长度方法，并在整个过程中比较平方长度，但可以节省大量的CPU周期。这可以通过LengthSquared()实现。