Declarative Kotlin: Lists, Sequences and RxJava

One of the reasons we love Kotlin is because it has such a rich standard library for Collections. Once you discover map, filter, flatMap and so on, it is really hard to go back to using loops.

Often code readability is the reason we adopt the declarative approach, although of course when performance is crucial we might choose the imperative way.

Before my Kotlin days, I often used RxJava 1 to write my list transformation code. In my team we had fun discussions about whether my code was an overkill:

Observable.from(text.split(SEPARATOR))
  .map(line -> line.trim() + NEW_LINE)
  .toList()
  .toBlocking()
  .single()

Fortunately, with the Kotlin standard library, this code can be simplified:

text.split(SEPARATOR)
  .map { it.trim() + NEW_LINE }

The question remains, though: how does RxJava 2 performance compare to Kotlin’s standard library?

You might think that the Kotlin standard library would be a clear winner, but that’s not always the case.

Simple Case

First, let’s have baseline comparison between Kotlin’s List and RxJava 2.

RxJava:

Observable.range(0, 1_000_000)
  .map { it + 1 }
  .blockingLast() // 863ms

Kotlin List:

(1..1_000_000)
  .map { it + 1 }
  .last() // 755ms

Kotlin is 14% faster.

Multiple Operations

What would happen when we would increase the number of operations?

RxJava:

Observable.range(0, 1_000_000)
  .map { it + 1 }
  .map { it + 1 }
  .map { it + 1 }
  .map { it + 1 }
  .map { it + 1 }
  .blockingLast() // 2843ms

Kotlin List:

(1..1_000_000)
  .map { it + 1 }
  .map { it + 1 }
  .map { it + 1 }
  .map { it + 1 }
  .map { it + 1 }
  .last() // 3439ms

No one would write this kind of code, but here I would like to demonstrate the case when we chain multiple map operations together.

To our surprise, RxJava is 20% faster than the Kotlin’s List.

Additionally, when using Android Profiler, the List solution required memory 40MB memory, whereas for RxJava the memory influence was barely noticeable (< 100 KB).

Kotlin compiler for each List’s map creates a new loop, so we loop the list five times, each time adding 1 to the item.

RxJava uses Operator Fusion which goes through all the items in one go and adds 1 as many times as there are map operations.

Unnecessary Work

Sometimes it’s not necessary to process every single item in the list.

RxJava:

Observable.range(0, 1_000_000)
  .map { it + 1 }
  .blockingFirst() // 104ms

Kotlin List:

(1..1_000_000)
  .map { it + 1 }
  .first() // 678ms

Here Rx is 651% faster!

In this case, the Kotlin code works similarly, but there is a big difference in the Rx code.

Rx knows that it is requested only the first item, so there is no use to calculate values for the others. There is no need to process other items.

Sequence to the rescue!

Thankfully, Kotlin provides us with a better solution — Sequences.

If you are not familiar with the concept, Sequences are similar to Iterable from Java as they are evaluated lazily, but have a similar interface as Kotlin’s List.

To use Sequence instead of List you just need to use the asSequence() method. The previous examples can be written like this:

(1..1_000_000)
  .asSequence()
  .map { it + 1 }
  .last()

Sequence does come with a price — every time you iterate a Sequence, it will recalculate each element. Items in Lists, on the other hand, are stored in the memory, so after the initial calculation, you can iterate over them without further performance penalty.

You should avoid passing or returning Sequences from your functions as other users of the function might iterate over the Sequences multiple times which is wasteful!

Use Sequence when you work with a large number of items and convert to a list if you want to pass it over.

Here is time comparison of the performance and how much faster are different approaches:

Not JITed benchmark

EDIT:

As Dávid Karnok mentioned the comments, JIT-ing the code is really important for benchmarking, that is why running the tests multiple times is crucial.

Even thou I’ve run my previous benchmark code multiple times, it was not enough to JIT it. The new version of the tests (thanks David for that!) yields the benefits of JIT compilation:

JITed benchmark

This time I’ve added IxJava library for comparison — if you can only use Java 1.6, IxJava is a great alternative for declarative list transformation!

The Unnecessary work example gets such a big performance boost after JIT compilation, that I had to put it in a different graph:

Unnecessary Work benchmark

Notice that the time scale here is in microseconds (μs)! List took almost 0.5s whereas Sequence need only 0.000043s!

As Android developers we were not used to processing lists in a declarative way, now we have the tools to do that. The interface of List and Sequence is so similar, developers might think that it does not matter which one to use.

Now you know better 😉!

If you are interested in a more pragmatic knowledge about when to use Sequences, check out my other post.

I would like to thank Peter Tackage for moderating and being patient with my blog posts!