Данная статья продолжает цикл моих переводов статей Jakob Jenkov об оптимизации Java приложений.
Довольно часто приложения Java хранят объекты в структурах данных, содержащих java.util. Экземпляры ArrayList. При копировании объектов в этих структурах данных мы также должны повторять объекты, хранящиеся в экземплярах ArrayList. В этом руководстве по производительности Java ArrayList я подробнее рассмотрю производительность различных способов итерации ArrayList. В этом руководстве также будет рассмотрена производительность класса OpenArrayList - класса, который имитирует java.util.ArrayList, но разработанный с учетом производительности.
Три способа перебора ArrayList
В основном существует три различных способа перебора объектов, содержащихся в ArrayList:
- Используя цикл for
- Используя цикл for-each
- Используя итератор.
Разница в производительности между этими тремя способами итерации ArrayList невелика, но она небольшая, и она достаточно велика, чтобы, если ваш код критичен к производительности, вы могли бы получить этот почти бесплатный прирост производительности. Но сначала позвольте мне показать вам три способа итерации ArrayList.
Цикл for
Итерация ArrayList с использованием стандартного цикла Java for выглядит следующим образом:
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
for(int i=0, n=arrayList.size(); i < n; i++){
Object element = arrayList.get(i);
}
Как вы можете видеть, цикл for использует стандартный счетчик для подсчета всех элементов, хранящихся в ArrayList. Каждый элемент получается из экземпляра ArrayList с помощью метода get().
Цикл for-each
Цикл for-each использует конструкцию for, добавленную в Java 5. Вот как выглядит итерация ArrayList с использованием цикла for-each:
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
for(Object obj : arrayList){
...
}
Итератор
Третий способ перебора ArrayList - использовать java.util.Итератор, полученный из ArrayList. Вот как выглядит итерация ArrayList с использованием итератора:
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
Iterator iterator = arrayList.iterator();
while(iterator.hasNext()) {
Object element = iterator.next();
}
Производительность итератора ArrayList
Чтобы измерить разницу в производительности итерации трех различных способов итерации ArrayList, я реализовал три различных метода тестирования с использованием Java Microbenchmark Harness. Код для этих контрольных показателей приведен в конце этого текста.
Чтобы получить более точное представление о скорости итерации каждого метода, я измерил скорость итерации ArrayList из 10 и 100 элементов. Таким образом, я полагаю, я получил бы более детальную картину представления.
Элементы в ArrayList - это длинные элементы, которые суммируются. Таким образом, контрольные показатели действительно измеряют как итерацию, так и суммирование 10 и 100 длинных элементов, хранящихся в ArrayList.
Тесты были выполнены с использованием JDK 1.8.0_u60 на сервере Intel Core i7-4770 Haswell, который не делал ничего, кроме тестов. Тесты были выполнены с использованием значений по умолчанию JMH, что означает 20 итераций прогрева, 20 итераций и 10 форков каждой. Вот результаты тестирования (выходные данные JMH):
Benchmark Mode Cnt Score Error Units
OpenArrayListBenchmark.jdkArrayList100SumUsingGet thrpt 200 15838998.503 ± 1017.752 ops/s
OpenArrayListBenchmark.jdkArrayList100SumUsingForEach thrpt 200 14068898.854 ± 946.976 ops/s
OpenArrayListBenchmark.jdkArrayList100SumUsingIterator thrpt 200 14069990.330 ± 512.600 ops/s
OpenArrayListBenchmark.jdkArrayList10SumUsingGet thrpt 200 77320532.538 ± 7421.267 ops/s
OpenArrayListBenchmark.jdkArrayList10SumUsingForEach thrpt 200 69926532.927 ± 732112.779 ops/s
OpenArrayListBenchmark.jdkArrayList10SumUsingIterator thrpt 200 69879781.630 ± 727551.844 ops/s
Как вы можете видеть, итерация ArrayList с использованием цикла for-each и итератора дает практически ту же производительность. Это было ожидаемо, так как цикл for-each, вероятно, компилируется компилятором Java в итерацию с использованием итератора.
Вы также можете видеть, что итерация ArrayList с использованием стандартного цикла Java for со счетчиком и получение каждого элемента путем вызова метода ArrayList get() выполняется примерно на 10% быстрее для ArrayList с 10 элементами и примерно на 12,5% быстрее, когда ArrayList содержит 100 элементов.
Трудно точно сказать, почему существует такая разница в производительности. Частично разница, вероятно, вызвана созданием объекта-итератора для каждой итерации. Однако можно было бы ожидать, что накладные расходы будут выровнены (менее заметны), когда ArrayList содержит больше элементов. Но вместо этого, похоже, разница в производительности растет (с 10% при 10 элементах до 12,5% при 100 элементах). Это может быть вызвано более оптимизированным выполнением цикла процессором для версии for loop, но я не могу сказать наверняка.
OpenArrayList
Класс OpenArrayList - это очень простая имитация ArrayList, которую я реализовал, чтобы посмотреть, может ли он выполнять итерацию набора элементов быстрее, чем ArrayList. Вот сокращенная версия реализации OpenArrayList:
public Object[] elements = null;
public int capacity = 0;
public int size = 0;
public OpenArrayList(){
}
public OpenArrayList(int capacity){
this.capacity = capacity;
this.elements = new Object[capacity];
}
public OpenArrayList(Object[] elements){
this.elements = elements;
this.capacity = elements.length;
}
public void add(Object element){
this.elements[this.size++] = element;
}
public boolean addIfCapacity(Object element){
if(this.size < this.capacity){
this.elements[this.size++] = element;
return true;
}
return false;
}
}
Первое, на что следует обратить внимание, - это то, что все переменные-члены OpenArrayList являются общедоступными. Вот почему я назвал его "Открытым". Его переменные-члены открыты для внешнего мира. Я сделал переменные-члены общедоступными, чтобы вы могли напрямую обращаться к массиву элементов при повторении элементов в OpenArrayList. Это должно быть немного быстрее, чем вызов метода ArrayList get(), хотя JVM может оптимизировать вызов метода get().
Еще одним преимуществом общедоступности массива элементов является то, что вы можете записывать в него или копировать из него с помощью System.arraycopy(), что очень быстро.
Производительность OpenArrayList
Как и в случае с ArrayList, я измерил суммирование объектов длиной 10 и 100, хранящихся в OpenArrayList. Тесты были выполнены с использованием той же настройки, что и тесты ArrayList.
Вот контрольные показатели итерации OpenArrayList (с контрольными показателями ArrayList ниже для удобства сравнения):
Benchmark Mode Cnt Score Error Units
OpenArrayListBenchmark.openArrayList100Sum thrpt 200 16040305.970 ± 1490.153 ops/s
OpenArrayListBenchmark.openArrayList10Sum thrpt 200 81301297.431 ± 15104.301 ops/s
OpenArrayListBenchmark.jdkArrayList100SumUsingGet thrpt 200 15838998.503 ± 1017.752 ops/s
OpenArrayListBenchmark.jdkArrayList100SumUsingForEach thrpt 200 14068898.854 ± 946.976 ops/s
OpenArrayListBenchmark.jdkArrayList100SumUsingIterator thrpt 200 14069990.330 ± 512.600 ops/s
OpenArrayListBenchmark.jdkArrayList10SumUsingGet thrpt 200 77320532.538 ± 7421.267 ops/s
OpenArrayListBenchmark.jdkArrayList10SumUsingForEach thrpt 200 69926532.927 ± 732112.779 ops/s
OpenArrayListBenchmark.jdkArrayList10SumUsingIterator thrpt 200 69879781.630 ± 727551.844 ops/s
Как вы можете видеть, итерация OpenArrayList выполняется примерно на 1% быстрее, когда ArrayList содержит 100 элементов, и примерно на 5% быстрее с 10 элементами. Почему именно существует такая разница в производительности, я не могу сказать наверняка. Тот факт, что производительность настолько близка, вероятно, является признаком того, что JVM оптимизировала вызов get(). Но все же интересно, что, по-видимому, существует большая разница в производительности для меньшего количества элементов.
Производительность итератора
Вот эталонный код, используемый для измерения скорости итерации различных методов итерации как для ArrayList, так и для OpenArrayList.
public class OpenArrayListBenchmark {
@State(Scope.Thread)
public static class BenchmarkState {
public ArrayList<Long> jdkArrayList10 = new ArrayList<>();
public ArrayList<Long> jdkArrayList100 = new ArrayList<>();
public OpenArrayList openArrayList10 = new OpenArrayList(10);
public OpenArrayList openArrayList100 = new OpenArrayList(100);
@Setup(Level.Trial)
public void toSetup() {
Object[] elements = openArrayList10.elements;
for(int i=0; i < openArrayList10.capacity; i++){
elements[i] = new Long(i);
jdkArrayList10.add(new Long(i));
}
openArrayList10.size = openArrayList10.capacity;
elements = openArrayList100.elements;
for(int i=0; i < openArrayList100.capacity; i++){
elements[i] = new Long(i);
jdkArrayList100.add(new Long(i));
}
openArrayList100.size = openArrayList100.capacity;
}
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long openArrayList10Sum(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Object[] elements = state.openArrayList10.elements;
for(int i=0; i<state.openArrayList10.size; i++){
sum += ((Long) elements[i]).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long openArrayList100Sum(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Object[] elements = state.openArrayList100.elements;
for(int i=0; i<state.openArrayList100.size; i++){
sum += ((Long) elements[i]).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingGet(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
ArrayList arrayList = state.jdkArrayList10;
for(int i=0, n=state.jdkArrayList10.size(); i < n; i++){
sum += ((Long) arrayList.get(i)).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingGet(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
ArrayList arrayList = state.jdkArrayList100;
for(int i=0, n=state.jdkArrayList100.size(); i < n; i++){
sum += ((Long) arrayList.get(i)).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingForEach(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
for(Long element : state.jdkArrayList10){
sum += element.longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingForEach(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
for(Long element : state.jdkArrayList100){
sum += element.longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingIterator(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Iterator<Long> iterator = state.jdkArrayList10.iterator();
while(iterator.hasNext()){
sum += iterator.next().longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingIterator(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Iterator<Long> iterator = state.jdkArrayList100.iterator();
while(iterator.hasNext()){
sum += iterator.next().longValue();
}
blackhole.consume(sum);
return sum;
}
}
#code #java #performance