Announcing <Immutable Arrays> Immutable Arrays of...

# feed

[Dan Rusu]

Announcing Immutable Arrays

Immutable Arrays offer a safer and more efficient alternative to read-only lists while maintaining the same look and feel. They combine the safety of true immutability with hundreds of array-level optimizations resulting in significant performance and memory improvements.

The benchmark section is especially surprising.

[Stefan Oltmann]

Sounds interesting!

Is this Multiplatform or JVM only?
Looks like only JVM, but do you plan for KMP?

I currently use https://github.com/Kotlin/kotlinx.collections.immutable , mainly because that can be used in Composables while keeping the compose stability.

How do immutable arrays compare to immutable lists?
Will they also be detected as stable?

[Dan Rusu]

Thanks @Stefan Oltmann for your interest. Immutable Arrays rely on custom-equals-in-value-classes which has only been added for the JVM compiler backend (which covers both Android & JVM backend development).

This is the main ticket that's blocking Immutable Arrays from being used with Multiplatform (please upvote it to increase its priority):
https://youtrack.jetbrains.com/issue/KT-24874

[Stefan Oltmann]

Interesting. How does the performance compare to Kotlinx immutable collections?

[Dan Rusu]

I took a quick peek at Kotlinx Immutable Collections and it appears that they are still in progress with an active proposal so just a heads up that what I'm about to say might not be true in the future if they change their direction.

From a quick peek, it looks like they are combining the concepts of immutable collections and persistent collections together. This preserves immutability while also enabling "modifications" that create new instances instead of mutating the original and which share parts of the underlying data structure of the original.

From a quick glance at the code, it appears that immutable lists are persistent collections that implement the new ImmutableList interface. So while they are truly immutable, their persistent abilities introduce additional memory and performance overhead compared to regular read-only lists.

Since Immutable Arrays use less memory than regular lists and are between 2 to 8 times faster than regular lists for many common operations, I would expect Immutable Arrays to be even more efficient and even faster than Kotlinx immutable lists.

While Immutable Arrays have builders to allow accumulating elements efficiently and then build immutable arrays, the resulting immutable array cannot be modified. So if you plan to make modifications after creation, persistent collections might be interesting (or consider mutable lists).

[Stefan Oltmann]

Interesting. So for best performance and stable composables I'm interested in KT-24874, so that I can use immutable arrays in the future. Voted for that issue.

[Arjan van Wieringen]

The kotlinx collections are used actively in Compose, if I am correct

[mikehearn]

Incredible work Dan! I look forward to using these in my next Kotlin projects.

[Klitos Kyriacou]

This is interesting. A couple of questions:
1. Would it make sense to have ImmutableArray<T> implement List<T> , and ImmutableIntArray implement List<Int>? If it does make sense, it may make these classes more versatile.
2. In your readme, when comparing to Immutable Lists, are you referring to the kotlinx immutable collections library? If so, how did you figure that attempted mutation throws exception? That's the whole point of immutable lists, they're not like the regular List which is read-only but possibly mutable (see

https://www.youtube.com/watch?v=sGjeknOcqEo▾

).

[Dan Rusu]

@Klitos Kyriacou, thanks for asking! My responses respectively:
1. ImmutableIntArray doesn't implement List<Int> (etc.) because that would result in auto-boxing every single time an element is accessed because we can't override a method and change the return type from a reference type to a primitive type. This would affect the performance significantly and make Immutable Arrays no longer applicable for any sort of number crunching. Note that Immutable Arrays maximize the use of the primitive variants in order to minimize memory and improve performance so you can easily end up with a primitive immutable array even if you work with generic types since performing something like val peopleWeights = people.map { it.weightKg } produces an ImmutableFloatArray if the weightKg property type is Float. Immutable Arrays have the asList() method which returns a compatible list wrapper without copying the backing array. Alternatively, you can use toList() to create a standalone list copy.
2. I updated the readme to clarify that the comparison is against Java immutable lists such as those from the Google Guava library. I should probably add another section to compare against kotlinx immutable lists. I'm just wondering whether I should wait for the kotlinx library to stabilize to avoid creating any sort of misconceptions in case they decide to change the direction or implementation details.

[Klitos Kyriacou]

Thanks for the reply, you're quite right. I initially thought that ImmutableIntArray could implement List<Int> instead of using asList() but, of course, that would mean that indexing would create unwanted boxing.

I wouldn't hold my breath about kotlinx immutables. They're been in alpha for several years, and as I understand it, the current focus of JetBrains is to work on the K2 compiler and stabilize some other official libraries first, so stabilizing immutables is way into the future. Nevertheless, it is quite usable and has very few issues reported. I doubt the eventually released version will differ much from today.

[Arjan van Wieringen]

Kotlinx persistent collections is extremely performant and used by compose team in production already a while.

I think it is very important to do benchmarks against them, because you’ll be getting these questions a lot

[Stefan Oltmann]

But how performant is extremely performant? I switched because I need compose stability, but did not benchmark. I’m really curious to see benchmarks comparing normal mutable lists, kotlinx immutable collections and the new immutable arrays - both performance and memory consumption.

Back in my Java days I migrated my old app to Trove collections (trove4j) and this also made a big difference - like switching from json to protobuf.

For more performance and less memory consumption I’m ready to do extra work.

[Dan Rusu]

I think that kotlinx persistent collections can be performant when making extensive use of those persistent abilities to make many modifications instead of having to copy the entire collection each time.

However, for the dozens of operations that just inspect the data without modifying the collection or for the dozens of other operations that transform the data (eg. map, flatMap, partition, groupBy, sorted, etc.), it's physically impossible for persistent collections to match the performance of plain old lists. This is because persistent collections have to do more work to get at the elements and cache locality is also reduced by having a persistent collection share the data structure of the collection that it was modified from as that increases the number of memory hops.

The other thing to consider is that since Immutable Arrays are several times faster than regular lists for many non-trivial operations, this suggests that there's some sort of cutoff point where increasing the number of modifications makes it worthwhile to look at persistent collections.

Note that I'm not trying to say that persistent collections are bad as they can be great at what they're designed to tackle. So it's more about the proportion of time that your use-case requires modifications versus the proportion of time you just need to inspect or transform the existing data.

Creating representative benchmarks for persistent collections could be tricky as the sequence of steps that got you there will change the performance profile.

[Stefan Oltmann]

Interesting. 🤔

You could create multiple benchmarks, including cases with more read operations than write operations and others with significantly more write activity. This data would help people identify tipping points and guide them in choosing the most suitable approach.

[Arjan van Wieringen]

Benchmarks should be able to highlight in which use cases one is better over the other. That is the whole purpose of benchmarks. To make an educated choice based on your own requirements

[Stefan Oltmann]

In a perfect world, yes. Normally benchmarks are used for advertising. 😄

[mikehearn]

It leads to the question of whether the projects can one day merge. I suppose the compiler magic required to do that isn't there today.

[mikehearn]

But if there's some adaptive cutoff it'd be good to treat it as a speculative optimization and switch forms depending on write load.