loading...
Touchlab

Kotlin/Native - Isolated State

kpgalligan profile image Kevin Galligan ・6 min read

Kotlin Native Concurrent Mutable State (2 Part Series)

1) Kotlin/Native - Transferring State 2) Kotlin/Native - Isolated State

In the previous post we discussed transferring state. I started there because recently several people posted in the Kotlin slack discussing DetachedObjectGraph.

In my particular journey from JVM to Kotlin/Native (or KN), I went through a phase I think many new KN devs go through. In the JVM I was used to sharing mutable state between threads, and I assumed I must retain that ability at all costs. DetachedObjectGraph is one of the first things I started to focus on.

It seems like interest in KMP has picked up considerably this first month of 2020, and so we've had a lot of questions about DetachedObjectGraph. I have found that DetachedObjectGraph is of limited value, and once I understood the KN state model, I found I never needed it.

You will, however, occasionally need mutable state between threads.

Stately Collections V1

Going back to mid/late 2018, we released Stately.

GitHub logo touchlab / Stately

Kotlin Multiplatform State Library

Along with atomics, locks, and some other concurrency support stuff, there was also a set of concurrent collection classes. These internally used AtomicRef to implement collections. That meant I actually implemented a linked list and a hash map from scratch with AtomicRef.

These collections work, but performance is bad, their implementation is basic, and their use is inflexible. Also, just FYI, AtomicRef can leak memory, so you need to clear these collections when you're done with them.

As it turns out, if you just keep your state isolated, you can implement concurrent collections in an almost trivial manner, with far better performance.

Stately Collections V2 (Isolated State)

The next version of Stately will have a class called IsolateState. You create an instance in a manner similar to how you interact with DetachedObjectGraph. Pass in a producer lambda. One critical difference. The value returned from that lambda cannot be frozen.

Once you create this instance of IsolateState, you interact with it by way of the access method. access takes a lambda, which takes one argument: the mutable state.

As an example, let's create a simple shared map:

object StateSample {
    val cacheMap = IsolateState { mutableMapOf<String, SomeData>() }
}

data class SomeData(val s: String)

cacheMap is a simple mutable map, with String keys and SomeData values.

To be clear, according to KN state rules, object StateSample is frozen, so cacheMap is also frozen. The state it contains, the result of mutableMapOf<String, SomeData>(), is not frozen, and can never be (we call ensureNeverFrozen() internally).

Getting to that state and doing stuff with it is easy:

fun doStuff(){
    StateSample.cacheMap.access {map -> 
        map.put("Hello", SomeData("World"))
    }
}

Getting values from the state is also straightforward:

fun readStuff(){
    val sd = StateSample.cacheMap.access { it.get("Hello") }
    println("sd: $sd, isFrozen: ${sd.isFrozen()}")
}

Note, the value returned from access will be frozen, as is anything captured and passed into access.

There will be a separate stately-iso-collections module, but because isolated state is so flexible, I'm not sure how necessary a full MutableMap implementation, for example, would be as opposed to just using access to get at the methods you need. I didn't want to clutter the middle of the post, but I've included the entire implementation of a MutableMap using IsolateState at the bottom. It really is bordering on trivial.

One of the more inflexible aspects of any concurrent collection is the lack of atomic operations. Calling size will return a value, but if you want to insert a value based on that result, you could have race conditions.

Take the following example:

fun racyInABadWay(fmap:HashMap<String, SomeData>){
    val size = fmap.size
    fmap.put("i $size", SomeData("data $size")) // <- may result in missed values
}

Assume fmap is a concurrent map from Stately v1 collections. Between the call to get size and the call to put a value, the size could change. Your put call will be invalid. You could fix this by creating a Lock instance that's associated with fmap, then passing them both around, but that's ugly.

Using IsolateState, this is again trivial.

fun atomicOperations(isoMap: IsolateState<MutableMap<String, SomeData>>){
    isoMap.access { map ->
        map.put("i ${map.size}", SomeData("data ${map.size}"))
    }
}

