https://kotlinlang.org logo
Join Slack
Powered by
Hi! What is the best/recommended entry point to Ko...
# getting-started
b
Hi! What is the best/recommended entry point to Kotlin documentation? I'm having trouble finding algorithmic complexity of some operations. Maybe I miss something. I typed a bit too much for one message, so I'll hide examples/findings in the thread 🧵
So, I found two kinds of docs • Article-like pages, for example, Basic syntax or Conditions and loops. These are nice, there is a description of various language constructs and examples. But these pages kinda lack in completeness: you probably need to read all the "articles" to understand some details. • Reference, for example, kotlin.collections. These pages are definitely exhaustive, they list lots of functions/types. But, they are dry and lack details. Also, they mostly come up when you google "kotlin something".
I stumbled upon a few questions, let's use them as examples: • I'm solving some problem which needs mutable map/dict. I know from some experience that Kotlin has 
MutableMap
(and it can be created with 
mutableMapOf
). But it is a trouble to find characteristics of this data structure (for example, insertion algorithmic complexity). Googling "mutable map kotlin" brings you to jvm docs, where there the only perf-related phrase is "supports efficiently retrieving the value corresponding to each key." Maybe it is enough to get job done, maybe not. "MutableMap kotlin performance" brings some blog post which mentions that MutableMap can be seen as hash table. But no official docs still. • I want to use 
String
and I assume it would be actively sliced/taken substring of. I remember that `String`s are immutable, so probably it would take constant time to do this. But I totally fail to find this in docs.
Here are examples from other langs where complexity is mentioned. • C++ std::string::substr: Complexity: Linear in 
count
• Rust SliceIndex: 
This operation is _O_(1)
. Not quiet ideal place to describe this — there are functions for slicing above — but still on the same page.
e
MutableMap
is just an interface, it can have any number of implementations with different performance characteristics
the most common implementation (e.g. the one returned by 
mutableMapOf()
is LinkedHashMap, although that is considered an implementation detail
that, in turn, is implemented by java.util.LinkedHashMap, which does not explicitly document its complexity
not sure what Kotlin is supposed to promise if the underlying system doesn't
and in fact, things like 
String.substring
have changed behavior over different Java releases
l
benchmarking is a good way to verify the answers to your questions, and ensure you know quickly if there’s a change that affects performance.
b
@ephemient thanks! Suddenly just now I found details on the MutableMap implementation in the docs (bottom of the page). So, it looks like my exact questions are platform-dependent, and performance is heavily platform-dependent too.
@Landry Norris yep, measuring is always nice, thanks! I just thought there are some links for quick answers to similar questions.
e
in general, it is expected that 
.get()
and 
.iterator().next()
are O(1). there are a few types that break these assumptions though, such as 
LinkedList
and 
CoroutineContext
I guess there isn't really a list of these unwritten assumptions though -_-
s
At a high level, I'd say that • functions like 
mapOf
, 
listOf
, etc. are for cases when you don't really care about the complexity and just want it to be something reasonably sensible • when you do care more about the specific implementation, you can instead use one of the specific constructors for 
HashMap
, 
ArrayList
, etc.
I don't think I mind that the stdlib doesn't provide much in the way of documentation for the common data structures. They're not particularly exotic and so their complexity will be familiar to people who are worried about that sort of thing.
e
especially for types that simply wrap or alias Java types
s
Strings are another story, though 😄. Java's String implementation is super weird (because of history) and Kotlin inherits a lot of the weirdness, but fails to document it at all really.
e
kotlin.collections.ArrayDeque is one of the few collections types that doesn't simply alias java.util.ArrayDeque, but it doesn't specify complexity 😕
on the other hand, the only purpose for it to exist is to be more efficient than an 
ArrayList
, so you should already have expectations for it
l
Not documenting the time complexity also allows the Kotlin/Java teams to make changes. One day, the Kotlin team may want a pure-Kotlin solution, and the complexity may differ. If you look at the Jetpack Multiplatform preview, the collections are implemented as simply as possible. They will likely want to make improvements over time, which will change the complexity. Continuously benchmarking is the most reliable way to measure these changes.
5 Views
Open in Slack
PreviousNext
Powered by