Forem: Cody Sehl

How Efficient List Operators Work in Kotlin

Cody Sehl — Sat, 01 Sep 2018 21:16:06 +0000

This post originally prepared for blog.codysehl.net

In the previous post we took a look at whether or not Kotlin's List map, filter, and reduce operators are efficient.

If you haven't read that post, go ahead!

So, we understand that they are in fact not efficient, where the definition of efficient means for a given list, the list is iterated over a small number of times. It turns out that using Kotlin's list operators means a list is iterated once per operator! This was the A loop for every operator method I described.

I proposed a more efficient method called Many Operators, One Loop. That method iterated over the list only once and transformed the list operators into an if statement and a series of inline operations.

What would the Many Operators, One Loop method look like?

In an example from the previous post, I describe a transformation: .filter() would become an if.
Unfortunately, we're not writing a compiler and don't have the ability to transform one bit of code into another - any solution we come up with can only use the tools available in the language.

I've been thinking about this problem since I wrote the previous blog post: How would efficient list operators work?

Let's get specific about what efficient means:

Iterate over the list only once.
Only do work that is necessary - if a map comes after a filter that removes an element from a list, the map shouldn't be run.

How efficient list operators might work

Here's my guess at how efficient list operators work.

List operations performed on a list don't immediately execute, but instead, are saved off somewhere containing the source data and a list of other operations to perform. When you're ready for your data, you ask it to compute your results - maybe with a function called collect.

The collect function is just a loop that, for every element, applies every operation that's been saved off in sequence.
Every operation can return a result or null (or some other empty-type value). If an operation receives a null, it returns immediately and does no work.
At the end, all the non-null values are rounded up into a list and returned.

How efficient list operators actually work

Let's take a look at the source for Sequence.

