The original address is here.

This article focuses on the algorithms and optimizations used inside Flutter to make Flutter so powerful. Some references compare the consistency algorithms of Flutter to those of other development tools, but I feel they are too brief. I will spend more time on this topic later. Finally, it describes how Flutter’s API design meets the developers’ expectations. Due to the translator’s limited level, the omission of the place also please forgive me. I didn’t translate all of it because I was more concerned with the consistency algorithm part. In the last section of this article, I focus on the user-friendly design of apis. It’s good to know, but it doesn’t hurt to know.

This paper describes the inner workings of Flutter. Flutter widgets work in radical combinations, so users will use many of them when building their UI. To support this workload, Flutter uses sublinear algorithms to handle layouts, build components, and tree data structures. Other constants and optimizations are also included. Taking into account other details, this design also makes it easier for developers to use callbacks to create visible portions of an infinite scrolling list.

Radical combination

One of the characteristics of Flutter is its aggressive composability. Widgets are a combination of other, more basic components. For example, a Padding is a component, not a property of a component. In short, the user’s UI is made up of many, many components.

The components form a tree structure, with the last node of type RenderObjectWidget. The components of the leaf node are used to create the nodes that are drawn on the screen. A draw tree is a data structure that holds information about the geometry of the user interface (size, location, etc.). This geometry information is calculated during the layout phase and is used in painting and collision detection (HIT test). Basically, Flutter developers do not create render objects directly. Instead, they manipulate the draw tree through widgets.

To support radical composition at the component layer, Flutter uses a lot of algorithms and optimizations for both the component layer and the draw tree layer. These will be covered in subsequent chapters.

Sublinear Layout

How to deal with a large number of components and render objects, how to get good performance? The key is an effective algorithm! The key is the Layout algorithm, which determines the geometry of the object to draw, such as its size and position. Some tools have layout algorithms that run O(N²) or worse (for example, do fixed-point iterations under certain constraints). The goal of Flutter is to achieve linear performance in the first layout calculation and sublinear performance when updating an existing layout, especially when the layout calculation time increases slowly compared to a large number of drawn objects.

Flutter performs only one layout calculation per frame. Each layout calculation is a single pass operation. The constraints are passed down through the parent object’s layout method that calls each child object. The child objects recursively execute their layout methods and return geometry information up on return. Once a drawing object is returned from its Layout method, the drawing object is not accessed again until the layout of the next frame is computed. In this way, what would normally be two steps — measures and layout — are aggregated into a single pass. Thus, each Render object can be accessed at most two times when calculating the layout 2: once down the tree and once up the tree.

Flutter has multiple implementations of this Protocol. The most common representation is RenderBox, acting on a two-dimensional Cartesian coordinate system. In this box layout, its constraints are a maximum and minimum width and a maximum and minimum height. At layout time, a child is its geometry information by selecting a value in the boundary. When the child returns from the layout, the parent object knows its position in frame 3. Note: The layout of a child object is independent of its position, because its position is not known until the child object returns from Layout. Therefore, the parent object can position the child object arbitrarily without having to evaluate the layout again.

In general, the only thing that flows from parent to child during layout is constraints. The only data that flows from child to parent is geometric information. These invariants can significantly reduce the amount of work required for layout calculations.

  • If the child object does not mark its own layout as dirty, the child object can be returned immediately from the layout calculation. This is because the parent imposes the same constraints on the child as the previous layout.
  • Whenever a parent object calls the layout method of the child object, the parent object indicates whether the size data returned by the child object is needed. In many cases this is not necessary, so the parent object does not need to recalculate the layout. Even if the child chooses a new size, the child itself ensures that the new size fits the existing constraint.
  • Tight constraints can only be satisfied by explicitly unique and valid geometric information. For example, if the minimum and maximum widths are equal, and the minimum and maximum heights are equal, then there is only one width and one height value that satisfies this constraint. If the parent object provides a tight constraint, no matter how the child layout evaluates, the parent object itself does not need to reevaluate its layout, even if the parent object uses the size returned by the child’s layout, because the child object cannot change its size without the constraints provided by the parent.
  • A drawing object can declare that it computs geometric information using only the constraints provided by the parent object. This declaration explicitly tells the framework that the layout has been recalculated on the operator object, and that the parent object does not need to be evaluated. Even if the constraints of the parent object are not tight, even if the layout of the parent object depends on the size of the child object. Because the child object cannot change its size without the new constraints of the parent object.

