Servo Layout Engines Report
- Date: 31st March 2023
- Authors: Delan Azabani, Manuel Rego, Martin Robinson, Mukilan Thiyagarajan, Oriol Brufau
The layout engine, or layout phase, is one of the key parts of a web rendering engine. During this phase, the web engine computes the dimensions and positions of the different elements. This is a complex process, accounting for a large fraction of the codebase of any web engine, and there have been significant efforts to rewrite and improve this phase in all of the major open source engines.
Servo currently has two layout engines: the original engine, commonly known as Layout 2013, and one that began development in 2019, known as Layout 2020. Development on both engines has largely stalled, but Layout 2013 is more mature.
In this report, we discuss the idea of abandoning one of these engines and focusing entirely on the other, gradually improving the selected engine by fixing bugs and adding features. Our motivation is to avoid duplicate effort, clarify priorities, and to speed up support for missing CSS2 features, while preparing ourselves for further implementation of CSS3.
We make the argument that we should prioritize Layout 2020, because it fixes some fundamental design problems with Layout 2013 that make serialization-dependent parts of layout difficult, such as floats and CSS counters. Layout 2020 also makes it possible to implement proper fragmentation support, which is an important goal for a layout engine written from scratch to support modern CSS. This argument is made based on the design, features, and current status of each engine.
CSS organizes content into boxes, which are then split into fragments representing parts of boxes distributed across lines, columns, and pages.
Layout 2013 uses a single tree design, with eager parallelism for the layout process. This means boxes and fragments are stored in the same tree, known as the flow tree. In this tree, the internal nodes are Flow nodes, roughly corresponding to block and inline formatting contexts in the CSS spec, while the leaf nodes are fragments.
To enable eager parallel layout, Layout 2013 splits the process into what were originally four tree traversals, but have since evolved into seven traversals:
-
Propagate damage (top-down): This traversal propagates layout damage up and down the tree, and tracks the usage of counters for the next pass.
-
Calculate generated content (top-down): This sequential traversal computes the contents of counters and other generated content. If a subtree does not have any counters or generated content, then this pass can be skipped for that subtree.
-
Speculate float positions (top-down): This is another sequential pass, where we guess how much inline size floats should occupy.
-
Bubble inline size (bottom-up): In this traversal, the minimum and preferred inline sizes are calculated for all elements. This also flags some elements as participating in float layout for later traversals.
-
Assign inline size (top-down): In this traversal, the minimum and preferred sizes of the elements are used to actually assign an inline size to all elements. Since the actual inline size of an element depends on that of its parent, this must be top down.
-
Assign block size (bottom-up): In this traversal, line breaking is performed and text is wrapped around floats. Because floats can cause later elements to wrap around them, when we encounter those elements, we do a top-down sequential layout from an ancestor. In certain situations, such as when elements that clear floats, paralellism is once again possible.
-
Construct display list (top-down): In this traversal, we compute the final position of all fragments and turn them into display list items. A later sequential processing of that display list is needed to convert it to a WebRender display list, because Layout 2013 predates WebRender.
The Servo wiki contains a more detailed explanation of Layout 2013, though it is slightly out of date and does not mention some of the passes that were later added to address bugs that are difficult to fix under Layout 2013's original design.
Layout 2020's design aligns more closely with various CSS specifications in terms of structure and terminology than that of Layout 2013. The main design distinction is the use of two separate trees: a box tree and a fragment tree. Unlike Layout 2013, where fragments are strictly the leaves of the flow tree beneath boxes, fragmentation in Layout 2020 allows placing the resulting fragments in a way that does not have to hew so closely to the structure of the box tree.
The box tree represents the structure of the document being rendered, with boxes that each correspond to a DOM element or pseudo-element, and text sequences that corresponding to text nodes. The fragment tree is the output of the layout process, representing the fragments in which boxes and text sequences can be broken into. For example, when a text sequence is broken into multiple lines or a block is broken across columns or pages, it yields multiple fragments in the tree.
These two trees are built using a type system composed of Rust enums, which attempt to capture the rules about what is possible in CSS. The Rust type system ensures that the tree structure aligns with CSS specification rules.
Layout 2020 uses recursive tree traversals to produce the fragment tree, following a more traditional, imperative code style. Parallelism is used opportunistically, when a given subtree allows it. When floats are involved, parallelism will not be possible for sections of the tree, though it could still be used within descendant formatting contexts.
The final step of layout is to convert the fragment tree into a tree of stacking contexts. This step properly orders content in accordance with the painting order defined in CSS2 Appendix E. This is necessary because some elements may need to be painted before their ancestors.
This stacking context tree is converted directly into a WebRender display list. Layout 2020 does not use an intermediate display list structure, because it was designed after the use of WebRender in Servo.
More information about Layout 2020's design can be found on the Servo wiki.
Both layout engines would require a significant amount of work to bring them up to the standards of a modern web engine.
The project wiki contains a summary of the status of many CSS and HTML features in each engine. In general, Layout 2013 currently has support for more features, but there are a few cases where Layout 2020 has better support, such as content: attr() and containing block support for transformed elements.
There is no real support for modern layout techniques like flexbox or grid in either engine, and there are many bugs with basic layout features in both engines.
Perhaps the most notable feature missing from Layout 2020 is support for floats. There is an implementation in progress, but work has stalled and it is not yet enabled outside of unit tests.
Layout 2013 supports floats, though the eager parallelism design means that certain aspects of float layout are very difficult to implement and violate the original four-traversal layout structure. Over the years, an extra traversal has been added to handle them, but there are still bugs that would require a significant engineering effort to fix, making it difficult to maintain.
Incremental layout support in Layout 2020 is at a very early stage. While much discussion has gone into its design, very little implementation has taken place. Creating an implementation in Layout 2020 on par with the one in Layout 2013 would require more work, including the implementation of damage tracking and laying out only part of the DOM tree.
On the other hand, Layout 2013 already supports incremental layout, where style changes mark elements with different types of damage, meaning that layout does not necessarily have to modify the entire layout tree. We may be able to reuse some of this damage architecture for Layout 2020.
Generated content support is still quite basic in Layout 2020, with only preliminary support for :before and :after, and no support for counters, ordered lists, or quotes. That said, the design of Layout 2020 should make counters easier to implement than in Layout 2013.
Layout 2013 does have support for generated content and counters, but a special traversal has been added at the start of layout in order to properly calculate counter values. Like the implementation of floats in Layout 2013, this breaks the original four-traversal processing model.
We have created a dashboard to track the pass rate of various subsets of the WPT tests. Currently this dashboard focuses on the CSS2 features. In general, these tests show a greater differentiation in pass rate than the complete set of WPT tests. These tests confirm that with regard to CSS2, the main areas in which Layout 2020 lags behind Layout 2013 are floats and line layout.
| Focus | Layout 2013 | Layout 2020 |
|---|---|---|
| CSS2 focus folders | 83.2% | 64.0% |
| -- /css/CSS2/abspos/ | 40.3% | 86.5% |
| -- /css/CSS2/box-display/ | 81.1% | 65.5% |
| -- /css/CSS2/floats/ | 51.4% | 18.6% |
| -- /css/CSS2/floats-clear/ | 67.2% | 18.4% |
| -- /css/CSS2/linebox/ | 86.1% | 52.3% |
| -- /css/CSS2/margin-padding-clear/ | 90.6% | 67.6% |
| -- /css/CSS2/normal-flow/ | 87.5% | 71.8% |
| -- /css/CSS2/positioning/ | 81.4% | 78.2% |
| All WPT tests | 58.5% | 54.0% |
Performance is a critical component of a web engine, thus proper tracking of performance bottlenecks and regressions is very important for Servo. Part of Servo's key propositions is that Rust's "fearless concurrency" will unlock greater opportunities to increase performance over traditional web engines. Yet, regarding the performance of Layout 2013 and Layout 2020, given the current status of completeness and the difference in features supported between them, it is not entirely useful to do a performance comparison between the two engines.
While we may expect that Layout 2013's eager parallelization approach might lead to better performance than Layout 2020, in practice the benefits are difficult to observe. There are cases where this kind of parallelization can decrease performance. In addition, Layout 2020 still uses some amount of parallelization, and further development should allow even more use of parallelism.
We have run some basic Chromium performance tests in both engines for simple CSS features. The results show that Layout 2020 has good performance characteristics in comparison to Layout 2013, with Layout 2020 being slower in some cases and faster in others, but no large divergence in either engine.
| Test | Layout 2013 | Layout 2020 |
|---|---|---|
abspos.html (less is better) |
641 ms | 417 ms |
attach-inlines.html (more is better) |
34 runs/s | 54 runs/s |
chapter-reflow.html (more is better) |
110 runs/s | 78 runs/s |
line-layout.html (more is better) |
168 runs/s | 164 runs/s |
many-block-children-auto-inline-size.html (more is better) |
81 runs/s | 120 runs/s |
This topic deserves a deeper analysis in the future, especially when a more complete set of CSS features is supported. It would also be useful to compare Servo performance with that of other web engines. At some point, performance bots will be useful to track performance and catch regressions, as part of our ongoing work to improve Servo's infrastructure. That said, during the development phase of large it would not be unusual to find large performance fluctuations as features are added and then optimized.
Layout 2013 is Servo's original layout system, and thus has the benefit of years of implementation and bug fixing. Support for floats and many other basic CSS2 features is there, even though layout for certain basic pages is difficult to implement properly due to the design of Layout 2013. Layout 2013 is currently able to lay out many sites with better results than Layout 2020. In practice, that means Layout 2013 does a much better job of laying out the web than Layout 2020.
Layout 2013 is built from the start to implement a parallel layout. By default, when nothing serializes the layout of a page, it will use a parallel algorithm to do its work. This means that for some pages, Layout 2013 may do a better job of spreading work between multiple CPU cores.
Layout 2013 presents several weaknesses in comparison to Layout 2020, in particular owing to its creation as an experimental layout engine trying to fully take advantage of Rust's support for parallelism. This emphasis on maximal parallelism makes it much harder to correctly implement CSS features like floats and margin collapsing. While these features may be possible to implement in a fully parallel layout system like Layout 2013, it is impossible to do so cleanly, which hurts maintenance and slows development. The only alternative is to implement a serialized codepath for these features, which essentially means a dual implementation of basic layout.
Layout 2013 was designed as a novel three-pass system (described above) that is conceptually very clean, but CSS does not always conform to this three-pass system. Due to CSS painting rules, a fourth pass has been added (display list construction), and because WebRender was introduced after this fourth pass, yet another pass is necessary to convert the legacy display list to a WebRender display list. In Layout 2020, WebRender display lists are created directly from the Fragment tree after it is organized into stacking contexts.
Development on Layout 2013 started well before the stabilization of many features of the Rust language, and thus the code contains legacy design decisions and workarounds for old language limitations. For instance, Layout 2013 uses a pseudo-inheritance system that clashes with current Rust conventions. These can be gradually removed, but this presents an additional maintenance burden for a small team working on layout. Finally, the amount of unsafe code in Layout 2013 is quite large, due to the pseudo-inheritance and parallel layout designs.
Layout 2020 presents some advantages over the legacy Layout 2013 system. In particular, it has a two-tree design, like the next-generation layout systems of Blink and WebKit. This allows for proper fragmentation across pages and columns, which is a requirement for a fully spec-compliant web engine.
This new design also allows us to correct design mistakes from the previous engine, align ourselves with later, more mature, versions of the specification, and take advantage of the large improvements made to the Web Platform Tests (WPT) since the early days of Servo. As an example, transformed content in Layout 2020 properly uses the root of the transform as the containing block, while in Layout 2013, the containing block for transformed content is the initial containing block.
Perhaps most importantly, moving away from the "parallelization by default" approach that was an integral part of Layout 2013 makes the implementation of certain basic features, such as floats and counters, much more feasible. With Layout 2013, such an implementation would require much more work and likely more code. Layout 2020 can use design ideas from other web engines such as Blink and Gecko, while still taking advantage of parallelism opportunistically thanks to the safety guarantees of Rust and its rich ecosystem of third party libraries.
Key concepts in Layout 2020 use names that are more in line with the language used in the specification. For instance, Layout 2020 has data structures for inline formatting contexts and block formatting contexts and they are named using this terminology. This makes work on Layout 2020 more accessible to outside developers, who may only be familiar with the CSS specification itself. Layout 2013 often uses naming schemes for variables and data structures that do not accurately describe the concepts that they are used to implement or have become out of date.
The main weakness of Layout 2020 is that the implementation of basic layout features currently lags behind that of Layout 2013, and several of these features are quite important for a fully functioning layout system. A switch to Layout 2020 would require an intense emphasis on the implementation of floats, counters, and incremental layout. In addition, there would need to be effort to improve the implementations of margins and line layout. This is all work that would not need to be done with Layout 2013.
Layout 2020 took the design decision to make paralellization opportunistic. This means that all speedups for parallelization require manual intervention in the code base. This often involves reorganizing the code, though there are already some examples of this kind of work.
It is clear that any decision about the future of layout in Servo must balance the maturity of Layout 2013 with the unfulfilled opportunities of Layout 2020. Despite its immaturity, Layout 2020 has a more modern design that avoids some of the pitfalls of Layout 2013.
We believe that Layout 2020 is the best layout engine for Servo going forward. We've made this choice taking into account the goals of developer friendliness as well as possibilities of a more complete and standards-compliant implementation of CSS. We think that continuing to develop Layout 2013 will increase the overall maintenance burden of Servo, and make it harder to correctly implement features like floats than in Layout 2020.
Our proposal is to gradually transition Servo to use only Layout 2020. The first stage would be to implement a few missing features in Layout 2020 over the next quarter, to evaluate the developer experience of this engine. Some of the features we might attempt to implement immediately include <iframe>, position: sticky, text-indent, and outline. As time goes on, we may also explore some more complex features such as counters, writing direction, and writing modes.
This transition also involves gradually emphasizing Layout 2020 over Layout 2013 in builds and continuous integration, but we will not remove Layout 2013 in this period, leaving open the opportunity to reverse directions if necessary.
If our experiment proves successful, we will remove Layout 2013 from the tree, and by that point we will have the necessary experience and confidence in our decision to move onto the most complex and important CSS2 features like floats.