Введение
Я лид команды системных сервисов в SberDevices и провожу довольно много технических интервью по Android (более 100 в год). По опыту проведения собеседований я вижу, что абсолютное большинство разработчиков боятся использовать sequences в работе, потому что не понимают как они работают. А самое главное, не понимают в каких случаях sequences дают выигрыш, а в каких проигрыш.
В сети нигде нет четкой информации об этом (по крайней мере я не нашел). Везде приводятся только общие фразы, без описания конкретных кейсов и цифр. При этом есть довольно спорное правило detect, которое гласит
CouldBeSequence: Используйте sequences, если в вашем преобразовании коллекции больше 3 функций преобразований
Так как я достаточно хорошо знаю внутренний код kotlin, то понимаю что это правило не совсем корректно. Мне захотелось исправить этот пробел и я решил провести небольшое исследование производительности sequences. Понять, когда использование sequences дает нам выигрыш, а когда проигрыш. Мне захотелось подойти к этому с математической и инженерной точки зрения и получить конкретные цифры и кейсы.
Результаты исследования
Для тех, кто любит сразу получать ответы, привожу итоговые результаты своего исследования в заголовке статьи.
Проигрыш
Функции sequences, использование которых даст вам гарантированный проигрыш. Все эти функции тяжелые, поэтому неважно сколько функций преобразований у вас используется. Если среди них есть хотя бы одна из этих функций, вы гарантированно получите проигрыш.
sort | Тяжелая операция с копированием данных и огромный проигрыш |
flatten | Тяжелая операция и значительный проигрыш |
plus | Значительный проигрыш, так как сделана на базе flatten |
Небольшой проигрыш
Функции sequences, использование которых может давать небольшой проигрыш, но он может быть нивелирован добавлением других функций преобразования.
distinct | Дает небольшой проигрыш, который будет нивелирован в версии kotlin 2.0 Оффтопик, про улучшение производительности distinct в kotlin 2.0 будет отдельная статья |
chunked | Легкая операция, которая дает незначительный проигрыш |
Выигрыш
Все остальные функции sequences, действительно дадут выигрыш начиная уже с двух преобразований коллекции.
Выводы
Правило detect CouldBeSequence будет корректным, если в вашем преобразовании не используется одна из тяжелых функций: sort, flatten, plus
Я представил свое исследование производительности sequences на Мобиус 2023 и те, кому больше нравится смотреть видео, могут посмотреть запись моего доклада Mobius spring 2023, доклад "Измеряя sequences"
Те же, кто любит почитать и кому интересно как работают sequences под капотом, добро пожаловать в удивительный мир sequences. Дальше будет много кода и таблиц с результатами измерений.
Теория
Для того, чтобы разобраться какой профит мы можем получить от использования sequences, давайте сначала разберемся с теорией.
Как работает преобразование обычных коллекций
Каждое преобразование выполняется в отдельном цикле
На каждое преобразование создается копия исходной коллекции
Соответственно каждое наше преобразование - это выделение новой памяти и копирование исходного массива в отдельном цикле, что в теории выглядит не очень оптимальным.
Как работает преобразование sequences
Все преобразования выполняются за один проход цикла
Нет выделения дополнительной памяти для хранения промежуточных результатов
Таким образом, теоретически, кажется, что в случае использования преобразования через sequences мы избегаем всех негативных моментов, которые есть у обычных преобразований коллекций. Кажется, что sequences должны давать нам ощутимый прирост в производительности.
Так ли это и нет ли тут подводных камней и скрытых нюансов, давайте разбираться.
Что такое sequences
Про sequences часто говорят, что это ленивые коллекции, но это не совсем правильно.
Когда мы работаем с коллекцией, то мы работаем с набором данных. У набора данных есть начало и конец. Мы можем перемещаться по набору данных вперед и назад. Мы знаем про количество элементов в наборе данных.
Когда мы работаем с sequences, то мы работаем не с набором, а с последовательностью элементов. У нас нет информации о количестве элементов, мы не можем перемещаться по последовательности. Мы не знаем когда она началась и когда она закончится. По сути у нас всегда есть только текущий элемент.
Sequence
Sequences - это обычный интерфейс обертка над итератором и ничего более.
public interface Sequence<out T> {
public operator fun iterator(): Iterator<T>
}Когда мы используем функцию asSequence(), мы просто создаем анонимный класс реализующий интерфейс sequences, который скрывает в себе исходный итератор нашей коллекции или источника данных.
public fun <T> Iterable<T>.asSequence(): Sequence<T> {
return Sequence { this.iterator() }
}И дальше мы работаем с sequences используя только его итератор. Все что у нас есть, это значение текущего элемента и возможность перейти на следующий элемент.
Итератор
Вы можете назвать меня "Капитан очевидность", но давайте вспомним как устроен итератор. В мире sequences все построено на итераторах, поэтому важно понимать принципы его работы.
public interface Iterator<out T> {
public operator fun next(): T
public operator fun hasNext(): Boolean
}У итератора есть всего два метода
hasNext() - возвращает true если у нас есть следующий элемент
next() - переходит на следующий элемент и возвращает его значение
Таким образом мы всегда работаем с итератором в цикле и на каждой итерации цикла мы всегда вызываем связку методов hasNext() + next()
while (iterator.hasNext()) {
val value = iterator.next()
}Когда мы используем преобразование коллекции через sequences, то для каждой нашей функции преобразования под капотом создается декоратор над итератором исходной коллекции.
Давайте рассмотрим это на примере вот такого преобразования коллекции
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.map { it + 3 }
.toList()В этом случае под капотом оно развернется в следующую конструкцию.
val resultIterator =
MapIterator( { it + 3 },
MapIterator( { it + 2 },
MapIterator( { it + 1},
sourceCollection.iterator()
)
)
)
val result = mutableListOf<Int>()
resultIterator.forEach { result.add(it) }Все наши функции преобразования превратились в декораторы и заворачиваются друг в друга как матрешки, давая нам на выходе один результирующий итератор. В итоге нам остается лишь пробежаться один раз по результирующему итератору и мы получим на выходе преобразованную коллекцию.
При этом для каждого элемента результирующего итератора, последовательно выполнятся все наши функции преобразования. По сути, принцип вызова наших преобразований через декораторы очень хорошо демонстрирует следующий псевдокод.
Данный пример демонстрирует наше преобразование одного элемента исходной коллекции со значением равным 10 => 10 + 1 + 2 + 3 => 16.
resultIterator.next() => 16
| 16
mapIterator(it + 3).next() + 3 => 13 + 3 = 16
| 13
mapIterator(it + 2).next() + 2 => 11 + 2 = 13
| 11
mapIterator(it + 1).next() + 1 => 10 + 1 = 11
| 10
sourceIterator().next() => 10Ну вот, надеюсь с теорией мы разобрались, теперь давайте переходить к измерениям и смотреть под капот.
Методика измерения
Я использовал для замеров Jetpack Benchmark. Все измерения производились на рутованном устройстве на фиксированной тактовой частоте. Каждый тестовый прогон выполнял тестируемую функцию примерно 50 раз. Для каждой функции я производил 100 тестовых прогонов и брал медианный результат по минимумам.
Оффтопик, про нюансы использования Jetpack Benchmark будет отдельная статья.
Чтобы понять, в каких случаях sequence выигрывает у обычных коллекций, нам необходимо сравнить обычную функцию преобразования коллекции с функцией sequences. Но мы не можем сравнивать их напрямую, потому что в случае sequences мы начинаем получать выигрыш от исключения копирования промежуточных результатов только начиная со второго преобразования.
Поэтому я выработал следующую методику. Я принял за единицу тест сравнения двух преобразований через функцию map, который дает нам равновесное состояние. Никто не выигрывает и не проигрывает. А дальше я просто заменял второе преобразование map на тестируемую функцию.
В целом такой подход дал адекватные и повторяемые результаты, которые хорошо согласуются с теоретическими выкладками.
Важно понимать, что абсолютные цифры будут актуальны только для моего устройства. На других устройствах мы можем получить другие цифры, но их соотношение в процентах будет близким.
Измерение map
benchmarkRule.measureRepeated {
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.toList()
}Результаты измерений - 2 map
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 41 333 | 42 186 | -2% |
1 000 | 532 771 | 529 219 | 1% |
10 000 | 5 726 766 | 5 603 207 | 2% |
50 000 | 28 594 531 | 27 336 781 | 4% |
100 000 | 57 318 875 | 54 838 584 | 4% |
Как видите в этом тесте никто не проигрывает и не выигрывает. С ростом числа элементов у sequences наблюдается небольшой выигрыш, но он укладывается в размер статистической погрешности.
Теперь давайте попробуем добавить еще одно преобразование, чтобы оценить как это повлияет на результаты. В теории, каждое дополнительное преобразование должно давать нам прирост в производительности.
benchmarkRule.measureRepeated {
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.map { it + 3 }
.toList()
}Результаты измерений - 3 map
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 62 094 | 52 029 | 16% |
1 000 | 796 137 | 682 835 | 14% |
10 000 | 8 625 083 | 7 072 713 | 18% |
50 000 | 42 868 792 | 34 840 396 | 19% |
100 000 | 86 425 959 | 69 078 709 | 20% |
Как видите результаты хорошо согласуются с теорией. Мы сразу получили ощутимый выигрыш 15-20% при добавлении дополнительного преобразования.
Давайте проверим, как будет расти производительность, если добавить еще преобразований.
benchmarkRule.measureRepeated {
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.map { it + 3 }
.map { it + 4 }
.map { it + 5 }
.toList()
}Результаты измерений - 5 map
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 102 256 | 69 116 | 32% |
1 000 | 1 327 987 | 968 823 | 27% |
10 000 | 14 172 953 | 9 975 721 | 30% |
50 000 | 71 466 459 | 49 866 708 | 30% |
100 000 | 144 102 292 | 98 161 854 | 32% |
Наш выигрыш еще немного вырос и составляет уже внушительные 27-30%
Теперь давайте разберемся с магией. Посмотрим как же устроен sequences декоратор для функции map под капотом. Кому интересно, раскрывайте вложенный элемент.
Как устроен sequences декоратор для функции map
Как устроен sequences декоратор для функции map
Декоратор для map устроен предельно просто. На входе в него передается параметр sequence, который содержит исходный итератор, который мы декорируем и функция трансформации transformer. Собственно это та самая лямбда { it + 1 }, которая выполняется внутри map.
Исходный итератор, который мы декорируем берется из параметра sequence и запоминается во внутренней переменной iterator
constructor(private val sequence: Sequence<T>,
private val transformer: (T) -> R) : Sequence<R>
{
override fun iterator(): Iterator<R> = object : Iterator<R> {
val iterator = sequence.iterator()
override fun next(): R {
return transformer(iterator.next())
}
override fun hasNext(): Boolean {
return iterator.hasNext()
}
}
}На каждый вызов метода next() происходит вызов исходного итератора iterator.next() и полученное из него значение прогоняется через функцию трансформации transformer (нашу лямбду)
override fun next(): R {
return transformer(iterator.next())
}Таким образом при каждом вызове next() мы на выходе получим преобразованный элемент исходной последовательности.
Измерение sort
sourceCollection.asSequence()
.map { it + 1 }
.sortedByDescending { it }
.toList()Результаты измерений - sort
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 149 580 | 180 167 | -20% |
1 000 | 3 214 330 | 3 563 508 | -11% |
10 000 | 45 126 896 | 49 879 000 | -11% |
50 000 | 289 200 750 | 315 998 501 | -9% |
100 000 | 662 256 355 | 711 287 875 | -7% |
Как видите, с сортировкой у sequences все плохо. Проигрыш порядка ‑10%.
Но что здесь важно понимать: этот небольшой проигрыш в процентах на самом деле огромный, потому что сортировка очень тяжелая операция.
Это отчетливо видно, если сравнить время выполнения сортировки и функции map. Разница по времени отличается на порядок!
Функция | Время выполнения (ns) |
map | 54 838 584 |
sort | 711 287 875 |
То есть вы не сможете нивелировать проигрыш от функции sort добавлением дополнительных преобразований. Эффект от их общего профита будет намного меньше, чем проигрыш от функции sort.
Кому интересно, как sort работает под капотом, раскрывайте вложенный элемент.
Устройство декоратора функции sort
Функция sort, пожалуй, единственная функция в sequences, которая пытается нас обмануть. Она "как бы ленивая" и результаты этого обмана вы уже видели в цифрах.
Эта функция берет и сохраняет текущую последовательность в промежуточную коллекцию. Дальше эта коллекция сортируется стандартным методом коллекции и затем декоратор оборачивается уже вокруг этой промежуточной, отсортированной коллекции.
public fun <T> Sequence<T>.sortedWith(comparator: Comparator<in T>): Sequence<T> {
return object : Sequence<T> {
override fun iterator(): Iterator<T> {
val sortedList = this@sortedWith.toMutableList()
sortedList.sortWith(comparator)
return sortedList.iterator()
}
}
}Чтобы было понятней, давайте рассмотрим это на следующем примере.
sequenceOf(5, 4, 3, 2, 1)
.map { it + 1 }
.filter { it % 2 == 0 }
.sortedBy { it } // сортировка в середине преобразования
.map { it - 1 }
.map { it + 1 }Если наша функция sort встречается где то в середине преобразований, то сначала будут лениво выполняться все преобразования, которые идут до сортировки.
Затем произойдет копирование коллекции и ее сортировка.
И дальше все последующие функции преобразования снова будут выполнятся лениво, но уже по новой копии исходной и отсортированной коллекции.
То есть наше преобразование превратится (в тыкву) примерно в вот такой код
// Сохраняем преобразования, идущие до sort
// в промежуточный список
val list = sequenceOf(5, 4, 3, 2, 1)
.map { it + 1 }
.filter { it % 2 == 0 }
.toList()
// Сортируем промежуточную коллекцию методом коллекции
// и создаем на ее основе новый sequence
val newSequences = list.sortedBy { it }.asSequence()
// Продолжаем ленивые преобразования идущие после sort
// Но уже на новой посследовательности
val resultSort = newSequences
.map { it - 1 }
.map { it + 1 }Фокус, конечно, интересный, но результаты измерений отлично показывают, что это только фокус.
Измерение filter
Во время своего исследования я столкнулся с эффектом, когда некоторые функции sequences в сложных преобразованиях показывали разную производительность. Первое время я не мог понять и объяснить этот эффект. Но потом мне удалось установить четкую закономерность и чуть дальше я объясню природу ее появления.
Эту закономерность имеют все функции sequences, которые изменяют количество элементов в исходном наборе: filter, distinct, take, drop, minus.
лучший кейс - Чем меньше элементов исходной коллекции возвращает функция, тем больший выигрыш вы получаете по сравнению с коллекциями.
худший кейс - Если функция возвращает большую часть исходного набора, то выигрыш будет уменьшаться и стремиться к 0.
Поэтому для таких функций я буду приводить два теста на лучший и худший кейс. За лучший я принял возврат 10% исходного набора элементов. За худший 90% исходного набора элементов.
Лучший кейс
sourceCollection.asSequence()
.map { it + 1 }
.filter { it in 0..precent_10 }
.toList()Результаты измерений filter - оставляет 10% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 33 045 | 24 060 | 27% |
1 000 | 394 953 | 292 209 | 26% |
10 000 | 4 185 852 | 2 985 708 | 29% |
50 000 | 20 955 136 | 15 083 892 | 28% |
100 000 | 41 977 667 | 31 003 865 | 26% |
Как видите, в лучшем кейсе filter дает выигрыш примерно в 25%-30%.
Худший кейс
sourceCollection.asSequence()
.map { it + 1 }
.filter { it in 0..precent_90 }
.toList()Результаты измерений filter - оставляет 90% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 42 828 | 43 557 | -2% |
1 000 | 488 092 | 479 876 | 2% |
10 000 | 5 014 653 | 4 862 738 | 3% |
50 000 | 25 080 389 | 24 081 423 | 4% |
100 000 | 50 261 272 | 48 016 813 | 4% |
А вот в худшем кейсе наш выигрыш стремится к нулю и составляет 2%-4%
Кому интересно, как устроен декоратор sequences для функции filter, раскрывайте свернутый элемент. Наградой вам будет объяснение, откуда возникает зависимость производительности от количества возвращаемых элементов.
Заглянуть под капот filter
Устройство декоратора функции filter
Давайте попробуем разобраться в коде декоратора filter. Он содержит довольно много кода, поэтому давайте разбирать код по частям.
На вход декоратору передается параметр sequence, из которого он берет исходный итератор iterator и параметр predicate, который определяет условие фильтра (по сути наша лямбда)
internal class FilteringSequence<T>(
private val sequence: Sequence<T>,
private val sendWhen: Boolean = true,
private val predicate: (T) -> Boolean
) : Sequence<T> {
override fun iterator(): Iterator<T> = object : Iterator<T> {
val iterator = sequence.iterator()
// -1 for unknown, 0 for done, 1 for continue
var nextState: Int = -1
var nextItem: T? = nullВся соль скрыта в реализации метода hasNext(). При вызове этого метода, декоратор вызывает внутреннюю функцию calcNext(), которая вычисляет следующий элемент.
override fun hasNext(): Boolean {
if (nextState == -1)
calcNext()
return nextState == 1
}По сути он просто бежит вперед по исходному итератору iterator и ищет первый элемент, который удовлетворяет условию нашей лямбды, заданной в predicate. Если удалось найти следующий, удовлетворяющий фильтру элемент, то он запоминается в переменной nextItem
private fun calcNext() {
while (iterator.hasNext()) {
val item = iterator.next()
if (predicate(item) == sendWhen) {
nextItem = item
nextState = 1
return
}
}
nextState = 0
}И когда у декоратора вызывается метод next(), он сразу возвращает уже ранее найденный следующий элемент nextItem
override fun next(): T {
if (nextState == -1)
calcNext()
if (nextState == 0)
throw NoSuchElementException()
val result = nextItem
nextItem = null
nextState = -1
return result as T
}Полный исходный код декоратора filter
internal class FilteringSequence<T>(
private val sequence: Sequence<T>,
private val sendWhen: Boolean = true,
private val predicate: (T) -> Boolean
) : Sequence<T> {
override fun iterator(): Iterator<T> = object : Iterator<T> {
val iterator = sequence.iterator()
// -1 for unknown, 0 for done, 1 for continue
var nextState: Int = -1
var nextItem: T? = null
override fun hasNext(): Boolean {
if (nextState == -1)
calcNext()
return nextState == 1
}
private fun calcNext() {
while (iterator.hasNext()) {
val item = iterator.next()
if (predicate(item) == sendWhen) {
nextItem = item
nextState = 1
return
}
}
nextState = 0
}
override fun next(): T {
if (nextState == -1)
calcNext()
if (nextState == 0)
throw NoSuchElementException()
val result = nextItem
nextItem = null
nextState = -1
return result as T
}
}
}Как видите, все достаточно просто. Мы всегда работаем с итератором путем вызова пары методов hasNext() + next().
Таким образом, на вызов hasNext() функция фильтра бежит вперед и ищет следующий подходящий элемент. При этом все не подходящие под условие фильтра элементы будут пропущены.
А на вызов next() возвращается уже готовый, ранее найденный следующий элемент.
Объяснение закономерности, связанной с числом возвращаемых элементов
Так откуда же берется зависимость производительности функции от числа возвращаемых элементов?
Все очень просто. Когда мы ищем следующий элемент внутри метода calcNext(), то мы в цикле перебираем элементы исходного итератора и проверяем их на условие фильтра.
И пока элементы не удовлетворяют условию предиката, мы не имеем никаких дополнительных затрат по сравнению с коллекциями. Мы просто берем следующий элемент, вызываем лямбду и все.
private fun calcNext() {
while (iterator.hasNext()) {
val item = iterator.next()
if (predicate(item) == sendWhen) {
nextItem = item
nextState = 1
return
}
}
nextState = 0
}Но как только у нас появляется элемент, который удовлетворяет нашему условию фильтра, то у нас сразу возникает большое количество дополнительных операций чтения/записи, чтобы обработать и вернуть этот элемент.
Я пометил такие операции звездочками в коде, вы можете сами оценить их объем.
override fun iterator(): Iterator<T> = object : Iterator<T> {
val iterator = sequence.iterator()
// -1 for unknown, 0 for done, 1 for continue
var nextState: Int = -1
var nextItem: T? = null
private fun calcNext() {
while (iterator.hasNext()) {
val item = iterator.next()
if (predicate(item) == sendWhen) {
* nextItem = item
* nextState = 1
return
}
}
nextState = 0
}
override fun next(): T {
* if (nextState == -1)
calcNext()
* if (nextState == 0)
throw NoSuchElementException()
* val result = nextItem
* nextItem = null
* nextState = -1
return result as T
}
override fun hasNext(): Boolean {
if (nextState == -1)
calcNext()
return nextState == 1
}
}Собственно, эти дополнительные затраты на возврат каждого элемента и съедают почти весь наш выигрыш от исключения промежуточного копирования коллекции в случае худшего кейса, когда мы возвращаем большую часть коллекции.
И эти дополнительные затраты на возврат каждого элемента есть практически у всех подобных функций sequences: filter, distinct, take, drop, minus, groupBy
Измерение distinct
Оставляет в последовательности только уникальные элементы
Лучший кейс
sourceCollection.asSequence()
.map { it * 10 / 100 }
.distinctBy { it }
.toList()Результаты измерений distinct - оставляет 10% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 53 566 | 44 832 | 16% |
1 000 | 538 987 | 451 603 | 16% |
10 000 | 7 646 898 | 6 617 495 | 13% |
50 000 | 43 246 521 | 39 631 886 | 8% |
100 000 | 95 196 333 | 87 074 083 | 9% |
Как видите в лучшем кейсе distinct выигрывает у коллекций. Выигрыш 10%-15%
Худший кейс
sourceCollection.asSequence()
.map { it * 90 / 100 }
.distinctBy { it }
.toList()Результаты измерений distinct - оставляет 90% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 83 113 | 100 762 | -21% |
1 000 | 1 005 813 | 1 169 785 | -16% |
10 000 | 10 851 783 | 12 856 475 | -18% |
50 000 | 60 652 896 | 69 893 855 | -15% |
100 000 | 129 569 604 | 146 594 000 | -13% |
А вот в худшем случае distinct значительно проигрывает коллекциям, проигрыш -15%
Оффтопик: На самом деле все не так печально и в следующей версии kotlin 2.0 эту проблему уже устранили. Об этом у меня будет отдельная статья.
Как же устроен декоратор distinct?
Кому интересно, открывайте капот
Устройство декоратора функции distinct
На самом деле декоратор distinct работает почти также, как и filter.
Большая часть кода, который обслуживает возврат элемента и сами методы hasNext(), next() скрыты в общей абстрактной реализации в классе AbstractIterator. Тут виден задел kotlin на будущее)
Вся соль вынесена во внутреннюю функцию computeNext(), которая вычисляет следующий уникальный элемент (по сути полная аналогия с функцией фильтра calcNext()).
private class DistinctIterator<T, K>(
private val source: Iterator<T>,
private val keySelector: (T) -> K
) : AbstractIterator<T>() {
private val observed = HashSet<K>()
override fun computeNext() {
while (source.hasNext()) {
val next = source.next()
val key = keySelector(next)
if (observed.add(key)) {
setNext(next)
return
}
}
done()
}
}При каждом вызове hasNext() вызывается функция computeNext(), которая в цикле бежит по исходному итератору source и пытается каждый элемент исходного итератора добавить во внутренний HashSet observed.
Если элемента еще нет в observed, то он добавляется и возвращается как следующий уникальный элемент. Если элемент уже есть в observed, то значит он уже ранее возвращался и будет пропущен.
Измерение take
Берет первые N элементов последовательности.
Лучший кейс
sourceCollection.asSequence()
.map { it + 1 }
.take { countPercent_10 }
.toList()Результаты измерений take - берет 10% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 23 016 | 3 999 | 83% |
1 000 | 275 794 | 38 106 | 86% |
10 000 | 2 954 285 | 381 353 | 87% |
50 000 | 14 981 667 | 1 969 455 | 87% |
100 000 | 29 886 927 | 3 977 857 | 87% |
Как видите здесь разгром коллекций, выигрыш почти 90%
Худший кейс
sourceCollection.asSequence()
.map { it + 1 }
.take { countPercent_90 }
.toList()Результаты измерений take - берет 90% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 36 368 | 29 986 | 18% |
1 000 | 421 734 | 342 892 | 19% |
10 000 | 4 504 151 | 3 456 383 | 23% |
50 000 | 22 658 014 | 17 092 458 | 25% |
100 000 | 45 291 084 | 34 242 125 | 24% |
В худшем кейсе take также имеет значительный выигрыш 20%-25%, но он в 3 раза меньше лучшего кейса
устройство декоратора для take
Устройство декоратора функции take
Это предельно простой декоратор и он работает следующим образом.
Есть переменная left, в которой считается сколько записей осталось вернуть декоратору. Изначально она равна количеству, которое мы задаем вызывая функцию take
В методе hasNext() мы просто проверяем, что left > 0
В методе next() мы возвращаем элемент из исходного итератора iterator и уменьшаем счетчик left
override fun iterator(): Iterator<T> = object : Iterator<T> {
var left = count
val iterator = sequence.iterator()
override fun next(): T {
if (left == 0)
throw NoSuchElementException()
left--
return iterator.next()
}
override fun hasNext(): Boolean {
return left > 0 && iterator.hasNext()
}
}Измерение drop
Пропускает первые N элементов последовательности.
Лучший кейс
sourceCollection.asSequence()
.map { it + 1 }
.drop { countPercent_90 }
.toList()Результаты измерений drop - удаляет 90% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 23 993 | 19 886 | 17% |
1 000 | 282 420 | 191 700 | 32% |
10 000 | 3 052 168 | 2 032 454 | 33% |
50 000 | 15 293 025 | 9 922 920 | 35% |
100 000 | 30 413 583 | 19 863 292 | 35% |
Функция drop выигрывает у коллекций в лучшем кейсе, выигрыш 30%-35%
Худший кейс
sourceCollection.asSequence()
.map { it + 1 }
.drop { countPercent_10 }
.toList()Результаты измерений drop - удаляет 10% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 33 701 | 31 629 | 6% |
1 000 | 385 249 | 361 036 | 6% |
10 000 | 4 232 115 | 3 681 223 | 13% |
50 000 | 21 088 674 | 18 295 245 | 13% |
100 000 | 42 020 209 | 36 519 083 | 13% |
В худшем кейсе drop выигрывает у коллекций, но уже меньше. Выигрыш 6%-10%
Устройство декоратора для функции drop под капотом
Устройство декоратора функции drop
По сути декоратор drop аналогичен декоратору take. Он также хранит внутри счетчик и возвращает записи пока счетчик не обнулится.
override fun iterator(): Iterator<T> = object : Iterator<T> {
val iterator = sequence.iterator()
var left = count
private fun drop() {
while (left > 0 && iterator.hasNext()) {
iterator.next()
left--
}
}
override fun next(): T {
drop()
return iterator.next()
}
override fun hasNext(): Boolean {
drop()
return iterator.hasNext()
}
}Если функции take и drop так похожи, почему такие разные результаты?
Если мы сравним результаты замеров take и drop, то мы увидим, что take дает нам выигрыш, больший в несколько раз. Но при этом код этих функций как братья близнецы.
take | drop | |||||
Размер | Collection | Sequence | % | Collection | Sequence | % |
100 | 23 016 | 3 999 | 83% | 23 993 | 19 886 | 17% |
1 000 | 275 794 | 38 106 | 86% | 282 420 | 191 700 | 32% |
10 000 | 2 954 285 | 381 353 | 87% | 3 052 168 | 2 032 454 | 33% |
50 000 | 14 981 667 | 1 969 455 | 87% | 15 293 025 | 9 922 920 | 35% |
100 000 | 29 886 927 | 3 977 857 | 87% | 30 413 583 | 19 863 292 | 35% |
На самом деле, все очень просто. Дело в том, что take берет первые N элементов и дальше просто прекращает итерацию по списку, так как его итератор начинает возвращать false при вызове hasNext()
В случае с drop все несколько сложнее. Чтобы пропустить первые N элементов, функции drop приходится все равно вызывать у них метод next(). При этом, для этих элементов будут вызываться все функции преобразований, которые идут до drop. Соответственно, несмотря на то, что мы пропускаем элементы и они нам не нужны, мы все равно должны выполнить всю работу по получению и преобразованию каждого элемента.
Измерение flatten
Разворачивает список списков в один линейный список. В тесте используется список из N элементов, каждый элемент которого содержит внутренний список из 10 элементов.
Результаты измерений flatten
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 147 451 | 414 376 | -181% |
1 000 | 1 512 504 | 4 167 416 | -176% |
10 000 | 15 345 992 | 41 305 365 | -169% |
50 000 | 75 917 917 | 205 262 897 | -170% |
100 000 | 142 455 042 | 401 473 313 | -182% |
Как видите результаты flatten печальны. Проигрыш -180%
И что еще важно понимать, это весьма тяжелая операция, что видно по абсолютному времени выполнения функции.
Как устроен flatten и как он работает по капотом
Устройство декоратора функции flatten
Это достаточно сложный декоратор, поэтому давайте разбираться по шагам.
На вход декоратору передается параметр sequence, из которого он берет исходный итератор iterator. Это итератор основного списка.
Переменная itemIterator хранит ссылку на итератор вложенного списка для текущего элемента основного списка
override fun iterator(): Iterator<E> = object : Iterator<E> {
val iterator = sequence.iterator()
var itemIterator: Iterator<E>? = nullПри вызове hasNext() декоратор вызывает внутреннюю функцию ensureItemIterator(), которая вычисляет переменную itemIterator и прописывает в нее ссылку на итератор вложенного списка для текущего элемента. Она также возвращает наличие следующего элемента у вложенного списка.
override fun hasNext(): Boolean {
return ensureItemIterator()
}При вызове функции next() декоратор просто вызывает itemIterator.next() у итератора вложенного списка. Таким образом двумерный список разворачивается в одномерный.
override fun next(): E {
if (!ensureItemIterator())
throw NoSuchElementException()
return itemIterator!!.next()
}Вся основная работа происходит в функции ensureItemIterator(). Она вычисляет итератор для текущего элемента основного списка.
private fun ensureItemIterator(): Boolean {
if (itemIterator?.hasNext() == false)
itemIterator = null
while (itemIterator == null) {
if (!iterator.hasNext()) {
return false
} else {
val element = iterator.next()
val nextItemIterator = iterator(transformer(element))
if (nextItemIterator.hasNext()) {
itemIterator = nextItemIterator
return true
}
}
}
return true
}И наконец, полный код декоратора для flatten
override fun iterator(): Iterator<E> = object : Iterator<E> {
val iterator = sequence.iterator()
var itemIterator: Iterator<E>? = null
override fun next(): E {
if (!ensureItemIterator())
throw NoSuchElementException()
return itemIterator!!.next()
}
override fun hasNext(): Boolean {
return ensureItemIterator()
}
private fun ensureItemIterator(): Boolean {
if (itemIterator?.hasNext() == false)
itemIterator = null
while (itemIterator == null) {
if (!iterator.hasNext()) {
return false
} else {
val element = iterator.next()
val nextItemIterator = iterator(transformer(element))
if (nextItemIterator.hasNext()) {
itemIterator = nextItemIterator
return true
}
}
}
return true
}
}Измерение plus
Склеивает две последовательности
fun flatten_sequence(sourceCollection: List<List<Int>>): List<Int> {
return sourceCollection.asSequence()
.map { it }
.plus(sourceCollection)
.toList()
}Результаты измерений plus
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 28 685 | 84 539 | -195% |
1 000 | 325 547 | 902 038 | -177% |
10 000 | 3 400 506 | 8 951 631 | -163% |
50 000 | 16 999 468 | 43 911 542 | -158% |
100 000 | 33 640 031 | 88 627 167 | -163% |
Результаты измерения plus напоминают результаты flatten, потому что функция plus сделана на основе flatten. Проигрыш -160% - 170%
Как устроена функция plus смотрите под капотом
Устройство функции plus
Это уже не декоратор, а функция, сделанная на базе декоратора flatten.
Тут все предельно просто и даже нечего комментировать. Просто создается последовательность из двух последовательностей и к ней применяется функция flatten
public operator fun <T> Sequence<T>.plus(
elements: Iterable<T>
): Sequence<T> {
return sequenceOf(this, elements.asSequence()).flatten()
}Измерение minus
Вычитает одну последовательность из другой
Лучший кейс
sourceCollection.asSequence()
.map { it }
.minus(minusCollection_90perc)
.toList()Результаты измерений minus - удаляет 90% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 47 017 | 37 997 | 19% |
1 000 | 592 271 | 507 700 | 14% |
10 000 | 8 578 409 | 7 801 112 | 9% |
50 000 | 48 183 813 | 45 459 104 | 6% |
100 000 | 101 262 667 | 94 718 000 | 6% |
В случае лучшего кейса функция minus дает небольшой выигрыш 6% - 15%
Худший кейс
sourceCollection.asSequence()
.map { it }
.minus(minusCollection_10perc)
.toList()Результаты измерений minus - удаляет 10% исходного списка
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 56 503 | 55 714 | 1% |
1 000 | 623 336 | 615 714 | 1% |
10 000 | 6 832 593 | 6 839 409 | 0% |
50 000 | 37 601 979 | 39 143 896 | -4% |
100 000 | 80 364 834 | 86 419 125 | -8% |
В случае худшего кейса функцию minus можно считать нейтральной.
С ростом числа элементов наблюдается небольшой проигрыш -4% - 8%. Но надо учитывать, что это достаточно легкая операция и проигрыш в случае худшего кейса может быть нивелирован другими функциями преобразования.
Как устроено функция minus смотрите под капотом
Устройство функции minus
Функция minus сделана на базе декоратора filter.
Сначала она создает уникальный Set из удаляемых элементов elements и сохраняет его в переменной other.
А затем она просто создает декоратор фильтра и в качестве условия фильтра подставляет лямбду с условием, что элемент находится внутри удаляемого сета other
В результате фильтр фильтрует последовательность и в ней остаются только те элементы, которых нет в вычитаемой последовательности.
public operator fun <T> Sequence<T>.minus(
elements: Iterable<T>
): Sequence<T> {
return object: Sequence<T> {
override fun iterator(): Iterator<T> {
val other = elements.convertToSetForSetOperation()
if (other.isEmpty())
return this@minus.iterator()
else
return this@minus.filterNot { it in other }.iterator()
}
}
}Измерение zip
Объединение элементов двух последовательностей. По сути аналог combine для flow и zip в rxJava
return sourceCollection.asSequence()
.map { it + 1 }
.zip(sourceCollection.asSequence()) { v1, v2 -> v1 + v2 }
.toList()Результаты измерений zip
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 53 215 | 52 888 | 1% |
1 000 | 619 275 | 601 973 | 3% |
10 000 | 6 765 979 | 6 306 892 | 7% |
50 000 | 34 140 229 | 31 015 625 | 9% |
100 000 | 68 545 855 | 60 928 042 | 11% |
Функция zip имеет небольшой выигрыш 5% - 10% по сравнению с коллекциями
Как устроен zip смотрите под капотом
Устройство функции zip
Декоратор zip очень простой. Ему на вход передается сразу две последовательности sequence1 и sequence2.
При вызовах hasNext() и next() он просто попарно вызывает соответствующие методы у исходных последовательностей sequence1 и sequence2.
Таким образом, как только в одной из последовательностей закончатся элементы, то ее метод hasNext() начнет возвращать false и общий декоратор zip также вернет false и прекратит итерацию по последовательностям.
internal class MergingSequence<T1, T2, V>
constructor(
private val sequence1: Sequence<T1>,
private val sequence2: Sequence<T2>,
private val transform: (T1, T2) -> V
) : Sequence<V> {
override fun iterator(): Iterator<V> = object : Iterator<V> {
val iterator1 = sequence1.iterator()
val iterator2 = sequence2.iterator()
override fun next(): V {
return transform(iterator1.next(), iterator2.next())
}
override fun hasNext(): Boolean {
return iterator1.hasNext() && iterator2.hasNext()
}
}
}Измерение chunked
Сворачивает длинный список в список списков. По сути возврат длинного списка порциями по N элементов.
sourceCollection.asSequence()
.map { it }
.chunked(100)
.toList()Результаты измерения chunked
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 46 775 | 74 951 | -60% |
1 000 | 391 686 | 446 668 | -14% |
10 000 | 3 909 134 | 3 959 575 | -1% |
50 000 | 19 408 088 | 19 955 328 | -3% |
100 000 | 38 675 740 | 39 789 334 | -3% |
Функция chunked немного проигрывает коллекциям, но это легкая операция, поэтому проигрыш от нее легко будет нивелирован другими функциями преобразования.
Измерение groupBy
Группирует последовательность по заданному критерию. Возвращает Map из ключей группировки и соответствующих каждому ключу элементов
sourceCollection.asSequence()
.map { it }
.groupBy { it * 10 / 100 }
.toList()Результаты измерений groupBy
Размер списка | Collection (ns) | Sequence (ns) | % |
100 | 64 973 | 50 670 | 22% |
1 000 | 716 454 | 579 001 | 19% |
10 000 | 9 308 440 | 7 863 016 | 16% |
50 000 | 56 283 417 | 51 490 709 | 9% |
100 000 | 121 278 750 | 110 725 750 | 9% |
Как видим, функция groupBy дает выигрыш 10% - 15%
Если хотите отгадать небольшую загадку, смотрите под капот
Устройство функции groupBy
Детская загадка, найдите 10 отличий
Реализация sequences
public inline fun <T, K, M : MutableMap<in K, MutableList<T>>>
Sequence<T>.groupByTo(destination: M, keySelector: (T) -> K): M
{
for (element in this) {
val key = keySelector(element)
val list = destination.getOrPut(key) { ArrayList<T>() }
list.add(element)
}
return destination
}Реализация collections
public inline fun <T, K, M : MutableMap<in K, MutableList<T>>>
Iterable<T>.groupByTo(destination: M, keySelector: (T) -> K): M
{
for (element in this) {
val key = keySelector(element)
val list = destination.getOrPut(key) { ArrayList<T>() }
list.add(element)
}
return destination
}Ответ: Различие только в типе дженерика
Реализация этой функции в коллекциях и sequences идентична. Эта функция очень хорошо демонстрирует то, что весь наш профит мы получаем исключительно за счет исключения копирования промежуточных результатов, по сути копирования массивов.
Измерение остальных функций sequences
На самом деле все функции sequences делятся на две большие группы:
Декораторы итераторов - настоящие sequences, которые лежат в основе всего механизма. В своем исследовании я рассмотрел и измерил их все.
Производные функции - функции, которые сделаны на основе базовых декораторов. Яркий пример таких функций: plus, minus и другие.
Так как эти функции работают на основе существующих декораторов, то и их производительность напрямую зависит от их базовых декораторов.
Нет смысла измерять их все, так как они будут показывать такие же результаты, как и базовые декораторы. Вы можете видеть это по примерам производных функций plus, minus, distinct
Те же функции, которые вообще не используют базовые декораторы, всегда будут выигрывать у коллекций. Яркий пример таких функций: groupBy, associateBy, fold
Выводы
Спасибо тем, кто дочитал до конца. Я искренне вами горжусь. Материала действительно много и я очень надеюсь, что мне удалось показать и понятно объяснить как sequences работают под капотом. Собственно это было одной из моих главных задач.
На данный момент в sequences существует 3 тяжелые функции sort, flatten, plus, попытка использования которых в sequences, ставит крест на производительности вашего преобразования. Если вам необходимо использовать их, то в этом случае лучше использовать стандартные коллекции.
Во всех остальных случаях, если в вашем преобразовании больше двух функций, можете смело использовать sequences. Вы точно не проиграете и скорее всего даже немного выиграете.
Я специально не включаю в список тяжелых функций distinct, так как мне удалось ее оптимизировать и мои оптимизации уже попали в kotlin и выйдут вместе с версией kotlin 2.0.
Вы можете прочитать об этом в моей следующей статье (Оптимизируя sequences — или как мой код попал в kotlin)
Если вам понравилась моя статья, проголосуйте за мою статью на medium "Measuring sequences". Это поможет продвинуть ее на международной площадке.