The result of this optimization is that when the render object tree contains dirt nodes, only those dirty nodes and their surrounding subtrees need to be accessed in the layout.

Sublinear Widget Building

Similar to layout, the component construction algorithm of Flutter is sublinear. After the build, all components are held by the Element tree, which also maintains the logical structure of the UI. Element trees are necessary because components themselves are immutable. That is, if there are multiple Wigets, they will not remember the parent-child node relationship among them. The Element tree also holds the state object for the StatefuleWidget.

An element can become dirty after user data or other operations, such as a developer calling setState() on a state object. Then Flutter keeps a list of “dirty” elements and skips over them during construction, ignoring other clean elements. During the build phase, data flows unidirectionally up and down the Element tree, meaning that element nodes are accessed only once during the build phase. Once an Element is clean, it does not become dirty because all its ancestors were clean.

Because components are immutable, if the parent object is rebuilt using the same component, and the component’s corresponding Element does not mark itself as dirty, then that element can be returned immediately during construction. Furthermore, Element only needs to compare the ids referenced by two widgets to determine whether they are the same. This optimization is called the secondary projection pattern, which specifically means that a component contains a child component before it is built and stores it as a member variable at build time.

Flutter also avoids using the InheritedWidget to access the parent chain when it is built. If all components access the parent chain, for example to get the current theme color, the build becomes O(N²) depending on the depth of the tree. This time is very much back. To avoid this situation, Flutter has an InheritedWidget hash table on each element. Many elements only refer to the same hash table, and changes only when an Element references a new InheritedWidget.

Linear reconciliation

Contrary to popular belief, Flutter does not look different at the tree level. Instead, an O(N) algorithm is used: each element’s sub-element list is examined independently to determine whether to reuse the element. The optimization of sublist consistency algorithm can be divided into the following situations:

  • The old watch was empty
  • Both lists are the same
  • There is an explicit place in the list where one or more components are inserted or removed
  • If each list contains components with the same Key, the two components are considered to match

The usual approach is to compare the runtime type and key of each component in the two lists from beginning to end. It is very likely that you will find a paragraph in each list containing all mismatched components and their range. Flutter puts the components of the old list into a hash table based on their key. The Flutter then traverses the range of the new list and looks for the matching key from the hash table. Those that do not match are discarded, and those that do match are rebuilt with new components.

Tree Surgery

Reusing an Element is important for performance because it holds two important kinds of data: the state of the state component and the underlying draw object. When Flutter can reuse an element, the state of a logical part of the UI is preserved and the previously calculated layout data can be reused, essentially eliminating the need to traverse the entire subtree. In fact, Flutter supports non-local tree modifications of state and layout.

Developers can perform non-local tree modifications by associating a widget with a GlobalKey. Each global key is unique throughout the app and registered in a thread-specific hash table. During the construction phase, a developer can move a component with a global key anywhere in the Element tree. Instead of building a whole new component in that place. Flutter checks the hash table and then hangs the component under the new parent, preserving the entire subtree.

Drawing objects in a subtree can retain their layout information because the constraint on the layout is the only data that flows from the parent object of the tree to the child object. The new parent object is marked as dirty because its list of child objects has changed. However, if the new parent passes the same layout data as the old parent, the child object will immediately return, stopping traversal.

Global keys and non-local tree modifications are widely used for hero transition and navigation.

Constant factor optimization

