Why is Flutter Fast? — Part 1: Sublinear Building

Published in

Flutter Community

16 min readApr 4, 2022

In this series, we will have a deep dive into the Flutter framework, and answer the question “Why Flutter is Fast” in three articles.

In this first article, we will focus on the three trees of Flutter and explain the sublinear build phase.
In the second article, we will start with how Flutter takes a different approach compared to existing cross-platform solutions and continue with its layered architecture.
In the last article, we will analyze Flutter’s rendering pipeline step by step and show the steps of drawing a frame with an example.

Motivation

I am a software developer who is motivated with getting visual outcomes for end-users as fast as possible. I believe it takes a longer time to master new technologies for developers like me because we get overly excited about the deliveries and eventually miss the fundamentals of the technology. As an example, I would like to quote Gazihan Alankus’s signature comics in his talks.

We can still build Flutter apps without studying the topics such as the trees of Flutter, the architectural layers, and the rendering pipeline. However, when we want to implement special UI components efficiently, we need to truly understand how the framework works. This is the lesson I learned while working on my talk at the Flutter Vikings Conference “From Motion Design Specs To Flutter Code”.

Flutter does an amazing job of abstracting the most essential tasks in an efficient way. I hope this series would be useful for readers to understand the internals of the framework, prepare better for job interviews and convince their fellow developers to switch to Flutter.

Declarative vs. Imperative

James Turnbull compares the imperative and declarative paradigms as follows in a podcast episode: In the imperative paradigm, developers write the steps they are going to take to achieve a task. For example, in step 1 an object is created, in step 2 the object is updated, in step 3 the object is deleted, and so on. In the declarative paradigm, developers only care about the state instead of the steps. They will tell what the application should look like in a particular state. Then, the framework or the toolkit takes care of the details and the steps (the how) to achieve what is described [9].

Turnbull adds that almost any query language such as SQL is an example of a declarative paradigm. Using SQL queries, we tell what records we want to get without caring about how the records that meet the criteria are collected [9].

According to Turnbull, in a declarative world, all the resources are linked together in a graph-based model. When a change occurs, the application walks through all the nodes in the graph and finds out which nodes will be affected. Developers know what is happening in the current state, and what will happen in the next state.

In the podcast, Turnbull doesn’t talk about Flutter but a declarative programming tool for automating infrastructure resource creation called Terraform. This article will show how Flutter works as a declarative UI toolkit.

Three Trees of Flutter

Flutter has more than three trees but we will focus only on the widget tree, element tree, and render tree. Among these trees, the most relevant one for Flutter developers is the widget tree because it is the only tree that app developers explicitly declare and maintain.

“Mahogany Staircase refers to the Flutter framework design where a tree of representative objects is used to construct a parallel tree that describes the original objects in a new way” [1]

Unlike the Android native UI framework, where the code (Kotlin, Java) and markup (XML) is combined to add and edit the views in a window [6], Flutter uses only code (Dart) as markup to add widgets with a declarative paradigm [2].

Widget is simply a configuration. We tell the framework what we want to see in different portions of the screen using widgets. From the application developer’s perspective, building a Flutter UI is all about composing widgets into a tree according to the UI logic. Tim Sneath describes the widget concept in three ways: a unit of composition for Flutter, the building block of a Flutter UI, and a declarative component that everything in Flutter is built on [7].

I chose the word “building” deliberately because throughout this article we will focus on the build phase of rendering a frame. In Flutter, it is the app developer’s responsibility to compose widgets to tell what is wanted, and the framework’s responsibility to handle the rest of the rendering when drawing frames (handle the how).

Widgets are immutable, so we can’t update them. Once declared in the widget tree, they can’t be changed. This is a significant difference from UI development with native Android development where operations like setting properties, listeners, and visibility can be performed imperatively after the creation of the views [5].

Element is the information hub configured by a widget. There is a corresponding element in the element tree for every widget in the widget tree. When we want to know about the size, parent, children, and location of a widget in the widget tree, we get the answer from its element. Furthermore, the State object of a StatefulWidget is permanently associated with the element of the StatefulWidget.

