Эффективный Котлин: рассмотрите встроенный модификатор для функций высшего порядка

Эффективный Котлин: рассмотрите встроенный модификатор для функций высшего порядка

Вы могли заметить, что все функции обработки коллекции встроены. Вы когда-нибудь спрашивали себя, почему они определены таким образом? Вот, например, упрощенная функция filter из Kotlin stdlib:

inline fun <T> Iterable<T>.filter(predicate: (T)->Boolean): List<T>{
    val destination = ArrayList<T>()
    for (element in this) 
        if (predicate(element))
            destination.add(element)
    return destination
}

Насколько важен этот модификатор inline? Допустим, у нас есть 5 000 товаров, и нам нужно просуммировать цены тех, что были куплены. Мы можем сделать это просто:

users.filter { it.bought }.sumByDouble { it.price }

На моей машине на вычисления в среднем уходит 38 мс. Сколько было бы, если бы этой функции не было inline? 42 мс в среднем на моей машине. Убедитесь сами. Это не выглядит большим, но вы можете заметить эту разницу ~ 10% каждый раз, когда используете методы для обработки коллекции.

Гораздо большую разницу можно наблюдать, когда мы изменяем локальные переменные в лямбда-выражении. Сравните функции ниже:

inline fun repeat(times: Int, action: (Int) -> Unit) {
    for (index in 0 until times) {
        action(index)
    }
}

fun noinlineRepeat(times: Int, action: (Int) -> Unit) {
    for (index in 0 until times) {
        action(index)
    }
}

Вы могли заметить, что кроме имени, единственная разница в том, что у первого есть модификатор inline, а у второго - нет. Использование тоже такое же:

var a = 0
repeat(100_000_000) {
    a += 1
}
var b = 0
noinlineRepeat(100_000_000) {
    b += 1
}

Здесь у нас большая разница во времени выполнения. inlineRepeat закончили в среднем за 0,335 нс, в то время как noinlineRepeat потребовалось в среднем 153 980 484,884 нс. Это в 466 тысяч раз больше! Убедитесь сами.

Почему это так важно? Есть ли какие-либо затраты на повышение производительности? Когда мы действительно должны использовать встроенный модификатор? Это очень важные вопросы, и мы постараемся на них ответить. Хотя все должно начинаться с гораздо более простого вопроса: что делает встроенный модификатор?

Что делает встроенный модификатор?

Мы знаем, как обычно вызываются функции. Выполнение переходит в тело функции, вызывает все операторы и затем возвращается к тому месту, где была вызвана функция.

Хотя когда функция помечена модификатором inline, компилятор обрабатывает ее по-другому. Во время компиляции кода он заменяет такой вызов функции своим телом. print - это inline функция:

public inline fun print(message: Int) {
    System.out.print(message)
}

Когда мы определяем следующее main:

fun main(args: Array<String>) {
    print(2)
    print(2)
}

После компиляции это будет выглядеть так:

fun main(args: Array<String>) {
    System.out.print(2)
    System.out.print(2)
}

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

Почему IntelliJ предлагает использовать inline, когда у нас есть лямбда-параметры? Потому что, когда мы встраиваем тело функции, нам не нужно создавать лямбды из аргументов, и вместо этого мы можем встраивать их в вызовы. Этот вызов вышеупомянутой функции repeat:

repeat(100) { println("A") }

После компиляции будет выглядеть так:

for (index in 0 until 1000) {
    println("A")
}

Как видите, тело лямбда-выражения заменяет вызовы встроенной функции. Давайте посмотрим на другой пример. Использование этой filter функции:

val users2 = users.filter { it.bought }

Будет заменено на:

val destination = ArrayList<T>()
for (element in this) 
    if (predicate(element))
        destination.add(element)
val users2 = destination

Это важное улучшение. Это потому, что JVM наивно не поддерживает лямбда-выражения. Довольно сложно объяснить, как компилируются лямбда-выражения, но в целом есть два варианта:

• Анонимный класс
• Отдельный класс

Давайте посмотрим на это на примере. У нас есть следующее лямбда-выражение:

val lambda: ()->Unit = {
    // body
}

Может оказаться, что это анонимный класс JVM:

// Java
Function0 lambda = new Function0() {
   public Object invoke() {
      // code
   }
};

Или это может оказаться нормальный класс, определенный в отдельном файле:

// Java
// Additional class in separate file
public class TestInlineKt$lambda implements Function0 {
   public Object invoke() {
      // code
   }
}
// Usage
Function0 lambda = new TestInlineKt$lambda()

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

Это ответ, почему у нас такая разница между repeat и noinlineRepeat, когда мы изменяем локальные переменные. Лямбда в не встроенной функции должна быть скомпилирована в анонимный класс. Это огромные затраты, потому что их создание и использование медленнее. Когда мы используем встроенную функцию, нам вообще не нужно создавать какой-либо дополнительный класс. Убедитесь сами. Скомпилируйте и декомпилируйте в Java этот код:

fun main(args: Array<String>) {
    var a = 0
    repeat(100_000_000) {
        a += 1
    }
    var b = 0
    noinlineRepeat(100_000_000) {
        b += 1
    }
}

Вы найдете что-то похожее на это:

// Java
public static final void main(@NotNull String[] args) {
   int a = 0;
   int times$iv = 100000000;
   int var3 = 0;

   for(int var4 = times$iv; var3 < var4; ++var3) {
      ++a;
   }

   final IntRef b = new IntRef();
   b.element = 0;
   noinlineRepeat(100000000, (Function1)(new Function1() {
      public Object invoke(Object var1) {
         ++b.element;
         return Unit.INSTANCE;
      }
   }));
}

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

