Несколько недель назад я настраивал производительность некоторого кода, который выполнялся довольно регулярно и занимал больше времени, чем следовало, судя по сложности того, что делал. Как обычно, просто глядя, что в коде не было ничего явно, очевидно, полного и смехотворно неправильного — в конце концов, он работал правильно.
Поэтому я запустил верный старый JProfiler и посмотрел, просто чтобы выяснить, что иногда вы можете просто слишком лениться и полагаться на библиотеки, не осознавая их характеристики достаточно глубоко.
Код
Следующий фрагмент показывает соответствующий метод анализируемого кода. Окружение не очень важно, суть дела здесь:
protected List<String> getCurrentChunkList() {
List<String> all = getContext().getFullList();
List<String> result = new ArrayList<String>(chunkSize + 2);
int tempCount = 0;
for (Iterator<String> allIter = all.iterator(); allIter.hasNext()
&& tempCount < chunkSize; tempCount++) {
result.add(allIter.next());
if (tempCount == chunkSize) {
while (allIter.hasNext()) {
String current = allIter.next();
if (tCurrent.equalsIgnoreCase(result.get(result.size() - 1))) {
result.add(tCurrent);
} else {
break;
}
}
}
}
all.removeAll(result);
return result;
}
По сути, все, что это делает, — это взять часть длинного списка строк и перенести их в частичный список с некоторой привязкой к данным в конце фрагмента. После этого переданные элементы удаляются из основного списка.
Все это является частью системы пакетной обработки, которая может работать только в течение ограниченного времени. Таким образом, общий список элементов, которые все еще должны быть обработаны, постоянно хранится в объекте контекста, и определенное количество из них извлекается, основной список сокращается, и полученный фрагмент возвращается к фактической обработке при каждом запуске. Затем управление возвращается в окружающую среду, которая может назначить новый временной интервал для этого вида работы или по другому на свое усмотрение. Это будет повторяться до тех пор, пока основной список не станет пустым.
Весь список содержит около 10000 элементов, размер чанка равен 1000. Теперь это выглядит не так уж плохо, не так ли?
Первый забег
При выполнении задания обработки для упомянутых 10 000 элементов по 1000 штук весь процесс занял 490 секунд; из этого вышеупомянутого метода пришлось колоссальные 6,3% или 31 секунд! Немного долго, учитывая, что это просто вызов нескольких якобы хорошо оптимизированных операций сбора …
Но если присмотреться к этому более подробно, эти «несколько» операций — это еще несколько. С 1000 элементов на кусок, было
- 10 вызовов getCurrentChunkList
- 10 000 вызовов Iterator.hasNext
- 10 000 вызовов Iterator.next
- 10 000 вызовов ArrayList.add
- 10 новых ArrayLists
- 10 новых итераторов
- 10 вызовов ArrayList.removeAll
Не совсем минималистичный, но 31 секунда кажется чуть выше.
Проблема заключается в вызове ArrayList.removeAll — внутри ArrayList использует обычный массив в качестве внутреннего хранилища. Реализация removeAll — это просто зацикленный вызов метода remove для одного элемента. Затем команда remove будет выполнять внутреннюю итерацию массива и проверять равенство удаляемого элемента, в конце концов удаляя его из массива при его обнаружении.
Если элемент, подлежащий удалению, не находится в конце массива резервного хранилища, нужно сделать большую бухгалтерию, потому что удалить что-то из середины массива непросто — в любом случае, хороший кусок массив должен быть сдвинут, чтобы заполнить пробел.
Несмотря на то, что он использует довольно эффективную System.arraycopy в своей реализации, он все равно складывается, поскольку приведенный выше алгоритм удаляет элементы, которые он выбирает для обработки, с начала списка, что приводит к нескольким тысячам операций по смещению и изменению размера массива.
Для справки, это соответствующая часть из источника ArrayList:
public E remove(int location) {
E result;
int size = lastIndex - firstIndex;
if (0 <= location && location < size) {
if (location == size - 1) {
result = array[--lastIndex];
array[lastIndex] = null;
} else if (location == 0) {
result = array[firstIndex];
array[firstIndex++] = null;
} else {
int elementIndex = firstIndex + location;
result = array[elementIndex];
if (location < size / 2) {
System.arraycopy(array, firstIndex, array, firstIndex + 1,
location);
array[firstIndex++] = null;
} else {
System.arraycopy(array, elementIndex + 1, array, elementIndex,
size - location - 1);
array[--lastIndex] = null;
}
}
if (firstIndex == lastIndex) {
firstIndex = lastIndex = 0;
}
} else {
throw new IndexOutOfBoundsException(
// luni.0A=Index: {0}, Size: {1}
Messages.getString("luni.0A", //$NON-NLS-1
Integer.valueOf(location),
Integer.valueOf(lastIndex - firstIndex)));
}
modCount++;
return result;
}
Возможные оптимизации
Как видно из источника ArrayList.remove выше, идеальным вариантом было бы удаление элементов из конца массива, потому что это не требует какого-либо смещения элементов и копирования массива вообще. Операция удаления может быть просто сделана установкой последнего элемента на ноль и уменьшением lastIndex.
Поэтому я изменил код исходного метода на следующий:
protected List<String> getCurrentChunkList() {
List<String> all = getContext().getFullList();
List<String> result = new ArrayList<String>(chunkSize + 2);
int tempCount = 0;
for (int i = all.size() - 1; i >= 0 && tempCount < chunkSize; i--, tempCount++) {
result.add(all.remove(i));
}
return result;
}
Этот код строго удаляет из конца всего списка и добавляет каждый элемент в текущий блок результатов. Переход по этому маршруту также позволил удалить специальную тряпку в середине старого метода, даже если это не вносило ощутимых накладных расходов во время выполнения метода. Вызов removeAll полностью исчез, потому что remove уже позаботится об этом индивидуально.
Второй прогон
Теперь, с тем же набором данных, профилирование приходит к совершенно другому выводу:
- 10 вызовов getCurrentChunkList
- 10 000 вызовов ArrayList.remove
- 10 000 вызовов ArrayList.add
- 10 новых ArrayLists
В этой новой конфигурации процент общего времени выполнения для этого конкретного фрагмента кода был уменьшен до 23 мс, что составляет менее 0,005% от общего времени выполнения.
Вывод
Even though the Java Collections framework’s classes are well tested and contain lots of performance enhancing shortcuts, it is still vital to be aware of their characteristics. Even though the original method looked perfectly ok at first glance and for a few runs would not show up on the radar, the repeated execution time added up to quite a remarkable percentage of the overall process.
With just a few minor modifications — that made the code easier to understand, too, getting rid of intermediate Iterators and special handlings for edge cases — that single method’s performance was boosted significantly. Considering that it is part of a more general batch job framework, overall improvements are even greater than what this single isolated test case showed.
From http://www.danielschneller.com/2010/11/collection-performance-dont-become-too.html