Why does Java ArrayList use per-element casting instead of per-array casting?

Question

What happens inside Java's ArrayList<T> (and probably many other classes) is that there is an internal Object[] array = new Object[n];, to which T Objects are written. Whenever an element is read from it, a cast return (T) array[i]; is done. So, a cast on every single read.

I wonder why this is done. To me, it seems like they're just doing unnecessary casts. Wouldn't it be more logical and also slightly faster to just create a T[] array = (T[]) new Object[n]; and then just return array[i]; without cast? This is only one cast per array creation, which is usually far less than the number of reads.

Why is their method to be preferred? I fail to see why my idea isn't strictly better?

Answer 1

It's more complicated than that: generics are erased in byte code, and the erasure of T[] is Object[]. Likewise, the return value of get() becomes Object. To retain integrity of the type system, a checked cast is inserted when the class is actually used, i.e.

Integer i = list.get(0);

will be erased to

Integer i = (Integer) list.get(0);

That being the case, any type check within ArrayList is redundant. But it's really beside the point, because both (T) and (T[]) are unchecked casts, and incur no runtime overhead.

One could write a checked ArrayList that does:

T[] array = Array.newInstance(tClass, n);

This would prevent heap pollution, but at the price of a redundant type check (you can not suppress the synthentic cast in calling code). It would also require the caller to provide the ArrayList with the class object of the element type, which clutters its api and makes it harder to use in generic code.

Edit: Why is generic array creation forbidden?

One problem is that arrays are checked, while generics are unchecked. That is:

Object[] array = new String[1];
array[0] = 1; // throws ArrayStoreException

ArrayList list = new ArrayList<String>();
list.add(1); // causes heap pollution

Therefore, the component type of an array matters. I assume this is why the designers of the Java language require us to be explicit about which component type to use.

Answer 2

Whenever an element is read from it, a cast return (T) array[i]; is done. So, a cast on every single read.

Generic is a compile time check. At runtime the type T extends is used instead. In this case T implicitly extends Object so what you have at runtime is effectively.

return (Object) array[i];

or

return array[i];

Wouldn't it be more logical and also slightly faster to just create a

T[] array = (T[]) new Object[n]

Not really. Again at runtime this becomes

Object[] array = (Object[]) new Object[n];

or

Object[] array = new Object[n];

What you are really fishing for is

T[] array = new T[n];

except this doesn't compile, mostly because T isn't known at runtime.

What you can do is

private final Class<T> tClass; // must be passed in the constructor

T[] array = (T[]) Array.newInstance(tClass, n);

only then will the array actually be the type expected. This could make reads faster, but at the cost of writes. The main benefit would be a fail fast check, i.e. you would stop a collection being corrupted rather than wait until you detect it was corrupted to throw an Exception.