Введение

Я лид команды системных сервисов в SberDevices и провожу довольно много технических интервью по Android (более 100 в год). По опыту проведения собеседований я вижу, что абсолютное большинство разработчиков боятся использовать sequences в работе, потому что не понимают как они работают. А самое главное, не понимают в каких случаях sequences дают выигрыш, а в каких проигрыш.

В сети нигде нет четкой информации об этом (по крайней мере я не нашел). Везде приводятся только общие фразы, без описания конкретных кейсов и цифр. При этом есть довольно спорное правило detect, которое гласит

CouldBeSequence: Используйте sequences, если в вашем преобразовании коллекции больше 3 функций преобразований

Так как я достаточно хорошо знаю внутренний код kotlin, то понимаю что это правило не совсем корректно. Мне захотелось исправить этот пробел и я решил провести небольшое исследование производительности sequences. Понять, когда использование sequences дает нам выигрыш, а когда проигрыш. Мне захотелось подойти к этому с математической и инженерной точки зрения и получить конкретные цифры и кейсы.

Результаты исследования

Для тех, кто любит сразу получать ответы, привожу итоговые результаты своего исследования в заголовке статьи.

Проигрыш

Функции sequences, использование которых даст вам гарантированный проигрыш. Все эти функции тяжелые, поэтому неважно сколько функций преобразований у вас используется. Если среди них есть хотя бы одна из этих функций, вы гарантированно получите проигрыш.

Небольшой проигрыш

Функции sequences, использование которых может давать небольшой проигрыш, но он может быть нивелирован добавлением других функций преобразования. 

Выигрыш

Все остальные  функции 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

Как видите в этом тесте никто не проигрывает и не выигрывает. С ростом числа элементов у sequences наблюдается небольшой выигрыш, но он укладывается в размер статистической погрешности.

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

benchmarkRule.measureRepeated {
    sourceCollection.asSequence()
        .map { it + 1 }
        .map { it + 2 }
        .map { it + 3 }
        .toList()
}

Результаты измерений - 3 map

Как видите результаты хорошо согласуются с теорией. Мы сразу получили ощутимый выигрыш 15-20% при добавлении дополнительного преобразования.

Давайте проверим, как будет расти производительность, если добавить еще преобразований.

benchmarkRule.measureRepeated {
    sourceCollection.asSequence()
        .map { it + 1 }
        .map { it + 2 }
        .map { it + 3 }
        .map { it + 4 }
        .map { it + 5 }
        .toList()
}

Результаты измерений - 5 map

Наш выигрыш еще немного вырос и составляет уже внушительные 27-30%

Теперь давайте разберемся с магией. Посмотрим как же устроен sequences декоратор для функции map под капотом. Кому интересно, раскрывайте вложенный элемент.

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()
        }
    }
}

        override fun next(): R {
            return transformer(iterator.next())
        }

Измерение sort

    sourceCollection.asSequence()
        .map { it + 1 }
        .sortedByDescending { it }
        .toList()

Результаты измерений - sort

Как видите, с сортировкой у sequences все плохо. Проигрыш порядка ‑10%.

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

Это отчетливо видно, если сравнить время выполнения сортировки и функции map. Разница по времени отличается на порядок!

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

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 
    // в промежуточный список
    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% исходного списка

Как видите, в лучшем кейсе filter дает выигрыш примерно в 25%-30%.

Худший кейс 

   sourceCollection.asSequence()
        .map { it + 1 }
        .filter { it in 0..precent_90 }
        .toList()

Результаты измерений filter - оставляет 90% исходного списка

А вот в худшем кейсе наш выигрыш стремится к нулю и составляет 2%-4%

Кому интересно, как устроен декоратор sequences для функции 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
        }

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
        }
    }
}

        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
        }
    }

Измерение distinct

Оставляет в последовательности только уникальные элементы

Лучший кейс 

    sourceCollection.asSequence()
        .map { it * 10 / 100 }
        .distinctBy { it }
        .toList()

Результаты измерений distinct - оставляет 10% исходного списка

Как видите в лучшем кейсе distinct выигрывает у коллекций. Выигрыш 10%-15%

Худший кейс 

    sourceCollection.asSequence()
        .map { it * 90 / 100 }
        .distinctBy { it }
        .toList()

Результаты измерений distinct - оставляет 90% исходного списка

А вот в худшем случае distinct значительно проигрывает коллекциям, проигрыш -15%

Оффтопик: На самом деле все не так печально и в следующей версии kotlin 2.0 эту проблему уже устранили. Об этом у меня будет отдельная статья.

