Reconciliation

The basic task sounds like this: build a minimal set of commands for transforming tree A into tree B.

Problem: the general algorithm for constructing a set of operations required to transform one tree into another has a speed of O (n3).

Cubic time complexity means that if we have a tree with a thousand elements (well, the average static of such a UI), then we will need to do one billion operations to update them. Will not work.

Experienced guys know: if you need to do it faster, put the cash! Well, in general, we need to make some simplifications, understand where we can save time to make the algorithm faster.

Simplification 1 (a very general simplification, which together with the second simplification is applied in some form in React, Compose): if we understand that the updated element / subtree is the same, then we can update the tree without recalculating completely.

Simplification 2: if the input of this component does not change, then the subtree that corresponds to it does not change either.

This allows, on average, in linear time to transform tree A into tree B.

In general, if we allow specifying the UI as a function of the state, then this will allow the framework to remove transitions between states for developers. But under the hood, we still need to make these transitions and preferably quickly, otherwise this one won’t be using the framework. As we found out, this is called Reconciliation.

Let’s see how we do this inside Jetpack Compose.