Why do I need your permanent collections? They are slow

It happens that when a person starts writing on Kotlin, Scala or %language_name% , he makes manipulations with collections as he used to, as “conveniently”, as “clearer” or even “as quickly”. In this case, of course, cycles and mutable collections are used instead of higher-order functions (such as filter , map , fold , etc.) and immutable collections.

This article is an attempt to convince the orthodox that the use of “this is your functionalism” does not significantly affect productivity. The examples were pieces of code in Java, Scala, and Kotlin, and the JMH microbranking framework was chosen to measure speed.



For those who do not know, JMH ( Java Microbenchmark Harness ) is a relatively young framework in which developers have tried to take into account all the JVM nuances. You can learn more about him from the reports of Aleksey Shipilev (for example, from this ). In my opinion, the easiest way to get to know him is by examples , where all the necessary information is in javadoc.
')
The most interesting part in writing benchmarks was to make the JVM really do something. This clever infection knew the answer to everything beforehand and gave answers for meager time. That is why their source code is prepare to trick the JVM. By the way, Java Streams with the predicted result worked an order of magnitude slower than other methods.

Dicslaimer: everyone knows that it is impossible to write a benchmark correctly, but suggestions for how to write it are less incorrectly welcomed. If it seems to you that you definitely need to consider an example with X, feel free to write in the comments what else you need to test.
In addition, despite the fact that both Kotlin, Scala and Java will be on the same graph, it is not worth comparing the speed of the code in these languages. At least in the examples on Scala there is an overhead of converting scala.Int ⇔ java.lang.Integer and not Java-collections are used, but its own.

The source code of the examples can be viewed on github , and all the results in CSV are here . As the size of the collections, values ​​from 10 to 100,000 were used. I don’t see much point in testing for larger sizes - there is a DBMS and other ways to work with large amounts of data. All graphs are made on a logarithmic scale and show the average operation time in nanoseconds.

Simple map

Let's start with the simplest examples that are in almost every article about elements of functional programming: map , filter , fold and flatMap .

In java looping, converting collections is a bit faster than using the Streams API. Obviously, the point is the overhead of the conversion to stream , which does not justify itself here. In Kotlin, converting using map will be faster than a loop, and even faster than a loop in Java. Why is this happening? We look at the source code of the 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) } 

We get the winnings due to the fact that the final size of the collection is known in advance. Of course, you can do that in Java, but how often do you see this?

In Scala, the difference between the cycle and the map already noticeable. If the Kotlin map fairly straightforwardly converted into a loop, then Scala is not so simple: if the implicit CanBuildFrom is a CanBuildFrom ReusableCBFInstance from the list, then a tricky while is used (those interested can see the source code of the Skal map for the list here ).

Simple filter

In Java, for very small collections, the Stream API is a bit slower than the loop, but again, not significant. If the collection is of a normal size, there is no difference at all.

In Kotlin, there is practically no difference (transparent compilation into a loop), but with large volumes the loop is slightly slower.

In Scala, the situation is similar to Java: on small collections, the functional approach loses a little, on large collections there is no difference.

Simple fold

Not quite a suitable example (because the output is a number), but still quite interesting.

In all three languages, the differences between the iterative form and the functional form are insignificant, although fold in Scala is slower than we would like.

Simple flatMap

Again, the difference between approaches is almost indistinguishable.

Chain of transformations

Let's look at a couple of examples in which complex transformations are performed. I note that a lot of problems can be solved by the combination of filter and map and very long chains are rare.

Moreover, if you still have a long chain of transformations, then it makes sense to switch to lazy calculations (that is, to apply transformations only when necessary). In Kotlin this is a transformation to Sequence , in Scala it is an iterator . Streams in Java are always executed lazily.

Consider the flatMap chain ⇒ filter ⇒ fold :

 someList .flatMap(this::generate) .filter(this::filter) .fold(initialValue(), this::doFold) 

The difference in speed between the imperative approach and the functional one is again quite small. The exception is Scala, in which the functional approach is slower than the cycle, but with the iterator difference is reduced to zero.

Nested conversions chain

Consider the sequence of transformations, where the elements of the intermediate collection are also collections, and on which actions must also be performed. For example, the top 10 of something on some tricky metric:

 someList .groupBy(this::grouping) .mapValues { it.value .filter(this::filter) .map(this::transform) .sum() } .entries .sortedByDescending { it.value } .take(10) .map { it.key } 

Honestly, it was already hard for me to write in the imperative style (you quickly get used to the good; I made two stupid mistakes and confused the variable in one place).

Here the results are already a little more interesting. On collections up to a hundred in size, the difference between the iterative and functional approach has become noticeable. However, in larger collections, the difference can already be neglected. Should you save 10 microseconds of CPU time? Especially if you need to maintain a code like this:

 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; 

Conclusion

In general, it turned out that for all cases the functional approach, if there is a loss, then, in my opinion, it is insignificant. In this case, the code, in my opinion, becomes cleaner and more readable (if we talk about Kotlin, Scala and other languages ​​that initially support the FP), and under the hood there can be useful optimizations.

Do not save on matches: you do not write in assembler, because “so faster”? Indeed, it may turn out faster, and maybe not. Compilers are now smarter than one programmer. Trust the optimization to them, this is their job.

If you are still using some mutableListOf , think about it. First, there are more lines of code and a greater likelihood of making a mistake. Secondly, you may lose the optimizations that will appear in future versions of the language (or are already there). Thirdly, with the functional approach, encapsulation is better: it is simpler to divide filter and map than to break the loop into two. Fourthly, if you already write in a language in which there are elements of the FP and write “cycles”, then you should follow the recommendations and style (for example, Intellij Idea would be strongly recommended to replace for with the appropriate conversion).