I have been thinking about replacing some chains of things where the source is a list and the final result is a list as well to avoid copying over large collections in each step.
So, from e.g. .flatten().map { ... }
to .asSequence().flatten().map { ... }.toList()
The latter avoids intermediate copying of the collection but there may be a performance overhead of using a sequence at all. So I tested it with a collection of 10000 elements, specifically with something I can flatten (because this is my particular use case right now).
import kotlin.random.Random
import kotlin.system.measureTimeMillis
fun main() {
val map = mutableMapOf<Long, List<Int>>()
for (i in 0..100000) {
map[Random.nextLong()] = IntArray(Random.nextInt() % 2 + 1) { Random.nextInt() }.toList()
}
// 1x iterate sequence, 1x copy
val sequenceTime = measureTimeMillis {
map.values.asSequence().flatten().map { it % 100 }.toList()
}
println("Sequence time: $sequenceTime")
// 2x copy
val copyTime = measureTimeMillis {
map.values.flatten().map { it % 100 }
}
println("Copy time: $copyTime")
}
The result seems to be that it doesn’t really make a substantial difference or that using a sequence is actually slower. How is that? Or am I doing something wrong?
I think there is a common misconception that sequences are “just faster”. Depending on the case they could be faster or they could be slower.
As you said yourself, sequences involves additional overhead. Operators pass items between them which requires a lot of function calls. Operations on collections are simpler to implement and they are fully inlined.
Some collection operators like map() know the size of the resulting collection upfront, so they can reserve a specific amount of space. Sequences can’t do that. You are concerned about just a single data copying, but remember that if you create an empty list and add 1000 items to it, you actually copy the data 12 times just to grow the list (but not all items for each grow).
There are use cases when sequences are a clear winner. Most importantly, if the data is too big to keep it all in the memory at once. Or if we operate on lazily generated and possibly infinite sequences. Intuition tells me that e.g. flatMap() followed by filter() that ignores most of items should be also faster with sequences, but I’m not sure about this. But generally speaking: no, sequences are not faster.
Also, there is a very interesting topic here on what kind of optimizations we could add to the language to overcome current performance problems of sequences and get advantages of both worlds.
P.S.
You can’t really measure the performance in Java like this. It gives almost meaningless results. Use JMH instead.
Just wanted to bring more attention to the failures of micro benchmarks like this. You should at least run your tests multiple times within a single JVM run. For small tests like this, if you change the order of your tests, then it will likely show the opposite results.
Not just multiple times, but a large number of times. JVMs can judge whether to compile methods, and how much effort to expend in optimising them, on the number of times they’re called — you could see improvements that kick in even after many tens of thousands of times.
Microbenchmarks have other problems, too. Often they’re set up on toy problems that aren’t representative of real-world use — and which the JVM can optimise more than usual as a result. (In extreme cases, the JVM might optimise entire loops out of existence if they have no lasting effect or it can be calculated outside.) And if the problems are too small, you can end up measuring memory locality effects or machine loading or anything else that has a bigger effect on timing than the little code you’re trying to test.
Microbenchmarks are hard to get right… At the very least, use an existing framework, which will avoid some of the more egregious problems. But it’s far better to check a real-world problem in situ if you can.