Не все патчи одинаково полезны

Эта заметка продолжает разбор улучшений производительности, которые могли бы стать явью, если бы не разные "но". Предыдущая часть о StringBuilder-е находится здесь.

Здесь мы рассмотрим несколько "улучшений", отклонённых из-за непонимания тонкостей спецификации языка, неочевидных угловых случаев и других причин. Поехали!

Когда ничто не предвещает беды

Думаю, каждый из нас работал с методами Collections.emptySet() / Collections.emptyList(). Это очень полезные методы, которые позволяют вернуть пустую неизменяемую коллекцию без создания нового объекта. Посмотрев внутрь класса EmptyList мы увидим там вот это:

private static class EmptyList<E> {

  public Iterator<E> iterator() {
    return emptyIterator();
  }

  public Object[] toArray() {
    return new Object[0];
  }
}

Видите мощный потенциал для улучшения? Метод EmptyList.iterator() возвращает пустой итератор из наличия, почему бы не сделать такой же финт ушами для массива, возвращаемого методом toArray()?

Иными словами, метод должен всегда возвращать новый массив.

Вы скажете: "Он же неизменяемый! Что может пойти не так!?"

Ответить на этот вопрос могут только опытные знатоки:

— Кто отвечает?
— Отвечают знатоки Пол Сандоз и Тагир Валеев

Вот это утверждение наверняка вызовет у вас недоумение:

E. g. somebody might synchronize on the array object returned by toArray call, so this change might cause unwanted lock sharing.

Вы скажете: "Кто в здравом уме будет синхронизироваться на массиве (!) возвращаемом (!!!) из коллекции!?"

Звучит не очень правдоподобно, но такую возможность язык предоставляет, а значит существует вероятность того, что некий пользователь сделает это (а то и уже сделал). Тогда предлагаемое изменение в лучшем случае изменит поведение кода, а в худшем — приведёт к поломке в синхронизации (поди потом, отлови её). Риск настолько неоправдан, а предполагаемый выигрыш столь незначителен, что лучше оставить всё как есть.

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

Мораль сей басни такова: спецификация и обратная совместимость — священные коровы острова Ява. Даже не пытайтесь покушаться на них: стража стреляет без предупреждения.

Стараешься-стараешься...

В JDK существует сразу несколько классов, основанных на массиве, и все они реализуют методы List.indexOf() и List.lastIndexOf():

• java.util.ArrayList
• java.util.Arrays$ArrayList
• java.util.Vector
• java.util.concurrent.CopyOnWriteArrayList

Код указанных методов в этих классах повторяется почти один к одному. Свои решения для этой же задачи предлагают также многие приложения и фреймворки:

• org.hibernate.bytecode.enhance.internal.tracker.SimpleFieldTracker
• com.intellij.util.ArrayUtil
• com.intellij.util.ArrayUtilRt
• org.springframework.oxm.jibx.JibxMarshaller

В итоге имеем бродячий код, который нужно компилировать (при чём иногда по несколько раз), который занимает место в ReserverCodeCache, который нужно тестировать и который просто кочует из класса в класс почти без изменений.

Разработчики, в свою очередь, очень любят писать что-то вроде

int i = Arras.asList(array).indexOf(obj);

// или
boolean contains = Arrays.asList(array).contains(obj);

// при тяжёлом стримозе
boolean contains = Arrays.stream(names).anyMatch(nm -> nm.equals(name));

Хотелось бы ввести в JDK обобщённые утилитный методы, и использовать их повсюду, что и было предложено. Заплатка простая как две копейки:

1) реализации List.indexOf() и List.lastIndexOf() переезжают в java.util.Arrays
2) вместо них вызываются, соответственно, Arrays.indexOf() и Arrays.lastIndexOf()

Казалось бы, что может пойти не так? Выигрыш от этого подхода [вроде бы] очевиден. Но статья о провалах, поэтому подумайте, что может пойти нет так.

— Кто отвечает?
— Отвечают знатоки Мартин Бухгольц и Пол Сандоз

Переписка: http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-March/051968.html

Мораль сей басни такова: ваш гениальный патч могут зарезать на ревью просто потому, что не увидят в нём особой ценности. Ну да, есть повторяющийся код, но он никому особо не мешает, так что пусть живёт.

Улучшения для ArrayList-a? Их есть у меня

Мопед патч не мой, я просто размещу для подумать. Само предложение было озвучено здесь, и выглядит оно очень даже привлекательно. Смотрите сами:

Невооруженным глазом видно, что предложение очень и очень логично. Измерить производительность можно с помощью простого бенчмарка:

@State(Scope.Benchmark)
public class ArrayListBenchmark {

  @State(Scope.Benchmark)
  public static class Data {

    @Param({"10", "100", "1000", "10000"})
    public int size;

    ArrayList<Integer> arrayRandom = new ArrayList<Integer>(size);

    @Setup(Level.Invocation)
    public void initArrayList() {
      Random rand = new Random();
      rand.setSeed(System.currentTimeMillis());
      // Populate the ArrayList with size-5 elements 
      for (int i = 0; i < size - 5; i++) {
        Integer r = rand.nextInt() % 256;
        arrayRandom.add(r);
      }
    }
  }

