%language_name%, он делает манипуляции с коллекциями так, как привык, как “удобно”, как “понятнее” или даже “как быстрее”. При этом, разумеется, используются циклы и изменяемые коллекции вместо функций высшего порядка (таких как filter, map, fold и др.) и неизменяемых коллекций.Эта статья — попытка убедить ортодоксов, что использование “этой вашей функциональщины” не влияет существенно на производительность. В качестве примеров использованы куски кода на Java, Scala и Kotlin, а для измерения скорости был выбран фреймворк для микробенчмаркинга JMH.
Для тех, кто не в курсе, JMH (Java Microbenchmark Harness) — это сравнительно молодой фреймворк, в котором разработчики постарались учесть все нюасы JVM. Подробнее о нем можно узнать из докладов Алексея Шипилева (например, из этого). На мой взгляд, проще всего с ним познакомится на примерах, где вся необходимая информация есть в javadoc.
Самая интересная часть в написании бенчмарков заключалась в том, чтобы заставить JVM реально что-то делать. Эта умная зараза заранее знала ответ на все и выдавала ответы за мизерное время. Именно поэтому в их исходном коде фигурирует
prepare, чтобы обхитрить JVM. Кстати, Java Streams с предвычисленным результатом работали на порядок медленнее других способов.Dicslaimer: все прекрасно знают, что написать бенчмарк правильно — невозможно, но предложения по тому, как написать его менее неправильно приветствуются. Если вам кажется, что обязательно надо рассмотреть пример с X, не стесняйтесь писать в комментариях, что еще надо потестить.
Кроме того, несмотря на то, что на одном графике будут и Kotlin, и Scala, и Java, считать это сравнением скорости кода на этих языках не стоит. Как минимум, в примерах на Scala есть накладные расходы на конвертацию
scala.Int?java.lang.Integer и используются не Java-коллекции, а свои.Исходный код примеров можно посмотреть на гитхабе, а все результаты в CSV — здесь. В качестве размера коллекций использовались значения от 10 до 100 000. Тестировать для бОльших размеров я особо не вижу смысла — для этого есть СУБД и другие способы работы с большими объемами данных. Все графики выполнены в логарифмической шкале и показывают среднее время выполнения операции в наносекундах.
Простой map
Начнем с самых простых примеров, которые есть в почти каждой статье про элементы функционального программирования:
map, filter, fold и flatMap.
В Java циклом преобразовывать коллекции немного быстрее, чем с использованием Streams API. Очевидно, что дело в накладных расходах на преобразование в
stream, которые здесь себя не оправдывают. В Kotlin преобразование с использованием map будет быстрее, чем цикл, причем даже быстрее, чем цикл на Java. Почему же это происходит? Смотрим исходный код map:@PublishedApi
internal fun <T> Iterable<T>.collectionSizeOrDefault(default: Int): Int =
if (this is Collection<*>) this.size else default
…
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
}
...
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}
Получаем выигрыш за счет того, что заранее известен конечный размер коллекции. Конечно можно и в Java так сделать, но часто ли вы такое встречали?
В Scala разница между циклом и
map уже ощутима. Если в Kotlin map довольно прямолинейно конвертируется в цикл, то в Scala уже не все так просто: если неявный CanBuildFrom — переиспользуемый ReusableCBFInstance из списка, то применяется хитрый while (заинтересованные могут посмотреть исходный код скаловского map для списка здесь).Простой filter
В Java для коллекций очень маленького размера Stream API немного медленнее, чем цикл, но, опять же, несущественно. Если коллекции нормального размера — разницы вообще нет.
В Kotlin разницы практически нет (прозрачная компиляция в цикл), но при больших объемах цикл чуть медленнее.
В Scala ситуация аналогична Java: на маленьких коллекциях функциональный подход немного проигрывает, на больших — нет разницы.
Простой fold
Не совсем подходящий пример (потому что на выходе число), но все равно довольно интересный.
Во всех трех языках различия между итеративной формой и функциональной несущественны, хотя
fold в Scala работает медленнее, чем хотелось бы.Простой flatMap
Снова разница между подходами практически неразличима.
Цепочка преобразований
Давайте рассмотрим еще пару примеров, в которых выполняются сложные преобразования. Отмечу, что очень много задач можно решить комбинацией
filter и map и очень длинные цепочки встречаются редко. При этом если у вас все-таки получилась длинная цепочка преобразований, то имеет смысл перейти на ленивые вычисления (т.е. применять преобразования только тогда, когда необходимо). В Kotlin это преобразование к
Sequence, в Scala — iterator. Streams в Java всегда выполняются лениво. Рассмотрим цепочку
flatMap?filter?fold:someList
.flatMap(this::generate)
.filter(this::filter)
.fold(initialValue(), this::doFold)
Разница по скорости между императивным подходом и функциональным снова весьма мала. Исключение составляет Scala, в которой функциональный подход медленнее цикла, но с
iterator разница сводится к нулю.Цепочка со вложенными преобразованиями
Рассмотрим последовательность преобразований, где элементами промежуточной коллекции тоже являются коллекции, и над которыми тоже надо выполнять действия. Например топ-10 чего-то по какой-нибудь хитрой метрике:
someList
.groupBy(this::grouping)
.mapValues {
it.value
.filter(this::filter)
.map(this::transform)
.sum()
}
.entries
.sortedByDescending { it.value }
.take(10)
.map { it.key }
Честно говоря, мне такое уже тяжело было написать в императивном стиле (к хорошему быстро привыкаешь; я сделал две тупых ошибки и в одном месте перепутал переменную).
Здесь результаты уже немного интереснее. На коллекциях размером до сотни разница между итеративным и функциональным подходом стала заметна. Однако на коллекциях большего размера разницей можно уже пренебречь. Стоит ли вам экономить 10 микросекунд процессорного времени? Особенно если при этом надо поддерживать код вроде такого:
Map<Integer, Integer> sums = new HashMap<>();
for (Integer element : someList) {
Integer key = grouping(element);
if (filter(element)) {
Integer current = sums.get(key);
if (current == null) {
sums.put(key, transform(element));
} else {
sums.put(key, current + transform(element));
}
}
}
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(sums.entrySet());
entries.sort(Comparator.comparingInt((x) -> -x.getValue()));
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < 10; i++) {
if (entries.size() <= i){
break;
}
result.add(entries.get(i).getKey());
}
return result;
Заключение
В целом получилось, что для всех случаев у функционального подхода если и есть проигрыш, то, на мой взгляд, он несущественный. При этом код, на мой взгляд, становится чище и читабельнее (если говорить про Kotlin, Scala и другие языки, изначально поддерживающие ФП), а под капотом могут быть полезные оптимизации.
Не экономьте на спичках: вы же не пишете на ассемблере, потому что “так быстрее”? Действительно, может получиться быстрее, а может и нет. Компиляторы сейчас умнее одного программиста. Доверьте оптимизации им, это их работа.
Если вы все еще используете какой-нибудь
mutableListOf, задумайтесь. Во-первых, это больше строк кода и бОльшая вероятность сделать ошибку. Во-вторых, вы можете потерять оптимизации, которые появятся в будущих версиях языка (или уже есть там). В-третьих, при функциональном подходе лучше инкапсуляция: разделить filter и map проще, чем разбить цикл на два. В-четвертых, если вы уж пишете на языке, в котором есть элементы ФП и пишете “циклами”, то стоит следовать рекомендациям и стилю (например, Intellij Idea вам будет настоятельно рекомендовать заменить for на соответствующее преобразование).Комментарии (29)
vird
05.07.2017 13:34+3Логарифмическая шкала вводит в заблуждение
ov7a
05.07.2017 13:38На обычной для коллекций малого размера вообще все неразличимо.
vird
05.07.2017 13:44(если я взял правильные столбики)
"collections.chain.JavaFor.benchmark","avgt",1,5,1220522.342690,762881.441383,"ns/op",1000
"collections.chain.JavaStreams.benchmark","avgt",1,5,1159477.123056,779167.349278,"ns/op",1000
(762881.441383-779167.349278)/762881.441383
-0.021347888428739102
"collections.chain.JavaFor.benchmark","avgt",1,5,10819.745871,3922.925920,"ns/op",10
"collections.chain.JavaStreams.benchmark","avgt",1,5,10495.110603,5289.096391,"ns/op",10
(10495.110603-10819.745871)/10495.110603
-0.030932048291821133
ov7a
05.07.2017 13:48В csv «Benchmark»,«Mode»,«Threads»,«Samples»,«Score»,«Score Error (99.9%)»,«Unit»,«Param: collectionSize»
Вы для Score Error разницу посчитали.
Но как уже ниже написали, есть «ощутимая» разница, которую плохо видно. Но в абсолютном выражении — это ничто.vird
05.07.2017 13:52+2Исправил комментарий т.к. во втором случае действительно взял не оттуда.
3% это не так уж что бы и ничто…
Это в идеальном случае prefetch'а процессором.
Как только вылетите за кэш процессора или возьмете коллекцию, которая не умещается в памяти несколько раз, то… как вы думаете что происходит
knotri
05.07.2017 13:36+5В целом получилось, что для всех случаев у функционального подхода если и есть проигрыш, то он несущественный (в пределах погрешности измерений).
Манипуляции какие-то, у вас же логарифмический масштаб — и ваши "пределы погрешности" составляют разницу в три раза (скажем на последнем графике javaFor vs javaSteams)
ov7a
05.07.2017 13:44-1Согласен, но в абсолютном выражении для коллекции размером 30 000 это 0,5 миллисекунды… Подправил в статье.
knotri
05.07.2017 13:49+1это 0,5 миллисекунды…
И что, это много или мало?
Вот вроде айпад новый вышел с 120 фпс = 8 мс на кадр. Можно ли в кадре потерять 0.5 мс? Нет.ov7a
05.07.2017 13:54-1Я считаю, что с точки зрения цены времени программиста — это мало.
Если вы для вас скорость критична — это много.
Если вы разрабатываете «обычное» ПО, и у вас есть другие источники тормозов — база данных, пинг HTTP, накладные расходы от вашего любимого Application Server и т.д., то это мало.
kekekeks
05.07.2017 16:55+2База данных и пинг HTTP, они асинхронны и процессорное время внутри приложения не кушают. А вот код — вполне себе. Полмиллисекунды здесь, полторы там, всё это внутри часто вызываемой процедурки, а потом сервер полностью жрёт 8-ядерный Xeon на сотне пользователей.
bormotov
06.07.2017 11:24+3вы правы, вот только «рано остановились», нужно довести эту логику до денег.
Денег, которые принесут эти 100 пользователей, и денег, которые нужно будет отдать программистам и за аренду сервера. К сожалению, на шаге «перевод в деньги», очень многие обламываются, а он самый важный показатель. Потому, что серверные мощности со временем дешевеют, а программисты — дорожают.
А практика (увы, подкрепить цифрами не могу) написания кода показывает, что функциональный оптимизировать легче. Он гораздо более наглядно передает суть «что тут вообще происходит», чем императивная лапша.
mayorovp
05.07.2017 13:56+7Это означает лишь тот факт, что не следует перебирать коллекцию в 30 000 элементов каждый кадр.
kekekeks
05.07.2017 16:56-1Если у меня 30К объектов на игровом поле, как их прикажете обсчитывать?
alexeykuzmin0
05.07.2017 17:07Например, можно каждый кадр обновлять лишь те, что видит игрок, а остальные — реже
bormotov
06.07.2017 11:29+1Я еще в школу ходил, игрушки были еще 2D, но люди уже понимали, что «отрисовывать» то, что не видно — нет никакого смысла. Можно сказать не «реже», а «вообще не нужно».
Пытаясь вернуться в контекст статьи — если в коллекции «поле» 30000 объектов, то перед отрисовкой нужно сделать viewField.filter(isVisible()), вдруг в итоге останется вообще один объект, потому что игрок носом уперся в стену.knotri
07.07.2017 08:40viewField.filter(isVisible())
Так это же и будет вызов функции filter на 30 000 элементов.
Я не говорил про отрисовку — я говорил именно про разные проходы (циклы) этих 30 000.
mayorovp
05.07.2017 17:10+4Отказаться от модели "каждый кадр отображаем все объекты" и придумать алгоритм по-лучше.
К примеру, в Factorio где-то посередине ветки .14 однажды отказались от поиска коллизий между конвейером и лежащим на земле предметом при каждом обновлении, и стали явно связывать предмет с конвейером при бросании предмета на землю или при строительстве конвейера.
А в версии .15 вместо хранения координат едущего по конвейеру предмета с обновлением на каждом кадре стали хранить расстояние до следующего предмета на конвейере (или до края конвейера) — такие расстояния надо обновлять только для первого предмета из группы.
Обе этих оптимизации ускоряли игру на несколько порядков ощутимее чем обсуждаемая тут разница между javaFor и javaStream.
Там, кстати, этих предметов в свободной игре во всяческих мега-заводах запросто может 30 тысяч набраться.
vintage
05.07.2017 17:11+2Вам не кажется странным сравнивать функциональщину и императивщину на задачах создания новой коллекции? Сравните на задачах вида "добавление элемента в список" или "сортировка огромных списков". И не забудьте померить потребление и фрагментацию памяти.
Nakosika
05.07.2017 17:38+2В среднем у меня получались в два раза медленнее ява стримы чем императивный код. В узких местах приходится ArrayList как ни крути.
Смешной факт: если не комбинировать потоки а просто возвращать новую коллекцию каждый раз, то скорость будет такая же. Нас накололи, никаких преимуществ по скорости ленивость не дает...
nerumb
05.07.2017 19:46Нас накололи, никаких преимуществ по скорости ленивость не дает...
Для больших коллекций при большом количестве chain преобразований думаю ленивый подход лучше себя покажетNakosika
07.07.2017 21:45+3Я делал бенчмарки, где-то от тысячи элементов начинается незначительный выигрыш. Который зависит от погоды на Марсе. А на маленьких коллекциях стримы в полтора раза медленнее, тк им приходится много лямбд аллоцировать и итераторов.
dougrinch
07.07.2017 21:42+2То-то я думаю как это в колтине цикл медленней. Вроде же одно и то же должно получаться. Так он из-за боксинга проигрывает!
В функциональном варианте компилятор не мудрит и компилирует это как обычный foreach на Integer. А вот в цикле компилятор обманул сам себя. Он видит что цикл по notnullable интам, потому превращает их в Integer.intValue(). После чего, радостно, боксит обратно, чтобы засунуть в result (это ведь ArrayList обычный).
Это еще раз очень наглядно демострирует бессмысленность бенчей без дальнейшего анализа. Ибо разница вообще не циклах. На любой коллекции небоксящихся типов (или боксящихся, но "с вопросиком") разницы вообще нет.
alexeykuzmin0
Пожалуйста, выложите куда-нибудь эти данные таблицами. На графиках много кривых, а масштаб невелик, они сливаются.
ov7a
В посте есть ссылка на csv с результатами: https://pastebin.com/sMsNDDm4
alexeykuzmin0
Упс. Спасибо