java 処理速度 改善 - Java 2D配列の塗りつぶし - 無邪気な最適化によりひどい減速



2 Answers

私は "シンプル"より速く動作するバージョンを書いた。 しかし、なぜそれが速いのかわかりません(ここにコードがあります:

class A {
  public static void main(String[] args) {
    int n = 8009;

    long st, en;

    // one
    int gg[][] = new int[n][n];
    st = System.nanoTime();
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        gg[i][j] = i + j; 
      }
    }
    en = System.nanoTime();

    System.out.println("\nOne time " + (en - st)/1000000.d + " msc");

    // two
    int g[][] = new int[n][n];
    st = System.nanoTime();
    int odd = (n%2), l=n-odd;
    for(int i = 0; i < l; ++i) {
      int t0, t1;   
      int a0[] = g[t0 = i];
      int a1[] = g[t1 = ++i];
      for(int j = 0; j < n; ++j) {
        a0[j] = t0 + j;
        a1[j] = t1 + j;
      }
    }
    if(odd != 0)
    {
      int i = n-1;
      int a[] = g[i];
      for(int j = 0; j < n; ++j) {
        a[j] = i + j;
      }
    }
    en = System.nanoTime();
    System.out.println("\nOptimized time " + (en - st)/1000000.d + " msc");

    int r = g[0][0]
    //  + gg[0][0]
    ;
    System.out.println("\nZZZZ = " + r);

  }
}

結果は次のとおりです。

One time 165.177848 msc

Optimized time 99.536178 msc

ZZZZ = 0

誰かが私になぜそれが速いのかを説明することはできますか?

java 高速化 設定

私は、正方形の2次元Java配列の塗りつぶしを各要素のインデックスの合計で最適化しようとしました。これは、2つの要素に対してそれぞれの合計を1回計算し、主対角線に対して反対です。 しかし、スピードアップまたは少なくとも同等のパフォーマンスの代わりに、私は23(!)倍遅いコードを持っています。

私のコード:

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(ArrayFill.N * ArrayFill.N)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ArrayFill {
    public static final int N = 8189;
    public int[][] g;

    @Setup
    public void setup() { g = new int[N][N]; }

    @GenerateMicroBenchmark
    public int simple(ArrayFill state) {
        int[][] g = state.g;
        for(int i = 0; i < g.length; i++) {
            for(int j = 0; j < g[i].length; j++) {
                g[i][j] = i + j;
            }
        }
        return g[g.length - 1][g[g.length - 1].length - 1];
    }

    @GenerateMicroBenchmark
    public int optimized(ArrayFill state) {
        int[][] g = state.g;
        for(int i = 0; i < g.length; i++) {
            for(int j = 0; j <= i; j++) {
                g[j][i] = g[i][j] = i + j;
            }
        }
        return g[g.length - 1][g[g.length - 1].length - 1];
    }
}

ベンチマーク結果:

Benchmark               Mode     Mean   Mean error    Units
ArrayFill.simple        avgt    0.907        0.008    ns/op
ArrayFill.optimized     avgt   21.188        0.049    ns/op


質問:
どうしてそんなに大きなパフォーマンス低下が説明できますか?

PS Javaのバージョンは1.8.0-ea-b124,64-bit 3.2 GHz AMDプロセッサーで、ベンチマークは1つのスレッドで実行されました。




私は、2番目の実行のために新しい配列を割り当てましたが、まだ、 "最適化されていない"および "最適化された"実行の順序を変更しようとしましたか? - fikto

私はそれらの順序を変更し、それを少し最適化しました:

class A {
  public static void main(String[] args) {
    int n = 8009;
    double q1, q2;
    long st, en;

    // two
    int g[][] = new int[n][n];
    st = System.nanoTime();
    int odd = (n%2), l=n-odd;
    for(int i = 0; i < l; ++i) {
      int t0, t1;   
      int a0[] = g[t0 = i];
      int a1[] = g[t1 = ++i];
      for(int j = 0; j < n; ++j, ++t0, ++t1) {
        a0[j] = t0;
        a1[j] = t1;
      }
    }
    if(odd != 0)
    {
      int i = n-1;
      int a[] = g[i];
      for(int j = 0; j < n; ++j, ++i) {
        a[j] = i;
      }
    }
    en = System.nanoTime();
    System.out.println("Optimized time " + (q1=(en - st)/1000000.d) + " msc");

    // one
    int gg[][] = new int[n][n];
    st = System.nanoTime();
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        gg[i][j] = i + j; 
      }
    }
    en = System.nanoTime();

    System.out.println("One time " + (q2=(en - st)/1000000.d) + " msc");

    System.out.println("1 - T1/T2 = " + (1 - q1/q2));

  }
}

結果は次のとおりです。

Optimized time 99.360293 msc
One time 162.23607 msc
1 - T1/T2 = 0.3875573231033026



Related