爪哇：多维数组对一维

Question

例如：

• 一个）int [x][y][z]

  VS

• B）int[x*y*z]

最初以为我会去a）为简单起见

我知道Java不像C那样在内存中线性存储数组。但是这对我的程序有什么影响？

Answer 1

通常情况下，最好的东西对于这样的问题，搜索anwers时做的是看选用的是如何编译成JVM字节码：

multi = new int[50][50]; 
single = new int[2500]; 

这被翻译成：

BIPUSH 50 
BIPUSH 50 
MULTIANEWARRAY int[][] 2 
ASTORE 1 
SIPUSH 2500 
NEWARRAY T_INT 
ASTORE 2 

因此，如您所见，JVM已知道我们正在讨论多维数组。

进一步保持它：

for (int i = 0; i < 50; ++i) 
    for (int j = 0; j < 50; ++j) 
    { 
     multi[i][j] = 20; 
     single[i*50+j] = 20; 
    } 

这被翻译（跳过周期）分为：

ALOAD 1: multi 
ILOAD 3: i 
AALOAD 
ILOAD 4: j 
BIPUSH 20 
IASTORE 

ALOAD 2: single 
ILOAD 3: i 
BIPUSH 50 
IMUL 
ILOAD 4: j 
IADD 
BIPUSH 20 
IASTORE 

所以， 你可以看到， 多维阵列在内部处理中虚拟机， 无用的指令产生的开销， 而使用单一的指令使用更多的指令，因为抵消是手工计算。

我不认为表现会是这样的问题。

编辑：

我做了一些简单的基准测试，看看是怎么回事了这里。 我选择尝试不同的例子： 线性读取， 线性写入， 和随机存取。 时间以毫秒表示（并使用System.nanoTime()计算。 下面是结果：

线性写

• 尺寸：100×100（10000） 多：5.786591 单：6.131748
• 尺寸：200×200（40000） 多：1.216366 单：0.782041
• 尺寸：500×500（250000） 多：7.177029 单：3.667017
• 尺寸：1000x100 0（1000000） 多：30.508131 单个：18.064592
• 尺寸：2000×2000（400万） 多：185.3548 单个：155.590313
• 尺寸：5000x5000（25000000） 多：955.5299 单个：923.264417
• 尺寸：10000x10000（100000000） 多：4084.798753 单个：4015.448829

线性读

• 尺寸：100×100（10000） 多：5.241338 单：5.135957
• 尺寸：200×200（40000） 多：0.080209 单：0.044371
• 尺寸：500×500（250000） 多：0.088742 单：0.084476
• 尺寸：1000×1000（1000000） 多：0.232095 单：0.167671
• 尺寸：2000×2000（400万） 多：0.481683 单：0.33321
• 尺寸：5000x5000（25000000） 多：1.222339 单：0.828118 大小：10000x10000（100000000） 多：2.496302 单：1.650691

随机读

• 尺寸：100x100（10000） Multi：22.317393 Single：8.546134
• 尺寸：200×200（40000） 多：32.287669 单个：11.022383
• 尺寸：500×500（250000） 多：189.542751 单个：68.181343
• 尺寸：1000×1000（1000000） 多：1124.78609 单个：272.235584
• 尺寸：2000×2000（400万） 多：6814.477101 单：1091.998395
• 尺寸：5000x5000（25000000） 多：50051.306239 单：7028。422262

随机的一个有点误导，因为它为多维数组生成2个随机数，而对于单维（和PNRG可能消耗一些CPU）只产生一个随机数。

请注意，我试图让JIT在同一循环的第20次运行后才通过基准测试工作。为了完整我的Java VM如下：

Java版本 “1.6.0_17” 的Java（TM）SE运行时环境（建立1.6.0_17-B04） 的HotSpot的Java（TM）64位服务器VM（构建14.3-B01，混合模式）

Answer 2

如果你选择后一种路线，那么你将不得不为每一个数组访问执行算术。这将是一个痛苦和错误的倾向（除非你把它包装在提供这种功能的类中）。

我不认为在选择平面数组时有任何（显着的）优化（尤其是考虑到用于索引的算术）。与优化一样，您需要执行一些测量并确定它是否真的值得。

Answer 3

使用第一变体（3维），因为它是更容易理解并有机会少做一些逻辑错误（特别是如果你使用它的造型3维空间）

Answer 4

在当前的CPU，非缓存存储器访问是几百倍算术（见this presentation和读What every programmer should know about memory）慢。 a）选项将导致大约3次内存查找，而b）选项将导致大约1次内存查找。此外，CPU的预取算法也可能无法正常工作。所以b）选项在某些情况下可能会更快（这是一个热点，并且阵列不适合CPU的缓存）。快多少？ - 这取决于应用程序。

我个人会首先使用a）选项，因为它会导致更简单的代码。如果剖析器显示数组访问是一个瓶颈，那么我会将它转换为b）选项，以便有一对帮助器方法用于读取和写入数组值（这样混乱的代码将被限制为这两个方法）。

我做了一个比较3维int数组（“多”列）与等效1维int数组（“单”列）的基准。代码是here和测试here。我使用JVM选项-server -Xmx3G -verbose:gc -XX:+PrintCompilation（我从以下结果中删除了调试输出）将它运行在64位jdk1.6.0_18，Windows 7 x64，Core 2 Quad Q6600 @ 3.0 GHz，4 GB DDR2上。结果如下：

Out of 20 repeats, the minimum time in milliseconds is reported. 

Array dimensions: 100x100x100 (1000000) 
      Multi Single 
Seq Write 1  1 
Seq Read 1  1 
Random Read 99  90 (of which generating random numbers 59 ms) 

Array dimensions: 200x200x200 (8000000) 
      Multi Single 
Seq Write 14  13 
Seq Read 11  8 
Random Read 1482 1239 (of which generating random numbers 474 ms) 

Array dimensions: 300x300x300 (27000000) 
      Multi Single 
Seq Write 53  46 
Seq Read 34  24 
Random Read 5915 4418 (of which generating random numbers 1557 ms) 

Array dimensions: 400x400x400 (64000000) 
      Multi Single 
Seq Write 123  111 
Seq Read 71  55 
Random Read 16326 11144 (of which generating random numbers 3693 ms) 

这表明1维阵列要快一些。虽然差异非常小，但对于99％的应用程序而言，它并不会引人注目。

我也做了一些测量，以便通过用preventOptimizingAway += x * y * z;代替preventOptimizingAway += array.get(x, y, z);来估计在Random Read基准中产生随机数的开销，并手动将测量结果添加到上述结果表中。生成随机数占随机读取基准测试总时间的1/3或更少，所以内存访问如预期般支配基准。用4维和更多维的数组重复这个基准将会很有趣。可能会使速度差异更大，因为多维数组的最高级别将适合CPU的高速缓存，并且只有其他级别需要查找内存。