UI layout calculations are slow. This is the nature of a responsive system which allows bidirectional size constraints, like basically any decent layout system offers. I’ve done a lot of work with layout before, and it popped up again after I wrote about Unity’s new UI Toolkit. Solving this problem was one of the most challenging projects I’ve had, and I’ve already written several articles on it. In this article, I’d like to take a high-level view of the problem, to explain why UI layout calculations are slow.
The bad news is it’s an exponential algorithm. Yet, in practice, we can heavily optimize it to near linear performance. But, more bad news: your favourite library may not be doing that.
UI’s can also suffer from render-time slowness, which is orthogonal to the calculation speed. I won’t be looking at render performance here.
The Basic Structural Issue
Consider this basic layout, which can be done with any modern layout system. I’ll be using a pseudo-language here to make my intended layout clear; the actual language used in tools, such as flex-box, can be quite confusing.
-
Vertical Stack Panel, place on left-center of screen
- Single-Line Text
- Center Image
Rather than jumping into a full calculation system, let’s do some hand-waving to understand what happens. To place this panel in the correct location, we need to calculate the size of the child elements. In this case, it is relatively easy. Calculate the extents of the text, load the image’s size, then add them together. Knowing the panel’s size, we can calculate where to put it on the screen.
But we said the image is centered, in this case, we want it centered horizontally in the panel. We can’t know what the center is until we’ve calculated the size of the panel. I said this example is simple because the centering of the image doesn’t affect its size, but it still requires multiple layout passes. In the first pass we figure out the size needed, and in the second pass we position the elements.
We might also assume that our text should be centered if the image is wider than it. These are dependent positions: the position of an element depends on the positions of those around it.
Dependent Sizing
Let’s add another element to create a more complex system: some multi-line wrapping text.
-
Vertical Stack Panel, place on left-center of screen
- Single-Line Text
- Center Image
- Multi-Line Text, wrap to panel
What does “wrap to panel” mean? We’d like to express that this text should flow into the natural width of the panel, but doesn’t contribute to the width itself. If you consider a text document, the text flows to the full width of the page. It always flows to fill something. In our case of the panel, it flows to fill the panel, and that’s the problem.
In the first pass to figure out the sizes of the child elements, but what width do we use for the wrapping of the text? On this first pass through, the multi-line text can’t properly answer, since it doesn’t know how big it will be. Specifically, it doesn’t know how tall it will be until it knows how wide it should be.
This creates the notion of a dependent size: the size of the multi-line text depends on the size of its siblings. Or, more generally, the size of elements can depend on the size of other elements, either immediate siblings, ancestors, or basically anywhere else in the tree.
What does this mean for an implementation? We can glance at this and see the solution, but obviously code can’t. A layout engine needs to do multiple sizing passes over the panel. In the first pass, it needs to ask the children what size they want. In the second pass, it asks them again, this time with another constraint.
This may not seem too bad, but let’s continue…
Another Panel
What happens if we add our vertical panel into a horizontal one, with another image in it?
-
Horizontal Stack Panel, center vertically on left of screen
- Tall-Image, stretch to height
-
Vertical Stack Panel
- Single-Line Text
- Center Image
- Multi-Line Text, wrap to panel
We want the tall-image to stretch to fill the height of the horizontal panel. Its width will depend on this height, keeping its natural aspect ratio. This type of layout is quite common, such as an icon placed beside an author box, or a vertical divider between sections.
We know that the vertical stack panel requires multiple passes over its children to determine its size. By the same logic we know that the horizontal stack panel will need multiple passes, as the tall-image can’t determine its height, nor width until we know the height of the vertical stack panel.
We’ve come to the crux of the performance issue. Each time you add a constraint to the layout, you need another calculation pass. The first pass for the horizontal panel gets the initial values. It then uses those values as a constraint for the next pass. In each pass of the horizontal stack panel, you ask the vertical one for its size, but in both cases it has different constraints. And for each set of constraints, you do two-passes on its children.
If each element requires two-passes to determine its size, then a tree of N elements requires 2^N passes to determine all the sizes. Yikes! We’re facing an exponential algorithm. No wonder layout is slow.
Optimization
Yet, our browsers and mobile apps manage to layout hundreds, even thousands of elements. Are they not using an exponential algorithm? Well, they have to be, since they provide layout systems that require it. It’s relatively easy to create deeply nested layouts where the size of a deep leaf node can alter the layout of the entire tree. And if you add some dynamic elements, or worse, animation, then the costly calculation needs to happen again and again.
If the layout system designers were clever, they can create a system that in typical use doesn’t require exponential passes. While we can play with highly dependent sizes, real layouts involve lots of constraints and fixed sizes. An algorithm can use this knowledge to avoid most of the passes.
My goal when doing Fuse’s layout system was to get as close to a linear calculation as possible. I did this with lots of memoization, as well as giving onerous requirements to per-element layout calculations. They weren’t allowed to be naive, but had to consider constraints. It was okay, since I had to write those as well. Anyway, I go into this more in the “Engine” part of “Writing a UI Engine”.
I fear, however, that many layout systems don’t use this additional knowledge. Certainly, the origins of Fuse’s system, WPF, didn’t allow it; I had to change architecture to make it a tractable problem. In HTML, the table element creates an intractable layout calculation. And while common flex-box layouts can be optimized, does it allow for situations allowing deep exponential passes?
I think about all the libraries doing layout, and wonder how many of them suffer exponential recursion. In relation to my current project, is this why uGUI in Unity is slow? Does the reported slowness of UI Toolkit stem from the same problem? Hopefully the answer is yes, since it implies that it can be fixed. It also means that, once optimized, there are rules to follow to avoid making slow UIs.
This is part of a series on Writing a UI Engine
