18

プロジェクトの実行時間の90％を占め、事前計算できない3D補間コードがあります。

これをスピードアップするために使用できるテクニックは何ですか？アルゴリズムまたはマイクロ最適化？

これが興味のある人のためのコードです。

基本的に、2つの3D配列に配置されたデータを取得し、残りのデータを補間します。

編集：また、パフォーマンスを向上させるために、これをより高いレベルでスレッドに分割していますが、Windows Phoneはすべてシングルコアであるため、これは役に立ちません...

マルチD配列のヒットを削除するには、おそらく（Single [] DensityMap = new Single [128 * 128 * 128];）のようなことをします。私は何百もの場所で配列にアクセスし、それを行う必要がないことを望んでいました（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);

これら 2 つの項は ​​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 は遅いので使用しないでください
  • 複数のスレッドを使用する
  • double 変数に double としてキャストされる変数を格納する
  • できることはすべて事前に計算してください (手斧の投稿を参照)

配列

3D アレイをシミュレートするには、次のようにします。

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

多次元ではなくジャグ配列を使用します。

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

次に、for ループまたはLINQ 構文(最適ではない可能性があります)を使用して内部配列を作成します。

これにより、多次元配列を使用するよりもはるかに優れたパフォーマンスが得られ、1 次元配列を使用して自分でオフセットを計算するよりも同等またはそれ以上のパフォーマンスが得られます。つまり、ジャグ配列を初期化するコストが重要でない限りです。結局、128^2 の配列が作成されます。私はそれをベンチマークし、コストが本当に重要な場合にのみ 1 次元配列に戻します。

于 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 % 計算と 6 万回以上の乗算を排除できます。

--編集-- 申し訳ありませんが、「!」が抜けていました。3つのモッズであなたのラインに。これらの計算の一部をスキップすることもできます。以下のコメントを参照してください。

于 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 に答える