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

Question

我试图通过计算两个元素的每个和,相对于主对角线相反,优化每个元素的索引和的方形二维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

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

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

Answer 1

旁注:即使我们将所有可能的问题都抛在一边,您的"优化"版本可能也不会更快.现代CPU中有多种资源,其中一种资源可能会阻止您进行任何改进.我的意思是:速度可能受内存限制,并且尝试在一次迭代中写入速度快两倍可能根本不会改变任何内容.

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

• 您的访问模式可以强制执行绑定检查.在"简单"循环中,只有当数组是正方形时,它们才能在"优化"中明显消除.它是,但这个信息只在方法之外可用(而且一段不同的代码可以改变它!).

• "优化"循环中的内存位置不好.它访问基本上随机的内存位置,因为在Java中没有像2D数组那样(只有一个数组的数组new int[N][N]是快捷方式).在按列迭代时,您只使用int每个加载的高速缓存行中的一个,即64个中的4个字节.

• 该内存预取器可以有你的访问模式的问题.具有8189*8189*4字节的数组太大,无法容纳在任何缓存中.现代CPU具有预取器,当它发现常规访问模式时,允许预先加载高速缓存行.prefetchers的功能差异很大.这可能与此无关,因为您只是在编写,但我不确定是否可以写入尚未获取的缓存行.

我猜内存位置是罪魁祸首:

我添加了一个方法"逆转",它的工作方式就像简单,但有

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