Many Flutter developers think that they are not using elements in their daily work. However, they are so wrong because the Element class implements the BuildContext interface which is provided by the framework to the developers when building a widget subtree. There are some Flutter packages aiming to eliminate or undercover the usage of BuildContext and introduce this as a good practice. In my opinion, BuildContext is a vital part of UI development to understand where we are, and what we can do in a particular location of the widget tree.

“BuildContext objects are actually Element objects. The BuildContext interface is used to discourage direct manipulation of Element objects.” [4]

Once we provide the initial widget tree, the framework creates the corresponding element and render trees from top to down. The nodes in the element and render trees are updated (if possible) in one top-down pass.

An element can be a ComponentElement or RenderObjectElement. For example, the element node for a StatelessWidget or the StatefulWidget extends the ComponentElement abstract class. ComponentElement is a host for other elements as the root of these elements in its subtree. It doesn’t have an associated RenderObject.

“Rather than creating a RenderObject directly, a ComponentElement creates RenderObjects indirectly by creating other Elements.”

RenderObjectElement nodes in the element tree participate in the layout and painting phases of the rendering [7]. These elements have associated RenderObject nodes in the render tree which are responsible for the heavy work such as sizing, positioning, hit-testing, and painting.

Component Element Vs RenderObject Element [10]

To sum up:

Widget tree is maintained by app developers: widgets only hold the configuration data.
Element tree is the logical structure of the UI: it is (re)constructed by the widget tree and knows about the location of the widget in the tree.
Render tree is the data structure that is managed by the element tree: the geometry is computed during the layout phase and used in the painting and hit testing.
An element node has references to a corresponding widget, state object, and an optional render node. The render tree can be considered a subset of the element tree.

For more detailed information regarding the Three Trees of Flutter, I would suggest watching the talk by Andrew Fitz Gibbon and Matt Sullivan at Google Developer Days China 2019 conference.

Sublinear Build Performance

As an Android developer who has long experience with building UI using XML files and code, it wasn’t easy for me to get used to the declarative UI paradigm. In Android, we change the UI by updating the existing UI components imperatively (unless Jetpack Compose is used). Because Flutter’s widgets are immutable, when we want to change a portion of the UI, we have to provide a new widget subtree in the next build phase. The frequency of these builds can be in the milliseconds level.

“Because Flutter widgets are built using aggressive composition, user interfaces built with Flutter have a large number of widgets.” [3]

At first, I did not feel comfortable with this fact. I thought it should have been expensive in terms of performance considering the number of widgets instantiated during a build. I was so wrong because although at every build we create new widget subtrees according to the new desired configuration set, the framework reuses the nodes in the element tree and the render tree as much as possible. Despite how wasteful it sounds that the widgets come and go at the milliseconds level, keeping the elements and render objects around where possible is a critical success factor for Flutter’s performance. [8]

As Flutter app developers, when we want to update a portion of the screen, we implicitly mark the root of the corresponding widget subtree as needing a build which makes them dirty just before the next build pass.

Dirty Region — A portion of an app where widgets and components are different in one frame as compared to previous frames that have been displayed. [1]

During the build phase, the “dirty” elements are rebuilt and the subtree of the dirty elements are examined to be reused from top to down by their parent elements.

In the previous section, we mentioned that the element tree is the logical structure. While widgets have no idea about their positions in the widget tree, elements can know their parent and children.

The examination happens inside the parent element’sperformRebuild method. During this call, updateChild method is called on all child elements. The parent checks if a child element can be updated, removed, or added to the element tree in this build stage.

"Element.updateChild method is the core of the widgets system. It is called each time we are to add, update, or remove a child based on an updated configuration.” [4]

Initially Linear, Subsequently Sub-linear

Flutter performs one build pass per frame. Child elements are visited and examined by their parent elements only once during the drawing of a frame.

