Even in Java 9, ArrayList can still (and should) be improved.

I think most javistes would agree that java.util.ArrayList is the most used collection in the Java world. It appeared in version 1.2 and quickly became the “default collection”, because in most cases its capabilities are enough for everyday work. Many changes have been made to this class (see, for example, the change history in the JDK 8 repository ) to make it as productive as possible. In this note, I will show that even such a pumped-up component as ArrayList still holds room for improvement.

Suppose we need to convert part of a list into an array. To do this, we describe the method:

 public T[] toSubArray(ArrayList<T> list, int from, int to) { return list .subList(from, to) .toArray(new T[0]); } 

Let's estimate its performance in comparison with conversion to an array of the source list:

 @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"}) public class SubListToArrayBenchmark { /** * baseline */ @Benchmark public Integer[] list(Data data) { return data.list.toArray(new Integer[0]); } @Benchmark public Integer[] subList(Data data) { return data.list.subList(0, data.size).toArray(new Integer[0]); } @State(Scope.Thread) public static class Data { ArrayList<Integer> list; @Param({"0", "10", "100", "1000"}) int size; @Setup public void setup() { list = IntStream .range(0, size) .boxed() .collect(toCollection(ArrayList::new)); } } } 

After completing the measurements, we find that the performance of the subList() method is significantly inferior to that of the baseline:

Given the fact that in both cases an equal amount of data moves, the significant difference looks surprising.

The answer lies in the class of ArrayList :

 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //... public Object[] toArray() { return Arrays.copyOf(elementData, size); } public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } //... } 

Both methods directly access the array using Arrays.copyOf() and System.arraycopy() to move the data. Let's look inside:

 public class Arrays { //... @HotSpotIntrinsicCandidate // since Java 9 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } //... } 

 public final class System { //... @HotSpotIntrinsicCandidate // since Java 9 public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); //... } 

These methods are marked as @HotSpotIntrinsicCandidate , which allows @HotSpotIntrinsicCandidate create high-performance machine code for them to substitute their implementation with high-performance machine code to achieve the best performance.

Now let's turn to the subList() method:

 public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList<>(this, fromIndex, toIndex); } 

As you can see, ArrayList has its own implementation of this method, and (more importantly) its own implementation of the list part view:

 private static class SubList<E> extends AbstractList<E> implements RandomAccess { private final ArrayList<E> root; private final SubList<E> parent; private final int offset; private int size; //... } 

Now the main thing: although SubList marked as RandomAccess and has a direct access to the array through the root field, it does not have its own implementation of the toArray() and toArray(T[]) methods. And if so, then the inherited methods of the AbstractCollection class are used :

 public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()]; Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; } public <T> T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) { // fewer elements than expected if (a == r) { r[i] = null; // null-terminate } else if (a.length < i) { return Arrays.copyOf(r, i); } else { System.arraycopy(r, 0, a, 0, i); if (a.length > i) { a[i] = null; } } return a; } r[i] = (T)it.next(); } // more elements than expected return it.hasNext() ? finishToArray(r, it) : r; } 

Here, the array is filled in a loop using an iterator, and this works slower than transferring data with Arrays.copyOf() and System.arraycopy() . It follows that to improve performance, we need to override toArray() and toArray(T[]) and use the same approach as ArrayList . Let's add:

 private static class SubList<E> extends AbstractList<E> implements RandomAccess { private final ArrayList<E> root; private final SubList<E> parent; private final int offset; private int size; //... @Override public Object[] toArray() { return Arrays.copyOfRange(root.elementData, offset, offset + size); } @Override public <T> T[] toArray(T[] a) { if (a.length < size) return (T[]) Arrays.copyOfRange(root.elementData, offset, offset + size, a.getClass()); System.arraycopy(root.elementData, offset, a, 0, size); if (a.length > size) a[size] = null; return a; } //... } 

Have we done everything right? Not! The methods we override do not take into account the likelihood that the source list can be changed after the call to the subList() method. We must take this opportunity into account. Therefore, we add a check to the beginning of each of the overridden methods:

 @Override public Object[] toArray() { checkForComodification(); // <-- return Arrays.copyOfRange(root.elementData, offset, offset + size); } @Override public <T> T[] toArray(T[] a) { checkForComodification(); // <-- if (a.length < size) return (T[]) Arrays.copyOfRange(root.elementData, offset, offset + size, a.getClass()); System.arraycopy(root.elementData, offset, a, 0, size); if (a.length > size) a[size] = null; return a; } 

subList() benchmark with a modified ArrayList , we find out that now the performance of the subList() method is only slightly lower than that of the baseline. A slight lag is due to the creation of a sublist and calling checkForComodification() at the beginning of the toArray(T[]) method.

The bottom line:
Ticket and link to patch (most likely to close in Java 11)

What to read:
A long, complex and extremely useful article about black witchcraft in the pool of VM

The original correspondence on the topic notes: is here

findings

• even painfully familiar classes can hide flaws
• abstract collections are written to cover as many cases as possible and offer generalized algorithms, therefore, when creating a specific implementation, it is often possible to write more efficient code, tailored to the peculiarities of your data structure
• to make changes it is not necessary to be an employee of Orakla; if you have a patch that fixes a proven mistake or introduces a tangible improvement, it will be accepted for consideration
• look more often at the platform code: javist can never know too much about the JDK

PS Ticket closed, changes poured.