Is there a low-level difference between int[large][small] or int[small][large] in Java?
JavaArraysMemoryMultidimensional ArrayJvmJava Problem Overview
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)?
Java Solutions
Solution 1 - Java
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
Solution 2 - Java
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.
Solution 3 - Java
int[2][veryLargeNumber]
creates two arrays with verlarnumber of items
while
int[veryLargeNumber][2]
creates verylargenumber of arrays having two items.
Note: array creation has a overhead. so preferred the first one
Solution 4 - Java
In short, int[2][veryLargeNumber]
is the better approach.
The one suggested by Peter (int[] array = new int[2 * veryLargeNumber];
) is even better, or if memory is your problem, then you can use longs instead of integers (long[] array = new long[veryLargeNumber];
) and bitwise operators, or better yet, use caching whenever possible.
Beware! The representation [I@106d69c
in most JDK/JRE distributions (Sun's & Oracle's) is given by System.identityHashCode()
and it's not guaranteed to be unique per each object. So you cannot rely on System.out.println(array);
to check the unicity of the array object.