  @Benchmark
  public ArrayList construct_new_array_list(Data d) {
    ArrayList al = new ArrayList(d.arrayRandom);
    // once a new ArrayList is created add a new element
    al.add(new Integer(900));
    return al;
  }
}

Итоги:

Benchmark                 (size)   Mode  Cnt    Score    Error  Units

До

construct_new_array_list      10  thrpt   25  388.212 ± 23.110  ops/s
construct_new_array_list     100  thrpt   25   90.208 ±  7.995  ops/s
construct_new_array_list    1000  thrpt   25   23.289 ±  1.687  ops/s
construct_new_array_list   10000  thrpt   25    7.659 ±  0.560  ops/s

После

construct_new_array_list      10  thrpt   25  562.678 ± 37.370  ops/s
construct_new_array_list     100  thrpt   25  119.791 ± 13.232  ops/s
construct_new_array_list    1000  thrpt   25   33.811 ±  3.812  ops/s
construct_new_array_list   10000  thrpt   25   10.889 ±  0.564  ops/s

Совсем неплохо как для такого простого изменения. Главное, что подвохов-то вроде бы нет. Честно создаём массив, честно копируем данные и про размер не забываем. Вот сейчас патч точно должны принять!

Ничто не запрещает мне отпочковаться от ArrayList-а, а данные хранить в связанном списке. Тогда c instanceof ArrayList вернёт истину, мы попадём на участок копирования и благополучно свалимся.

Мораль сей басни такова: причиной отказа может стать возможное изменение поведения. Иными словами нужно держать в уме вероятность даже самого абсурдного изменения, если оно допускается средствами языка. И да, всё могло бы получиться, если бы ArrayList с самого начала объявили final.

Снова спецификация

Отлаживая своё приложение я случайно провалился в кишки Спринга и нашел там вот такой код:

// обратите внимание на использование переменной paramTypes

