Антипаттерны производительности API коллекций Kotlin

Kotlin Collections API является выразительным и богатым, но с большой силой приходит большая ответственность — есть определенные методы, которые могут привести к ненужной сложности времени и накладным расходам на выделение объектов.

Чтобы полностью понять контекст, обязательно сначала ознакомьтесь с предыдущей статьей.

1. Цепочка вызовов map()

Два последовательных вызова map() могут выглядеть невинными и оправданными с точки зрения удобочитаемости, но могут быть неприемлемы из-за влияния на производительность.

Давайте посмотрим на простой пример:

list
  .map { it.toString() }
  .map { it.toUpperCase() }

Все станет ясно, если мы разберем его по частям и взглянем на реализацию map():

val map = list.map { it.toString() }
val anotherMap = map.map { it.toUpperCase() }
public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
    for (item in this) destination.add(transform(item))
    return destination
}

Каждый вызов map() запускает новый O(n)-цикл for и создание нового объекта списка, который после завершения обработки удаляется сборщиком мусора. Это много? Это зависит™, но определенно лучше знать об этом компромиссе.

Оказывается, решение такое же тривиальное, как свертывание последовательных вызовов:

list.map { it.toString().toUpperCase() }

2. Цепочка вызовов map() и flatMap()

Как и в приведенном выше примере, всякий раз, когда вы видите комбинацию map() и flatMap(), драгоценные циклы ЦП можно сэкономить, включив их в один вызов flatMap().

Так:

list
  .map { it.toList() }
  .flatMap { it }

становится:

list.flatMap { it.toList() }

3. Цепочка map() и filterNotNull()

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

val list = listOf(1, 2, 3, null)

list
  .filterNotNull()
  .map { it.toString() }

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

public fun <C : MutableCollection<in T>, T : Any> Iterable<T?>.filterNotNullTo(destination: C): C {
    for (element in this) if (element != null) destination.add(element)
    return destination
}

• filterNotNull() создаст новую коллекцию, переберет существующую и переупаковает ненулевые элементы в новую, а затем вернет ее.
• map() создаст новую коллекцию, переберет существующую, применит сопоставление и сохранит сопоставленные элементы в новой коллекции, а затем вернет ее.

Эти две операции можно объединить и оптимизировать, используя метод mapNotNull():

list.mapNotNull { it.toString() }

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

4. Объединение map()/flatMap() с last()/first()

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

list
  .map { it * 42 }
  .last()

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

list
  .last() * 42

Или, если мы хотим сохранить структуру связанных вызовов, мы можем использовать let():

list
  .last()
  .let { it * 42 }

5. Цепочка filter() и first()/last()

Всякий раз, когда мы хотим отфильтровать определенные элементы, а затем выбрать первый/последний из них, нет необходимости сначала обрабатывать все элементы:

val list = listOf(1, 2, 3)

list
  .filter { it % 2 == 1 }
  .last() // first()

Мы можем добиться большего успеха, просто используя специальный параметризованный метод last(predicate: (T) -> Boolean):

list.last { it % 2 == 1 }

Оказывается, этот фактически запускает обратную итерацию с конца коллекции:

public inline fun <T> List<T>.last(predicate: (T) -> Boolean): T {
    val iterator = this.listIterator(size)
    while (iterator.hasPrevious()) {
        val element = iterator.previous()
        if (predicate(element)) return element
    }
    throw NoSuchElementException("List contains no element matching the predicate.")
}

6. Цепочка filter() и count()

Всякий раз, когда необходимо вычислить все вхождения элементов, соответствующих заданному предикату, нет необходимости сначала создавать отфильтрованную коллекцию с помощью filter(), а только затем применять count():

list
  .filter { it % 2 == 1 }
  .count()

Вышеуказанное может быть просто достигнуто с помощью специальной перегрузки count(), которая избавит нас от создания нового объекта:

list.count { it % 2 == 1 }

Ключевые вынос

Kotlin Collection API является мощным и лучше знать о компромиссах, связанных с его рвением.

Фрагменты кода, как всегда, можно найти на GitHub.