In addition to these algorithm optimizations, several constant factor optimizations are needed to achieve the combination. These optimizations are also critical to the algorithms mentioned above.

  • Submodel independenceUnlike other tools that use sublists, the draw tree of Flutter does not depend on a particular subpattern. For instance,RenderBoxClass has an abstractvisitChildren()Method rather than actualfirstChildandnextSiblingInterface. Many subclasses support a single child, directly as a class member variable, rather than as a list of child nodes. For instance,RenderPaddingSupport a unique child. Only a shorter, simpler Layout method will be executed.
  • Visual drawing tree, logical component tree: Drawing trees in Flutter is done on a device-indepent visual coordinate system. That is, the smaller value on the X-axis is further to the left, even though the current reading direction is from right to left. The component tree is based on a logical coordinate system, which means that the start and end values are resolved depending on the reading direction. The transition from the logical coordinate system to the visual coordinate system is done hand by hand from the component tree to the drawing tree. This approach is more efficient because the layout and painting calculations in the painting tree are more frequent than component to tree transitions, thus avoiding repeated coordinate system transitions.
  • Text has special draw object handlingA large number of draw objects do not process complex text, text is only processed by specialized draw objects,RenderParagraph. This is a leaf node to draw the tree. Text is processed not by inheritance, but by composition. That way it can be avoidedRenderParagraphRecalculates the text it holds and evaluates the layout data again with the same constraints passed by the parent node. It’s very common, even in tree decomposition.
  • Observable: Flutter uses an observer model and a responsive model. Obviously, responsiveness has been dominant, but Flutter uses the observer model on the data structure of leaf nodes. For example, an observer list is notified when the value of an animation changes. Flutter passes these observer objects from the component tree to the draw tree. The return receipt can directly observe these objects and invalidate them at an appropriate point in the draw pipe when they change. For example, changes to an animation value will only start painting instead of both building and painting.

Given the large number of components, the performance gains from such optimizations are significant.

Split Element tree and draw tree

Draw object trees (draw trees) and Element trees are isomorphic (strictly speaking, draw trees are a subset of Element trees). An obvious simplification is to combine these two arrays into one. In practice, however, there are many benefits to separating the two numbers.

  • Performance: When the layout changes, only the relevant parts of the layout tree need to be traversed. There are always many nodes in an Element tree that need to be skipped due to aggressive composition.
  • Explicit: The separation of concerns allows the component and the drawing object to focus on their respective focus. This greatly simplifies the API and greatly reduces the risk and testing burden.
  • Type safety: Drawing a tree ensures that the types of its nodes are appropriate at run time, so drawing a tree ensures type safety. Composite components do not care about the coordinate system of the layout, so in the Element tree, checking the type of object to draw will result in a tree traverse.

The infinite scroll

The implementation of infinite scrolling lists is very difficult for all kinds of tools. Flutter was built to provide a very simple interface to this function. A list that uses a callback to visually display a component as the user scrolls. Supporting this functionality requires the use of viewport-aware layouts and build-on-demand components.

Viewport senses the layout

Like most things about the Flutter, the scrollable components are made up of combinations. Outside of the scrollable component is a child component of Viewport that can extend outside of the visual window, and can also scroll into the view. However, a viewport has a child of type RenderSilver, not of type RenderBox. The RenderSilver type has a view aware interface.

The Silver layout protocol is structurally identical to the boxed layout protocol and also passes constraints to child nodes and returns geometry information. However, constraints and geometric information are different between the two. In the Silver protocol, children receive viewPort data, including the remaining visible space. The geometry they return makes a variety of scroll-related effects possible, including foldable headers and parallax effects.

Different Silver fills the viewport’s remaining space differently. For example, a silver can generate a list of child components, one next to the other, until the silver displays all the child components or runs out of space. Similarly, a Silver generates a two-dimensional grid, with child components filling only the visible parts of the grid. Because they can sense how much space is left. Silver can also generate a finite number of child components, although they can also generate infinite child components.