Как же устроен декоратор distinct?

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()
    }
}

Измерение take

Берет первые N элементов последовательности.

Лучший кейс 

    sourceCollection.asSequence()
        .map { it + 1 }
        .take { countPercent_10 }
        .toList()

Результаты измерений take - берет 10% исходного списка

Как видите здесь разгром коллекций, выигрыш почти 90%

Худший кейс 

    sourceCollection.asSequence()
        .map { it + 1 }
        .take { countPercent_90 }
        .toList()

Результаты измерений take - берет 90% исходного списка

В худшем кейсе take также имеет значительный выигрыш 20%-25%, но он в 3 раза меньше лучшего кейса

     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% исходного списка

Функция drop выигрывает у коллекций в лучшем кейсе, выигрыш 30%-35%

Худший кейс 

    sourceCollection.asSequence()
        .map { it + 1 }
        .drop { countPercent_10 }
        .toList()

Результаты измерений drop - удаляет 10% исходного списка

В худшем кейсе drop выигрывает у коллекций, но уже меньше. Выигрыш 6%-10%

    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()
        }
    }

Измерение flatten

Разворачивает список списков в один линейный список. В тесте используется список из N элементов, каждый элемент которого содержит внутренний список из 10 элементов.

Результаты измерений flatten

Как видите результаты flatten печальны. Проигрыш -180%

И что еще важно понимать, это весьма тяжелая операция, что видно по абсолютному времени выполнения функции.

    override fun iterator(): Iterator<E> = object : Iterator<E> {
        val iterator = sequence.iterator()
        var itemIterator: Iterator<E>? = null

        override fun hasNext(): Boolean {
            return ensureItemIterator()
        }

        override fun next(): E {
            if (!ensureItemIterator())
                throw NoSuchElementException()

            return itemIterator!!.next()
        }

    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
    }

    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

Результаты измерения plus напоминают результаты flatten, потому что функция plus сделана на основе flatten. Проигрыш -160% - 170%

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% исходного списка

В случае лучшего кейса функция minus дает небольшой выигрыш 6% - 15%

Худший кейс 

    sourceCollection.asSequence()
        .map { it }
        .minus(minusCollection_10perc)
        .toList()

Результаты измерений minus - удаляет 10% исходного списка

В случае худшего кейса функцию minus можно считать нейтральной.

С ростом числа элементов наблюдается небольшой проигрыш -4% - 8%. Но надо учитывать, что это достаточно легкая операция и проигрыш в случае худшего кейса может быть нивелирован другими функциями преобразования.

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

Функция zip имеет небольшой выигрыш 5% - 10% по сравнению с коллекциями 

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

Функция chunked немного проигрывает коллекциям, но это легкая операция, поэтому проигрыш от нее легко будет нивелирован другими функциями преобразования.

Измерение groupBy

Группирует последовательность по заданному критерию. Возвращает Map из ключей группировки и соответствующих каждому ключу элементов

    sourceCollection.asSequence()
        .map { it }
        .groupBy { it * 10 / 100 }
        .toList()

Результаты измерений groupBy

Как видим, функция groupBy дает выигрыш 10% - 15%

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
}

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, которые лежат в основе всего механизма. В своем исследовании я рассмотрел и измерил их все.

Производные функции - функции, которые сделаны на основе базовых декораторов. Яркий пример таких функций: plus, minus и другие.

Так как эти функции работают на основе существующих декораторов, то и их производительность напрямую зависит от их базовых декораторов.

Нет смысла измерять их все, так как они будут показывать такие же результаты, как и базовые декораторы. Вы можете видеть это по примерам производных функций plus, minus, distinct

Те же функции, которые вообще не используют базовые декораторы, всегда будут выигрывать у коллекций. Яркий пример таких функций: groupBy, associateBy, fold

Выводы

Спасибо тем, кто дочитал до конца. Я искренне вами горжусь. Материала действительно много и я очень надеюсь, что мне удалось показать и понятно объяснить как sequences работают под капотом. Собственно это было одной из моих главных задач.

На данный момент в sequences существует 3 тяжелые функции sort, flatten, plus, попытка использования которых в sequences, ставит крест на производительности вашего преобразования. Если вам необходимо использовать их, то в этом случае лучше использовать стандартные коллекции.

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

Я специально не включаю в список тяжелых функций distinct, так как мне удалось ее оптимизировать и мои оптимизации уже попали в kotlin и выйдут вместе с версией kotlin 2.0.

Я напишу об этом подробно в своей следующей статье.