[Из песочницы] Даже в Java 9 ArrayList всё ещё можно (и нужно) улучшать
Думаю, большинство джавистов согласится, что java.util.ArrayList
— наиболее используемая коллекция в мире Java. Она появилась в версии 1.2 и быстро стала "коллекцией по умолчанию", ведь в большинстве случаев её возможностей вполне достаточно для повседневной работы. В этот класс вносилось множество изменений (см., например, историю изменений в репозитории JDK 8), чтобы сделать его как можно более производительным. В этой заметке я покажу, что даже такой прокачанный компонент, как ArrayList
всё ещё хранит в себе возможности для улучшения.
Положим, нам необходимо преобразовать в массив часть списка. Для этого опишем метод:
public T[] toSubArray(ArrayList<T> list, int from, int to) { return list .subList(from, to) .toArray(new T[0]);
}
Оценим его производительность в сравнении с преобразованием в массив исходного списка:
@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)); } }
}
Выполнив замеры обнаружим, что производительность метода subList()
значительно уступает производительности baseline-а:
Benchmark | size | Score | Error | Unit |
---|---|---|---|---|
list | 0 | 7,2 | 0,1 | ns/op |
subList | 0 | 12,8 | 0,2 | ns/op |
list | 10 | 34,6 | 3,9 | ns/op |
subList | 10 | 44,7 | 1,0 | ns/op |
list | 100 | 141,9 | 2,2 | ns/op |
subList | 100 | 252,1 | 4,9 | ns/op |
list | 1000 | 1201,6 | 21,0 | ns/op |
subList | 1000 | 2310,4 | 53,0 | ns/op |
Учитывая то обстоятельство, что в обоих случаях перемещается равный объём данных, значительная разница выглядит удивительной.
Разгадка лежит врутри класса 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; } //... }
Оба метода напрямую обращаются к массиву, используя Arrays.copyOf()
и System.arraycopy()
для перемещения данных. Заглянем внутрь:
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); //... }
Указанные методы помечены как @HotSpotIntrinsicCandidate
, что позволяет ВМ создавать для них высокопроизводительный машинный код для достижения наилучшего быстродействия.
Теперь обратимся к методу subList()
:
public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList<>(this, fromIndex, toIndex);
}
Как видим, ArrayList
располагает собственной реализацией данного метода, и (что гораздо важнее) собственной реализацией представления части списка:
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; //...
}
Теперь главное: хотя SubList
и помечен как RandomAccess
и через поле root
имеет прямой доступ к массиву, он не располагает собственной реализацией методов toArray()
и toArray(T[])
. А раз так, то используются унаследованные методы класса AbstractCollection
:
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;
}
Здесь массив заполняется в цикле с помощью итератора, а это работает медленнее, чем перенос данных с помощью Arrays.copyOf()
и System.arraycopy()
. Отсюда следует, что для улучшения производительности нам нужно переопределить toArray()
и toArray(T[])
и использовать тот же подход, что и ArrayList
. Дополним:
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; } //... }
Всё ли мы сделали правильно? Нет! Переопределённые нами методы не учитывают вероятность того, что исходный список может быть изменён уже после вызова метода subList()
. Мы обязаны учесть такую возможность. Поэтому добавим проверку в начало каждого из переопределённых методов:
@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;
}
Прогнав бенчмарк с изменённым ArrayList
-ом обнаруживаем, что теперь производительность метода subList()
лишь незначительно уступает производительности baseline-а. Небольшое отставание обусловлено созданием подсписка и вызовом checkForComodification()
в начале метода toArray(T[])
.
Benchmark | size | Score | Error | Unit |
---|---|---|---|---|
list | 0 | 7,2 | 0,1 | ns/op |
subList | 0 | 7,5 | 0,2 | ns/op |
list | 10 | 24,5 | 0,5 | ns/op |
subList | 10 | 25,4 | 0,6 | ns/op |
list | 100 | 142,8 | 4,5 | ns/op |
subList | 100 | 141,6 | 2,5 | ns/op |
list | 1000 | 1243,6 | 28,5 | ns/op |
subList | 1000 | 1247,8 | 23,7 | ns/op |
В сухом остатке:
Тикет и ссылка на патч (закроют, скорее всего, в Java 11)
Что почитать:
Длинная, сложная и чрезвычайно полезная статья о чёрном колдовстве в омуте ВМ
Исходная переписка по теме заметки: находится тут
Выводы
- даже до боли знакомые классы могут скрывать недоработки
- абстрактные коллекции написаны для покрытия как можно большего числа случаев и предлагают обобщённые алгоритмы, поэтому при создании конкретной реализации нередко есть возможность написать более производительный код, заточенный под особенности вашей структуры данных
- для внесения изменений необязательно быть сотрудником "Оракла"; если у вас есть патч, устраняющий доказанную ошибку или привносящий ощутимое улучшение, — он будет принят к рассмотрению
- чаще заглядывайте в исходный код платформы: джавист никогда не может знать о JDK слишком много