Silver can be combined to produce different scrollable layouts and effects. For example, a single viewport can have a foldable Heaer, followed by a linear list and a grid. All three Silver components interact according to the Silver protocol to generate child components visible in the viewport, whether they belong to a header, list, or grid.

Create components as needed

If Flutter has a strict build, layout, and draw pipeline, this would be very inefficient when building an infinite scroll list, because the amount of available viewport space is only known at the Layout stage. Without other means, the layout phase is too late to build the components that fill the remaining space. Flutter solves this problem by intersecting the construction and layout phases of the pipeline. At any point during the layout phase, Flutter can build new components on demand, as long as these components are children of the drawing object currently performing the layout.

Cross-build and layout is possible only because of the strict data transfer controls in the build and layout algorithms. In particular, during the construction phase, data can only be passed down. When a drawing object evaluates the layout, the layout traversal does not yet access the subtree of the drawing object, meaning that the subtree generates writes that cannot overwrite the current layout. Similarly, once a layout is returned from a drawing object, the drawing object is not accessed during the layout calculation, meaning that any subsequent writes generated by the layout calculation do not affect the data used by the current drawing object to build the subtree.

In addition, both linear consistency and tree decomposition are necessary for efficient updating of elements during scrolling. It is also important to modify the drawing tree when an element scrolls in or out of the viewable area.

API developer friendly design

Fast only makes sense if the framework can be used correctly. To achieve apI-friendly results, Flutter and its developers conducted extensive experience studies. These sometimes confirm previous decisions, sometimes help prioritize features, and sometimes change the direction of API design. For example, the Flutter API is well documented. The UX study confirmed the value of these documents, but also clarified the use of sample code and ICONS.

This section discusses the DESIGN of the Flutter API for emergency use.

A specific API fits a developer’s specific understanding

The base classes of Flutter widgets, Element and RenderObject tree nodes do not have child Models. This also allows a node to be a submodel of a node to which it applies.

Most component objects have only one child component, so only one child parameter is exposed. Some components support many child components, exposing a list parameter called children. Some components do not have any child components and therefore do not expose any parameters. Similarly, RenderObjects exposes specific submodel apis. The RenderImage is a leaf node with no concept of child objects. RenderPadding accepts a single child, so it only has a single reference to a child. RenderFlex accepts an unknown number of children and manages them using a linked list.

In some special cases, more complex submodels are required. The RenderTable object receives a two-dimensional array of getters and setters that control the number of rows and columns, and a certain number of methods that can replace an X, y subscript child.

The properties of Chip components and InputDecoration objects also match those of related controls. A one-size-fits-all submodel enforces semantics at the top of the submodel hierarchy. For example, if the first child is defined as a prefix value and the second child as a suffix value, a particular child model can be used for a particular named attribute.

This flexibility allows each node of these trees to act according to its role. It is rare to insert a cell into a table because all other cells will be deformed and shifted. Similarly, it is rare to remove an element from a Flex row using subscripts instead of references.

The RenderParagraph object is an extreme example of a group: it has a completely different child, TextSpan. Within the Scope of the RenderParagraph, the RenderObject tree becomes a TextSpan tree.

Overall, getting the API design to meet developer expectations is not just an effort on a submodel.

Some simple components exist so that developers can call them when solving a problem. Adding space to a row or column is easy once you know how to do it: Use Expanded components and a zero-size SiezedBox child, but that’s not the best approach. If you search for space you’ll find the Spacer component, which uses Expanded and SizedBox internally.

Similarly, it’s easy to hide a component’s subtree, as long as you don’t include that component’s subtree at build time. The developer wanted a component to do this, and that’s the Visibility component.

Display parameters

UI frameworks have many parameters, and developers rarely remember the semantics of each parameter in the constructor. Flutter uses response mode, so a lot of constructors are used when it is built. With Dart language named parameters, the Flutter API ensures that each build method is clear and easy to understand.

