Is there a low-level difference between int[large][small] or int[small][large] in Java?

Question

This question will probably require some compiler knowledge to answer. I am currently working on a project where I will be creating an array that may be either

int[2][veryLargeNumber] 

or

int [veryLargeNumber][2] 

It makes no difference logically but I was thinking that the form (and therefore size) in memory may differ (perhaps the question should be, are the compilers clever enough to rearrange arrays to suit them)?

Answer 1

Interesting question, I ran a simple program

int N = 100000000; long start = System.currentTimeMillis(); int[][] a = new int[2][N]; System.out.println(System.currentTimeMillis() - start + " ms"); 

Which resulted in 160 ms. Then I ran the other variant

int N = 100000000; long start = System.currentTimeMillis(); int[][] a = new int[N][2]; System.out.println(System.currentTimeMillis() - start + " ms"); 

Which resulted in 30897 ms. So indeed the first option seems much better.

Answer 2

Java only actually implements single dimensional arrays. It has multi-dimensional types, however two dimensional arrays are actually implemented as an array of arrays. Each array has an overhead of about 16 bytes. You are better off with int[2][x] to minimise overhead.

You can avoid this issue entirely by using helper methods.

final int[] array = new int[2 * veryLargeNumber];  public int get(int x, int y) {     return array[idx(x, y)]; }  public void set(int x, int y, int val) {     array[idx(x, y)] = val; }  private int idx(int x, int y) {     return x * 2 + y; // or x * veryLargeNumber + y; } 

To provide this to yourself, each object hash a unique, generate hashCode which is stored in its Object header.

You can see from http://ideone.com/oGbDJ0 that each nested array is an object in itself.

int[][] array = new int[20][2]; for (int[] arr : array) {     System.out.println(arr); } 

prints the internal representation of an int[] which is [I followed by @ followed by the hashCode() stored in the header. This is not as some believe, the address of the object. The address can't be used as the hashCode, as the object can be moved at any time by the GC (unless you have a JVM which never moves objects)

[I@106d69c [I@52e922 [I@25154f [I@10dea4e [I@647e05 [I@1909752 [I@1f96302 [I@14eac69 [I@a57993 [I@1b84c92 [I@1c7c054 [I@12204a1 [I@a298b7 [I@14991ad [I@d93b30 [I@16d3586 [I@154617c [I@a14482 [I@140e19d [I@17327b6 

You can see how much memory is used if you turn off the TLAB with -XX:-UseTLAB https://github.com/peter-lawrey/Performance-Examples/blob/master/src/main/java/vanilla/java/memory/ArrayAllocationMain.java

public static void main(String[] args) {      long used1 = memoryUsed();     int[][] array = new int[200][2];      long used2 = memoryUsed();     int[][] array2 = new int[2][200];      long used3 = memoryUsed();     if (used1 == used2) {         System.err.println("You need to turn off the TLAB with -XX:-UseTLAB");     } else {         System.out.printf("Space used by int[200][2] is " + (used2 - used1) + " bytes%n");         System.out.printf("Space used by int[2][200] is " + (used3 - used2) + " bytes%n");     } }  public static long memoryUsed() {     Runtime rt = Runtime.getRuntime();     return rt.totalMemory() - rt.freeMemory(); } 

prints

Space used by int[200][2] is 5720 bytes Space used by int[2][200] is 1656 bytes