Hash maps are extremely common data structures, and Jetpack Compose unsurprisingly takes advantage
of them for various tasks. Kotlin makes it easy to create a new mutable hash map by calling the
mutableMapOf() function. Most developer will — and should — stop there, and use the map however
they need to. Things are however a bit different when working on a toolkit like Jetpack Compose as
we need to ensure the toolkit’s behavior is as unintrusive as possible for the app.
So let’s peek at the implementation of
1public inline fun <K, V> mutableMapOf(): MutableMap<K, V> = LinkedHashMap()
LinkedHashMap is an
expect class that on Android defers to
the API of the same name:
1public actual typealias LinkedHashMap<K, V> = java.util.LinkedHashMap<K, V>
Since this API is battle-tested and offers good performance characteristics, it is a good choice
as a standard hash map in Kotlin1. Unfortunately the implementation of
LinkedHashMap is not
memory-friendly, as each entry inserted into the map creates a new
(this is also true with the base
HashMap class and its
HashMap.Node). For our use case, this
has several negative consequences:
- Each entry uses more memory than necessary. Storing an
LinkedHashMaprequires 3 extra pointers, and a copy of the hash, on top of the overhead of an
- Memory accesses, especially iterations, are not cache friendly, especially over time as the heap gets scrambled.
- It puts pressure on the garbage collector, which can be painful especially on older devices and/or older versions of the Android Runtime (ART).
To work around these issues, we created a new hash map called
to be much more memory-efficient. This new API is part of the
library as of version 1.4,
which recently reached Release Candidate status.
Some of the characteristics of
- The overhead per entry is 1 byte.
- Insertion is allocation-free unless the map needs to grow its internal storage.
- Iteration is allocation-free.
- Allocation-free versions of common APIs (
removeIf()for instance is
inlineto avoid allocating the predicate lambda).
- Keys and values are stored linearly, offering a good memory cache behavior when iterating over the map, with no indirections required.
- Performance on insertion/removal/retrieval/iteration that’s better than or on par with
- API consistent with Kotlin’s maps (factory functions,
- Offers specialized variants to store primitives (
ObjectFloatMapfor instance) with no auto-boxing.
Here are benchmark numbers2 on a Pixel 6 running Android 13:
|Insert 1k elements
|Remove 1k elements
|Iterate 1k elements
|Query 1k elements3
Note that in the context of this benchmark, the iteration test is likely the best number
LinkedHashMap can produce since all elements are created immediately one after the other, giving
them good memory locality.
ScatterMap’s performance will remain the same over time.
The main drawback of
ScatterMap is that it does not implement the standard
Map interface, which
forces memory-unfriendly behaviors. It is possible to get a
MutableMap) interface out of
ScatterMap by calling
asMap(), but the default API tries to provide the most common features
found in Kotlin with regular maps, such as
ScatterMap a better hash map? Yes… if memory allocations, memory usage, and memory access
are something you need to optimize for. I believe it is a great tool to be aware of, but which
data structure to use is ultimately your choice and responsibility.
In future installments, I’ll explain where
ScatterMap came from, how it works internally, how it
was optimized to produce efficient ARM 64 assembly5, and how it could be even better with SIMD
I do have an issue with this choice though.
LinkedHashMapguarantees a predictable iteration order, which can lead to subtle bugs if you ever rely on this behavior and write your code to accept generic types like
These are the original benchmark numbers.
ScatterMapreceived several small optimizations since then. ↩︎
The benchmark calls
get(key: K)1,000 times. ↩︎
To insert 1,000 elements. ↩︎