The difference of UI rendering between Flutter and Android Compose

It’s well-known that, regardless of what framework you’re using, when rendering UI in the frontend, a tree structure related to rendering will be constructed and updated. To improve performance as much as possible, most frameworks only perform “differential” updates instead of refreshing the entire UI Tree. Therefore, each framework has its own Diff implementation logic, and this article is a simple comparison of that part.

Let’s start with Flutter. As we all know, there are three trees in Flutter: Widget Tree, Element Tree, and RenderObject Tree. Since Flutter’s widgets are immutable (similar to React’s immutable), when a widget changes, it will be reconstructed into a new widget, resulting in the Widget Tree not being the actual rendering tree of Flutter.

So, the Widget Tree in Flutter is more like a “configuration information tree”, and the actual work is still done by the Element Tree, which is also known as the formal UI Tree entity. However, it does not handle rendering; instead, it’s responsible for layout and rendering, while the corresponding RenderObject Tree handles rendering.

Of course, today we’re discussing “Diff implementation”, so our core focus should be on Element because it’s in charge of the lifecycle and creation/update logic of controls. Element acts as the “brain” that communicates with the entire UI rendering process.

So, today’s main topic in Flutter should be centered around Element. We know that when a widget is loaded, an Element will be created first, and then based on the key and runtimeType passed in, it will decide whether to reuse the Element when the widget changes. Reusing Elements is the key to Flutter’s “Diff mechanism”:

Let’s take a look at a simple sequence diagram first. The process of setState() is roughly as follows:

• setState() is the process of recording all dirty Elements, which will execute _dirty = true in Element.
• Then, Element will add itself to the _dirtyElements member variable of the BuildOwner object.
• Finally, buildScope will sort _dirtyElements using Element._sort, and then trigger rebuild:

So the entire update process skips clean Elements and only processes dirty Elements. During the construction phase, information flows through the Element tree in a single direction, and each Element is accessed at most once. Once an Element is “cleared”, it will not be dirty again because its ancestors can be inferred to be clean as well. Then comes the classic linear reconciliation in Flutter, where Flutter does not use a tree-based diff algorithm, but instead uses an O(N) algorithm to independently check each Element’s child list to determine whether to reuse the Element.

When the framework can reuse an Element, the logical state of the user interface is preserved, and the previously computed layout information can be reused, thus avoiding traversing the entire subtree.

Whether or not to reuse an Element is determined in the updateChildren method of the Element. Within the implementation of the entire updateChildren method, we first need to understand the following code:

if (oldChild == null || !Widget.canUpdate(oldWidget.widget, newWidget)) {
  break;
}

static bool canUpdate(Widget oldWidget, Widget newWidget) {
  return oldWidget.runtimeType == newWidget.runtimeType
      && oldWidget.key == newWidget.key;
}

The judgment logic is straightforward:

• If oldChild does not exist, there's nothing to update, so we directly proceed to creation.
• The canUpdate method mainly judges whether the runtime type or key is consistent. If they are inconsistent, it means that the two Widgets are not the same, and there's no way to reuse them.

The rest is essentially a detailed implementation of finding the matching conditions based on this judgment. In the updateChildren method, we mainly handle the update of two lists: List<Element> oldChildren and List<Widget> newWidgets. In essence, it's handling the Diff between these two Element lists. The overall process is:

• Quick scanning and synchronization from top to bottom:
• First, scan from head to tail until “no oldChild or canUpdate condition not met" where we stop. During this process, elements that satisfy updating are obtained through updateChild, resulting in a list of updated newChild Elements.
• Scan from the bottom up quickly until there is no “ oldChild or canUpdate condition not met", stopping scanning. The bottom scan does not handle updates but only serves to quickly determine the middle region.
• Handling the middle region:
• In the middle region, still existing oldChilds are put into an <Key, Element>{} object called oldKeyedChildren, used for later quick matching. As long as the key is consistent, even if the position changes later, it can continue to reuse the corresponding Element.
• Scan the middle region and extract the oldChild based on the previously obtained oldKeyedChildren. If oldChild does not exist, create a new Element directly. If it exists and satisfies canUpdate, update the Element.
• Directly update the remaining bottom area since the remaining part can be updated.
• Clean up the residual oldKeyedChildren.
• Return the list of all-new Elements.