Under the hood, all access calls run on the same thread, so while your block is running, nothing can change the map. You can implement arbitrarily complex atomic operations.

Performace

Performance is kind of relative. Inserting 50k elements in a v1 Stately map vs v2 is pretty good.

    val times = 50_000
    val v1Time = measureTimeMillis {
        val fmap = frozenHashMap<String, SomeData>()
        repeat(times){c ->
            fmap.put("i $c", SomeData("data $c"))
        }
    }

    println("v1Time: $v1Time")

    val isoTime = measureTimeMillis {
        val isomap = IsolateState{ mutableMapOf<String, SomeData>()}
        repeat(times){c ->
            isomap.access { it.put("i $c", SomeData("data $c")) }
        }
    }

    println("isoTime: $isoTime")

The result:

v1Time: 13785
isoTime: 1937

Compared to using a regular MutableMap? Well, not as good.

    val normalTime = measureTimeMillis {
        val map = mutableMapOf<String, SomeData>()
        repeat(times){c ->
            map.put("i $c", SomeData("data $c"))
        }
    }

    println("normalTime: $normalTime")
isoTime: 1937
normalTime: 201

Of course, you're crossing thread contexts for each call to the IsolateState instance. There's a lot of overhead involved. Because IsolateState is inherently more flexible than a fixed concurrent map implementation, inserting in blocks is pretty easy to implement. The performance boost is dramatic.

    val isoBlockTime = measureTimeMillis {
        val isomap = IsolateState{ mutableMapOf<String, SomeData>()}
        val outerTimes = times / 1000
        repeat(outerTimes){ c ->
            val blockMap = mutableMapOf<String, SomeData>()
            repeat(1000){inner ->
                val putCount = (c * 1000) + inner
                blockMap.put("i $putCount", SomeData("data $putCount"))
            }

            isomap.access { it.putAll(blockMap) }
        }
    }

    println("isoBlockTime: $isoBlockTime")
normalTime: 201
isoBlockTime: 330

You've inserted 50k elements into a concurrent map structure in a time that's ~65% slower than a local mutable map. It's "slower", relatively, but that performance is fantastic all things considered. That's also without inline on any of the IsolateState methods, which may slightly improve the situation.

Can you insert in Stately v1's collections in blocks? Sure, but it's rigid, and because they're implemented with AtomicRef, the performance is dismal.

    val v1BlockTime = measureTimeMillis {
        val fmap = frozenHashMap<String, SomeData>()
        val outerTimes = times / 1000
        repeat(outerTimes){ c ->
            val blockMap = mutableMapOf<String, SomeData>()
            repeat(1000){inner ->
                val putCount = (c * 1000) + inner

                blockMap.put("i $putCount", SomeData("data $putCount"))
            }

            fmap.putAll(blockMap)
        }
    }

    println("v1BlockTime: $v1BlockTime")

It's the same as inserting values individually.

v1Time: 13785
isoTime: 1937
normalTime: 201
isoBlockTime: 330
v1BlockTime: 13623

To round out our timing comparison, if you use DetachedObjectGraph to insert 50k elements, things get much, much worse.

fun timeTest() {
    val times = 50_000
    val detachedTime = measureTimeMillis {
        val detachedMap = SharedDetachedObject { mutableMapOf<String, SomeData>() }
        detachedMap.freeze()
        repeat(times){c ->
            val sd = SomeData("data $c")
            detachedMap.access {
                it.put("i $c", sd)
            }
        }
    }

    println("detachedTime: $detachedTime")
}
detachedTime: 68334

That's about 35x slower than using IsolateState. It'll also get worse as the size grows because you lose the Big O advantage of a hash map. You could certainly optimize access to DetachedObjectGraph a bit, but what's the point?

In summary, use IsolateState for KMP concurrent state.

We've published an experimental version of Stately to try this out:

implementation "co.touchlab:stately-isolate:0.10.2"

