Does Kotlin optimize the `while (true) { when (state) { ... } }` pattern?


#1

Many compilers, primarily native ones like GCC, Clang, and Rust, attempt to optimize immediate state machines like this into simple gotos where possible:

enum class Foo { ... }

Foo state = Foo::Start
while (true) {
    switch (state) {
    // ...
    }
}

Does Kotlin make a similar optimization for this, or does it actually generate a table switch?

enum class Foo { ... }

var state = Foo.Start
while (true) {
    when (state) {
        // ...
    }
}

#2

Taking into account the fact that there is no goto statement in Java I don’t think the Kotlin compiler optimizes it the way you say, at least on Kotlin JVM, maybe the Kotlin Native compiler does.

Anyway you can check it yourself if you’re using IntelliJ by going to Tools → Kotlin → Show Kotlin Bytecode, and then clicking decompile.


#3

When enum value used in when statement, Kotlin compiler actually generates TABLESWITCH JVM instruction, so it can be seen as kind of “goto”.


#4

there is actually GOTO in bytecode, but kotlin should not bother itself with such optimizations (at least in the JVM platform) as the JIT compiler will take care of them.


#5

Looking at the decompiled bytecode won’t always help, especially with optimization questions like this. Java bytecode can have gotos, and decompiling them will try to approximate equivalent Java code from which it is not necessarily apparent what kind of optimizations happened in the bytecode.


#6

Well in that case just don’t hit decompile and just look at the bytecode :wink:


#7

Fair point, but I was replying to the explicit suggestion to look at the decompiled bytecode :stuck_out_tongue:
But on a serious not, lots of people (myself included) are not fluid enough in JVM bytecode to judge things like this.


#8

But in that case I think worrying to much about optimizations like this is not necessary anyways. If you don’t know enough about bytecode to look for optimizations like this, you probably don’t even know that they exist (so you would not worry).


#9

If you look at the java bytecode generated by javac you will find that it is very limited in its optimization. Optimization is left entirely to the JIT to the point that even obvious things like dead code elimination are not done. The Kotlin compiler works from the same perspective even though it has a few extra optimizations. A case could be made for more optimizations in the Kotlin compiler (as Kotlin bytecode is not entirely the same as that generated by javac and the JIT may not recognize all patterns), but as the JIT generally does a good enough job and the resources in the compiler team are limited it is not a top priority.


#10

How could it optimize away the table switch when state is a var and Kotlin does not try to determine if vars are not changed? The only way it could make that optimization is if state were a val. Not sure it does make the optimization and not interested enough to go see.

I will note that Kotlin originally did not even optimize away conditionals based on constant expressions until 1.1.2 I believe it was.


#11

It could be optimized into a series of static GOTOs when all assignments are local, like what GCC does for C. It’s a complex optimization to do, but it’s possible, and it enables local state machines to be encoded as a while (true) { when (state) { ... } } with near-zero cost, much like how coroutines are encoded. It’s also not as prone to branch prediction issues, since computed jumps are usually either highly predictable (think: dynamic method dispatch) or highly unpredictable, which is usually the case here.

This pattern is only mainly used by parsers, which gain a lot from simplified, more predictable (unconditional) branching that CPUs like. If the JIT can also perform this optimization, that’s great, but I’m not 100% sure if Android can, and it’s not common for JITs to detect this kind of pattern, especially when they don’t have a tableswitch instruction and they don’t know to manufacture one from a series of if/else statements comparing against constants.

It can be detected by checking that:

  1. The loop only contains the minimal code for performing a table switch.
  2. The table switch variable is a local stack operand, not an object member or global variable (important - it could get changed otherwise).

Assuming both of these are true, each case that sets the variable to a static enum value can just jump to that case at the end of the break. If the assignment is conditional, you could either store the condition result and test it later, or you could test the variable locally before branching to avoid the whole table switch.

But this is a sometimes non-trivial level of static analysis, especially when it’s compiled to a sequence of if/else comparisons instead of treated as a simple table switch.