When the widgets of the initial widget tree are inflated one by one from top to down, all the corresponding elements and render objects are created. This is a linear O(n) performance because the execution is dependent on the total number of widgets.

After the initial build, only the widgets whose elements are marked as dirty will be rebuilt, and the clean elements will be skipped. This is a sub-linear performance because the build time depends on the subset of the widget tree. This sub-linear algorithm is summarized in the diagram below.

Here is the terminology for the code snippet we will go through in detail:

Parent element: The element that examines its child elements in the element tree.
Child element: The element that is examined by its parent element to be added, removed, updated, or reused in the current build pass.
New widget: The widget that the child element will have reference to in the current build pass.
Old widget: The widget that the child element has reference to in the beginning of the build pass.
Slot: Each child element occupies a slot in its parent element relative to other children. It corresponds to a position in the child element list. When the slot in the child element list is updated as a result of a call to the updateChild method, the corresponding child render object’s slot in its parent render object is also updated. Hence, a slot can also be considered as the location of a node in the element and the render trees.

[CASE 1] If the child element is non-null, and the new widget of the child element is null, then the framework removes the child element from the element tree. The parent element calls the deactivateChild method which puts the child element to the inactive state and detaches the child’s corresponding render object from the render tree. Until the build phase is completed, the framework waits for unmounting the child element and clearing its resources because, during the build, there is still a chance that the inactive element can be retaken to the tree using a GlobalKey. This process is called tree surgery.

[CASE 2] If both the child element and its new widget are non-null and, the old widget and the new widget of the child element are the same instances, then the current child element is reused without a need for an update. As a result, the build method for the corresponding child widget will not be called. This is the most ideal case in terms of performance.

“Because widgets are immutable, if an element has not marked itself as dirty, the element can return immediately from build, cutting off the walk, if the parent rebuilds the element with an identical widget. [3]”

Using const constructor on widgets is recommended if applicable. When we create multiple widget instances with const constructors, if the constructor parameters are not runtime dependent, then the framework knows that the old and the new widgets are in the same memory at every build.

“… the element need only compare the object identity of the two widget references in order to establish that the new widget is the same as the old widget [3]”

Note that a widget can have a const constructor, but this doesn’t make all the instances of the widget const since all of its constructor parameters should also be declared as const . Therefore, strategic thinking maybe needed to include const widgets in the widget tree. For example, the String parameter for the Text widgets are usually localized and the locale is runtime-dependent. Furthermore, in many projects, the size and distance arguments of the widgets such as Padding, SizedBox are double values that are adjusted according to the screen density calculated at runtime using the MediaQuery.

As a final note, although a widget class may meet the criteria to be able to construct a const widget, the app developers should still explicitly declare a constructor with a const keyword. Thus, it is suggested to include a linter rule to be warned when the constructor can be invoked as const, but misses the const keyword.

[CASE 3] If both the child element and its new widget are non-null and, the old and new widgets are NOT the same instances but canUpdate method returns true then the update method on the child element is called. canUpdate method returns true if the key and runtime type of the old widget and the new widget are the same.

In the update method, the old widget reference in the child element is replaced with the new widget, the existing render object is updated if the element has an associated RenderObject, and the new widget is rebuilt.

Below is the screenshot where you can see the flow of updating the StatelessElement . It is the element of a StatelessWidget and it doesn’t create a render object, but instead, composes children that have render objects. During the update process of a stateless element, developers can provide a new widget subtree by overriding the build method of the StatelessWidget.

Note that both widgets might have the same configuration but if they are not the same instance, then the corresponding element and render object nodes will still be updated, the build method will be called on the child widget, and the widgets in the subtree will be re-created. In many cases, this is still ok in terms of performance since creating a widget usually is not heavy work. However, imagine you need to add a widget that opens a camera with animation, then it might be better to cache the camera widget as suggested in Case 2.

