Measuring sequences
Let’s look under the hood and understand how sequences work and how we get performance benefits.
I conduct a significant number of technical interviews for Android (over 100 per year). Based on my interview experience, I have observed that the vast majority of developers are hesitant to use sequences in their work because they do not understand how they work. Most importantly, they lack an understanding of when sequences provide benefits and when they do not.
There is no clear information about this anywhere on the web (at least I haven’t found it). Everywhere only general phrases are given, without description of specific cases and numbers.
Meanwhile, there is a rather controversial detect rule that states.
CouldBeSequence: Use sequences if your collection transformation have more than 3 operations
Since I have a good understanding of Kotlin’s internal code, I realize that this rule is not exactly correct. I wanted to fix this gap and decided to do a little research on the performance of sequences. My goal is to understand when using sequences provides performance benefits and when it can lead to disadvantages. I wanted to approach this from both a mathematical and engineering perspective and get concrete numbers cases.
Results of the research
For those who prefer to get answers right away, I present the final results of my investigation in the article headline.
Performance lose
Sequence functions that result in guaranteed performance loss. All of these functions are computationally intensive, so it doesn’t matter how many transformations you use. If there is at least one of these functions among them, you are guaranteed to lose.
- sort - heavy operation with data copying and huge losses
- flatten - heavy operation and significant losses
- plus - a significant loss, since it is based on flatten
Light loss of performance
Functions in sequences that result in a slight performance drawback, but it can be offset by other transformation functions.
- distinct - a small loss that will be corrected in kotlin 2.0 (there will be a separate article on performance improvements for distinct in Kotlin 2.0)
- chunked - an easy operation with little loss
Performance gain
All other sequence functions will indeed give gains starting as early as two transformations of the collection.
Conclusions
The CouldBeSequence rule would be accurate if one of the heavy functions is not used in your collection transformation: sort, flatten, plus
In principle, you have learnt everything you need for your work. However, if you want to delve into how sequences work internally and see detailed measurement results and analysis, welcome to the amazing world of sequences. Ahead, there will be a lot of code and measurements.
To understand the benefits we can derive from using sequences, let’s first delve into the theory.
Measurement methodology
I used the Jetpack Benchmark for the measurements. All measurements were performed on a rooted device at a fixed clock frequency. Each test run executed the tested function approximately 50 times. For each function, I performed 100 test runs and took the median result based on the minimum values.
To understand in which cases sequences outperform regular collections, we need to compare a regular collection transformation function with a sequences function. However, we can’t compare them directly because with sequences, we start to gain benefits from avoiding copying intermediate results until the second transformation.
Therefore, I developed the following methodology. I did a comparison test between two transformations using the map function as the baseline, which provides an equilibrium state where neither side gains nor loses. Then, I simply replaced the second map transformation with the function being tested.
Overall, this approach provided reasonable and reproducible results that align well with theoretical expectations.
It is important to note that the absolute values are specific to my device. On other devices, the numbers may be different, but the percentage ratios should be similar.
Measuring the map function
Measuring 2 map
benchmarkRule.measureRepeated {
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.toList()
}
As you can see in this test, there are no clear winners or losers. With an increasing number of elements, sequences show a slight advantage, but it falls within the range of statistical error.
Now let’s try adding one more transformation to evaluate how it affects the results. In theory, each additional transformation should provide a performance boost.
Measuring 3 map
benchmarkRule.measureRepeated {
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.map { it + 3 }
.toList()
}
It is clear that the results align well with the theory. We immediately gained a noticeable improvement of 15–20% upon adding the additional transformation.
Let’s check how the performance will grow if we add more transformations.
Measuring 5 map
benchmarkRule.measureRepeated {
sourceCollection.asSequence()
.map { it + 1 }
.map { it + 2 }
.map { it + 3 }
.map { it + 4 }
.map { it + 5 }
.toList()
}
Our performance gain has further increased and now stands at an impressive 27–30%.
Measuring the sort function
sourceCollection.asSequence()
.map { it + 1 }
.sortedByDescending { it }
.toList()
As you can see, sequences perform poorly with sorting operations, resulting in a performance loss of about 10%. However, it is important to understand that this small percentage loss is actually significant because sorting is a computationally intensive operation.
This becomes evident when comparing the execution time of sorting with the map function. The difference in time is orders of magnitude.
- map = 54 838 584 ns
- sort = 711 287 875 ns
So, you will not be able to offset the performance loss from the sort function by adding additional transformations. The benefit gained from those transformations will be much smaller compared to the loss incurred from the sort function.
For those who are interested, please open link to learn how the sort function works under the hood
Measuring the filter function
During my research, I encountered a phenomenon where certain sequence functions exhibited varying performance in complex transformations. At first, I couldn’t understand or explain this effect. However, I eventually identified a clear pattern, and I will explain the cause of its occurrence in more detail shortly.
This pattern applies to all sequence functions that modify the number of elements in the original set such as filter, distinct, take, drop, minus.
Best case — It is when the function returns a smaller subset of the original collection, resulting in a larger performance gain compared to regular collections.
Worst case — It is when the function returns a significant portion of the original set, causing the performance gain to decrease and approach zero.
Therefore, for such functions, I will provide two tests for the best and worst case scenarios. For the best case, I will consider returning 10% of the original set of elements. For the worst case, I will consider returning 90% of the original set of elements.
Best case
sourceCollection.asSequence()
.map { it + 1 }
.filter { it in 0..precent_10 }
.toList()
As you can see, in the best-case scenario, the filter function provides a performance gain of approximately 25%-30%.
Worst case
sourceCollection.asSequence()
.map { it + 1 }
.filter { it in 0..precent_90 }
.toList()
In the worst-case scenario, our performance gain approaches zero and ranges from 2% to 4%.
For those who are interested, please open link to learn how the sequence decorator for the filter function works. Your reward will be an explanation of the dependency of performance on the number of returned elements.
Measuring the distinct function
Retains only the unique elements in the sequence.
Best case
sourceCollection.asSequence()
.map { it * 10 / 100 }
.distinctBy { it }
.toList()
As you can see, in the best-case scenario, distinct outperforms regular collections, achieving a performance gain of 10%-15%.
Worst case
sourceCollection.asSequence()
.map { it * 90 / 100 }
.distinctBy { it }
.toList()
In the worst case scenario, distinct performs worse than regular collections, with a significant -15% performance loss.
Off-topic: In reality, things are not so bleak, and in the upcoming Kotlin 2.0 version, this issue has already been fixed. I will have a separate article on this.
How is the distinct decorator implemented? For those who are interested, please open the hood.
Measuring the take function
Take the first N elements of the sequence.
Best case
sourceCollection.asSequence()
.map { it + 1 }
.take { countPercent_10 }
.toList()
As you can see, there is a significant advantage for sequences over regular collections in the take function, with a performance gain of almost 90%.
Worst case
sourceCollection.asSequence()
.map { it + 1 }
.take { countPercent_90 }
.toList()
In the worst-case scenario, the take function also has a significant performance gain of 20%-25%, but it is three times smaller compared to the best-case scenario.
Measuring the drop function
Skips the first N elements of the sequence.
Best case
sourceCollection.asSequence()
.map { it + 1 }
.drop { countPercent_90 }
.toList()
The drop function outperforms regular collections in the best-case scenario, with a performance gain of 30%-35%.
Worst case
sourceCollection.asSequence()
.map { it + 1 }
.drop { countPercent_10 }
.toList()
In the worst-case scenario, the drop function still outperforms regular collections, with a performance gain of 6%-10%.
Now let’s take a look at how the drop decorator is implemented
If the take and drop functions are so similar, why do they produce such different results?
If we compare the measurement results of take and drop, we will see that `take` provides a much larger performance gain. However, it is interesting to note that the code of these functions is nearly identical, like identical twins.
Actually, it is quite simple. The difference lies in the fact that the take function takes the first N elements and then stops iterating through the list, as its iterator starts returning false in hasNext().
In the case of the drop function, it is a bit more complex. In order to skip the first N elements, the drop function needs to call the next() method on them. As a result, all transformation functions that come before drop will still be executed for these elements. Therefore, even though we are skipping the elements and do not need them, we still have to perform all the work to retrieve each element.
Measuring the flatten function
Flattens a list of lists into a single linear list. In the test, a list is used consisting of N elements, each of which contains an internal list of 10 elements.
fun flatten_sequence(sourceCollection: List<List<Int>>): List<Int> {
return sourceCollection.asSequence()
.map { it }
.flatten()
.toList()
}
The results for flatten are indeed disappointing, with a -180% performance loss. It is also important to understand that flatten is a computationally intensive operation, as evidenced by the absolute execution time of the function.
Now let’s explore how flatten is implemented and how it works under the hood.
Measuring the plus function
Adds two sequences
fun flatten_sequence(sourceCollection: List<List<Int>>): List<Int> {
return sourceCollection.asSequence()
.map { it }
.plus(sourceCollection)
.toList()
}
The plus measurement results are similar to the flatten results because the plus function is based on flatten. Loss -170%
Implementation of the plus function
This is no longer a decorator but a function based on the flatten decorator. It is quite simple and there is not much to comment on. It simply creates a sequence from two sequences and applies the flatten
public operator fun <T> Sequence<T>.plus(elements: Iterable<T>): Sequence<T> {
return sequenceOf(this, elements.asSequence()).flatten()
}Measuring the minus function
Subtracts one sequence from another
Best case
sourceCollection.asSequence()
.map { it }
.minus(minusCollection_90perc)
.toList()
In the best case, the minus function gives a small gain of 6% — 15%
Worst case
sourceCollection.asSequence()
.map { it }
.minus(minusCollection_10perc)
.toList()
In the worst-case scenario, the minus function can be considered neutral, with a slight performance loss of -4% to -8% as the number of elements increases. However, it’s important to note that minus is a relatively lightweight operation, and the performance loss in the worst-case scenario can be offset by other transformation functions.
To understand how the minus function works under the hood, let’s take a look at its implementation
Measuring the zip function
Merging the elements of two sequences. Essentially, it is similar to the combine operation in Flow and the zip operation in RxJava.
return sourceCollection.asSequence()
.map { it + 1 }
.zip(sourceCollection.asSequence()) { v1, v2 ->
v1 + v2
}
.toList()
The zip function has a slight performance gain of 5% to 10% compared to regular collections.
To understand how zip works under the hood, let’s take a look at its implementation
Measuring the chunked function
Flattens a long list into a list of sublists. Essentially, it returns the long list in chunks of N elements at a time.
sourceCollection.asSequence()
.map { it }
.chunked(100)
.toList()
The chunked function has a slight performance loss compared to regular collections, but it is a lightweight operation. Therefore, the performance loss from chunked can be easily offset by other transformation functions.
Measuring the groupBy function
Groups the sequence based on a given criterion and returns a map where the keys represent the grouping criteria and the values represent the elements corresponding to each key.
sourceCollection.asSequence()
.map { it }
.groupBy { it * 10 / 100 }
.toList()
As you can see, the groupBy function provides a performance gain of 10% to 15%.
If you want to guess a little riddle, take a look under the hood.
Measuring other sequences functions
All sequence functions can be divided into two main groups:
Iterator decorators, which are the core of the sequence mechanism. In my research, I have examined and measured all the iterator decorators.
Derivative functions, which are built on top of the base decorators. Since these functions operate on top of the existing decorators, their performance depends directly on their base decorators.
There is no point in measuring all of them, since they will show the same results as the basic decorators. You can see this in the examples of the derived functions: plus, minus, distinct.
The same functions that don’t use basic decorators at all will always outperform collections. Examples of such functions: groupBy, associateBy, fold
Conclusions
Thanks to everyone who read to the end. I really hope that I was able to show and clearly explain how sequences work under the hood.
As of now, there are three heavy functions in sequences: sort, flatten, and plus. Attempting to use these functions in sequences can significantly impact performance. If you need to use them in your transformations, it is better to stick to standard collections.
In all other cases, if your transformation involves more than two functions, you can confidently use sequences. You won’t lose and you may even gain some performance benefits.
I intentionally did not include the distinct function in the list of heavy functions because I have optimized it, and my optimizations have already been incorporated into Kotlin and will be released with Kotlin version 2.0.
I write more about this in my article “Sequence optimizations”.
