Как стать автором
Обновить

Измеряя sequences

Уровень сложностиСложный
Время на прочтение38 мин
Количество просмотров5.3K

Введение

Я лид команды системных сервисов в 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". Это поможет продвинуть ее на международной площадке.

Теги:
Хабы:
Всего голосов 21: ↑21 и ↓0+21
Комментарии12

Публикации

Истории

Работа

Ближайшие события