В Java есть два основных способа обхода коллекций: простой цикл for и цикл for-each, появившийся в JDK 5. Задумывались ли вы когда-нибудь об их разнице с точки зрения производительности?
Реализация for-each
Цикл for-each — это синтаксический сахар. Компилятор преобразует for-each в вызов итератора. Давайте рассмотрим следующий пример:
public class TestForeach {
List<Integer> integers;
public void testForeach(){
for(Integer i : integers){
}
}
}Скомпилируем и посмотрим на байткод с помощью команды javap -verbose Testforeach.
public void testForeach();
descriptor: ()V
flags: ACC_PUBLIC
Code:
stack=1, locals=3, args_size=1
0: aload_0
1: getfield #2 // Field integers:Ljava/util/List;
4: invokeinterface #3, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
9: astore_1
10: aload_1
11: invokeinterface #4, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z
16: ifeq 32
19: aload_1
20: invokeinterface #5, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
25: checkcast #6 // class java/lang/Integer
28: astore_2
29: goto 10
32: return
LineNumberTable:
line 11: 0
line 13: 29
line 14: 32
LocalVariableTable:
Start Length Slot Name Signature
29 0 2 i Ljava/lang/Integer;
0 33 0 this Ltest/TestForeach;
}Общий смысл этого байткода заключается в использовании команды getfield для получения переменной integers и вызова List.iterator для получения экземпляра итератора, у которого вызывается метод hasNext. Если hasNext возвращает true, то вызывается метод Iterator.next.
Тест производительности
Теперь давайте сравним производительность циклов for и for-each.
public class ForLoopTest {
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000000; i++) {
arrayList.add(i);
}
long arrayListStartTime = System.currentTimeMillis();
for (int i = 0; i < arrayList.size(); i++) {
arrayList.get(i);
}
long arrayListCost =System.currentTimeMillis()-arrayListStartTime;
System.out.println("ArrayList for loop traversal cost: "+ arrayListCost);
long arrayListForeachStartTime = System.currentTimeMillis();
for (Integer integer : arrayList) {
}
long arrayListForeachCost =System.currentTimeMillis()-arrayListForeachStartTime;
System.out.println("ArrayList foreach traversal cost: "+ arrayListForeachCost);Результаты приведены в таблице ниже.
Наверняка вы видите вполне ожидаемые результаты. Для ArrayList производительность for лучше, чем for-each. Можно ли объявить for победителем? Нет. Давайте заменим ArrayList на LinkedList и повторим эксперимент.
Результаты будут несколько другими.
Анализ результатов
Почему цикл for работает с ArrayList быстрее, чем с LinkedList? Все дело во внутреннем устройстве ArrayList и LinkedList.
В ArrayList элементы хранятся в массиве. Массив представляет собой непрерывную область памяти с доступом к элементам по индексу. Временная сложность — O(1).
LinkedList представляет собой двусвязный список. Получение элемента по индексу на каждой итерации for происходит путем обхода списка с головы. Временная сложность — O(n*n).
Заключение
ArrayList работает быстрее с циклом for, потому что в for-each используется итератор, выполняющий проверку конкурентных модификаций.
При использовании LinkedList цикл for-each выполняется намного быстрее for, поскольку LinkedList реализован с использованием двусвязного списка. Поиск элемента на каждой итерации начинается с головы списка. При использовании LinkedList лучше избегать использования цикла for.
Используя паттерн "итератор", циклу for-each не нужно заботиться о конкретной реализации коллекции. При необходимости можно легко изменить реализацию коллекции без модификации кода.
Совсем скоро состоится открытый урок, на котором начинающие java разработчики смогут усвоить основы ООП в java. На этом уроке поговорим о конструкторах, создании объектов, состоянии объектов, полях класса, методах, поведении объектов, интерфейсах, контракте взаимодействия. Регистрация доступна по ссылке.
Комментарии (10)
panteleymonov
05.12.2022 19:01ArrayList for-each 4
LinkedList for-each 1
Ощущение что тест некорректный или криво проводился. Сама по себе последовательная скорость прохода по ArrayList должна выигрывать. Неужели в ArrayList итератор так криво реализован что работает медленнее чем дополнительное обращение к памяти в LinkedList?
Вообще я не вижу этого самого уникального особого for-each, есть for где используется get - который медленно работает у LinkedList, и есть тот же for с итераторами (хоть с it.next(), хоть без него - как вы сами написали for-each это всего лишь синтаксический сахар). В результате вы сравниваете разные операторы доступа к элементам массива. Какая-то мода пошла выдумывать несуществующее из воздуха.
Возможно вы живете в мире где for-each и for является уникальными функциями, не происходящими одно из другого, и вам хотелось разоблачить этот миф - получилось не очень.
Alexufo
05.12.2022 19:24+1А почему эти числодробилки еще не замерены какой нибудь IDE для подствечивания статическим анализатором? Типа бро - у тебя такая коллекция, давай лучше через другой цикл?
panteleymonov
05.12.2022 20:07А что автогенераторы кода уже больше не развиваются?
давай лучше через другой цикл?
Есть две формы записи одного и того же
for (Thing thing : list) и for (Iterator<Thing> it = list.iterator(); it.hasNext(); Thing thing = it.next())Никакого другого цикла нет.
VGoudkov
05.12.2022 20:17+10В этом посте прекрасно примерно всё:
Код не компилируется – в примере забыли закрывающие фигурные скобки
Проверять такие штуки на однократном прогоне (пусть и при нескольких запусках программы – так себе идея. Потому что есть jit, и на 100К или 100М выполнений блока кода (что как бы ожидаемый сценарий для back) – результаты могут быть совсем не такими
Результат операций внутри цикла никак не используется, чего не будет в реальной жизни. Так что нужно хотя бы суммировать эти дурацкие числа и выводить результат. Не уверен, но КМК jit может такие циклы упрощать до «пройти мимо».
Хорошо бы прогнать код под профайлером, а результат выложить как КДПВ :)
Миллисекундной точности для таких упражнений – недостаточно, наш выбор System.nanoTime()
Итого:
Разница столь невелика, что на фоне остальных затрат времени в приложении совершенно всё равно как итерироваться. Выбирайте цикл, который более читаем исходя из решаемой задачи, и не забывайте, что IDEA умеет менять тип цикла по Alt+Enter на ключевом словеforКод с доработками:
@SuppressWarnings("java:S106") //можно печатать на консоль public class ForLoopTest { public static void main(String[] args) { List<Integer> arrayList = new ArrayList<>(); for (int i = 0; i < 10_000_000; i++) { arrayList.add(i); } System.out.println("Elements: " + arrayList.size()); for (int iter = 0; iter < 100; iter++) { System.out.println("===== Iteration #" + iter); long sum; long arrayListForeachStartTime = 0; sum = 0; long arrayListStartTime = System.currentTimeMillis(); for (int i = 0; i < arrayList.size(); i++) { sum += arrayList.get(i); } long arrayListCost = System.currentTimeMillis() - arrayListStartTime; System.out.println("ArrayList for loop traversal cost: " + arrayListCost + ", sum: " + sum); sum = 0; arrayListForeachStartTime = System.currentTimeMillis(); for (Integer integer : arrayList) { sum += integer; } long arrayListForeachCost = System.currentTimeMillis() - arrayListForeachStartTime; System.out.println("ArrayList foreach traversal cost: " + arrayListForeachCost + ", sum: " + sum); } } }Результаты:
Elements: 10000 ===== Iteration #0 ArrayList for loop traversal cost: 2, sum: 49995000 ArrayList foreach traversal cost: 1, sum: 49995000 ===== Iteration #99 ArrayList for loop traversal cost: 0, sum: 49995000 ArrayList foreach traversal cost: 0, sum: 49995000 Elements: 10000000 ===== Iteration #0 ArrayList for loop traversal cost: 21, sum: 49999995000000 ArrayList foreach traversal cost: 25, sum: 49999995000000 *** ===== Iteration #99 ArrayList for loop traversal cost: 17, sum: 49999995000000 ArrayList foreach traversal cost: 16, sum: 49999995000000PS: Пользуясь случаем, передаю отдельный привет разработчикам редактора для комментариев. Это такой специальный способ усложнить аффтару жизнь?
panteleymonov
05.12.2022 21:10-1Разница столь невелика, что на фоне остальных затрат времени в приложении совершенно всё равно как итерироваться. Выбирайте цикл, который более читаем исходя из решаемой задачи
Я бы тут заметил, что использование итераторов предпочтительнее, поскольку считается что умножение дороже сложения, поэтому использование get на отдельных платформах может влететь в копеечку.
ermadmi78
05.12.2022 21:07+6В заголовке статьи обещают сравнить производительность циклов for или for-each а в тексте по факту сравнивают производительность доступа к элементу списка по индексу в разных реализациях списка... Выглядит это мягко говоря странно.
mosinnik
05.12.2022 23:07+3Статья про производительность языковых конструкций без тестов на JMH, да еще и десятая статья за день - у OTUS-а походу план на шлако-статьи
Maccimo
06.12.2022 10:02+2Совсем скоро состоится открытый урок, на котором начинающие java разработчики смогут усвоить основы ООП в java.
Я бы посоветовал начинающим жаба-разработчикам держаться подальше от конторы, показывающей полное непонимание предмета.
harios
Очень странно получилось. В заголовке мы сравниваем циклы, а в заключении мы сравниваем циклы + реализацию какой то конретной коллелкции. Пойэтому какой цикл быстрее, однозначно for. Какой следует использовать для коллекции, зависит от коллекции.