Kotlin 1.2.70 только что был выпущен. Если вы обновились до него, то, возможно, заметили новые предупреждения IntelliJ о том, что «Цепочка вызовов при сборе должна быть преобразована в« Последовательность »». Применение предложения добавляет пару дополнительных вызовов функций в цепочку вызовов. Этот дополнительный код полезен?

В анонсе релиза сказано следующее:

Использование последовательностей помогает избежать ненужных накладных расходов на временное выделение памяти и может значительно повысить производительность сложных конвейеров обработки

«Значительно повысить производительность»? Подобные утверждения вызывают у меня скепсис, когда у них нет никаких данных, подтверждающих их, так что давайте выясним, правда ли это.

Прежде чем мы углубимся, как вы думаете, какой ответ? Вы думаете, что последовательности всегда быстрее? Всегда медленнее? есть ли какой-то размер списка или количество связанных операций, с которых вы должны начать использовать последовательности? Давайте разберемся.

Что такое последовательности?

Если вы уже знакомы с расширениями коллекций и последовательностями Kotlin, не стесняйтесь переходить к следующему разделу.

Стандартная библиотека Kotlin включает в себя набор полезных функций расширения, которые вы можете использовать для преобразования коллекций в функциональном стиле. Каждый раз, когда вы вызываете расширение коллекции, оно немедленно проходит по всей коллекции. Такие операции, как filter и map, создают новый список при каждом запуске. Если вы объедините несколько вызовов в цепочку, каждый из них создаст промежуточный список, который будет удален после следующего шага.

Последовательности были созданы, чтобы позволить вам выполнять одни и те же операции лениво, так что не нужно создавать промежуточные списки. Вместо этого создаются промежуточные итераторы, и все итераторы запускаются для каждого элемента ввода перед добавлением окончательного результата в список. Ленивые последовательности особенно полезны, если вам не нужно выводить весь список, а просто нужно найти определенный элемент.

Например, если вы используете карту, ​​а затем найти. В случае с последовательностью преобразование map нужно будет применять только к элементам до тех пор, пока не будет совпадать предикат find. Остальная часть ввода игнорируется, поскольку совпадение уже найдено. Без последовательностей весь ввод будет сопоставлен с новым списком, и find будет работать с ним.

Настройка сравнительного анализа

Я написал большой набор тестов, используя JMH. Поскольку примеры в объявлении о выпуске и Проблема с YouTrack сосредоточены на filter и map, я тоже.

Я тестировал производительность различного количества связанных операций с последовательностями и без них при различных размерах списков. Чтобы сосредоточиться на накладных расходах вызовов Sequence, ни одна из операций не изменяет список.

Например, вот как я тестировал цепочку из четырех операций без последовательности:

list.filter { true }.map { it }.filter { true }.map { it }

и с Последовательностью:

list.asSequence()
    .filter { true }.map { it }.filter { true }.map { it }
    .toList()

Чем больше «длина цепочки», тем больше пар filter и map.

Здесь вы можете найти тестовый код.

Полученные результаты

Давайте попробуем ответить на вопрос, который я задал во вступлении: существует ли какая-то длина списка или количество связанных операций, при которых последовательности выполняются быстрее или медленнее?

Вот график с количеством связанных операций по оси x, длиной списка по оси y и общим временем выполнения по оси z.

Даже если убрать все накладные расходы, точки очень близко друг к другу. Однако похоже, что последовательности действительно становятся медленнее с увеличением количества операций. Давайте увеличим список одного размера (1 миллион элементов), чтобы легче было увидеть разницу.

А вот тот же график, но с разницей между временем списка и последовательности:

Таким образом, последовательности немного быстрее при небольшом количестве операций и заметно медленнее при большом количестве операций. Это определенно не согласуется с общепринятой идеей о том, что размещение списков - дорогое удовольствие и что последовательности будут работать быстрее.

Но эти результаты относятся к максимально быстрым операциям. Что делать, если выполнение ваших map или filter функций занимает немного больше времени?

Вот график или общее время выполнения отдельных filter и map, где выполнение `map` занимает 5 мкс.

list.filter { true }.map { Thread.sleep(0, 5000); it }

В этом случае различия полностью исчезают. 5 мкс - небольшой промежуток времени, но он все же на порядки больше, чем крошечные накладные расходы от использования последовательностей или без них.

Есть один случай, когда Sequences значительно превосходят операции со списком: когда имеет значение ленивость. Если вы используете список функций first или find, то версия Sequence будет работать только до тех пор, пока не будет найден элемент. версия списка по-прежнему должна проходить по всему списку.

Вот приведенный выше график, но с first, используемым с предикатом, который соответствует после второго элемента:

list.map { Thread.sleep(0, 5000); it }.first { it > 2 }

В этом случае последовательности явно превосходят версию со списком.

Заключение

Тот факт, что Последовательности медленнее для более длинных цепочек операций, вероятно, противоречит интуиции для большинства людей. Но производительность JVM часто бывает. Современные компиляторы, и особенно JIT, в большинстве случаев чрезвычайно хороши для оптимизации кода. JVM очень быстро выделяет память, и простые встроенные функции, используемые для операций со списком, вероятно, являются хорошими целями для оптимизации. С другой стороны, реализация Sequences сравнительно сложна, поскольку для создания итераторов, которые в конечном итоге используются, необходимо несколько распределений. Вероятно, JIT с этим справляется труднее.

Но, как и на все вопросы о производительности, ответ заключается не в предположениях, а в измерении. Возможно, вы работаете на устройстве, где выделение ресурсов дороже, или JIT принимает другие решения. Единственный способ узнать, имеет ли это значение, - это измерить свой код.

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