Asynchronous DiffUtil with Kotlin Coroutines

Take advantage of Coroutines to make your DiffUtil asynchronous

By now you’ve probably heard about DiffUtil, or you maybe you’re using it in your projects, or you might even have paired it with RxJava. But if you haven’t, you should consider evaluating how your project could benefit from it.
DiffUtil allows us to achieve RecyclerView animations that were once nearly impossible to achieve with ListView. It also provides an abstraction to dispatch granular updates rather than invalidating the entire list — greatly improving RecyclerView’s performance. But as the size of your data set increases, or your comparison logic is complex, you should be computing the diff on a background thread. That’s what this post is about — how you can take advantage of Coroutines to compute the diff asynchronously — easily and safely.

The challenge

Typically, for small data sets with simple diffing logic, you would do the following on the main thread:

1. Implement DiffUtil.Callback
2. Instantiate a new instance of the DiffUtil.Callback and pass the current list and the new list along to your DiffUtil.Callback
3. Invoke DiffUtil.calculateDiff and pass your DiffUtil.Callback as the argument
4. Use the DiffResult to dispatch the updates to your adapter

But what happens when your data set becomes large or your diff logic becomes complex. Now you need to move things off to a background thread. This is when things start to get complicated. You can move the DiffUtil.calculateDiff operation to a background thread. Then you can pass the results back to the UI thread where you dispatch the updates to your adapter. But your DiffUtil calculation needs the current and new list, so now your current list could be modified by other threads. You also need to swap out the current list with the new list when the diff completes but other threads could be operating on that data too. You also need to manage safely switching between background and UI threads.

All of a sudden, what was once a trivial task now requires careful management of shared memory across threads.

The thing about Threads

• Threads are expensive
• Each Thread requires it’s own stack and therefore consumes memory
• Context switches between Threads are expensive
• Blocked threads are wasted resources
• Threads operate on shared memory. Care is needed or you could be viewing stale data or modifying shared data.
• Sharing memory requires locking and locks are expensive

Coroutines are a far better alternative and mitigate these limitations.
First, coroutines are cheap. Think of them like lightweight threads. Second, you can leverage channels to safely communicate across coroutines that span different threads. Channels operate on the principle of message passing rather than sharing memory.

How it works

The general concept revolves around the use of a Coroutine and the Actor pattern.

Each new list update is dispatched to the AsyncDiffUtil. This can be a null list, and empty list, or one that contains several items. The AsyncDiffUtil transforms this into a UpdateOperation — which can either be an Insert or Clear. This operation is delivered to an UpdateActor. The UpdateActor processes these operations serially on a single Coroutine. If the operation is a Clear operation, then we can directly notify the DiffUtil.Callback that the items have been removed and swap the list. Otherwise, the operation implies items have been added, removed, changed, or moved. This requires computation to determine the diff. The UpdateActor captures the current list and the new list and switches to a background thread. Once the result is received, the UpdateActor switches back to the UI thread, swaps the list with the new list, and dispatches the changes to the Adapter.

Overview of the pipeline for computing a diff and submitting the result to the Adapter

You might be wondering what happens if new list updates arrive while the current diff operation is being computed.
The UpdateActor is created with a Conflated mailbox. This means if an update arrives while the UpdateActor is busy processing a request, the update is queued into the UpdateActor’s mailbox. Once the UpdateActor finishes with the current request it will process the next entry in the mailbox. If a new update arrives before that, the new update replaces the current update in the queue. This provides a simple mechanism for dealing with fast updates or updates that arrive in batches.

What if a Clear operation arrives while the UpdateActor is busy computing a diff? Waiting for it to complete a diff only to clear the Adapter seems to be wasted computation cycles.
Yes, this is true. And we can parallelize some of the computation and still retain thread safety but at the cost of added complexity. The above solution should handle the majority of scenarios.

You can find the complete source along with a sample app here: https://github.com/jsaund/AsyncDiffUtil

Resources

More about the Actor model in Kotlin
https://github.com/Kotlin/kotlinx.coroutines/blob/master/docs/shared-mutable-state-and-concurrency.md#actors

Using DiffUtil and Why
https://proandroiddev.com/diffutil-is-a-must-797502bc1149