Kotlin : Slow List and Lazy Sequence

Came from Java 7 into Kotlin, we are so happy that we could easily have Collection operators on List and chain them together. But little did we know List with it’s iterator is not the best thing still (for some case), there another thing call Sequence.

A little background on List, the hard worker.

Before we get into telling why Sequence is better (in some case), let me tell you something about List.

List is operated with Iterator. It is a very hardworking bunch, where each operation I chain to it, it will ensure it is done.

val list = listOf(1, 2, 3, 4, 5, 6)
list.map{ it * 2 }.filter { it % 3 == 0 }.average()

As you see in the illustration above, for every step, each of the items is processed fully.

To proof this, let’s log out something

val list = listOf(1, 2, 3, 4, 5, 6)
val result = list
.map{ println("In Map"); it * 2 }
.filter { println("In Filter");it % 3 == 0 }
println("Before Average")
println(result.average())

The result will be as below

In Map
In Map
In Map
In Map
In Map
In Map
In Filter
In Filter
In Filter
In Filter
In Filter
In Filter
Before Average
9.0

Well, nice. Hardworking, and complete all the process.

The lazy guy, Sequence…

Okay, now let’s change the code by adding asSequence() to make the List a Sequence instead.

val list = listOf(1, 2, 3, 4, 5, 6)
val result = list.asSequence()
.map{ println("In Map"); it * 2 }
.filter { println("In Filter");it % 3 == 0 }
println("Before Average")
println(result.average())

Let’s see the result

Before Average
In Map
In Filter
In Map
In Filter
In Map
In Filter
In Map
In Filter
In Map
In Filter
In Map
In Filter
9.0

Wow, interesting… Notice the Before First is now printed first. In another word, if I don’t call average(), nothing is done for the Sequence.

It is lazy, doesn’t want to do any work, until a Terminal is connected to it. A Terminal is like an operation that will result something e.g. sum, average, first, etc…. and even toList which is use to convert the Sequence into List.

Besides that, you notice it interleave the In Map and In Filter. This means it is passing the item one by one through the chain lazily until it reach the Terminal i.e. Average operation, before passing the next one.

Well, so what’s so good about Sequence?

If you think about if, imagine if you like to get the first element of the processed item.

Let’s look at List

val list = listOf(1, 2, 3, 4, 5, 6)
val result = list
.map{ println("In Map $it"); it * 2 }
.filter { println("In Filter $it");it % 3 == 0 }
println(result.first())

The result is as following

In Map 1
In Map 2
In Map 3
In Map 4
In Map 5
In Map 6
In Filter 2
In Filter 4
In Filter 6
In Filter 8
In Filter 10
In Filter 12
6

All together 13 lines, which means 13 operations.

Let’s look at Sequence

val sequence = sequenceOf(1, 2, 3, 4, 5, 6)
val result = sequence
.map{ println("In Map $it"); it * 2 }
.filter { println("In Filter $it");it % 3 == 0 }
println(result.first())

The result is

In Map 1
In Filter 2
In Map 2
In Filter 4
In Map 3
In Filter 6
6

Only 7lines i.e. 7 operations. This means the moment it found the first elements, it terminate the entire process.

As you could imagine, this will speed up the process.

Is the speed up only apply to first()?

Well, let’s do a few experiments.

Experimenting on Map operation.

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Map Sum= "
+ measureNanoTime { list.map { it * 2 }.sum() })
println("Sequence Map Sum "
+ measureNanoTime { sequence.map { it * 2 }.sum() })

println("List Map Average "
+ measureNanoTime { list.map { it * 2 }.average() })
println("Sequence Map Average "
+ measureNanoTime { sequence.map { it * 2 }.average() })

The result

List Map Sum 14727907362
Sequence Map Sum 2074397969
List Map Average 11460520785
Sequence Map Average 3268960487
  • List is taking 14.7s for the Map:Sum, and 11.5s for Map:Average.
  • Sequence is taking 2.1s for Map:Sum, and 3.3s for Map:Average.

Looks like when there’s a Map operation in front, Sequence is resulting faster performance than List. Perhaps it doesn’t require the intermediate storage of Map result, like List does, hence result in faster operation.

Experimenting on Filter operation.

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Filter Sum "
+ measureNanoTime { list.filter { it % 3 == 0 }.sum() })
println("Sequence Filter Sum "
+ measureNanoTime { sequence.filter { it % 3 == 0 }.sum() })

println("List Filter Average "
+ measureNanoTime { list.filter { it % 3 == 0 }.average() })
println("Sequence Filter Average "
+ measureNanoTime { sequence.filter { it % 3 == 0 }.average() })

The result

List Filter Sum 506351694
Sequence Filter Sum 873175271
List Filter Average 391790033
Sequence Filter Average 838510968
  • List is taking 0.5s for the Filter:Sum, and 0.4s for Filter:Average.
  • Sequence is taking 0.9s for Filter:Sum, and 0.8s for Filter:Average.

For Filter operation in front, Sequence is resulting slower performance than List. Deep dive into the function, looks like the Filter operation of Sequence has more overhead of checking some state, while the Filter of List is a simple if check and collect the new items.

Experimenting on Map and Filter operations.

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Map Filter Sum\t\t " + measureNanoTime {
list.map { it * 2 }.filter { it % 3 == 0 }.sum() })
println("Sequence Map Filter Sum\t " + measureNanoTime {
sequence.map { it * 2 }.filter { it % 3 == 0 }.sum() })

println("List Map Filter Average\t\t " + measureNanoTime {
list.map { it * 2 }.filter { it % 3 == 0 }.average() })
println("Sequence Map Filter Average\t " + measureNanoTime {
sequence.map { it * 2 }.filter { it % 3 == 0 }.average() })

The result

List Map Filter Sum 34845242323
Sequence Map Filter Sum 2820436086
List Map Filter Average 2328258876
Sequence Map Filter Average 18618444560
  • List is taking 34.8s for the Map:Filter:Sum, while 2.3s for Map:Filter:Average.
  • Sequence is taking 2.8s for Map:Filter:Sum, while 18.6s for Map:Filter:Average.

A relatively surprising result, as the for Map:Filter:Sum, Sequence is much faster than List, while Map:Filter:Average, List is much faster than Sequence.

Experimenting on direct Sequence/List.

val sequence = generateSequence(1) { it + 1 }.take(50000000)
val list = sequence.toList()

println("List Sum " + measureNanoTime { list.sum() })
println("Sequence Sum " + measureNanoTime { sequence.sum() })

println("List Average " + measureNanoTime { list.average() })
println("Sequence Average " + measureNanoTime { sequence.average() })

The result

List Sum 91726022
Sequence Sum 592771887
List Average 101141460
Sequence Average 622616340
  • List is taking 0.1s for the Sum, while 0.1s for Average.
  • Sequence is taking 0.5s for Sum, while 0.6s for Average.

Without any operations, clearly List is faster than Sequence.

In Summary

  • When no operation needed, use List
  • When there’s Map operation only, use Sequence
  • When there’s Filter operation only, use List
  • If it ends with First, use Sequence.
  • For a combination of the operators, or other operators that are not mentioned here, do experiment out using measureNanoTime.

I don’t think I have a very good conclusive summary. If you have one that is better way to determined when to use which, let me know.


I hope you appreciate this post and it’s helpful for you.

You could check out my other interesting topics here.

Follow me on medium, Twitter or Facebook for little tips and learning on Android, Kotlin etc related topics. ~Elye~