Java 2D数组填充 - 无辜的优化导致可怕的减速

arrays performance multidimensional-array java benchmarking

2022-09-01 17:48:33

我尝试通过计算两个元素的每个总和来优化正方形二维Java数组的填充，其中包含每个元素的索引和，相对于主对角线相反。但是，我没有加速，或者至少是可比的性能，而是代码慢了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

问题：
如何解释如此巨大的性能下降？

_{P. S. Java 版本是 1.8.0-ea-b124，64 位 3.2 GHz AMD 处理器，基准测试在单个线程中执行。}

答案 1

旁注：即使我们将所有可能的问题放在一边，您的“优化”版本可能根本不会更快。现代 CPU 中有多个资源，其中一个资源饱和可能会使您无法进行任何改进。我的意思是：速度可能是内存绑定的，并且尝试在一次迭代中以两倍的速度写入可能根本不会改变任何东西。

我可以看到三个可能的原因：

您的访问模式可能会强制执行绑定检查。在“简单”循环中，它们显然可以被消除，只有在数组是正方形的情况下，在“优化”中。是的，但此信息仅在方法之外可用（此外，另一段代码可能会更改它！
“优化”循环中的内存局部性是坏的。它基本上访问随机内存位置，因为Java中没有像2D数组（只有数组数组是快捷方式）一样。按列迭代时，您仅使用每个加载的高速缓存行中的单个 int，即 64 个字节中的 4 个字节。new int[N][N]
内存预取程序可能存在访问模式问题。具有 8189 * 8189 * 4 字节的数组太大，无法放入任何缓存。现代CPU有一个预取器，允许提前加载缓存行，当它发现常规访问模式时。预取器的能力差异很大。这可能在这里无关紧要，因为你只是在写，但我不确定是否有可能写入尚未获取的缓存行。

我猜記憶地點是罪魁禍首：

我添加了一个“反向”方法，其工作原理很简单，但

g[j][i] = i + j;

而不是

g[i][j] = i + j;

这种“无害”的变化是一种性能下降：

Benchmark                                Mode   Samples         Mean   Mean error    Units
o.o.j.s.ArrayFillBenchmark.optimized     avgt        20       10.484        0.048    ns/op
o.o.j.s.ArrayFillBenchmark.reversed      avgt        20       20.989        0.294    ns/op
o.o.j.s.ArrayFillBenchmark.simple        avgt        20        0.693        0.003    ns/op

答案 2

我写的版本比“简单”更快。但是，我不知道为什么它更快（。代码如下：

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

有人可以向我解释为什么它更快吗？