[CASE 4] If both the child element and its new widget are non-null and, the old and new widgets are NOT the same but canUpdate returns false then as in the removal case the deactivateChild method of the child element is called, the corresponding render object is detached from the render tree. Finally, a new element for the new widget is returned to the element tree. This is the most expensive case in terms of performance since a new element node and render object node are instantiated.
[CASE 5] If the child element is null, and its new child is non-null, then we have a new widget in this location of the tree within this build stage. Thus, the parent element first calls the inflateWidget method which calls the new widget’s createElement method and returns a new element of the new widget. At this point, the parent also sets a slot for the created element.

To sum up, for the very first build, it will be only Case 5, and for the subsequent builds the more we reuse the better performance we will achieve in our Flutter apps.

“Flutter aims for linear performance for initial layout, and sublinear layout performance in the common case of subsequently updating an existing layout.” [3]

State

StatefulWidget is useful when we track data associated with a widget to apply necessary UI changes when needed by simply rebuilding the widget.

When a StatefulWidget is inflated, a corresponding StatefulElement is constructed. Inside the constructor method of the StatefulElement, createState method of the StatefulWidget returns the permanently associated State object to its element.

2. After the StatefulElement is mounted in the element tree, initState and didChangeDependencies methods of the StatefulElement are called just before the first build. The initState method can be overridden to perform one-time initializations.

3. After the initialization, State object’s build method can be called at any time during the lifespan of the element.

4. In CASE 3, we mentioned that if canUpdate returns true, then the element is updated. In this case, didUpdateWidget method of the State object is called. After this call, the build method will be called so there is no need to explicitly trigger a build inside this method.

This method can be overridden to implicitly start animations according to configuration changes. For example, imagine that we have a view sliding up from the bottom of the screen. The widget that controls this animation has isExiting boolean. Initially, the isExiting flag is false, and in the initState method, we can call forward on the enter animation controller to start the enter animation. When isExiting is set true in any of the next builds, we can call forward on the exit animation controller within didUpdateWidget method to trigger the exit animation.

5. When the State object is removed from the tree, the dispose method is called. We should override this method if we have to release any resources retained by the State object.

Below, you can watch the amazing video by the Flutter team regarding the usage of StatefulWidget .

Marking as Needs Build

When we want to change a portion in the UI, we pollute the corresponding widget subtree. Then the framework cleans the dirty elements in the subtree within the next frame.

Once a widget is built, its element can’t be dirty again within the same frame. Below is the screenshot that you can see inside which functions the framework marks the widgets as needs build.

In the following cases markNeedsBuild method is called internally on Element objects:

attachToRenderTree method is called in runApp method during the creation of the widget, element, and render trees.
setState method is called on the State object of a StatefulWidget usually during the event handlers such as onPressed. Note that the method provided as a parameter to setState will be invoked before the widget is marked as needing build.
didChangeDependencies method is called on an Element when its widget depends on a parent InheritedWidget and the parentInheritedWidget changes. The Element subscribes to the changes of the parent InheritedWidget (creates a dependency) by calling the dependOnInheritedWidgetOfExactType method on its own BuildContext.

dependOnInheritedWidgetOfExactType — “Obtains the nearest widget of the given type T, which must be the type of a concrete InheritedWidget subclass, and registers this build context with that widget such that when that widget changes (or a new widget of that type is introduced, or the widget goes away), this build context is rebuilt so that it can obtain new values from that widget.”

reassemble method is called only during the development phase whenever the entire application needs to be redrawn possibly because of the hot reload command.
activate method is called when a StatefulWidget is reinserted into the Element tree within the tree surgery process.
Finally, whenever the InheritedNotifier which is variant of a InheritedWidget updates its dependencies, the element is marked as dirty.

Conclusion

In this article, we started with the three trees of Flutter and learned how the framework optimizes the performance by reusing the nodes in the trees as much as possible. Then, we explained the State object which is permanently associated with the lifetime of its stateful element.

In the next article, we will continue answering the question “Why is Flutter fast?” by explaining the layered architecture of Flutter and its effect on performance.

References

https://twitter.com/FlutterComm