Обработка потока коллекции по сравнению с классическим способом

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

return data.filter { filterLoad(it) }.map { mapLoad(it) }

Работает так же и имеет такое же время выполнения, как и этот:

val list = ArrayList<String>()
for (it in data) {
    if (filterLoad(it)) {
        val value = mapLoad(it)
        list.add(value)
    }
}
return list

Конкретные результаты эталонных измерений (код здесь):

Benchmark           (size) Mode  Cnt        Score    Error  Units
filterAndMap           10  avgt  200      561.249 ±      1  ns/op
filterAndMap         1000  avgt  200    29803.183 ±    127  ns/op
filterAndMap       100000  avgt  200  3859008.234 ±  50022  ns/op

filterAndMapManual     10  avgt  200      526.825 ±      1  ns/op
filterAndMapManual   1000  avgt  200    28420.161 ±     94  ns/op
filterAndMapManual 100000  avgt  200  3831213.798 ±  34858  ns/op

С программной точки зрения эти две функции почти равны. Хотя с точки зрения удобочитаемости первый вариант намного лучше. Вот почему мы всегда должны предпочесть использовать функции обработки интеллектуальной коллекции вместо того, чтобы реализовывать всю обработку самостоятельно. Также, если нам нужна какая-то другая функция обработки коллекции, отличная от stdlib, не стесняйтесь написать свою собственную функцию. Это, например, функция, которую я добавил в свой последний проект, когда мне нужно было переставить список списков:

fun <E> List<List<E>>.transpose(): List<List<E>> {
    if (isEmpty()) return this

    val width = first().size
    if (any { it.size != width }) {
        throw IllegalArgumentException("All nested lists must have the same size, but sizes were ${map { it.size }}")
    }

    return (0 until width).map { col ->
        (0 until size).map { row -> this[row][col] }
    }
}

Просто не забудьте написать несколько модульных тестов:

class TransposeTest {

    private val list = listOf(listOf(1, 2, 3), listOf(4, 5, 6))

    @Test
    fun `Transposition of transposition is identity`() {
        Assert.assertEquals(list, list.transpose().transpose())
    }

    @Test
    fun `Simple transposition test`() {
        val transposed = listOf(listOf(1, 4), listOf(2, 5), listOf(3, 6))
        assertEquals(transposed, list.transpose())
    }
}

Стоимость встроенного модификатора

Inline не следует использовать слишком часто, потому что это также имеет свою цену. Скажем, мне очень нравится печать 2. Сначала я определил следующую функцию:

inline fun twoPrintTwo() {
    print(2)
    print(2)
}

Мне этого показалось мало, поэтому я добавил такую ​​функцию:

inline fun twoTwoPrintTwo() {
    twoPrintTwo()
    twoPrintTwo()
}

Все еще не удовлетворен. Я определил следующие функции:

inline fun twoTwoTwoPrintTwo() {
    twoTwoPrintTwo()
    twoTwoPrintTwo()
}

fun twoTwoTwoTwoPrintTwo() {
    twoTwoTwoPrintTwo()
    twoTwoTwoPrintTwo()
}

Затем я решил проверить, что у меня есть в скомпилированном коде, поэтому я скомпилировал его в байт-код JVM и декомпилировал в Java. twoTwoPrintTwo был уже довольно большим:

public static final void twoTwoPrintTwo() {
   byte var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
}

Но twoTwoTwoTwoPrintTwo было действительно страшно:

public static final void twoTwoTwoTwoPrintTwo() {
   byte var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print(var1);
   var1 = 2;
   System.out.print();
}

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

Различные аспекты использования встроенных модификаторов

Встроенный модификатор из-за своего характера меняет гораздо больше, чем то, что мы видели в этой статье. Это позволяет нелокальный возврат и овеществленный универсальный тип. У него также есть некоторые ограничения. Хотя это не связано с серией Effective Kotlin и это материал для отдельной статьи. Если хотите, чтобы я это написал, напишите об этом в Твиттере или в комментарии.

Когда вообще следует использовать встроенный модификатор?

Самый важный случай, когда мы используем модификатор inline, - это когда мы определяем утилитарные функции с функциями параметров. Коллекция или обработка строк (например, filter, map или joinToString) или просто автономные функции (например, repeat) являются прекрасным примером.

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

Когда у нас нет параметра типа функции, параметра повторного типа и нам не нужен нелокальный возврат, то нам, скорее всего, не следует использовать модификатор inline. Вот почему у нас будет предупреждение в Android Studio или IDEA IntelliJ.

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

Эффективный Котлин

Это первая статья об Effective Kotlin. Когда увидим интерес, опубликуем следующие части. В Кот. Academy мы также работаем над книгой на эту тему:

Он будет охватывать гораздо более широкий круг тем и углубляться в каждую из них. Он также будет включать в себя лучшие практики, опубликованные командой Kotlin и Google, опыт членов команды Kotlin, с которой мы сотрудничаем, и темы, затронутые в серии Эффективная Java в Kotlin. Чтобы поддержать это и ускорить публикацию, воспользуйтесь этой ссылкой и подпишитесь.

Вам нужна мастерская Kotlin? Посетите наш сайт, чтобы узнать, что мы можем для вас сделать.

Чтобы быть в курсе отличных новостей о Kt. Academy, подписывайтесь на рассылку новостей, следите за Твиттером и следите за нами в среде.

Чтобы сослаться на меня в Twitter, используйте @MarcinMoskala.

Если вам это нравится, не забудьте хлопать. Обратите внимание: если вы удерживаете кнопку хлопка, вы можете оставить больше хлопков.

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