This pattern can be extended to every method that takes many parameters. In particular, for each bool argument, each true and false in the method has its own document property.

Avoid falling pit

One technique commonly used in Flutter is to define an API where error conditions do not exist. This avoids too much focus on the error.

For example, if an interpolation method allows one or both ends of the interpolation to be null, Flutter does not define this as an error. Instead, if both ends of the interpolation are null, it returns NULL. If either end is null, it is equivalent to inserting a value into a value of a particular type of 0. That is, if a developer accidentally passes a null value to the interpolation method, no error will occur and a reasonable value will be output.

There is a more subtle example in the Flex layout algorithm. The concept of the layout is that the space of the Flex drawing object will be divided by one or more of its child components, so the size of the Flex layout should take up the available space. In the original design, providing a wireless space was a mistake: it implicitly indicated that the Flex layout was infinite in size, a useless layout. However, the API has been modified so that when an infinite size is assigned to a Flex drawing object, it becomes the size required by the child components, reducing possible error situations.

Actively report errors

Not all mistakes can be avoided by design. For problems that still exist while being debugged, Flutter will usually catch exceptions this morning and report them promptly. The use of assertions is very common. Constructor arguments are also examined in detail. Life cycles are also monitored, and exceptions are thrown when errors occur.

In some cases, this goes to extremes: for example, when running unit tests, each RenderBox subclass checks whether the inherent size method meets the inherent size contract, regardless of what is being tested. This helps find problems in the API that are not easily exposed.

The exceptions thrown also contain an unexpectedly rich amount of information.

Responsive model

Mutable tree-based apis all experience confusion: the set of operations that create the initial state of the tree and the combination of operations for subsequent updates are quite different. The drawing layer of Flutter uses this model, which is an effective way to maintain a persistent tree and is key to making layout and drawing efficient. However, manipulating the drawing layer directly can be very strange, and worse, can introduce bugs.

The component layer of Flutter uses reactive patterns to combine components and manipulate the underlying draw tree. This API combines the tree creation and modification steps into a single tree build step. Whenever the APP’s state changes, the UI generates a new configuration, which is controlled by the developer. Flutter then performs the necessary calculations on the tree modifications to reflect the new modifications.

The interpolation

Flutter encourages developers to configure Flutter based on the current state of their APP. In other words, when the App state changes, the corresponding component changes too. A mechanic is needed to make sure the changes are animated.

For example, in state 1 we have S1, and the interface contains a circle. But in the next state, S2, it becomes a box. Without any animation mechanics, this would be very awkward. An implicit animation that turns the circle into a box after a few frames makes the experience much better.

conclusion

The slogan of Flutter is “Everything is a widget”. This means building complex components using basic components. The result of aggressive composition is that developers use a large number of components, which requires careful design of algorithms and data structures so that components can be processed efficiently. In addition, these data structures also allow developers to easily create an infinite scrolling list of components.

note

This is true for layout calculations. However, it will be accessed again for drawing, building barrier-free trees (if necessary), and crash testing.

2 will be more complex in the real world. Some layouts require measurements of intrinsic dimension or baseline, which can result in additional traversal of related subtrees (aggressive caching is designed to deal with such extreme cases). It’s very rare. In particular, shrink-wrapping does not necessarily require intrinsic dimensions.

Technically speaking, the position of the Child is not in the RenderBox geometry, so it does not need to be calculated during layout. Most of the time drawing objects position their child at (0,0) relative to their origin, so there is no need to evaluate or store anything. Some draw objects avoid positional calculations until the final calculation of the location of their child nodes is dedicated, and there will be no calculations if the child components are not drawn at the end.

There is an exception to this rule. As discussed in the Section build Components on Demand (## Create Components on Demand), some components are rebuilt because of changes in layout constraints. If a component marks itself dirty in the same frame for unrelated reasons, then it will also be affected by the change of layout constraints, and it will be updated twice. This build occurs only in the component itself and does not affect its children.