Часть 1. invokevirtual
Я уже писал, что invokeinterface — страшная операция, сейчас хочу развить эту тему.
Оптимизатор работает так:
Если тип объекта точно известен, то оптимизатор заменяет вызов виртуального метода на обычный goto, и даже инлайнит, и всё хорошо.
Если тип объекта неизвестен, но в 99,99% случаев оказывается объектом одного типа, оптимизатор генерирует примерно такой код:
if (obj.getClass() == ConcreteType.class) {
invokespecial obj.foo(params);
} else {
invokevirtual/invokeinterface obj.foo(params);
}
Предсказатель ветвлений процессора успешно предсказывает первую проверку, и вызов выполняется как обычный goto, и даже инлайнится, и всё хорошо.
Но если объект каждый раз разный, то оптимизатор ничего уже поделать не может, и вынужден делать invokevirtual или даже invokeinterface.
Часть 2. Не используйте Collections.emptyList()
Что это значит на практике.
В JDK есть утилита Collections.emptyList(). Несть числа разработчиков пишут такой код:
if (condition) {
return Collections.emptyList();
} else {
List r = new ArrayList();
// fill r
return r;
}
Вот это как раз этот случай. Замена первого return на new ArrayList(0) приводит к существенному ускорению работы с коллекциями, но появляется небольшая потеря скорости на GC.
Я написал небольшой тест для иллюстрации этих утверждений. Тест сначала генерирует случайное число от 0 до 2, если выпадает на 0, создаёт пустую коллекцию различными способами, иначе создаёт ArrayList и заполняет его числами. Список возвращается из метода, по нему делается проход с помощью обычного foreach.
По ссылке четыре варианта теста:
— intsArrayList всегда создаёт ArrayList
— intsEmptyList создаёт Collections.emptyList() для пустого списка
— intsArrayListCached всегда возвращает ArrayList, но для пустого списка использует глобальную переменную, чтобы не тратить время на выделение пустого ArrayList
— intsArrayListUnmodifiable всегда возвращает ArrayList, завёрнутый в Collections.unmodifiableList(), для пустого списка используется закешированная копия
Результаты такие (меньше — лучше):
empty_list: 2632
array_list: 2216
arl_cached: 2011
unmodifiab: 2844
Использование emptyList считаем за baseline.
Выделение нового ArrayList даёт 10-20% прироста производительности (но надо помнить, что не учитываются накладные расходы на сам тест, т. е. чистый прирост ещё больше, и что не учитывается работа GC, которая КМК, создаёт небольшую нагрузку)
Использование закешированного ArrayList даёт ещё 5-10% производительности.
Использование ArrayList+unmodifiableList существенно проигрывает всем вариантам. Почему это происходит, понятно не до конца. То ли из-за indirect memory access, то ли оптимизатор не догадывается, что работа происходит всегда с одним и тем же типов, внутри которого лежит один и тот же тип, может быть итерирование слишком дорогое в unmodifiableList, может быть дело в излишней нагрузке на GC. Скорее всего замедление происходит по совокупности этих причин.
Вообще надо понимать, что числа очень условные, в зависимости от сценария различные подходы могут давать как несущественную разницу, так и разницу в десятки процентов.
Практические выводы.
Вариант с ArrayList+unmodifiableList использовать не надо.
Использование shared пустого ArrayList кажется мне слишком опасным: если возвращать из метода этот общий пустой объект, какой-нибудь стажёр в него что-нибудь запишет, потом придётся год отлаживать, чтобы найти проблему.
Я думаю, можно всегда возвращать новый ArrayList.
Часть 3. Используйте ReadOnlyArrayList
Правильное решение — это использование класса ReadOnlyArrayList.
Схематично класс ReadOnlyArrayList выглядит так:
public class ReadOnlyArrayList extends AbstractList {
private final T[] array;
private final int offset;
private final int length;
ReadOnlyArrayList(T[] array, int offset, int length) { ... }
public static class Builder extends AbstractList {
private T[] array = EMPTY_ARRAY;
private int length;
public void add(T t) { ... }
public ReadOnlyArrayList build() {
if (length == 0) return EMPTY_ARRAY_LIST;
ReadOnlyArrayList r = new ReadOnlyArrayList(this.array, 0, this.length);
this.array = null;
this.length = 0;
return;
}
}
}
Вместо ArrayList пользоваться классом нужно так:
ReadOnlyArrayList.Builder b = new ReadOnlyArrayList.Builder();
// add elements to b
return b.build();
В чём фишка класса ReadOnlyArrayList:
— класс immutable. Это очень хорошо, т. к. с кодом с неизменяемыми объектами гораздо проще работать
— список имеет константные по memory и cpu операции take(n) и drop(n), которые возвращают, опять же, объект типа ReadOnlyArrayList. Это очень удобно для многих алгоритмов. subList так же возвращает настоящий ReadOnlyArrayList, а не view
— в ReadOnlyArrayList не нужна дурацкая проверка на modCount. Она и в ArrayList не нужна, но тут проверка совсем не нужна
— создание списка по такой схеме дороже чем создание ArrayList на константу — создание экземпляра ReadOnlyArrayList.Builder
— хороший оптимизатор выделяет ReadOnlyArrayList.Builder на стеке
— для конструирования пустого списка не происходит выделения памяти (можно вернуть, например, ссылку на ReadOnlyArrayList.EMPTY_LIST)
— результирующий список всегда имеет один тип, что сильно облегчает оптимизацию (см. выше)
— и самое главное: производительность чтения из ReadOnlyArrayList равна ArrayList, потому что ReadOnlyArrayList имеет ровно такую же структуру, ровно те же поля, ровно такие же реализации методов, что и ArrayList
Я считаю, что в каждом проекте нужна какая-нибудь реализация ReadOnlyArrayList.
В библиотеке bolts есть реализация ReadOnlyArrayList (Builder называется ArrayListF, а метод build — convertToReadOnly).
Я буду лоббировать добавление в стандартную библиотеку Kotlin реализации класса ReadOnlyArrayList как "основного" класса коллекций в стандартной библиотеке, в т. ч. по-умолчанию для возврата из функций filter, map и т. п. (как это сделано в bolts).
U: Проверил, если заменить Collections.emptyList на shared empty ArrayList, а Collections.singletonList на новый ArrayList, тесты компилятора Kotlin ускоряются на 0,002. |
