18

我有一些 3d 插值代码占用了我项目运行时间的 90%，并且无法预先计算。

我可以使用哪些技术来加快速度？算法优化还是微优化？

这是给感兴趣的人的代码。

它基本上采用放置在 2 个 3d 数组中的数据并插入其余数据。

编辑：此外，我已经将其拆分为更高级别的线程以提高性能，但这对 windows phone 没有帮助，因为它们都是单核......

我可能会执行类似 (Single[] DensityMap = new Single[128 * 128 * 128];) 的操作来移除多维数组命中。我在 100 多个地方访问数组，并希望不必这样做（包装在函数中无济于事，因为 windows phone 不会内联函数调用，然后它无助于性能......）

float[, ,] DensityMap = new float[128, 128, 128];
float[, ,] PressureMap = new float[128, 128, 128];

unchecked
{
    for (int x = 0; x < g_CraftWorldConstants.RegionSizeX; x++)
    {
        int offsetX = (x / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
        int plusOffsetX = SAMPLE_RATE_3D_HOR + offsetX;
        int poxox = plusOffsetX - offsetX;
        double poxxpoxox = ((plusOffsetX - x) / (double)poxox);
        double xoxpoxox = ((x - offsetX) / (double)poxox);

        for (int y = 0; y < g_CraftWorldSettings.GET.RegionSizeY; y++)
        {
            int offsetY = (y / SAMPLE_RATE_3D_VERT) * SAMPLE_RATE_3D_VERT;
            int plusOffsetY = SAMPLE_RATE_3D_VERT + offsetY;
            int poyoy = plusOffsetY - offsetY;
            double poyypoyoy = ((plusOffsetY - y) / (double)poyoy);
            double yoypoyoy = ((y - offsetY) / (double)poyoy);

            for (int z = 0; z < g_CraftWorldConstants.RegionSizeZ; z++)
            {
                if (!(x % SAMPLE_RATE_3D_HOR == 0 && y % SAMPLE_RATE_3D_VERT == 0 && z % SAMPLE_RATE_3D_HOR == 0))
                {
                    int offsetZ = (z / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
                    int plusOffsetZ = SAMPLE_RATE_3D_HOR + offsetZ;
                    int pozoz = plusOffsetZ - offsetZ;
                    double pozzpozoz = ((plusOffsetZ - z) / (double)pozoz);
                    double zozpozoz = ((z - offsetZ) / (double)pozoz);

                    double x00 = poxxpoxox * in_DensityMap[offsetX, offsetY, offsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, offsetY, offsetZ];
                    double x10 = poxxpoxox * in_DensityMap[offsetX, offsetY, plusOffsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, offsetY, plusOffsetZ];
                    double x01 = poxxpoxox * in_DensityMap[offsetX, plusOffsetY, offsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, plusOffsetY, offsetZ];
                    double x11 = poxxpoxox * in_DensityMap[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * in_DensityMap[plusOffsetX, plusOffsetY, plusOffsetZ];

                    double r0 = poyypoyoy * x00 + yoypoyoy * x01;
                    double r1 = poyypoyoy * x10 + yoypoyoy * x11;
                    in_DensityMap[x, y, z] = (float)(pozzpozoz * r0 + zozpozoz * r1);

                    double x02 = poxxpoxox * in_CaveDensity[offsetX, offsetY, offsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, offsetY, offsetZ];
                    double x12 = poxxpoxox * in_CaveDensity[offsetX, offsetY, plusOffsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, offsetY, plusOffsetZ];
                    double x03 = poxxpoxox * in_CaveDensity[offsetX, plusOffsetY, offsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, plusOffsetY, offsetZ];
                    double x13 = poxxpoxox * in_CaveDensity[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * in_CaveDensity[plusOffsetX, plusOffsetY, plusOffsetZ];

                    double r2 = poyypoyoy * x02 + yoypoyoy * x03;
                    double r3 = poyypoyoy * x12 + yoypoyoy * x13;
                    in_CaveDensity[x, y, z] = (float)(pozzpozoz * r2 + zozpozoz * r3);
                }
            }
        }
    }
}
4

5 回答 5

17

看来你有很多机会来优化你的代码。您的 x 循环执行 128 次，您的 y 循环执行 128*128=16,384 次，您的 z 循环执行 128^3=2,097,152 次。z 循环中有许多项仅取决于 x 或 y 迭代，但在每次 z 迭代时都会重新计算它们。例如，

int poxox = plusOffsetX - offsetX;

和

double poxxpoxox = ((plusOffsetX - x) / (double)poxox);

这两个项被计算了超过 200 万次，但如果我对你的函数的粗略扫描是正确的，则只需要计算 128 次。将项移动到适当的循环级别，这样您就不会浪费循环多次重新计算相同的值。

这是您进行了基本优化的代码。我很想知道这如何影响您的运行时间。其中一些项仅取决于迭代值，并且对于 x、y 和 z 是相同的。所以我将它们完全提取出来并预先计算了一次。我还将外部 mod 操作移出内部循环，并修改了逻辑以确保评估短路，这应该会删除以前执行的大部分 mod 操作。

int[] offsets = new int[128];
int[] plusOffsets = new int[128];
double[] poii = new double[128];
double[] ioip = new double[128];
for (int i = 0; i < 128; i++) {
    offsets[i] = (i / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
    plusOffsets[i] = SAMPLE_RATE_3D_HOR + offsets[i];
    double poioi = (double) (plusOffsets[i] - offsets[i]);
    poii[i] = ((plusOffsets[i] - i) / poioi);
    ioip[i] = ((i - offsets[i]) / poioi);
}

float[, ,] DensityMap = new float[128, 128, 128];
float[, ,] PressureMap = new float[128, 128, 128];

for (int x = 0; x < g_CraftWorldConstants.RegionSizeX; x++)
{
    int offsetX = offsets[x];
    int plusOffsetX = plusOffsets[x];
    double poxxpoxox = poii[x];
    double xoxpoxox = ioip[x];
    bool xModNot0 = !(x % SAMPLE_RATE_3D_HOR == 0);

    for (int y = 0; y < g_CraftWorldConstants.RegionSizeY; y++)
    {
        int offsetY = offsets[y];
        int plusOffsetY = plusOffsets[y];
        double poyypoyoy = poii[y];
        double yoypoyoy = ioip[y];
        bool yModNot0 = !(y % SAMPLE_RATE_3D_VERT == 0);

        for (int z = 0; z < g_CraftWorldConstants.RegionSizeZ; z++)
        {
            //if (!(x % SAMPLE_RATE_3D_HOR == 0 && y % SAMPLE_RATE_3D_VERT == 0 && z % SAMPLE_RATE_3D_HOR == 0))
            if (xModNot0 || yModNot0 || !(z % SAMPLE_RATE_3D_HOR == 0))
            {
                int offsetZ = offsets[z];
                int plusOffsetZ = plusOffsets[z];
                double pozzpozoz = poii[z];
                double zozpozoz = ioip[z];

                double x00 = poxxpoxox * DensityMap[offsetX, offsetY, offsetZ] + xoxpoxox * DensityMap[plusOffsetX, offsetY, offsetZ];
                double x10 = poxxpoxox * DensityMap[offsetX, offsetY, plusOffsetZ] + xoxpoxox * DensityMap[plusOffsetX, offsetY, plusOffsetZ];
                double x01 = poxxpoxox * DensityMap[offsetX, plusOffsetY, offsetZ] + xoxpoxox * DensityMap[plusOffsetX, plusOffsetY, offsetZ];
                double x11 = poxxpoxox * DensityMap[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * DensityMap[plusOffsetX, plusOffsetY, plusOffsetZ];

                double r0 = poyypoyoy * x00 + yoypoyoy * x01;
                double r1 = poyypoyoy * x10 + yoypoyoy * x11;
                DensityMap[x, y, z] = (float)(pozzpozoz * r0 + zozpozoz * r1);

                double x02 = poxxpoxox * PressureMap[offsetX, offsetY, offsetZ] + xoxpoxox * PressureMap[plusOffsetX, offsetY, offsetZ];
                double x12 = poxxpoxox * PressureMap[offsetX, offsetY, plusOffsetZ] + xoxpoxox * PressureMap[plusOffsetX, offsetY, plusOffsetZ];
                double x03 = poxxpoxox * PressureMap[offsetX, plusOffsetY, offsetZ] + xoxpoxox * PressureMap[plusOffsetX, plusOffsetY, offsetZ];
                double x13 = poxxpoxox * PressureMap[offsetX, plusOffsetY, plusOffsetZ] + xoxpoxox * PressureMap[plusOffsetX, plusOffsetY, plusOffsetZ];

                double r2 = poyypoyoy * x02 + yoypoyoy * x03;
                double r3 = poyypoyoy * x12 + yoypoyoy * x13;
                PressureMap[x, y, z] = (float)(pozzpozoz * r2 + zozpozoz * r3);
            }
        }
    } 
}
于 2012-05-25T12:36:34.333 回答
8

你可以做一些事情来加速你的代码：

  • 避免使用 multidim.-arrays 因为它们很慢
  • 使用多个线程
  • 将要转换为双精度的变量存储在双精度变量中
  • 预先计算一切你可以（见斧头的帖子）

数组

要模拟 3D 阵列，您可以这样做：

Single[] DensityMap = new Single[128 * 128 * 128];
DensityMap[z + (y * 128) + (x * 128 * 128)] = ...;
于 2012-05-25T12:39:18.373 回答
2

Use a jagged array rather than multi-dimensional, i.e. do

float[][][] DensityMap = new float[128][][];

And then create the inner arrays using for loops, or the LINQ syntax (which might be sub-optimal).

This will give MUCH better performance than using a multi-dimensional array, and equal or better performance than using a single-dimensional array and calculating the offsets yourself. That is, unless the cost of initializing the jagged array is significant; it will after all create 128^2 arrays. I'd benchmark it and only revert to a single-dimensional array if the cost really is significant.

于 2012-05-25T15:42:23.153 回答
1

您可以更改您的 for 循环，因为您没有为所有这些的中间值做任何事情

for (int x = 0; x < 128; x+= SAMPLE_RATE_3D_HOR) {
   for (int y = 0; y < 128; y+= SAMPLE_RATE_3D_VERT) {
      for (int z = 0; z < 128; z+= SAMPLE_RATE_3D_HOR) {

并行执行这些会更好。

有了这个，您可以消除 600 万个 mod % 计算和 60+ 千次乘法。

--edit-- 对不起，我错过了“！” 与 3 个 mods 在线上。您仍然可以跳过其中一些计算。请参阅下面的评论。

于 2012-05-25T15:04:26.417 回答
0

1）你真的需要双打吗？特别是你正在混合一些浮点数、双精度数和整数。

2) 您应该预先计算 k / SAMPLE_RATE_3D_HOR * SAMPLE_RATE_3D_HOR 模式。

int pre_calc[128];
for( int i = 0; i < 128; ++i )
    pre_calc[i] = (i / SAMPLE_RATE_3D_HOR) * SAMPLE_RATE_3D_HOR;
于 2012-05-25T15:22:39.700 回答