Думаю, большинство джавистов согласится, что 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-а:

Учитывая то обстоятельство, что в обоих случаях перемещается равный объём данных, значительная разница выглядит удивительной.

Разгадка лежит врутри класса 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[]).

В сухом остатке:
Тикет и ссылка на патч (закроют, скорее всего, в Java 11)

Что почитать:
Длинная, сложная и чрезвычайно полезная статья о чёрном колдовстве в омуте ВМ

Исходная переписка по теме заметки: находится тут

Выводы

• даже до боли знакомые классы могут скрывать недоработки
• абстрактные коллекции написаны для покрытия как можно большего числа случаев и предлагают обобщённые алгоритмы, поэтому при создании конкретной реализации нередко есть возможность написать более производительный код, заточенный под особенности вашей структуры данных
• для внесения изменений необязательно быть сотрудником "Оракла"; если у вас есть патч, устраняющий доказанную ошибку или привносящий ощутимое улучшение, — он будет принят к рассмотрению
• чаще заглядывайте в код платформы: джавист никогда не может знать о JDK слишком много

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