Одна маленькая оптимизация

Совсем недавно со мной поделились историей одной оптимизации (привет stanislaw ^[1]), которая показалась мне довольно забавной.

Проект игровой и с постоянно растущей базой пользователей, но так как расширятся в ширь не хотелось — возникла задача оптимизировать существующий код в узких местах. После недолгого профайлинга, буквально сразу, удалось найти одно такое узкое место, которое на первый взгляд не вызвало бы ни у кого подозрений:

for (A a : arrayListA) { 
    // do something
    for (B b : arrayListB) {
        // do something
        for (C c : arrayListC) {
            // do something
        }
    }
}

Доступа к коду у меня нету, поэтому я передаю лишь суть повествования. Есть некий метод просчета ситуации на карте, в котором происходит много итераций по разного рода циклам. При чем, граф объектов уже создан и изменяется лишь его состояние. То есть новых объектов фактически не создается… Но тем не менее профайлер показывал приблизительно такую картину:

И при частых вызовах метода сборка занимала довольно большую часть времени работы метода.

Проблема оказалась в for циклах. Как известно, компилятор преобразовывает for цикл для коллекций в следующий код:

for (Iterator<A> i = arrayListA.iterator(); i.hasNext();) {
    a = i.next();
}

//смотрим во внутрь метода iterator() ArrayList
public Iterator<E> iterator() {
    return new Itr();
}

//и сам класс итератора. поля которые потребляют память
private class Itr implements Iterator<E> {
	int cursor = 0;
	int lastRet = -1;
	int expectedModCount = modCount;
}

Все бы хорошо, но если у вас несколько вложенных циклов, при чем короткие циклы на самом нижнем уровне вложения, то получается, что просто один лишь проход по циклам создаст тысячи объектов, а если метод постоянно вызывается, то еще и постоянные срабатывания сборщика.
Например, для первого примера — в случае если arrayListA.size() == 1000, arrayListB.size() == 100, arrayListC.size() == 10 за один проход по циклам будет создано около 100 тыс. объектов итераторов…

Решение тут довольно очевидно — получать доступ по индексу:

for (int i = 0; i < arrayListA.size(); i++) {
    A a = arrayListA.get(i);
}

Такое вот маленькое изменение кода в данном конкретном случае позволило увеличить скорость работы горячего метода в 2 раза.
Стоит отметить, что такого рода оптимизация возможна в основном в случае ArrayList.

Будьте внимательны и с прошедшим Вас Новым годом!

Автор: doom369

Источник ^[2]