Думаю, большинство джавистов согласится, что 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 слишком много
P. S. Тикет закрыли, изменения влиты.