(Just as before, you probably don't want to follow the links - the files are thousands of lines long.)

Map

The source describes a function that simply returns a TransformingSequence, which is created by passing a source sequence and a transformation function.

Ok!

TransformingSequence

What's a TransformingSequence?

Let's look at its implementation.

Mostly, it's something that implements the behavior of an iterator.

override fun iterator(): Iterator<R> = object : Iterator<R> {
  val iterator = sequence.iterator()
  override fun next(): R {
    return transformer(iterator.next())
  }

  override fun hasNext(): Boolean {
    return iterator.hasNext()
  }
}

Asking this TransformingSequence for its next element will cause it to ask its source sequence for its next element, then apply a given transformation function.

This recursive behavior could go on for a while - interesting!

Filter

How about Filter?

The source describes a function that returns a new FilteringSequence that takes a source sequence, a boolean value¹, and a function that takes an input and returns true or false (a predicate).

FilteringSequence

What's a FilteringSequence?

Let's look at its implementation.

override fun iterator(): Iterator<T> = object : Iterator<T> {
  val iterator = sequence.iterator()
  var nextState: Int = -1 // -1 for unknown, 0 for done, 1 for continue
  var nextItem: T? = null

  private fun calcNext() {
    while (iterator.hasNext()) {
      val item = iterator.next()
      if (predicate(item) == sendWhen) {
        nextItem = item
        nextState = 1
        return
      }
    }
    nextState = 0
  }

  override fun next(): T {
    if (nextState == -1)
      calcNext()
    if (nextState == 0)
      throw NoSuchElementException()
    val result = nextItem
    nextItem = null
    nextState = -1
    @Suppress("UNCHECKED_CAST")
    return result as T
  }

  override fun hasNext(): Boolean {
    if (nextState == -1)
      calcNext()
    return nextState == 1
  }
}

Take a few minutes to read that over and understand it.

FilteringSequence is similar to TransformingSequence in that it the source sequence for a next value, but - here's where it differs! - it'll keep asking until it finds one that satisfies the given predicate! Neat!

Reduce

Finally, let's look at reduce and its source.

public inline fun <S, T : S> Sequence<T>.reduce(operation: (acc: S, T) -> S): S {
  val iterator = this.iterator()
  if (!iterator.hasNext()) throw UnsupportedOperationException("Empty sequence can't be reduced.")
  var accumulator: S = iterator.next()
  while (iterator.hasNext()) {
    accumulator = operation(accumulator, iterator.next())
  }
  return accumulator
}

There's no ReducingSequence!

That's because reduce is a terminal operation. A terminal operation is the last thing done to a Sequence. It transforms the Sequence (which is really just a bunch of potential values, yet to be computed) into actual values that are usable by the rest of a program. In the case of reduce, all the values in a Sequence are squashed down into one value.

As you can see, the implementation of reduce for Sequence looks pretty dang similar to reduce for List, which we covered in the previous post:

public inline fun <S, T : S> Array<out T>.reduce(operation: (acc: S, T) -> S): S {
  if (isEmpty())
    throw UnsupportedOperationException("Empty array can't be reduced.")
  var accumulator: S = this[0]
  for (index in 1..lastIndex) {
    accumulator = operation(accumulator, this[index])
  }
  return accumulator
}

Is Sequence efficient?

After looking at Kotlin's Sequence and implementations of map, filter, and reduce we can see that they satisfy the definition of efficient put forward at the beginning. The implementations above iterate through the list only once, and in the case of filter, only provide a value when the predicate is fulfilled.

My guess at how efficient list operators might work is a bit off from how they're actually implemented - for one, my list concept is replaced with a series of Sequences calling each other - but I think the outlines match up.

Wrapping up

I hope this dive into source code has shown you how fun learning the details can be!

Moreover, I hope you've also noticed that the guesswork solution wasn't enormously far off from the real implementation.

It just goes to show, everyone is capable of solving interesting problems like these, whether you're a whiz creating a programming language or a plebe who just likes to puzzle things out.

Explaining this boolean value inline seemed a bit verbose. I think the docs are clear on what role this parameter plays: If true, values for which the predicate returns true are returned. Otherwise, values for which the predicate returns false are returned. ↩

Are Kotlin List Operators Efficient?

Cody Sehl — Thu, 16 Aug 2018 17:21:58 +0000

This post originally prepared for blog.codysehl.net

Well, that depends on what you mean by efficient!

Let's start by exploring some ways list operators (map, filter, reduce and their ilk) might work.

An example:

val numbers = listOf(1, 2, 3, 4, 5, 6)
val evenNumbers = list.filter { num -> num % 2 == 0 } // 2, 4, 6
val evenNumbersDoubled = evenNumbers.map { num -> num * 2 } // 4, 8, 12
val sum = evenNumbersDoubled.reduce { sum, num -> sum + num } // 24

In this example, we're given a list of numbers, find the even ones, double those, then sum the whole thing.
Each step is broken out into a variable so that every operation has a name.

Here's a more concise version, closer to how this would probably be written in production:

listOf(1, 2, 3, 4, 5, 6)
  .filter { num -> num % 2 == 0 } // 2, 4, 6
  .map { num -> num * 2 } // 4, 8, 12
  .reduce { sum, num -> sum + num } // 24

Given the above, I can conceive of two reasonable ways this code looks under the hood:
(in pseudo-Java for simplicity)

A loop for every operator

list = [1, 2, 3, 4, 5, 6]

// Filter
evenNumbers = []
for(i=0; i<list.length, i++) {
  num = list[i]
  if(num % 2 == 0) {
    evenNumbers.add(num)
  }
}

// Map
evenNumbersDoubled = []
for(i=0; i<evenNumbers.length, i++) {
  num = evenNumbers[i]
  transformedResult = num * 2
  evenNumbersDoubled.add(transformedResult)
}

// Reduce
sum = 0
for(i=0; i<evenNumbersDoubled.length, i++) {
  num = evenNumbersDoubled[i]
  sum = sum + num
}

With this method, the list is iterated over three times.

Many operators, one loop

list = [1, 2, 3, 4, 5, 6]

sum = 0
evenNumbers = []
for(i=0; i<list.length, i++) {
  num = list[i]

  // Filter
  if(num % 2 == 0) {

    // Map
    num = num * 2

    // Reduce
    sum = sum + num
  }
}

With this method, the list is iterated over one time.

Which way does Kotlin do it?

Now that we've established two possible ways list operators could work, which way does Kotlin choose?

Let's look at the source for map, filter, and reduce!

(You probably don't want to follow the links - the files are thousands of lines long.)

Map

The source takes us to _Arrays.kt:8255, which uses mapTo defined on line 8542.

Here's the implementation for mapTo:

public inline fun <T, R, C : MutableCollection<in R>> Array<out T>.mapTo(destination: C, transform: (T) -> R): C {
  for (item in this)
    destination.add(transform(item))
  return destination
}

Filter

The source takes us to _Arrays.kt:3000, which uses filterTo defined on line 3417.

Here's the implementation for filterTo:

public inline fun <T, C : MutableCollection<in T>> Array<out T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
  for (element in this) if (predicate(element)) destination.add(element)
  return destination
}

Reduce

The source takes us to _Arrays.kt:11384.

Note: Reduce does the same thing as Fold, except the initial value of the accumulator is the first element in the given list

Here's the implementation for reduce:

public inline fun <S, T : S> Array<out T>.reduce(operation: (acc: S, T) -> S): S {
  if (isEmpty())
    throw UnsupportedOperationException("Empty array can't be reduced.")
  var accumulator: S = this[0]
  for (index in 1..lastIndex) {
    accumulator = operation(accumulator, this[index])
  }
  return accumulator
}

As we can see, map, filter, and reduce all use the A loop for every operator method, rather than queuing up the operations and using the Many operators, one loop method.

Are Kotlin list operators efficient?

So we're back to our main question - are these operators efficient?
I'll define the word efficient in this context to mean using the Many operators, one loop method.

Then clearly, no! Kotlin list operators are not efficient.

Why not?

Language implementers tend to be pretty sharp folks and it's unlikely they've never thought of the scenario I described above.

Let's partake in some apologetics and think about why Kotlin's list operators were implemented this way - there's probably a reason!

Impure functions

I was talking to my friend Chris Bolin about this question the other day and he mentioned a confounding factor: global variables.

What if your map and filter function write to, then read from a variable defined outside of the scope of the operators? Given the same interface or contract, the result of the operators would change based on their implementation details. Definitely not something you want to have happen!

(Also a description of why functions that can give different answers depending on the state of the world, a.k.a, impure functions, are a bad idea)

They ain't built for efficiency

Perhaps another reason Kotlin's list operators aren't that efficient is because they were never meant to be. As with all things performance related, it's not a problem until it's a problem. Which is to say, until you're in a situation where efficiency matters, who cares how many times you're running a for loop?

Maybe Kotlin has a less efficient list type for small amounts of data, and a different list type for very large amounts of data? Maybe the language implementers made a conscious decision to separate efficient operations into their own special concept?

Next time, we'll take a look at the internals of Sequence - a list type that does just that!