We're taught that Java's ArrayList is less efficient for integers, because the list actually contains pointers, while an array of ints contains the integers in place, thus avoiding memory allocations and access.
My question is whether the JDK/JIT compiler optimizes this kind of inefficiency away? It has all the information to conclude these implementations are functionally equivalent , so it might as well replace ArrayList with an int[]-backed implementation under the hood.
No, it can't, because you can store null in an ArrayList.
EDIT: Oh, and it also can't because generics are erased at compile time — at run time, the JRE can't distinguish ArrayLists by their element types. IOW, it's worse than just null — you can store any object in an ArrayList<Integer>.
null issue is a permanent blocker for going all the way to int[]. Moreover, I know of quite a bit of code which stores nulls in arraylists, so it's not something that's likely to be able to vanish.
It could in theory but it doesn't. It may not be more efficient unless auto-boxing could be optimised out as well.
You can instead http://trove4j.sourceforge.net/javadocs/gnu/trove/TIntArrayList.html which wraps int[].
int isn't type-related to Object. While it would have been possible for the generic system to have been designed to support this sort of thing, it would have involved a much larger change to the classloader system than the language developers could stomach. After all, Java is deliberately less elaborate than C++.So the implementation of such array can be like this
import java.util.AbstractList;
import java.util.List;
import java.util.RandomAccess;
public class IntArrayList extends AbstractList<Integer>
implements List<Integer> , RandomAccess /* todo , Cloneable, java.io.Serializable */{
private static final int INT_SIZE_MINUS_ONE = 15;
private static final int RIGHT_SHIFT = 4;
private int size;
private int isNull[];
private int data[];
IntArrayList(int size) {
if (size < 0) {
throw new RuntimeException("invalid size");
}
this.size = size;
isNull = new int[(size + INT_SIZE_MINUS_ONE) >>> RIGHT_SHIFT];
data = new int[size];
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
}
public Integer set(int index, Integer element) {
rangeCheck(index);
Integer oldValue = get(index);
if (element == null) {
isNull[index >>> RIGHT_SHIFT] &= ~(1 << (index & INT_SIZE_MINUS_ONE));
} else {
isNull[index >>> RIGHT_SHIFT] |= (1 << (index & INT_SIZE_MINUS_ONE));
data[index] = element;
}
return oldValue;
}
@Override
public Integer get(int index) {
rangeCheck(index);
if ((isNull[index >>> RIGHT_SHIFT] & (1 << (index & INT_SIZE_MINUS_ONE))) == 0) {
return null;
}
return new Integer(data[index]);
}
@Override
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
It can be used anywhere as List<Integer>
Such kind of object can be useful for long term storage of information that rarely used. It will decrease fragmentation of heap at a cost of increased garbage generation on access to elements.