for (Constructor<?> candidate : candidates) {
  Class<?>[] paramTypes = candidate.getParameterTypes();

  if (constructorToUse != null && argsToUse != null && argsToUse.length > paramTypes.length) {
    // Already found greedy constructor that can be satisfied ->
    // do not look any further, there are only less greedy constructors left.
    break;
  }
  if (paramTypes.length < minNrOfArgs) {
    continue;
  }

По счастливому стечению обстоятельств, зайдя внутрь java.lang.reflect.Constructor.getParameterTypes() я прокрутил код чуть ниже и нашел прекрасное:

@Override
public Class<?>[] getParameterTypes() {
  return parameterTypes.clone();
}

/**
 * {@inheritDoc}
 * @since 1.8
 */
public int getParameterCount() { return parameterTypes.length; }

Понимаете, да? Если нам нужно узнать количество аргументов конструктора/метода, то достаточно вызвать java.lang.reflect.Method.getParameterCount() и обойтись без копирования массива. Проверим, стоит ли игра свеч на простейшем случае, в котором у метода нет параметров:

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class MethodToStringBenchmark {
  private Method method;

  @Setup
  public void setup() throws Exception { method = getClass().getMethod("toString"); }

  @Benchmark
  public int getParameterCount() { return method.getParameterCount(); }

  @Benchmark
  public int getParameterTypes() { return method.getParameterTypes().length; }
}

На моей машине и с JDK 11 получается так:

Benchmark                                       Mode  Cnt     Score    Error   Units

getParameterCount                               avgt   25     2,528 ±  0,085   ns/op
getParameterCount:·gc.alloc.rate                avgt   25    ≈ 10⁻⁴           MB/sec
getParameterCount:·gc.alloc.rate.norm           avgt   25    ≈ 10⁻⁷             B/op
getParameterCount:·gc.count                     avgt   25       ≈ 0           counts

getParameterTypes                               avgt   25     7,299 ±  0,410   ns/op
getParameterTypes:·gc.alloc.rate                avgt   25  1999,454 ± 89,929  MB/sec
getParameterTypes:·gc.alloc.rate.norm           avgt   25    16,000 ±  0,001    B/op
getParameterTypes:·gc.churn.G1_Eden_Space       avgt   25  2003,360 ± 91,537  MB/sec
getParameterTypes:·gc.churn.G1_Eden_Space.norm  avgt   25    16,030 ±  0,045    B/op
getParameterTypes:·gc.churn.G1_Old_Gen          avgt   25     0,004 ±  0,001  MB/sec
getParameterTypes:·gc.churn.G1_Old_Gen.norm     avgt   25    ≈ 10⁻⁵             B/op
getParameterTypes:·gc.count                     avgt   25  2380,000           counts
getParameterTypes:·gc.time                      avgt   25  1325,000               ms

Что мы можем с этим сделать? Можем поискать использование антипаттерна Method.getParameterTypes().length в JDK (по меньшей мере в java.base) и заменить его там, где это имеет смысл:

java.lang.invoke.MethodHandleProxies

java.util.concurrent.ForkJoinTask

java.lang.reflect.Executable

sun.reflect.annotation.AnnotationType

Патч был отправлен вместе с сопроводительным письмом.

Внезапно оказалось, что уже несколько лет как существует похожая задача и по ней даже подготовлены изменения. В комментариях отмечен довольно приличный, как для таких простых изменений, прирост производительности. Однако, и они, и мой патч пока убраны под сукно и лежат без движения. Почему? Вероятно потому, что разработчики слишком заняты более нужными вещами и у них тупо не доходят руки.

Мораль сей басни такова: ваши гениальные изменения могут зависнуть просто из-за нехватки рабочих рук.

Но это ещё не конец! В ходе обсуждения рациональности описанной замены в других проектах более опытные товарищи выдвинули встречное предложение: может не стоит делать замену Method.getParameterTypes().length -> Method.getParameterCount() руками, а поручить это компилятору? Возможно ли это и будет ли это "законным"?

Попробуем проверить с помощью теста:

@Test
void arrayClone() {
  final Object[] objects = new Object[3];
  objects[0] = "azaza";
  objects[1] = 365;
  objects[2] = 9876L;

  final Object[] clone = objects.clone();

  assertEquals(objects.length, clone.length);
  assertSame(objects[0], clone[0]);
  assertSame(objects[1], clone[1]);
  assertSame(objects[2], clone[2]);
}

который проходит, и который показывает, что если клонированный массив не покидает область видимости, то его можно удалить, т. к. доступ к любому элементу из его ячеек или полю length можно получить из оригинала.

Умеет ли делать это JDK? Проверяем:

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ArrayAllocationEliminationBenchmark {

    private int length = 10;

    @Benchmark
    public int baseline() {
        return new int[length].length;
    }

    @Benchmark
    public int baselineClone() {
        return new int[length].clone().length;
    }
}

Вывод для JDK 13:

Benchmark                                Mode  Cnt     Score     Error   Units

baseline                                 avgt   50     6,135 ±   0,140   ns/op
baseline:·gc.alloc.rate.norm             avgt   50    56,000 ±   0,001    B/op

clone                                    avgt   50    18,359 ±   0,619   ns/op
clone:·gc.alloc.rate.norm                avgt   50   112,000 ±   0,001    B/op

Выходит, что openjdk не умеет выбрасывать new int[length], в отличие от Грааля, хе-хе:

Benchmark                                Mode  Cnt     Score     Error   Units

baseline                                 avgt   25     2,470 ±   0,156   ns/op
baseline:·gc.alloc.rate.norm             avgt   25     0,005 ±   0,008    B/op

сlone                                    avgt   25    13,086 ±   1,059   ns/op
сlone:·gc.alloc.rate.norm                avgt   25   112,113 ±   0,115    B/op

Получается, что можно немного подкрутить оптимизирующий компилятор openjdk, чтобы он мог делать то же, что умеет Грааль. Т. к. влезть в плюсовый адЪ в коде ВМ и напилить что-то осмысленное могут не только лишь все, то я ограничился письмом, в котором изложил свои наблюдения.

Оказалось, и здесь есть несколько тонкостей. Владимир Иванов указывает, что:

Considering there's no way to grow/shrink Java arrays,
"cloned_array.length => original_array.length" transformation is correct
irrespective of whether cloned variant escapes or not.

Moreover, the transformation is already there:

http://hg.openjdk.java.net/jdk/jdk/file/tip/src/hotspot/share/opto/memnode.cpp#l2388

I haven't looked into the benchmarks you mentioned, but it looks like
cloned_array.length access is not the reason why cloned array is still
there.

Regarding your other ideas, redirecting accesses from cloned instance to
original is problematic (in general case) since compiler has to prove
there were no changes in both versions and indexed accesses make it even
harder. And safepoints cause problems as well (for rematerialization).

But I agree that it would be nice to cover (at least) simple cases of
defensive copying.

Т. е. грохнуть клон вроде бы и можно, и не особо сложно. А вот с преобразованием

int len = new int[arrayLength].length;

-->

int len = arrayLength;

возникают сложности:

We don't eliminate array allocations that doesn't have a known length
because they might cause a NegativeArraySize Exception. In this case we
should be able to prove that the length is positive though.

Anyway — I have an almost finished patch that replace unused array
allocations with a proper guard.

Иными словами нельзя просто так взять и выбросить создание массива, т. к согласно спецификации исполнение обязано бросить NegativeArraySizeException и ничего мы с этим поделать не можем:

@Test
void arrayWithNwgativeSize() {
  int length = 0;
  try {
    int newLen = -3;
    length = new Object[newLen].length; // выбросить new Object[newLen] нельзя
    fail();
  } catch (NegativeArraySizeException e) {
    assert length == 0;
  }
}

Почему же Грааль смог? Думаю, причина в том, что значение поля length в бенчмарке выше было постоянным и всегда равнялось 10, что позволило профилировщику сделать вывод о том, что проверка отрицательного значения не нужна, а значит её можно убрать вместе с созданием самого массива. Поправьте в комментариях, если я ошибся.

На сегодня всё :) Добавляйте свои примеры в комментариях, будем разбираться.