The documentation hasn't been updated, but you can see samples here:

GitHub logo touchlab / StatelyIsoStateSample

Stately IsolatedState sample

We should have a more formal version soon, pending community feedback.

Hiring!

Touchlab is hiring! Looking for Android-focused mobile developers, and also for experienced or very interested Kotlin Multiplatform devs. We really need to find a solid Android dev at this precise moment, though. Just FYI. Remote friendly (US-only, for now).


MutableMap Implementation

Here's the code for a MutableMap implemented with IsolateState. We're essentially just wrapping mutableMapOf<K, V>().

class IsoMutableMap<K, V>(producer: () -> MutableMap<K, V> = { mutableMapOf() })
    : IsolateState<MutableMap<K, V>>(createState(producer)), MutableMap<K, V> {
    override val size: Int
        get() = access { it.size }

    override fun containsKey(key: K): Boolean = access { it.containsKey(key) }
    override fun containsValue(value: V): Boolean = access { it.containsValue(value) }
    override fun get(key: K): V? = access { it.get(key) }
    override fun isEmpty(): Boolean = access { it.isEmpty() }
    override val entries: MutableSet<MutableMap.MutableEntry<K, V>>
        get() = access { IsoMutableSet(StateHolder(it.entries)) }
    override val keys: MutableSet<K>
        get() = access { IsoMutableSet(StateHolder(it.keys)) }
    override val values: MutableCollection<V>
        get() = access { IsoMutableCollection(StateHolder(it.values)) }
    override fun clear() = access { it.clear() }
    override fun put(key: K, value: V): V? = access { it.put(key, value) }
    override fun putAll(from: Map<out K, V>) = access { it.putAll(from) }
    override fun remove(key: K): V? = access { it.remove(key) }
}

open class IsoMutableCollection<T> internal constructor(stateHolder: StateHolder<MutableCollection<T>>) :
    IsolateState<MutableCollection<T>>(stateHolder), MutableCollection<T> {
    constructor(producer: () -> MutableCollection<T>) : this(createState(producer))
    override val size: Int
        get() = access { it.size }

    override fun contains(element: T): Boolean = access { it.contains(element) }
    override fun containsAll(elements: Collection<T>): Boolean = access { it.containsAll(elements) }
    override fun isEmpty(): Boolean = access { it.isEmpty() }
    override fun add(element: T): Boolean = access { it.add(element) }
    override fun addAll(elements: Collection<T>): Boolean = access { it.addAll(elements) }
    override fun clear() = access { it.clear() }
    override fun iterator(): MutableIterator<T> = access { IsoMutableIterator(StateHolder(it.iterator())) }
    override fun remove(element: T): Boolean = access { it.remove(element) }
    override fun removeAll(elements: Collection<T>): Boolean = access { it.removeAll(elements) }
    override fun retainAll(elements: Collection<T>): Boolean = access { it.retainAll(elements) }
}

class IsoMutableSet<T> internal constructor(stateHolder: StateHolder<MutableSet<T>>) :
    IsoMutableCollection<T>(stateHolder), MutableSet<T> {
    constructor(producer: () -> MutableSet<T> = { mutableSetOf() }) : this(createState(producer))
}

class IsoMutableIterator<T> internal constructor(stateHolder: StateHolder<MutableIterator<T>>) :
    IsolateState<MutableIterator<T>>(stateHolder), MutableIterator<T> {
    override fun hasNext(): Boolean = access { it.hasNext() }
    override fun next(): T = access { it.next() }
}

Kotlin Native Concurrent Mutable State (2 Part Series)

1) Kotlin/Native - Transferring State 2) Kotlin/Native - Isolated State

Posted on by:

kpgalligan profile

Kevin Galligan

@kpgalligan

#kotlin Multipatform and Native

Touchlab

We are the Kotlin Multiplatform experts. We partner with mobile engineering leaders to accelerate feature development, maximize efficiency, and future-proof teams.

Discussion

markdown guide