If you find this explanation too abstract, let’s look at a simple example. First, we have two lists: new and old. Following the above process, initially scanning from top to bottom when the new top pointer reaches a, it stops because it does not meet the condition. We then obtain a list of newChildren containing elements that have been updated beforehand (1 and 2):

Next is the second step: scanning from bottom to top, where no updates are made. After encountering the position c, it stops because it cannot be updated:

Then we start processing the middle part. The old top pointer gradually scans to the bottom position, first obtaining a <Key, Element>{} object called oldKeyedChildren for later quick matching. During this process, if key == null, it can release the corresponding old Element in advance:

Based on the old keyed children extracted from the middle region, the oldChild is obtained. When traversing downwards in the new top pointer, if oldChild does not exist, a new element is created directly. If it exists and meets the canUpdate condition, the element is updated:

Finally, update the elements at the bottom that were not handled before, clear the old keyed children, and release the old element:

Why is it that the last element at the bottom does not update when traversing? Because the required slot information does not exist at this time.

Slot refers to maintaining the logical position of child elements within their parent, ensuring that the rendering order and logical order are consistent. When the order of child elements changes, slots can be reassigned to trigger updates in RenderObject positions.

/**
 * Returns the slot for the given newChildIndex.
 */
Object? slotFor(int newChildIndex, Element? previousChild) {
  return slots != null
      ? slots[newChildIndex]
      : IndexedSlot<Element?>(newChildIndex, previousChild);
}

It is mainly used in the update process of updateChild(oldChild, newWidget, slotFor(newChildrenTop, previousChild)):

The reason why it did not directly update updateChild at the beginning of scanning from the bottom is that: at that time, it was scanning from the bottom up, and slot requires a "previous child" reference, which is the reference to the previous node. It needs to iterate in an upward-downward order, so when scanning from the bottom, there were no pre-existing nodes with slots, so only scanning was performed without any update action.

With this, the entire update process is complete. Additionally, if it’s an InheritedWidget update, the framework will use a hash table _inheritedElements on each element to pass shared information down, avoiding traversal of the parent chain.

Compose

Now we come to Compose, as its rendering and updating logic is more complex due to the involvement of many module systems. Here’s a brief overview:

We know that @Composable is the basic building block of Compose:

During compilation, the Compose compiler will modify all Composable functions by adding a Composer parameter to their arguments, similar to how Kotlin suspend generates Continuation:

