Даже в 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 слишком много

P. S. Тикет закрыли, изменения влиты.

FavoriteLoadingДобавить в избранное

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *