Java: Multi-dimensional array vs. one-dimensional

Question

For example:

• a) int [x][y][z]

  vs

• b) int[x*y*z]

Initially thought I'd go with a) for simplicity.

I know that Java doesn't store arrays linearly in memory like C does, but what implications does this have for my program?

Answer 1

Usually the best thing to do when searching anwers for such questions is to see how the choices are compiled into JVM bytecode:

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

This is translated into:

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

So, as you can see, the JVM already knows that we are talking about a multi dimensional array.

Keeping it further:

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

This is translated (skipping the cycles) into:

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

So, as you can see, the multi-dimensional array is treated internally in the VM, no overhead generated by useless instructions, while using a single one uses more instructions since offset is calculated by hand.

I don't think that performance will be such an issue.

EDIT:

I did some simple benchmarks to see what's going down here. I chose to try different examples: linear read, linear write, and random access. Times are expressed in millisecs (and calculated using System.nanoTime(). Here are the results:

Linear write

• Size: 100x100 (10000)
  • Multi: 5.786591
  • Single: 6.131748
• Size: 200x200 (40000)
  • Multi: 1.216366
  • Single: 0.782041
• Size: 500x500 (250000)
  • Multi: 7.177029
  • Single: 3.667017
• Size: 1000x1000 (1000000)
  • Multi: 30.508131
  • Single: 18.064592
• Size: 2000x2000 (4000000)
  • Multi: 185.3548
  • Single: 155.590313
• Size: 5000x5000 (25000000)
  • Multi: 955.5299
  • Single: 923.264417
• Size: 10000x10000 (100000000)
  • Multi: 4084.798753
  • Single: 4015.448829

Linear read

• Size: 100x100 (10000)
  • Multi: 5.241338
  • Single: 5.135957
• Size: 200x200 (40000)
  • Multi: 0.080209
  • Single: 0.044371
• Size: 500x500 (250000)
  • Multi: 0.088742
  • Single: 0.084476
• Size: 1000x1000 (1000000)
  • Multi: 0.232095
  • Single: 0.167671
• Size: 2000x2000 (4000000)
  • Multi: 0.481683
  • Single: 0.33321
• Size: 5000x5000 (25000000)
  • Multi: 1.222339
  • Single: 0.828118
• Size: 10000x10000 (100000000)
  • Multi: 2.496302
  • Single: 1.650691

Random read

• Size: 100x100 (10000)
  • Multi: 22.317393
  • Single: 8.546134
• Size: 200x200 (40000)
  • Multi: 32.287669
  • Single: 11.022383
• Size: 500x500 (250000)
  • Multi: 189.542751
  • Single: 68.181343
• Size: 1000x1000 (1000000)
  • Multi: 1124.78609
  • Single: 272.235584
• Size: 2000x2000 (4000000)
  • Multi: 6814.477101
  • Single: 1091.998395
• Size: 5000x5000 (25000000)
  • Multi: 50051.306239
  • Single: 7028.422262

The random one is a little misleading since it generates 2 random numbers for multi-dimensional array while just one for single dimensional (and PNRGs may consume some CPU).

Mind that I tried to let JIT work by benchmarking only after the 20th run of the same loop. For completeness my java VM is the following:

java version "1.6.0_17" Java(TM) SE Runtime Environment (build 1.6.0_17-b04) Java HotSpot(TM) 64-Bit Server VM (build 14.3-b01, mixed mode)