Java:多维数组与一维数组

Question

例如:

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

  VS

• b) int[x*y*z]

最初我认为我会选择a)以简化

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

Answer 1

通常,在搜索此类问题时,最好的办法是查看如何将选项编译为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

因此,正如您所看到的,多维数组在VM内部处理,没有无用指令产生的开销,而使用单个数据则使用更多指令,因为偏移是手动计算的.

我认为性能不会是这样的问题.

编辑:

我做了一些简单的基准测试,看看这里发生了什么.我选择尝试不同的例子:线性读取,线性写入和随机访问.时间以毫秒表示(并使用计算System.nanoTime().以下是结果:

线性写入

• 尺寸:100x100(10000)多:5.786591单身:6.131748
• 尺寸:200x200(40000)多种:1.216366单身:0.782041
• 尺寸:500x500(250000)多种:7.177029单身:3.667017
• 尺寸:1000x1000(1000000)倍数:30.508131单身:18.064592
• 大小:2000x2000(4000000)倍数:185.3548单身:155.590313
• 尺寸:5000x5000(25000000)多种:955.5299单身:923.264417
• 尺寸:10000x10000(100000000)倍数:4084.798753单身:4015.448829

线性读取

• 尺寸:100x100(10000)多:5.241338单:5.135957
• 尺寸:200x200(40000)多:0.080209单:0.044371
• 尺寸:500x500(250000)多:0.088742单身:0.084476
• 尺寸:1000x1000(1000000)多:0.232095单:0.167671
• 尺寸:2000x2000(4000000)倍数:0.481683单身:0.33321
• 尺寸:5000x5000(25000000)多:1.222339单身:0.828118尺寸:10000x10000(100000000)多:2.496302单身:1.650691

随机阅读

• 尺寸:100x100(10000)倍数:22.317393单身:8.546134
• 尺寸:200x200(40000)多:32.287669单身:11.022383
• 尺寸:500x500(250000)多:189.542751单身:68.181343
• 大小:1000x1000(1000000)多个:1124.78609单身:272.235584
• 大小:2000x2000(4000000)多: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)Java HotSpot(TM)64位服务器VM(版本14.3-b01,混合模式)

Answer 2

在当前的CPU上,非缓存内存访问速度比算术缓慢几百倍(参见本演示文稿并阅读每个程序员应该了解的内存).a)选项将导致大约3次内存查找,而b)选项将导致大约1次内存查找.CPU的预取算法也可能不起作用.因此b)选项在某些情况下可能更快(它是一个热点,并且数组不适合CPU的缓存).多快了？ - 这取决于应用程序.

我个人首先会使用a)选项,因为它会产生更简单的代码.如果探查器显示数组访问是瓶颈,那么我会将其转换为b)选项,以便有一对帮助方法来读取和写入数组值(这样凌乱的代码将被限制为那两个方法).

我做了一个基准,用于比较三维int数组("Multi"列)和等效的1维int数组("Single"列).代码在这里并在这里进行测试.我使用JVM选项在64位jdk1.6.0_18,Windows 7 x64,Core 2 Quad Q6600 @ 3.0 GHz,4 GB DDR2上运行它-server -Xmx3G -verbose:gc -XX:+PrintCompilation(我已从以下结果中删除了调试输出).结果是:

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 += array.get(x, y, z);与preventOptimizingAway += x * y * z;和手工添加的测量,以上述结果表.生成随机数需要随机读取基准测试总时间的1/3或更少,因此内存访问在预期基准测试中占主导地位.用4维和更多维的数组重复这个基准测试会很有趣.可能会使速度差更大,因为多维数组的最高级别适合CPU的缓存,只有其他级别需要内存查找.