Very poor performance of immutable maps


I think that supporting persistent data structures ala Clojure as the default implementation that the kotlin stdlib resorts to for Map and List is a very reasonable request.
It makes functional programming in kotlin feasible for much bigger problems, out of the box without resorting to external libraries.


Adding an item to a map is expected to be an O(1) operation. Kotlin has an operation which allows you to add an item to a read-only map; therefore it’s reasonable to expect that this operation is O(1). You can only implement this via an immutable implementation, so the fact that Kotlin has this operation at all leads you to expect that there’s an immutable implementation. The documentation uses the word ‘immutable’ in several places, which reinforces this assumption.

The fact that Kotlin’s implementation is not, in fact, immutable, and the addition operation is O(n), is very weird. The fact that it’s implemented as an extension function is the reason why it’s weird, but that’s just an implementation detail — it’s not relevant to the shape of the API. The fact is that the API contains an operation which users will reasonably expect to be O(1), but which is actually O(n).

This should not have come as a surprise to me. This sort of thing needs to be clearly and explicitly called out in the documentation, so that doesn’t come as a surprise to anybody else.


The term immutable doesn’t have any performance implication. So the documentation is not wrong.
The argument is that Kotlin could do much better by using state of the art persistent data structures when dealing with immutable Maps/Lists


I’ve never seen that use of the word ‘persistent’ before — in all the literature I’ve seen, ‘immutable’ has been used instead (see, e.g. ‘Persistent’, however, has always meant that the data was stored on disk.

For everything I’ve written above, please consider me to have said ‘persistent’ when I said ‘immutable’.


Yeah, it’s confusing, though it’s how the CS literature calls them since '86


Yeah, I think it depends on where you come from — I was at St.Andrews when they were doing work with the other kind of persistence (e.g. Orthogonal Persistent Object Systems). But persistent is obviously the term used here, so I’ll try to use that from now on.


By the way, it seems like there is some effort underway in that direction


I can accept that the documentation was not sufficient for you @david.given. It was sufficient for me. It is arguable how confusing it is for the general public. I’d assume not as much as you are trying to suggest.


It would be good to maintain the positive vibe that the Kotlin community has always had. If @david.given is taking the trouble to comment here, there is probably an opportunity for improvement.

Also, one thing that has benefitted US-based tech companies in becoming world-famous is that customer service is generally good in the US and companies try to be attentive to users/customers rather than just saying “you’re wrong”.


David said that “Adding an item to a map is expected to be an O(1) operation.”, but I don’t think that’s a reasonable expectation. In fact, I don’t think you should make any assumptions about performance in general.

For example, in the simpler case of lists, appending an item to a list could be O(1) if the list were doubly-linked; amortised O(1) for an ArrayList, or O(N) for a singly-linked or FP-style list. (Those last would be much faster prepending, of course.) And for maps, there could be even more variation.

So it all depends on the particular implementation. And for that, you need to check the documentation.

This is example is rather like the classic Java gotcha of appending to a string in a loop; that also involved an overload of a plus sign, and that also needed you to understand what the code was actually doing.


I agree, people with different backgrounds have different expectations. For example, for me it seems absolutely unreasonable to append elements to read-only (or even immutable) map. Kotlin developers in this case follow good old java tradition that if you need something special, you need to declare it explicitly and I am completely opposed to breaking this tradition in favor of implicit “universal” solutions.

As for @jpliska comment, it is not quite relevant since there were no “negative” comments, just the regular discussion, and people in this thread are not customer service. There was only one completely neutral comment from JetBrains team member. By the way, I do not know, what US have to do with that.


I agree with the idea that if you want something special you need to declare it. That said maybe it’s worth thinking about changing the operations on read only lists to use kotlins immutable lists once they are a stable feature and not just a prototype. Until then there is not much we can do, except maybe improve the documentation.


I will assume that once immutable lists are stable, they will stay a separate kotlinx library. Like serialization, reflection or kotlinx-html.

Will it be feasible to change operations on read-only lists in such a case?