Когда выходит новая версия Java, главные фичи всегда активно обсуждают. Но есть и работа, которая обычно остается «невидимой»: небольшие оптимизации в стандартной библиотеке. Они помогают нам, незаметно ускоряя наш код и ничего не требуя взамен, а мы даже ничего о них не знаем!
Эту ситуацию исправляет Тагир Валеев (lany), рассказывая о таких оптимизациях. Сначала он выступил на Joker 2019 с докладом «Java 9-14: маленькие оптимизации», можете посмотреть его видеозапись. Затем, поскольку зрителям очень понравилось, на JPoint 2020 он развил тему. А теперь мы решили сделать из второго доклада пост для Хабра, чтобы его можно было не только увидеть, но и прочитать.
Далее под катом текст пойдет от лица спикера.
Вступление
Мы посмотрим только на самые базовые вещи, которыми прямо или косвенно пользуются все: строки, коллекции и рефлексию. Мы не рассматриваем API, появившиеся после Java 8. Все улучшения производительности вы получите бесплатно, если будете запускать ваш Java 8-код на более новой JVM.
Проведем замеры производительности кода. Я не буду делать вид, что они очень научные, но надеюсь, что показательные и выводы из них правильные. Тесты проводились на Intel Core i7-6820HQ под Windows 10. Все они однопоточные, поэтому количество ядер процессора не принципиально. Чтобы нивелировать эффект от смены сборщика мусора по умолчанию, всегда использовалась опция +UseParallelGC. На всех иллюстрациях производительность измеряется по среднему времени выполнения, то есть «чем меньше, тем лучше».
Если вы знаете доклад Алексея Шипилёва о производительности, то должны помнить «Кривую имени Ш.» В качестве упражнения можете про каждую оптимизацию в этом докладе прикинуть, где она на этой кривой.
String.hashCode
Начнем с замера производительности String.hashCode. Напишем бенчмарк, в котором будем вычислять хеш-код строки «Бегавшая через бары»:
@Benchmark
public int calcHashCode() {
return "Бегавшая через бары".hashCode();
}При сравнении Java 12 и Java 13 получаем следующее:
Как же удалось ускорить вычисление хеш-кода более чем в 4 раза? Все дело в самой строке, она не случайная. Вы скорее выиграете в лотерею, чем наткнётесь на такую. Сравним производительность вычислений двух строк: «Бегавшая через бары» и «Бегавший через бары»:
@Benchmark
public int calcHashCode() {
return "Бегавшая через бары".hashCode();
}
@Benchmark
public int calcHashCode2() {
return "Бегавший через бары".hashCode();
}
Оказывается, в Java 12, когда «он» уже бегал через бары быстро, «она» ещё бегала медленно. Но в Java 13 наконец наступило равенство полов. В чём дело?
В значении хеш-кода. С Java 9 по Java 12 метод hashCode() выглядел так (до этого чуть по-другому, потому что не было Compact Strings):
/** Cache the hash code for the string */
private int hash; // Default to 0
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
hash = h = isLatin1() ? StringLatin1.hashCode(value)
: StringUTF16.hashCode(value);
}
return h;
}Формула хеш-кода давно специфицирована, и ее нельзя менять. В одном случае из 4 миллиардов значением хеш-кода получается 0. И в этом случае полученный хеш-код нельзя закешировать. Чтобы различать ситуации, когда хеш-код подсчитан и еще нет, во втором случае как раз используют 0 как его значение. А если у вашей строки он такой и оказался — ну что ж, вы неудачник, будете пересчитывать его всегда.
Об этом на JPoint 2015 рассказывал Алексей Шипилёв в докладе «Катехизис java.lang.String». На Java 8 его пример «сверхинструментом пренебрегшая» также давал хеш-код 0, а строка «пренебрегшая сверхинструментом» давала уже другое значение. Он также раскритиковал мнение перфекционистов, что необходимо добавить специальный флаг для таких случаев, потому что размер объекта String вырос бы для всех.
Но теперь некоторые перфекционисты победили, причем Алексей им помог.
Посмотрим на layout объекта String в Java 8. Оказывается, на 64-битной JVM в String и так терялось 4 байта, причем хоть со сжатыми ссылками, хоть без. То есть можно занять 1 байт.
С другой стороны, в 32-битной JVM потерь не было. Может быть, еще в каких-то экзотических конфигурациях с другим выравниванием в строках тоже не пропадало место, поэтому добавление флага заняло бы дополнительную память.
Однако в Java 9 появились компактные строки, большую часть которых делал сам Алексей Шипилёв, и все это стало неважно. Для их обозначения уже требуется дополнительный байт, который показывает, влезает ли строка в кодировку Latin-1, или же в ней есть UTF-16 символы. Теперь полезная нагрузка строки теряет 3 байта, и вряд ли можно представить такую конфигурацию VM, в которой 3 лишних байта превратятся в 0. А раз они свободны, почему же тогда не занять еще один из них?
Это и сделали в Java 13, добавив булево поле String.hashIsZero:
И еще два байта осталось для потомков. Теперь вычисление хеш-кода выглядит так:
private int hash; // Default to 0
private boolean hashIsZero; // Default to false;
public int hashCode() {
int h = hash;
if (h == 0 && !hashIsZero) {
h = isLatin1() ? StringLatin1.hashCode(value)
: StringUTF16.hashCode(value);
if (h == 0) {
hashIsZero = true;
} else {
hash = h;
}
}
return h;
}Но почему добавили именно поле hashIsZero? Кажется, логичнее было бы завести поле hashIsCalculated и устанавливать его в true, когда хеш вычислен.
Оказывается, метод hashCode() никак не синхронизирован, поэтому в нем возможна гонка по данным. Когда поле одно, подобное можно делать аккуратно, так как благодаря гарантии атомарности каждый из потоков увидит либо вычисленный хеш-код, либо 0 (тогда он вычислит вручную). Но запись двух полей неатомарна, и другие потоки могут увидеть одну из этих записей. И если сделать поле hashIsCalculated и не добавить синхронизации, то другой поток может увидеть в hashIsCalculated значение true и хеш, равный 0, и вернет неправильный хеш.
Поэтому придумали такое изящное решение, при котором никогда не пишут более одного поля в объект String: когда одно поле меняется, другое всегда имеет значение по умолчанию, поэтому атомарность сохраняется.
Когда это отправили на ревью, Алексей Шипилёв долго всех убеждал, что так делать не надо, потому что это неоправданная сложность. Но перфекционизм победил.
String.concat
Конкатенацию строк можно провести не только через +, но и через метод String.concat(). Выясним, какой из этих способов быстрее. Напишем бенчмарк:
@Param({"", "is a very very very very very very very very cool conference!"})
String data;
@Benchmark
public String concat() {
return "JPoint ".concat(data);
}
@Benchmark
public String plus() {
return "JPoint " + data;
}Сначала проверим на конкатенацию пустой строки с непустой:
Оказывается, метод String.concat() работает в Java 8-14 за ~3 нс, а конкатенация через + занимает больше 15 нс, причем замедляется в новых версиях до ~19 нс. Почему?
Проблема кроется в спецификации Java. Результатом конкатенации строк всегда должна быть новая строка. Это требование идет с ранних версий спецификации, и убрать его было бы breaking change. А String.concat() не скован этим ограничением, даже наоборот: в его спецификации четко прописано, что если длина строки-аргумента равна 0, то возвращается исходная строка. Это тоже странно, поскольку это правило в обратную сторону не работает: если строка слева пустая, тогда аргумент копируется в новую строку.
Пустые строки мы не так часто конкатенируем, давайте посмотрим на непустые.
С бенчмарком маленьких оптимизаций в непустых строках есть трудности, потому что были и большие оптимизации. В Java 8 String.concat() отработал вдвое медленнее, чем конкатенация через +, а в Java 9 он заметно ускорился благодаря внедрению компактных строк. До Java 12 картина была примерно одинаковой, но в Java 13 и Java 14 String.concat() работает быстрее конкатенации через + примерно на 10%.
Но не спешите переходить на String.concat(). В Java 9 был реализован JEP 280 — конкатенация строк через invokedynamic-вызовы. Однако для конкатенации через + необходимо перекомпилировать ваше приложение, а метод String.concat() будет использовать код из JEP 280 даже без перекомпиляции.
Перекомпилируем бенчмарк с таргетом Java 9 и запустим заново:
Если конкатенация была с пустой строкой, то она стала заметно быстрее и деградация в свежих версиях Java перестала наблюдаться. Конкатенация с непустой строкой также всегда быстрее, чем до перекомпиляции, и сравнялась по производительности со String.concat(). Что же стало решающим фактором в таком скачке производительности?
Посмотрим на код метода String.concat() в Java 12:
public String concat(String str) {
if (str.isEmpty()) {
return this;
}
if (coder() == str.coder()) {
byte[] val = this.value;
byte[] oval = str.value;
int len = val.length + oval.length;
byte[] buf = Arrays.copyOf(val, len);
System.arraycopy(oval, 0, buf, val.length, oval.length);
return new String(buf, coder);
}
int len = length();
int olen = str.length();
byte[] buf = StringUTF16.newBytesFor(len + olen);
getBytes(buf, 0, UTF16);
str.getBytes(buf, len, UTF16);
return new String(buf, UTF16);
}Метод проверяет компактность обеих строк, соединяет их в байтовый массив, а затем приватный конструктор из байтового массива создает новую строку. Все выглядит довольно оптимально, и неясно, как все улучшить.
public String concat(String str) {
if (str.isEmpty()) {
return this;
}
return StringConcatHelper.simpleConcat(this, str);
}
static String simpleConcat(Object first, Object second) {
String s1 = stringOf(first);
String s2 = stringOf(second);
// start "mixing" in length and coder or arguments, order is not
// important
long indexCoder = mix(initialCoder(), s2);
indexCoder = mix(indexCoder, s1);
byte[] buf =(indexCoder);
// prepend each argument in reverse order, since we prepending
// from the end of the byte array
indexCoder = prepend(indexCoder, buf, s2);
indexCoder = prepend(indexCoder, buf, s1);
return newString(buf, indexCoder);
}В Java 13 метод стал делегировать вспомогательному методу simpleConcat(), который теперь используется в обоих способах конкатенации строк. Кажется, что веток теперь меньше, однако они спрятаны в методы mix() и prepend(). Улучшение производительности кроется в реализации внутреннего метода newArray():
static byte[] newArray(long indexCoder) {
byte coder = (byte)(indexCoder >> 32);
int index = (int)indexCoder;
return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, index << coder);
}Метод выделяет неинициализированный массив, то есть еще не забитый нулями. На этом и экономим. А в Java 12 вместо внутреннего метода newArray() использовался публичный метод copyOf(), который должен занулить массив.
Конкатенация пустых строк
График конкатенации пустой строки мне долго не давал покоя.
Да, нужно создать новый объект, но 11 нс — это много. Я подумал над этим, и это вылилось в новый патч JDK-8247605, причем он попадет в Java 16.
Посмотрим снова на код метода simpleConcat():
static String simpleConcat(Object first, Object second) {
String s1 = stringOf(first);
String s2 = stringOf(second);
// start "mixing" in length and coder or arguments, order is not
// important
long indexCoder = mix(initialCoder(), s2);
indexCoder = mix(indexCoder, s1);
byte[] buf =(indexCoder);
// prepend each argument in reverse order, since we prepending
// from the end of the byte array
indexCoder = prepend(indexCoder, buf, s2);
indexCoder = prepend(indexCoder, buf, s1);
return newString(buf, indexCoder);
}Предположим, что строка s1 или s2 — пустая. Мы не можем просто вернуть другую строку, потому что нас ограничивает спецификация. Но спецификация не обязывает выделять под нее новый массив. Ведь массив с байтами внутри строки не меняется и спрятан, а значит, его можно переиспользовать и больше ничего не делать. Сделать это весьма просто — можно делегировать к конструктору строки от строки:
...
String s1 = stringOf(first);
String s2 = stringOf(second);
if (s1.isEmpty()) {
// newly created string required, see JLS 15.18.1
return new String(s2);
}
if (s2.isEmpty()) {
// newly created string required, see JLS 15.18.1
return new String(s1);
}
...Это публичный конструктор, он существует с давних пор и, как правило, не нужен, потому что строки неизменяемые. Но он как раз переиспользует внутренний массив, поэтому хорошо подходит под наши цели.
Патч добрался до ранних сборок Java 16, и их уже можно скачать и протестировать:
Теперь конкатенация любой строки (причем неважно, справа или слева находится пустая строка) уже не требует копирования массива, а значит, занимает гораздо меньше времени — ~6 нс.
Вдобавок мы экономим память: если и исходная строка, и результат конкатенации оказались долгоживущими, то они будут сидеть на одном массиве навсегда. Но это работает, если включена target-версия Java 9 и выше.
В этом и прелесть конкатенации через invokedynamic — мы можем улучшать существующую фичу, вообще не меняя байткода.
TreeMap.computeIfAbsent и другие методы коллекций
Речь пойдет о пяти методах, которые появились в Java 8 в интерфейсе map:
- putIfAbsent()
- computeIfAbsent()
- computeIfPresent()
- compute()
- merge()
Все они модифицируют не больше одной записи в map, и все, кроме putIfAbsent(), принимают лямбду, которая тем или иным образом говорит, как мы будем модифицировать значение. Так как эти методы были добавлены в интерфейс, они имеют реализацию по умолчанию, чтобы не сломать уже существующий код. Посмотрим, как выглядит реализация по умолчанию метода computeIfAbsent():
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}Метод computeIfAbsent() позволяет вычислить значение и поместить в map, если там ничего не было. Если же значение было, и не было равно null, то метод возвращает старое значение.
В реализации по умолчанию есть очевидный недостаток. Если записи не было, то придется ее искать дважды: сперва при вызове get() ищем запись в хеш-таблице или дереве, не находим, а затем при вызове put() нужно найти, куда положить запись. То есть мы 2 раза делаем одно и то же, а операция может быть недешевой.
Понятно, что мы ничего не сделаем, не зная устройства конкретного map. В противном случае мы можем предоставить специализированную реализацию. Если посмотреть на реализацию данного метода в Java 8, то видно, что во многих map специализация имеется:
А для TreeMap реализации нет. А ведь поиск в нем — недешевая операция с логарифмической сложностью, потому что там красно-чёрное дерево. В реализации по умолчанию поиск приходится делать дважды, хотя в оптимальной можно пройти по дереву всего один раз, найти подходящий узел и после вызова пользовательской функции не искать узел повторно.
Сергей Куксенко предложил оптимальную реализацию еще в 2017 году, когда шла работа над Java 10. Было несколько комментариев на Code Review, но потом дело заглохло. В 2019 году я подхватил патч и довел до конца, попутно исправив один баг в исходной реализации и добавив реализацию метода merge(), тесты и бенчмарки. Патч добрался до Java 15, и бенчмарки показывают, что работа не была напрасной:
Это специальный показательный бенчмарк, в котором каждый раз происходит два обращения к ключу. То есть в map в computeIfAbsent() изначально значений не было, и они туда добавляются. А в computeIfPresent() значения уже были, и их модифицировали. Для маленьких map эффект будет меньше, потому что глубина дерева меньше, но 10-20 % мы выигрываем даже на них.
У патча есть и обратная сторона. Чтобы ее проиллюстрировать, сделаем то, что рано или поздно многие программисты делают, только стесняются говорить — подсчет чисел Фибоначчи.
public BigInteger fibo(int arg) {
if (arg < 1) {
throw new IllegalArgumentException();
}
if (arg <= 2) {
return BigInteger.ONE;
}
return fibo(arg - 1).add(fibo(arg - 2));
}
public static void main(String[] args) {
Fibo fibo = new Fibo();
System.out.println(fibo.fibo(100));
}Совершенно без стыда напишем наивный рекурсивный алгоритм и запустим вычисление с аргументом 100. Программа надолго задумалась, и ждать смысла нет. Закэшируем:
Map<Integer, BigInteger> map = new HashMap<>();
private BigInteger calcFibo(int arg) {
if (arg < 1) {
throw new IllegalArgumentException();
}
if (arg <= 2) {
return BigInteger.ONE;
}
return fibo(arg - 1).add(fibo(arg - 2));
}
public BigInteger fibo(int arg) {
BigInteger value = map.get(arg);
if (value == null) {
value = calcFibo(arg);
map.put(arg, value);
}
return value;
}Делаем метод приватным, переименовываем его, а в публичный метод вставляем HashMap. При этом calcFibo() рекурсивно обращается к кэшу, поэтому каждое предыдущее число считается один раз, и мы не получаем экспоненциального взрыва, так что программа быстро выдаст правильный ответ.
Проверим, работает ли наш кэш:
public static void main(String[] args) {
Fibo fibo = new Fibo();
System.out.println(fibo.fibo(100));
// 354224848179261915075
System.out.println(fibo.map.get(100));
// 354224848179261915075
}Там действительно лежит наше число. Если мы второй раз будем считать число Фибоначчи от 100, то программа просто возьмет значение из map. Посчитаем, сколько записей в нашей map:
System.out.println(fibo.map.size());
// 100 И действительно в ней всего 100 записей. Приятно, когда программа работает, как ожидаешь.
Однако это код в стиле Java 7. Давайте используем более современные методы. Сама IntelliJ IDEA предлагает заменить if в методе fibo() на computeIfAbsent(), что мы и сделаем:
public BigInteger fibo(int arg) {
return map.computeIfAbsent(arg, this::calcFibo);
}В итоге весь метод свернулся в одну строку, и программа продолжает быстро работать. Однако поиск нашего числа в кеше теперь возвращает null. Странно. Размер map теперь составляет 185. Программа ведет себя совсем не так, как ожидалось.
На самом деле наша map оказалась сломанной, и такова цена оптимизации. Когда мы находимся внутри метода, мы должны сделать get() и put(), но не хотим проходить по хеш-таблице два раза.
У метода computeIfAbsent() довольно сложный код, поэтому посмотрим лишь на его алгоритм:
- Найти место в хэш-таблице.
- Если там есть запись, вернуть значение из неё.
- Иначе вызвать функцию mappingFunction().
- Если функция вернула null, вернуть null.
- Иначе создать запись и поместить её в ранее найденное место.
- При необходимости увеличить хеш-таблицу.
- Увеличить size на 1.
- Вернуть то, что вернула функция на шаге 3.
Это хорошо работает, если наша функция не модифицирует map, однако в редких случаях это не так. В случае с Фибоначчи функция рекурсивно вычисляет одно из предыдущих чисел и кэширует его тоже. В результате на предыдущем расчете хеш-таблица могла быть увеличена, то есть мог быть выделен новый массив, а старый уже никому не нужен. А здесь на шаге 5 мы создаем запись в старом массиве, который уже не проверяем.
Также могло оказаться, что мы уже на предыдущих шагах рекурсии уже посчитали текущее значение и засунули его в map, увеличив размер массива на 1. Поэтому HashMap стал сломанным. При этом алгоритм устроен так, что поломка HashMap не приводит к неправильному результату.
В Java 9, к счастью, эту проблему решили. Ну как решили: теперь код стал выкидывать ConcurrentModificationException. Зато благодаря этому все HashMap остаются целыми.
Если мы всё-таки очень хотим computeIfAbsent(), мы можем использовать TreeMap вместо HashMap, ведь, как мы выяснили, метод имеет в TreeMap неоптимизированную реализацию по умолчанию. Это хорошо работает в Java 8-14, но в Java 15 снова выскакивает та же ошибка, ведь теперь у метода есть моя оптимизированная реализация.
Получается, в таких сценариях метод computeIfAbsent() не подходит, и идея провалилась. Даже в документации указано, что
The mapping function should not modify this map during computation.
ArrayList.removeIf
Метод removeIf() появился в Java 8 у всех коллекций, и его реализация по умолчанию выглядит так:
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
} Мы создаем итератор, бежим им по коллекции, затем с помощью Iterator.remove() удаляем элементы, которые успешно прошли фильтр, а затем обновляем булеву переменную removed, чтобы сообщить, удалось ли удалить элемент. Такой код до Java 8 мы писали вручную, и теперь это не нужно.
Прелесть default-методов и в том, что их можно переопределить в конкретных классах и сделать более оптимальную реализацию. В ArrayList этот метод был переопределен еще в Java 8, но в Java 9 его улучшили. Измерим производительность, а затем посмотрим на реализацию.
Бенчмарк будет простым: создадим ArrayList, закинем в него числа от 0 до size-1 и будем удалять элементы:
data = new ArrayList<>();
for (int i = 0; i < size; i++) {
data.add(i);
}Проведем несколько бенчмарков, в которых будем копировать массив из эталона, а затем удалять элементы. Результаты удаления могут зависеть от количества удаляемых элементов и их расположения, поэтому сделаем несколько тестов:
removeAll: list.removeIf(x -> true);
removeHalf: list.removeIf(x -> x % 2 == 0);
removeLast: list.removeIf(x -> x == size - 1);
removeFirst: list.removeIf(x -> x == 0);
removeNone: list.removeIf(x -> false);Посмотрим, сколько времени занимает выполнение ArrayList.removeIf() в Java 8 со средним размером 1000 элементов:
Выглядит разумно, что removeAll победил removeHalf и removeFirst. Мы помним, что внутри ArrayList лежит обычный массив. Если удалить первый элемент, то весь массив необходимо сдвигать. В случае же удаления всего массива необходимо просто занулить все элементы. Однако удаление последнего элемента заняло больше всего времени, хотя кажется, что достаточно занулить последний элемент.
Обернем наш ArrayList в subList, содержащий все элементы, и снова замерим производительность:
Теоретически картина не должна была сильно меняться. Но на практике мы видим существенную разницу во всех тестах. В removeAll мы проигрываем более чем в 20 раз, в removeHalf — примерно в 6 раз. Но зато removeLast и removeFirst с subList работает в разы быстрее.
В чем секрет «длинных» графиков? В Java 8 subList(0, size).removeIf() не реализован вообще, и используется default-реализация с итераторами. Поэтому когда мы удаляем много элементов, каждое удаление двигает хвост массива, и в итоге мы имеем квадратичную сложность.
Посмотрим на результаты тех же тестов в Java 9:
Значения с subList и без него почти одинаковы, и все отличия в рамках погрешности, потому что в Java 9 о subList тоже подумали. Приятно, что исчезли огромные выбросы. Да и логика восторжествовала: removeLast перешел на второе место после removeNone. Хоть это решение выглядит более оптимальным, но оно проигрывает по производительности subList в removeFirst в Java 8. Разгадаем загадку таких странных графиков.
Реализация removeIf() в Java 8 состоит из двух кусков:
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces
// left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}В первом куске мы пробегаем по массиву, опрашиваем фильтр и заполняем BitSet, выставляя биты тем элементам, которые хотим удалить. Казалось бы, мы могли бы удалять сразу из массива без BitSet, но тогда в промежутках ArrayList был бы поломан. Так как в процессе мы вызываем пользовательскую функцию, поломанный ArrayList могут увидеть извне. Поэтому было решено делать все модификации после фильтрации. Тогда наш предикат будет видеть исходное состояние списка при чтении. Это отличается от поведения default-метода, где предыдущие модификации предикату видны.
Потом мы пробегаем по сформированному BitSet и стандартным методом двух курсоров выкидываем удаленные элементы. Затем циклом зануляем хвост, чтобы GC смог собрать удаленные объекты.
Становится понятно, почему removeLast был медленнее всего. В этом случае мы должны пробежать по всему BitSet в цикле:
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}Каждый раз мы находим пустой бит, кроме последнего, читаем элемент и его перезаписываем, не производя никакой полезной работы. И только в конце мы зануляем единственный удаленный элемент.
А removeAll в первый цикл вообще не заходит, потому что newSize равен 0. Он просто зануляет весь массив во втором цикле, который к тому же хорошо векторизуется.
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}Что произошло в Java 9? Во-первых, реализация переехала в закрытый метод, которому передается начало и конец массива, который надо обойти. Благодаря этому метод может использоваться и для subList.
boolean removeIf(Predicate<? super E> filter, int i, final int end) {
Objects.requireNonNull(filter);
int expectedModCount = modCount;
final Object[] es = elementData;
// Optimize for initial run of survivors
for (; i < end && !filter.test(elementAt(es, i)); i++)
;
// Tolerate predicates that reentrantly access the collection for
// read (but writers still get CME), so traverse once to find
// elements to delete, a second pass to physically expunge.
if (i < end) {
…
} else {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return false;
}
}Заметьте, что параметр i нещадно используется как счетчик цикла внутри метода вопреки всем канонам красивого программирования, но ради производительности.
Из этого кода видно, что сделана очень важная оптимизация — мы проматываем серию элементов в начале списка в случае, если фильтр возвращает false. В частности, если удаления нет, то цикл просто проматывается до конца, и больше ничего не делаем.
Основная часть метода проходит в условии, если фильтр что-то нашел:
if (i < end) {
final int beg = i;
final long[] deathRow = nBits(end - beg); // new long[((n - 1) >> 6) + 1];
deathRow[0] = 1L; // set bit 0
for (i = beg + 1; i < end; i++)
if (filter.test(elementAt(es, i)))
setBit(deathRow, i - beg); // bits[i >> 6] |= 1L << i;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
int w = beg;
for (i = beg; i < end; i++)
if (isClear(deathRow, i - beg)) // (bits[i >> 6] & (1L << i)) == 0;
es[w++] = es[i];
shiftTailOverGap(es, w, end);
return true;
} else { … }Чтобы избежать лишнего объекта, здесь сделан BitSet «на коленке». С помощью статических методов nBits(), setBit() и isClear мы напрямую выделяем массив long и оперируем в нем битами. Да, экономия на спичках, но для базового класса это допустимо.
Наш примитивный BitSet начинается уже с первого найденного элемента, а не с начала списка. Поэтому в removeLast мы выделим всего один элемент, заодно упростив жизнь сборщику мусора.
Заметим, что кое в чем мы проиграли. В прошлый раз мы отслеживали число удалений, благодаря чему мы знали, когда хвост BitSet содержит только удаленные элементы, и прекращали по нему бежать. В этот раз такая оптимизация не была сделана.
Подведем итог бенчмарков в Java 9. В Java 9 быстродействие более ровное и меньше зависит от того, что мы удаляем. Мы выигрываем, если удаляем элементы ближе к концу либо если удаляем очень много элементов. И существенное улучшение в одних случаях привело к небольшому ухудшению в других.
hashSet.removeIf()
Попробуем теперь удалять не из ArrayList, а из HashSet. Сперва нужно добавить что-то ненужное. Положим в HashSet списки целых чисел: [], [0], [0, 1] и т. д.:
HashSet<List<Integer>> set;
@Setup
public void setup() {
set = IntStream.range(0, 1000)
.mapToObj(i -> IntStream.range(0, i).boxed().collect(Collectors.toList()))
.collect(Collectors.toCollection(HashSet::new));
}Так как мы хотим удалять много раз, нам нужно восстанавливать HashSet в исходное положение. Поэтому бенчмарк будет выглядеть так:
@Benchmark
public Set<List<Integer>> removeHalf() {
Set<List<Integer>> copy = new HashSet<>(set);
copy.removeIf(list -> list.size() > 500);
return copy;
}
@Benchmark
public Set<List<Integer>> noRemove() {
return new HashSet<>(set);
}Второй бенчмарк только копирует, но ничего не удаляет. Оценим скорость копирования в Java 8:
Получаем, что копирование + удаление длится вдвое дольше, чем просто копирование. Следовательно, удаление по расходу ресурсов близко к копированию, что довольно накладно.
В Java 9 удаление стало значительно быстрее, и уже около 10 % времени уходит на удаление. Как же этого добились? Наверное, снова хитрую реализацию HashSet.removeIf() сделали? Однако специализированной реализации вообще нет. Вместо этого используется стандартная реализация Collection.removeIf(), которая делегирует к HashSet.iterator().remove(). HashSet.iterator().remove() делегирует далее к HashMap.keySet().iterator().remove(). Как мы помним, в HashSet лежит обычный HashMap с default-значением, где мы используем ключи как set. Далее мы переходим к HashMap.KeyIterator.remove(), но в нем нет метода remove(). Дело в том, что по HashMap можно создавать разные итераторы: keySet().iterator(), valueSet().iterator(), entrySet().iterator(), но удаление будет работать одинаково, поэтому оно вынесено в общий суперкласс.
Разгадка кроется в родительском классе HashIterator. Что же там оптимизировали, что удаление стало быстрее? В нем удалили две строчки и добавили одну:
Внутреннему методу removeNode(), который и выполняет удаление, передается хеш ключа. До Java 9 хеш вычислялся заново по ключу, хотя в этом особого смысла не было, потому что хеш уже хранится в доступном узле.
Понятно, что я схитрил с бенчмарком. Я создал множество списков, а списки свой хеш не хранят и каждый раз вычисляют заново. Во многих случаях хеш-код вычисляется быстро или кэшируется, поэтому разница не так заметна, но в таких сценариях становится просто гигантской.
Благодаря тому, что этот метод много где используется, эффект можно наблюдать во многих случаях. Если вы прямо или косвенно пользуетесь удалением через итератор, в любой коллекции, производной от HashMap или LinkedHashMap, вы пройдете через этот метод.
HashMap.containsKey
Схожая оптимизация появилась в Java 15 и касается пустых Map. Бенчмарк будет такой:
HashMap<List<Integer>, String> emptyMap;
HashMap<List<Integer>, String> nonEmptyMap;
List<Integer> key;
@Setup
public void setup() {
emptyMap = new HashMap<>();
nonEmptyMap = new HashMap<>();
nonEmptyMap.put(Collections.emptyList(), "");
key = IntStream.range(0, 500).boxed().collect(Collectors.toList());
}
@Benchmark
public boolean containsInEmpty() {
return emptyMap.containsKey(key);
}
@Benchmark
public boolean containsInNonEmpty() {
return nonEmptyMap.containsKey(key);
}Мы создали два HashMap. Один из них будет пустой, а в другой сложим один элемент. Мы проверяем наличие ключа со сложным хеш-кодом, например, список из 500 чисел. В результате мы получаем:
В Java 14 мы тратим около 500 нс и с пустым, и с непустым списком, а в Java 15 с пустым списком уходит всего около 3 нс. Очевидно, что не нужно считать хеш-код, если список пустой.
Здесь исправление очень простое, хоть и нетривиальное. Важной частью реализации HashMap является метод getNode(), который ищет элемент в хеш-таблице по ключу. До Java 15 он принимал сразу хеш и ключ, то есть хеш должен был вычислить тот, кто вызывает этот метод.
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
…
}
return null;
}А в Java 15 расчет хеш-кода перенесли внутрь getNode(). Это не только упростило использование метода, но и позволило отложить вычисление хеш-кода до того, как оно потребуется. А хеш-код может вообще не потребоваться, если таблица пустая.
final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
…
}
return null;
}Соответственно поменялись все точки вызова, в результате чего ускорился не только containsKey(), но и get() и getOrDefault(). Но за эту оптимизацию тоже пришлось заплатить цену.
Метод computeIfPresent() применяет функцию для существующего ключа и заменяет ее значение. А если функция вернула null, то значение надо удалить. И в этом редком случае ключ теперь нужно вычислять дважды.
Для демонстрации напишем бенчмарк. Чтобы он был стабильным, мы добавляем в пустой map один элемент и тут же удаляем его через computeIfPresent().
Конечно, computeIfPresent() тоже можно переписать, заинлайнив getNode(), чтобы повторного вычисления не требовалось, но это усложнит код, и на эту деградацию скрепя сердце пошли. Все-таки computeIfPresent() используется редко, а возвращает null еще реже.
Class.getSimpleName()
Поговорим про Reflection. У класса есть имя, и так сложилось, что оно может быть разное. Есть три разных метода получения имени: class.getName(), class.getCanonicalName(), class.getSimpleName(). Class.getName() возвращает имя, разделенное точками, а потом имя JVM-класса. Class.getCanonicalName() возвращает имя класса, где вложенный класс отделяется точками, как в исходниках Java-программы. Class.getSimpleName() возвращает имя класса без пакета и окружающих классов. Проверим, какой же из этих методов быстрее:
В Java 8 getName() работает почти мгновенно, и кажется, что имя кешируется. Методы getCanonicalName() и getSimpleName() возвращаются не так быстро, причем скорость зависит от того, вложенный ли класс или же верхнего уровня. Явно значения считаются на лету, а не берутся из кеша.
В Java 11 все стало гораздо быстрее, и явно значения стали кешировать. Однако getCanonicalName() и getSimpleName() все равно работают на 1,3 нс медленнее, чем getName(). Разберемся, откуда взялась разница.
public String getName() {
String name = this.name;
if (name == null)
this.name = name = getName0();
return name;
}
// cache the name to reduce the number of calls into the VM
private transient String name;
private native String getName0();В getName() мы видим обычную процедуру кеширования в поле. Даже в случае гонки несколько потоков просто вызовут getName(), который вернет одно и то же значение.
public String getCanonicalName() {
if (isArray()) {
String canonicalName = getComponentType().getCanonicalName();
if (canonicalName != null)
return canonicalName + "[]";
else
return null;
}
if (isLocalOrAnonymousClass())
return null;
Class<?> enclosingClass = getEnclosingClass();
if (enclosingClass == null) { // top level class
return getName();
} else {
String enclosingName = enclosingClass.getCanonicalName();
if (enclosingName == null)
return null;
return enclosingName + "." + getSimpleName();
}
}Если посмотреть на реализацию getCanonicalName() в Java 10, то никакого кеширования нет, и строки формируются на лету, делегируя к другим методам. В методе getSimpleName() все аналогично. Здесь авторы не захотели добавлять два поля в класс, потому что в Java 8 была проведена достаточно большая работа, направленная на уменьшения потребления памяти Java. В рамках этой работы, в частности, ужимали java.lang.Class, который «кушал» слишком много.
До Java 8 на 32-битной JVM объект класс съедал 112 байт, потому что в нем содержались SoftReference на данные reflection. Если класс использовался через reflection, то они заполнялись, в противном случае оставались пустыми. А в Java 8 решили эти данные перетащить в отдельный вложенный объект ReflectionData и повесить на один SoftReference. В результате мы экономим на 32-битной JVM 32 байта, когда класс не использует Reflection вообще, и 224 байта, когда используются все 8 кешей Reflection.
После этой оптимизации не хотелось откатываться назад и добавлять два новых поля в каждый класс. Все-таки getSimpleName() и getCanonicalName() для большинства классов никогда не вызываются. Они могут потребоваться для каких-либо фреймворков при обработке аннотаций, но обычно классу они не нужны. В итоге эти поля добавили в ReflectionData. Посмотрим подробнее на ReflectionData до добавления.
// reflection data that might get invalidated
// when JVM TI RedefineClasses() is called
private static class ReflectionData<T> {
volatile Field[] declaredFields;
volatile Field[] publicFields;
volatile Method[] declaredMethods;
volatile Method[] publicMethods;
volatile Constructor<T>[] declaredConstructors;
volatile Constructor<T>[] publicConstructors;
// Intermediate results for getFields and getMethods
volatile Field[] declaredPublicFields;
volatile Method[] declaredPublicMethods;
volatile Class<?>[] interfaces;
// Value of classRedefinedCount when we created this ReflectionData instance
final int redefinedCount;
ReflectionData(int redefinedCount) {
this.redefinedCount = redefinedCount;
}
}Мы видим различные кэши в массивах. Тонкость с этим объектом состоит в том, что любой класс может быть переопределен JVMTI-агентом, и тогда ReflectionData устареет, что усложняет кэширование ReflectionData.
private transient volatile SoftReference<ReflectionData<T>> reflectionData;
// Incremented by the VM on each call to JVM TI RedefineClasses()
// that redefines this class or a superclass.
private transient volatile int classRedefinedCount;
// Lazily create and cache ReflectionData
private ReflectionData<T> reflectionData() {
SoftReference<ReflectionData<T>> reflectionData = this.reflectionData;
int classRedefinedCount = this.classRedefinedCount;
ReflectionData<T> rd;
if (reflectionData != null &&
(rd = reflectionData.get()) != null &&
rd.redefinedCount == classRedefinedCount) {
return rd;
}
// else no SoftReference or cleared SoftReference or stale ReflectionData
// -> create and replace new instance
return newReflectionData(reflectionData, classRedefinedCount);
}Во-первых, оно кэшируется в SoftReference, чтобы при нехватке памяти можно было пустить под нож. Во-вторых, есть внутреннее поле redefinedCount, которое сама виртуальная машина обновляет при переопределении класса объектом. Интересно, что поле типа int, поэтому может переполниться за вполне реалистичное время.
В общем, пересоздавать ReflectionData нужно не только когда GC добрался до прошлой версии, но и если classRedefinedCount не совпадает.
private ReflectionData<T> newReflectionData(
SoftReference<ReflectionData<T>> oldReflectionData,
int classRedefinedCount) {
while (true) {
ReflectionData<T> rd = new ReflectionData<>(classRedefinedCount);
// try to CAS it...
if (Atomic.casReflectionData(
this, oldReflectionData, new SoftReference<>(rd))) {
return rd;
}
// else retry
oldReflectionData = this.reflectionData;
classRedefinedCount = this.classRedefinedCount;
if (oldReflectionData != null &&
(rd = oldReflectionData.get()) != null &&
rd.redefinedCount == classRedefinedCount) {
return rd;
}
}
}Само пересоздание происходит в CAS-цикле, потому что два потока могут обращаться одновременно, а в третьем потоке агент может пересоздавать класс.
И в Java 11 в ReflectionData добавили новые поля:
private static class ReflectionData<T> {
volatile Field[] declaredFields;
…
volatile Class<?>[] interfaces;
+ // Cached names
+ String simpleName;
+ String canonicalName;
+ static final String NULL_SENTINEL = new String();
…
}Так как у класса может не быть канонического имени (например, анонимный класс), нужно отличать неинициализированное значение от инициализированного, но отсутствующего (примерно как с хеш-кодом строк). Для этого делается уникальная пустая строка конструктором без аргументов.
public String getCanonicalName() {
ReflectionData<T> rd = reflectionData();
String canonicalName = rd.canonicalName;
if (canonicalName == null) {
rd.canonicalName = canonicalName = getCanonicalName0();
}
return canonicalName == ReflectionData.NULL_SENTINEL ?
null : canonicalName;
}В Java 11 в реализации getCanonicalName() все переехало в скрытые методы. Аналогично изменилась реализация getSimpleName(). Понятно, что если обратиться через ReflectionData, возникают дополнительные накладные расходы, где и теряются 1,3 нс.
Class.getConstructor
Последняя оптимизация в этом докладе связана с getConstructor(). Создадим классы с разными конструкторами:
public static class X {
public X() {}
}
public static class X1 {
public X1() {}
public X1(int p1) {}
public X1(int p1, int p2) {}
public X1(int p1, int p2, int p3) {}
public X1(int p1, int p2, int p3, int p4) {}
public X1(int p1, int p2, int p3, int p4, int p5) {}
}
public static class X2 {
public X2() {}
public X2(int p1) {}
public X2(int p1, int p2) {}
public X2(int p1, int p2, int p3) {}
public X2(int p1, int p2, int p3, int p4) {}
public X2(int p1, int p2, int p3, int p4, int p5) {}
public X2(int p1, int p2, int p3, int p4, int p5, int p6) {}
public X2(int p1, int p2, int p3, int p4, int p5, int p6, int p7) {}
public X2(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8) {}
public X2(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8, int p9) {}
public X2(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8, int p9, int p10) {}
}Посмотрим, сколько времени занимает получение конструктора без аргументов от каждого из трех классов:
@Benchmark
public Constructor<?> getConstructorX() throws NoSuchMethodException {
return X.class.getConstructor();
}
@Benchmark
public Constructor<?> getConstructorX1() throws NoSuchMethodException {
return X1.class.getConstructor();
}
@Benchmark
public Constructor<?> getConstructorX2() throws NoSuchMethodException {
return X2.class.getConstructor();
}В Java 8, оказывается, существует зависимость от количества конструкторов в программе:
90 нс кажутся перебором, и это заметили разработчики JDK и немного переделали код в Java 9:
Операции стали существенно быстрее, и это особенно заметно в классе с кучей конструкторов. Зависимость осталась, но существенно менее выраженная. Посмотрим, сколько памяти выделяется за одну операцию:
Выделяемая память в этом тесте неплохо коррелирует с временем работы. В Java 8 она зависела от других конструкторов, а в Java 9 стала меньше и уже не зависит. Что же изменилось?
После проверок прав доступа getConstructor() делегирует к приватному методу getConstructor(), который в Java 8 выглядел так:
private Constructor<T> getConstructor0(Class<?>[] parameterTypes, int which) throws NoSuchMethodException
{
Constructor<T>[] constructors = privateGetDeclaredConstructors((which == Member.PUBLIC));
for (Constructor<T> constructor : constructors) {
if (arrayContentsEq(parameterTypes, constructor.getParameterTypes())) {
return getReflectionFactory().copyConstructor(constructor);
}
}
throw new NoSuchMethodException(getName() + ".<init>" + argumentTypesToString(parameterTypes));
}Метод принимает желаемые аргументы и уровень доступа конструкторов. Они запрашиваются из ReflectionData с помощью privateGetDeclaredConstructors(). Затем в обычного цикле вида find-first ищем подходящий конструктор, сравнивая типы аргументов. Интересно, что конструкторы и вообще методы возвращаются reflection вовсе не в том порядке, как они объявлены в исходниках, а в произвольном. Поэтому хотя мы во всех трех классах нужный конструктор объявили первым, не факт, что он будет первым в массиве, и нам может потребоваться несколько итераций.
Проблема кроется здесь в методе getParameterTypes(): именно тут выделяется память в цикле. Это публичный метод, который возвращает массив (вообще весь Reflection API возвращает массивы, а не списки, по историческим причинам).
Понятно, что в классе Constructor публичный метод не может взять и вернуть внутренний массив, поэтому он его клонирует:
public final class Constructor<T> extends Executable {
…
@Override
public Class<?>[] getParameterTypes() {
return parameterTypes.clone();
}
…
}Кажется, что проблемы нет, и можно сделать еще один непубличный метод, который не будет копировать, и будем вызывать его. Но не все так просто. Class объявлен в пакете java.lang, а Constructor объявлен в java.lang.reflect, и права доступа необходимо соблюдать. Эту проблему давно решают в стандартной библиотеке, и между определенными методами вырыты «кротовые норы», которые позволяют их вызывать. Так поступили в Java 9 с getConstructor0():
private Constructor<T> getConstructor0(Class<?>[] parameterTypes, int which) throws NoSuchMethodException
{
ReflectionFactory fact = getReflectionFactory();
Constructor<T>[] constructors = privateGetDeclaredConstructors((which == Member.PUBLIC));
for (Constructor<T> constructor : constructors) {
if (arrayContentsEq(parameterTypes, fact.getExecutableSharedParameterTypes(constructor))) {
return constructor;
}
}
throw new NoSuchMethodException(methodToString("<init>", parameterTypes));
}Здесь мы спускаемся в «кротовую нору» через вспомогательный приватный класс ReflectionFactory:
package jdk.internal.reflect;
public class ReflectionFactory {
…
private final JavaLangReflectAccess langReflectAccess;
private ReflectionFactory() {
this.langReflectAccess = SharedSecrets.getJavaLangReflectAccess();
}
…
public Class<?>[] getExecutableSharedParameterTypes(Executable ex) {
return langReflectAccess.getExecutableSharedParameterTypes(ex);
}
…
}Класс появился ранее, но в нем сделали новую «дырку». «Дырка» делегирует к разделенным пакетам доступа с JavaLangReflect, и все это уже секретная часть java.base. Пакеты jdk.internal не экспортируются, поэтому простым смертным ковыряться в них не положено.
SharedSecrets, в свою очередь, объявлен в jdk.internal.access и содержит статические поля для различных пакетов, для которых необходимо проковыривать «дырки» в JDK, в том числе для JavaLangReflect:
package jdk.internal.access;
public class SharedSecrets {
private static JavaLangReflectAccess javaLangReflectAccess;
public static void setJavaLangReflectAccess(JavaLangReflectAccess jlra) {
javaLangReflectAccess = jlra;
}
public static JavaLangReflectAccess getJavaLangReflectAccess() {
return javaLangReflectAccess;
}
…
}JavaLangReflectAccess — это интерфейс в неэкспортируемом пакете, в который добавлен новый метод:
package jdk.internal.access;
/** An interface which gives privileged packages Java-level access to
internals of java.lang.reflect. */
public interface JavaLangReflectAccess {
/** Gets the shared array of parameter types of an Executable. */
public Class<?>[] getExecutableSharedParameterTypes(Executable ex);
…
}А сеттер вызывает статический инициализатор класса AccessibleObject:
package java.lang.reflect;
public class AccessibleObject implements AnnotatedElement {
static {
// AccessibleObject is initialized early in initPhase1
SharedSecrets.setJavaLangReflectAccess(new ReflectAccess());
}
…
}Класс AccessibleObject инициализируется достаточно рано в процессе запуска JVM, поэтому в нужный момент сеттер уже вызван.
Реализация соответствующего интерфейса — это уже непубличный класс внутри пакета java.lang.reflect, который наконец позволяет запустить непубличный метод публичного класса в том же самом пакете:
package java.lang.reflect;
/** Package-private class implementing the
jdk.internal.access.JavaLangReflectAccess interface, allowing the java.lang
package to instantiate objects in this package. */
class ReflectAccess implements jdk.internal.access.JavaLangReflectAccess {
…
public Class<?>[] getExecutableSharedParameterTypes(Executable ex) {
return ex.getSharedParameterTypes();
}
…
}В общем, такой поток данных — это слишком скучно:
А вот так окольными путями гораздо интереснее:
Все ради того, чтобы не копировать массив. Кстати, этого нельзя было сделать нормально, пока в Java не появились модули.
Итого
Мы посмотрели 9 оптимизаций, которые были добавлены в Java 9-16, изучили проблемы с производительностью, которые бывают у JDK, и какие подходы используются для их решения. И надеюсь, что данный доклад замотивирует перейти с Java 8 на новые версии тех, кто еще этого не сделал. Спасибо!
Напоследок — минутка рекламы. Несмотря на все сложности, Joker 2020 обязательно пройдет, хоть и впервые в онлайн-формате. А это значит, что присоединиться к конференции можно из любой точки мира.
Среди спикеров в этом году будет Питер Лоури — Java Champion и топ-1 по количеству ответов в темах о Java, JVM, concurrency, file-io и memory на Stack Overflow. Он выступит с докладом о необычных кейсах Java-программирования, подробно разберет каждый из них и объяснит, почему в этих случаях все сделано именно так.
