Java 2D数组填充-无意的优化导致严重减速。

Question

Java 2D数组填充-无意的优化导致严重减速。

javaarraysperformancemultidimensional-arraybenchmarking

25

我尝试用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

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

_{附言：Java版本为1.8.0-ea-b124，64位3.2 GHz AMD处理器，基准测试在单线程中执行。}

- leventov

1

你可能想阅读这个：https://dev59.com/eGQn5IYBdhLWcg3wn4NS - Mysticial

1

@Mysticial 我不相信缓存争用会导致x23的减速。 - leventov

如果你把 8189 远离 8192，性能会发生如何的变化？ - Mysticial

3

在你的“优化”版本中，你减少了比较和迭代所需的时间，但是增加了（很多）数组访问，其中3个因素中的数组访问成本最高。参见：https://dev59.com/90nSa4cB1Zd3GeqPNV0a - pedromss

@Mysticial 我希望内部数组恰好占用8页，但显然我忘记应用“-XX：+ UseCompressedOops”，它们占用了8页+ 4个字节:( - leventov

4个回答

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

有人可以解释一下为什么这样会更快吗？

- Chen Gupta

我明白了，你为第二次运行分配了一个新的数组，但是，你尝试过改变“未优化”和“优化”运行的顺序吗？ - fiktor

是的，它有一点不同，但第二个版本仍然更好。 - Chen Gupta

1

http://www.learn-java-tutorial.com/Arrays.cfm#Multidimensional-Arrays-in-Memory

图片：http://www.learn-java-tutorial.com/images/4715/Arrays03.gif

int[][] === 值的数组的数组

int[] === 值的数组

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

        int g[][] = new int[n][n];
        long st, en;

        // one
        st = System.nanoTime();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                g[i][j] = 10; 
            }
        }
        en = System.nanoTime();
        System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");

        // two
        st = System.nanoTime();
        for(int i = 0; i < n; i++) {
            g[i][i] =  20;
            for(int j = 0; j < i; j++) {
                g[j][i] = g[i][j] = 20; 
            }
        }
        en = System.nanoTime();
        System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");

        // 3
        int arrLen = n*n;
        int[] arr = new int[arrLen];
        st = System.nanoTime();
        for(int i : arr) {
            arr[i] = 30;
        }
        en = System.nanoTime();
        System.out.println("\n3   time " + (en - st)/1000000.d + " msc");

        // 4
        st = System.nanoTime();
        int i, j;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                arr[i*n+j] = 40;
            }
        }
        en = System.nanoTime();
        System.out.println("\n4   time " + (en - st)/1000000.d + " msc");
    }
}

两次 71.998012 毫秒

两次 551.664166 毫秒

3 次 63.74851 毫秒

4 次 57.215167 毫秒

P.S. 我不是 Java 规范 =)

- VoidVolker

0

我明白了，你为第二次运行分配了一个新的数组，但是你尝试过改变“未优化”和“已优化”的顺序吗？-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

- Chen Gupta

最好编辑原始答案并在评论中使用提及通知fictor：@fictor - leventov

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

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

- maaartinus · Accepted Answer

一个侧面说明：即使我们暂时不考虑所有可能存在的问题，你的“优化”版本可能根本不会更快。现代CPU中有多个资源，饱和其中一个可能会阻止任何改进。我的意思是：速度可能受到存储绑定的限制，在一次迭代中尝试以两倍的速度编写可能根本不会改变任何东西。

我能看出三个可能的原因：

您的访问模式可能会强制实施边界检查。在“简单”的循环中，它们显然可以被消除，在“优化”的循环中只有当数组是正方形时才能明显地消除。它是这样的，但是这个信息只在方法之外可用（而且不同的代码块可以改变它！）。
在您的“优化”循环中，内存局部性很差。它基本上访问随机的内存位置，因为在Java中没有像2D数组这样的东西（仅有一个数组的数组，对于其new int [N] [N]只是一个快捷方式）。在按列迭代时，您仅使用每个已加载缓存行中的单个int，即64字节中的4字节。
内存预取器可能会对您的访问模式产生问题。带有其8189 * 8189 * 4字节的数组太大了，无法适合任何缓存。现代CPU具有预取器，允许在发现常规访问模式时提前加载缓存行。预取器的功能差异很大。这可能与您仅编写有关，但我不确定是否可以写入尚未获取的缓存行。

我猜内存局部性是主要的问题：

我添加了一个名为“reversed”的方法，它的工作方式就像简单一样，但是使用

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