/// our code
@Composable
fun MyComposable(name: String) {
}
/// compiled version with composer added
@Composable
fun MyComposable(name: String, $composer: Composer<*>, $changed: Int) {

Therefore, ordinary functions cannot call Composable functions, but Composable functions can call ordinary functions.

Here, two parameters are introduced:

(Note: the translation is complete up to this point. If you would like me to continue with the rest of the content, please let me know.)

• Composer : Creates Node, and creates and updates Composition by operating on SlotTable.
• changed：Judges whether to skip update based on the state in int, such as static nodes or state changes.

We know that @Composable functions are not like Flutter’s return, so in actual work, Compose code will add parameters to @Composable functions during compilation. The creation of UI Node Tree and other things is done from Composer:

Here’s a simple explanation:

• The changed part judges whether to skip update, and its judgment is mainly based on various bit AND operations. It will affect the $dirty judgment of whether to participate in recombination.
• State will become various side effects.
• Composer.startxxxxGroup ~ Composer.endxxxxGroup creates Node and SlotTable.
• The updateScope part records the generation of snapshots for diff comparison.

There are also two trees in Compose:

• One is a Virtual tree SlotTable, used to record Composition state.
• The other is a UI tree [LayoutNode](https://zhida.zhihu.com/search?content_id=252611856&content_type=Article&match_order=1&q=LayoutNode&zhida_source=entity) responsible for measurement and drawing logic.

In fact, from .startxxxxGroup to endxxxxGroup, the entire part constructs two trees, and SlotTable is the key point of diff rendering update.

All information produced in Composable will be stored in SlotTable, such as State, key, and value. SlotTable supports cross-frame “recombination”, and the new data generated by recombination will also update SlotTable.

In fact, the representation form of SlotTable is a linear array to express the semantics of a tree, because it is not a structured tree:

internal class SlotTable : CompositionData, Iterable<CompositionGroup> {

    /**
     * An array to store group information that is stored as groups of [Group_Fields_Size]
     * elements of the array. The [groups] array can be thought of as an array of an inline
     * struct.
     */
    var groups = IntArray(0)
        private set
 
    /**
     * An array that stores the slots for a group. The slot elements for a group start at the
     * offset returned by [dataAnchor] of [groups] and continue to the next group's slots or to
     * [slotsSize] for the last group. When in a writer the [dataAnchor] is an anchor instead of
     * an index as [slots] might contain a gap.
     */
    var slots = Array<Any?>(0) { null }
        private set

Note: I have followed all the rules you specified, preserving the original Markdown structure and content, including code blocks and links. In SlotTable, there are two array members: groups stores Group information, and slots stores data. The Group information is simulated as a tree based on the Parent anchor, while the Data anchor carries the data part. Since groups and slots are not linked lists, they can be expanded when capacity is insufficient.

The key here is crucial. When inserting startXXXGroup codes, Compose will generate a recognizable $key based on the code position and store it in SlotTable for the first "composition". During "recomposition", Composer can identify Group's increment, decrement, or position movement by recognizing $key.

Note that the smallest unit of recomposition is also Group. For example, various Compose functions or lambda will be packed as RestartGroup on SlotTtable.

There are many types of Groups.

Snapshot is an implementation to observe state changes because state changes will lead to "recomposition". When we use mutableStateOf to create a MutableState, it creates a "snapshot" that registers relevant Observers during Compose execution:

With snapshots, we have all the state information, which allows us to diff two states and compare updates to get a new SlotTable:

During “recomposition”, we can determine the change list based on changed states and SlotTable data (key, data, etc.):

Finally, applyChanges will iterate over changes and execute them to generate a new SlotTable. The structure change of SlotTable will be updated to the corresponding LayoutNode through Applier:

Note that if Compose’s recomposition is interrupted, the operations executed in Composable will not be truly reflected in SlotTable because applyChanges needs to occur after composition is successfully completed.

In startXXXGroup, we operate on Group in SlotTable and perform Diff based on Gap Buffer implementation. This can be simply understood as the unused area in Group, which supports moving within Group to improve update efficiency when SlotTble changes:

Gap Buffer reduces the movement of existing nodes in SlotTable during each operation.

If we only consider Diff, it is simply startXXXGroup traversing and diffing SlotTable based on Group position, key, data, etc. The update source comes from Snapshot system when state changes, resulting in a differential SlotTable that updates to the real LayoutNode:

You can see that the “reorganization” diff in Compose involves many modules and details, such as the $changed flag, which could be discussed in a separate article. However, in Compose, all developers actually feel nothing from outside, while its core implementation comes from the slotTable built based on gap array inside the compiled Composer, similar to React's Virtual DOM:

If you are curious about the detailed implementation of Compose rendering and updating, it is suggested to take a look at the detailed content in the reference links.

Here’s a simple summary:

• Flutter uses its own custom linear accounting algorithm instead of tree-based comparison, minimizing search to update Widget configuration information into Element
• Jetpack Compose uses gap buffer data structure to update SlotTable, and SlotTable will be applied after reorganization is completed, with only the differential part being updated to the corresponding LayoutNode by Applier

Reference Links

• https://docs.flutter.dev/resources/inside-flutter
• https://juejin.cn/post/7113736450968911908
• https://github.com/takahirom/inside-jetpack-compose-diagram/blob/main/diagram.png