https://kotlinlang.org
Join Slack
I’ve heard a rumor that the `when` statement can evaluate its cases in constant time, because the co...
# announcements
g
I’ve heard a rumor that the 
when
statement can evaluate its cases in constant time, because the compiler will change the switch structure to a map. Does anyone know if this is true?
m
when
cases can be super complex. Some cases can be optimized, like having only 
Int
and 
String
cases.
g
I have a feeling the rumor is false partly for that reason — most likely developers want the option to short circuit some logic, some cases should never have to run, esp if they are long and blocking
it would cool though if there was a compiler plugin to allow the optimization in that rumor with an annotation or something
m
I’m not sure what kind of optimization you are talking about. Do you have an example 
when
?
g
Imagine a when statement with a million 
Int
cases for example. If the compiler replaced it with a map, the entire when statement can be evaluated instantly, whereas a typical switch structure would have to evaluate in linear time in the worst case.
Super contrived example, but imagine a project that makes heavy use of a single when block with a lot of cases that can sacrifice some memory for speed (cough, redux apps). This would be useful I think.
m
I think that’s already optimized on JVM with a switchmap internally.
n
when you say "instantly" I assume you just mean "in constant time"
the thing is that hash table lookups are pretty expensive, so you'd need quite a lot of cases for that to be worthwhile, may not be as sexy as it seems
the most common case where this happens in compiled languages is when you have a contiguous range of integers, and then you can just change it into a jump table
surprisingly even that is not worth it if you have less than I think 4-5 options
k
I don't think bytecode spec will even allow a class with a "million cases" to fit into the various 65K limitations.
g
There are plenty of usecases for this optimization for Kotlin frontends using unidirectional patterns. An example of a 
when
that could easily grow in size to 10+ cases for a particular feature in an Android app: https://github.com/grant-park/ReduxEngineSampleProject/blob/master/app/src/main/ja[…]i/grant/reduxenginesampleproject/model/reducers/NotesReducer.kt
k
You jumped from million down to 10+...
g
The “million” was just for illustration when I was explaining what I was talking about haha
In reality, the frontends I work with just loop through multiple series of 
when
statements at a time on a single thread, so we are probably looking at 50 cases at most. That is still a lot of iterations before rendering something on a screen.
It would be nice to even only apply this optimization for sealed classes…
n
for 10 cases, it's extremely unlikely a hash table is better
at N = 10 linear search will beat everything, except a jump table
maybe about tied; looking at some benchjmarks online
hard to say though, especially consider the secondary effects of creating a hash table, possible code bloat, reducing inlining, etc
at 50 yes
g
I can imagine real world use cases reaching even 1-3k cases.
If you are familiar with redux, that is an unacceptable amount of iterations per render loop.
but alas, states can get arbitrarily heavy
n
1-3K i assume would have to be the result of codegen
but once you get to these number of cases, it seems to make more sense to me to just have a hash table of key -> function anyway
and then you can control the data structure exactly as you want
m
HashMap
in JVM is incredibly fast. Creating a 
HashMap
is not though.
g
Not at all, you can have thousands of employees working on individual features for one frontend.
Such a simple optimization could make certain architectures possible.
n
any architecture where you have a when like that over thousands of cases seems pretty dubious
the same comment stands in any case
g
That is opinion 🙂
n
yes, it is 🙂 but one based on large scale consensus
anyway, not going to argue
like I said, if you want a hash table behavior, you can just use a hash map, not sure what the issue is
this is the same pattern that's used when you have a polymorphic factory, usually if you have more than a handful of derived classes you want to switch from a single centralized when, to some kind of factory that you register your derived with
g
I only say that it would be nice to have a compiler plugin out there.
It is as arbitrary as many of the other plugins available that do things we could perform with the language itself. It’s just a matter of convenience for developers like me 🙂
n
🤷 i feel like even if it existed, I would prefer a hash table of string to function as it's literally a more robust solution
g
gotcha, well we live in different worlds what can I say haha
n
possibly I'm missing something about your specific case. in the situations I've encountered a when with a thousand cases would be pretty brittle compared to a Map of functions
Can you explain what the downside of a Map of functions is?
g
thats reasonable to say
I don’t expect this to apply to a single 
when
with a thousand cases
more realistically a multitude of `when`s with much smaller amounts of cases
downside of a Map is that it is less semantically intuitive than a 
when
I think I would be abhorred by a map of several functions over a 
when
when walking into a codebase. I would flag that in a code review and ask why not use a simpler construct?
m
btw, the compiler becomes super slow when you have a lot of (nested) 
when
cases. I guess due to type inference. I had to split up my generated code into multiple functions. https://raw.githubusercontent.com/fluidsonic/fluid-i18n/master/modules/data-regions/sources/common/RegionNames_normal.generated.kt
(~30 minutes build time -> seconds)
g
excellent experiment 👏 how is the runtime?
m
super fast. nanoseconds
no, microseconds
us 😄
g
I think you had mentioned something about the interal jvm implementation using a switchmap
if its microseconds, that’s probably the case right? do you have any more info on that tidbit?
n
well, it really depends how big the 
when
is, if its 4 cases, then yes, I'd agree the Map is weird. But Map is already a super standard technique for many situations over a when, like a polymorphic factory. The fact that it's extensible non-locally is a big advantage; in your example, you can have thousands of developers each registering their own cases into this Map, and affect the behavior of the "when" without touching a central (and perhaps incomprehensible) piece of code
m
@Grant Park easiest is to just compile a file with a larger when and decompile the generated 
.class
file. Then you can see how it was translated. The Kotlin Bytecode Viewer in IDEA doesn’t show all optimizations.
g
Wow TIL. Thank you for that!
I wonder if there are similar things in the works or already the case for sealed classes
@Nir you make valid points about really specific patterns like the factory you mentioned, but I don’t think it would be productive to have thousands of developers working on a single map. If you are interested in my usecase, I would look into the Redux architecture with Kotlin. The usage of 
when
statements gets pretty heavy when looping through a bunch of them to produce new UI states in time to render on a screen.
One reason why this is a concern is that you probably don’t want to loop through too many cases to update your app state before inducing a change that is to be visually seen by the end user. Even a 200ms delay can be noticeable and contribute to what’s known as “Jank” (It is an official term dubbed by Google https://developer.android.com/topic/performance/vitals/render)
n
They are working on a single map regardless :-)
r
TABLESWITCH 0: L6 1: L7 default: L8
Untitled
I think the original optimization mentioned is related to when desugaring into tableswitches or similar at the JVM level when the subject cases are primitive types which can then be indexed. Something that matches on ints like this can be turned for example into a table switch
3 Views
Open in Slack
PreviousNext
Powered by

kotlinlang

A modern programming language that makes developers happier.

Powered by