Generic Top

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE

1. Overview

In Kotlin, functions are first-class citizens, so we can pass functions around or return them just like other normal types. However, the representation of these functions at runtime sometimes may cause a few limitations or performance complications.

In this tutorial, first we’re going to enumerate two seemingly unrelated issues about lambdas and generics and then, after introducing Inline Functions, we’ll see how they can address both of those concerns, so let’s get started!

2. Trouble in Paradise

2.1. The Overhead of Lambdas in Kotlin

One of the perks of functions being first-class citizens in Kotlin is that we can pass a piece of behavior to other functions. Passing functions as lambdas let us express our intentions in a more concise and elegant way but that’s only one part of the story.

To explore the dark side of lambdas, let’s reinvent the wheel by declaring an extension function to filter collections:

fun <T> Collection<T>.filter(predicate: (T) -> Boolean): Collection<T> = // Omitted

Now, let’s see how the function above compiles into Java. Focus on the predicate function that is being passed as a parameter:

public static final <T> Collection<T> filter(Collection<T>, kotlin.jvm.functions.Function1<T, Boolean>);

Notice how the predicate is handled by using the Function1 interface?

Now, if we call this in Kotlin:

sampleCollection.filter { it == 1 }

Something similar to the following will be produced to wrap the lambda code:

filter(sampleCollection, new Function1<Integer, Boolean>() {
  @Override
  public Boolean invoke(Integer param) {
    return param == 1;
  }
});

Every time we declare a higher-order function, at least one instance of those special Function* types will be created.

Why does Kotlin do this instead of, say, using invokedynamic like how Java 8 does with lambdas? Simply put, Kotlin goes for Java 6 compatibility, and invokedynamic isn’t available until Java 7.

But this is not the end of it. As we might guess, just creating an instance of a type isn’t enough.

In order to actually perform the operation encapsulated in a Kotlin lambda, the higher-order function – filter in this case – will need to call the special method named invoke on the new instance. The result is more overhead due to the extra call.

So, just to recap, when we’re passing a lambda to a function, the following happens under the hood:

  1. At least one instance of a special type is created and stored in the heap
  2. An extra method call will always happen

One more instance allocation and one more virtual method call doesn’t seem that bad, right?

2.2. Closures

As we saw earlier, when we pass a lambda to a function, an instance of a function type will be created, similar to anonymous inner classes in Java.

Just like with the latter, a lambda expression can access its closure, that is, variables declared in the outer scope. When a lambda captures a variable from its closure, Kotlin stores the variable along with the capturing lambda code.

The extra memory allocations get even worse when a lambda captures a variable: The JVM creates a function type instance on every invocation. For non-capturing lambdas, there will be only one instance, a singleton, of those function types.

How are we so sure about this? Let’s reinvent another wheel by declaring a function to apply a function on each collection element:

fun <T> Collection<T>.each(block: (T) -> Unit) {
    for (e in this) block(e)
}

As silly as it may sound, here we’re gonna multiply each collection element by a random number:

fun main() {
    val numbers = listOf(1, 2, 3, 4, 5)
    val random = random()

    numbers.each { println(random * it) } // capturing the random variable
}

And if we take a peek inside the bytecode using javap:

>> javap -c MainKt
public final class MainKt {
  public static final void main();
    Code:
      // Omitted
      51: new           #29                 // class MainKt$main$1
      54: dup
      55: fload_1
      56: invokespecial #33                 // Method MainKt$main$1."<init>":(F)V
      59: checkcast     #35                 // class kotlin/jvm/functions/Function1
      62: invokestatic  #41                 // Method CollectionsKt.each:(Ljava/util/Collection;Lkotlin/jvm/functions/Function1;)V
      65: return

Then we can spot from index 51 that the JVM creates a new instance of MainKt$main$1 inner class for each invocation. Also, index 56 shows how Kotlin captures the random variable. This means that each captured variable will be passed as constructor arguments, thus generating a memory overhead.

2.3. Type Erasure

When it comes to generics on the JVM, it’s never been a paradise, to begin with! Anyway, Kotlin erases the generic type information at runtime. That is, an instance of a generic class doesn’t preserve its type parameters at runtime.

For example, when declaring a few collections like List<Int> or List<String>, all we have at runtime are just raw Lists. This seems unrelated to the previous issues, as promised, but we’ll see how inline functions are the common solution for both problems.

3. Inline Functions

3.1. Removing the Overhead of Lambdas

When using lambdas, the extra memory allocations and extra virtual method call introduce some runtime overhead. So, if we were executing the same code directly, instead of using lambdas, our implementation would be more efficient.

Do we have to choose between abstraction and efficiency?

As is turns out, with inline functions in Kotlin we can have both! We can write our nice and elegant lambdas, and the compiler generates the inlined and direct code for us. All we have to do is to put an inline on it:

inline fun <T> Collection<T>.each(block: (T) -> Unit) {
    for (e in this) block(e)
}

When using inline functions, the compiler inlines the function body. That is, it substitutes the body directly into places where the function gets called.  By default, the compiler inlines the code for both the function itself and the lambdas passed to it.

For example, The compiler translates:

val numbers = listOf(1, 2, 3, 4, 5)
numbers.each { println(it) }

To something like:

val numbers = listOf(1, 2, 3, 4, 5)
for (number in numbers)
    println(number)

When using inline functions, there is no extra object allocation and no extra virtual method calls.

However, we should not overuse the inline functions, especially for long functions since the inlining may cause the generated code to grow quite a bit.

3.2. No Inline

By default, all lambdas passed to an inline function would be inlined, too. However, we can mark some of the lambdas with the noinline keyword to exclude them from inlining:

inline fun foo(inlined: () -> Unit, noinline notInlined: () -> Unit) { ... }

3.3. Inline Reification

As we saw earlier, Kotlin erases the generic type information at runtime, but for inline functions, we can avoid this limitation. That is, the compiler can reify generic type information for inline functions.

All we have to do is to mark the type parameter with the reified keyword:

inline fun <reified T> Any.isA(): Boolean = this is T

Without inline and reified, the isA function wouldn’t compile, as we thoroughly explain in our Kotlin Generics article.

4. Limitations

Generally, we can inline functions with lambda parameters only if the lambda is either called directly or passed to another inline function. Otherwise, the compiler prevents inlining with a compiler error.

For example, let’s take a look at the replace function in Kotlin standard library:

inline fun CharSequence.replace(regex: Regex, noinline transform: (MatchResult) -> CharSequence): String =
    regex.replace(this, transform) // passing to a normal function

The snippet above passes the lambda, transform, to a normal function, replace, hence the noinline.

5. Conclusion

In this article, we dove into issues with lambda performance and type erasure in Kotlin. Then, after introducing inline functions, we saw how these can address both issues.

However, we should try not to overuse these type of functions, especially when the function body is too large as the generated bytecode size may grow and we may also lose a few JVM optimizations along the way.

As usual, the sample codes are available on our GitHub project, so make sure to check it out!

Generic bottom

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE