Fluid layout animation: Invalidation and caching

Dynamic changes in layout properties, either because of user actions, or animations, requires a recalculation of the layout. Maintaining a stable frame rate during recalculation is challenging, as the layout process is relatively expensive. In this article we’ll talk about the two key approaches that make fluid layout animation possible: limited invalidation and layout caching.

Locality observations

We base this approach on two key observations:

• Most of the layout is static, only a few elements actively change
• Changes in layout tend to result in local effects: they may cause a change in parent layout, or a few children, but rarely impact the entire tree.

Our goal in layout is to limit the recalculations to only those elements that will get a new layout.

Downward caching

Let’s start with the easy case: caching. During layout traversal a parent element will make a few requests to a child element. When something small changes, many of these child requests will be the same as a previous request.

The first location is GetMarginSize, as described in the layout protocol. Given two equivalent LayoutParams, and assuming nothing has changed in the child’s tree, the resulting size should be the same. We can cache these results so that future calls to GetMarginSize need not traverse further down the tree.

There’s a trick here though. For constraints, and the occasional multi-pass calculation, GetMarginSize is called multiple times with different LayoutParams. Caching just one result is not sufficient. It turns out that two is enough — this comes from ensuring most of the layout code can be done in a single pass. One call to get the desired size followed only by another call to do the actual layout. If setting the cache size higher helps, it may be a sign that something is doing too many passes higher up.

The second optimization really isn’t a cache. A call to ArrangeMarginBox may provide the element with the same parameters and size it had before. We can avoid some local calculations if the resulting size is the same as before. Unless the LayoutParams is exactly the same though, we still need to traverse to the children.

Upward invalidation

When a layout parameter for an element changes we invalidate its layout. Since a parent’s layout may depend on the size of the child, we also mark the parent as invalid. We repeat this until we reach the root of the tree. During one frame multiple elements can be marked invalid, and they’ll each create an invalidation path to the root.

Each frame we check if there are any invalidations and start a new layout request from the root of the tree. The caches can speed up this part, but it’s still covering far more nodes than are strictly necessary. It’s a good place to start however, and it’s how we I started with the engine. The caches, and avoiding redundant layout on elements, provides a significant boost in performance.

The next boost is avoiding invalidation all the way to the root element. As most animations, and user interactions, take place near root elements, they tend not to alter the overall layout of the app. It’s silly to start the layout calculation at the root each time — even better than cached results is not calling those functions at all.

IsMarginBoxDependent

I created this virtual function on the elements:

/**    
    @return Yes if the child influences the results of ArrangeMarginBox (size or layout of this node),
        No if it cannot, and Maybe otherwise (in cases of stretching)
*/
protected virtual LayoutDependent IsMarginBoxDependent(Visual child) {
    return LayoutDependent.Maybe;
}

Ignoring the Maybe result at first, the function determines whether the layout of this element is affected by a particular child. For example, in a layered layout, the children are independent of each other, and the parent’s size is not dependent on them — it would return No for all children. An example of Yes is a StackPanel. If the size of any of it’s children changes, its own size changes, as well as the positions of all of its children.

The Maybe result is used when the answer can’t be determined locally. Consider these two examples:

Panel {Alignment=TopLeft}
    Rectangle {Color=Green}
        Text {Value="Hello"}
        
Panel {Width=200 Height=200}
    Rectangle {Color=Green}
        Text {Value="Hello"}

If the value of the Text changes it invalidates the layout of the text element. The element will call Rectangle.IsMarginBoxDependent( Text ), but the answer differs in each scenario. The Rectangle itself doesn’t know the answer, it depends on the parent Panel. In the first case the panel, thus rectangle, collapse to the inner size of the text — the Rectangle does depend on the Text size. In the second case, the Panel has a fixed size, the Rectangle expands to fill that — the Rectangle does not depend on the Text size.

A result of Maybe defers the question to a parent node. Once the definitive answer is known, the traversal goes back to the first element that said Maybe, and updates the answers.

The invalidation traversal algorithm isn’t large, but it’s complex. It must deal with multiple invalidations in the same frame — nodes that are invalidated by one element, may be invalidated by another one. My algorithm split No and Maybe to create a NoArrange and MaybeArrange. This allowed an element to say its own size is not affected, but the arrangement of the children is. A minor detail, but it brings a big boost in some common situations.

The value in the IsMarginBoxDependent function is no longer needing to start layout from the root node each time. We can localize the changes and jump down to those elements. Combined with caching this provides highly localized recalculation, fairly close to what you’d expect based on the visual changes.

To avoid another data structure, I built this tracking status into the normal invalidation flags. It still technically started at root, but it had a flag indicating whether layout was required, or to only scan the children looking for a change. If you consider the amount of pruning in the search, this is a nearly linear search, of the depth of the tree, to find the starting points. It’s tempting to store a list of entry points instead, but that gets rather costly when trying to resolve multiple invalidations in one frame.

The function IsMarginBoxDependent is typically answered by the layout a panel has. It can be a tricky function to get right. One must err on the side of caution, essentially returning Yes by default, and No only in some specific situations.

Testing and iteration

A good thing is that this approach can be built iteratively. The caching bits can be implemented independently, as well as the tree invalidation.

IsMarginBoxDependent need not be implemented everywhere at first, the default value always works; it simply isn’t optimal. I implemented this per layout as I found situations where it’d be helpful. Indeed, most of the details in all these optimizations were based on common use-cases — the general case is too broad.

Testing is essential during invalidation. Tests need to cover all sorts of invalidation to ensure that the correct elements get invalidate, as well as verifying the optimized paths are applied. Minor changes in the code can have major effects!

As with the other articles, this article leaves out many details about how the code might look. It covers some key concepts and approaches to optimization. Precisely how this implemented depends a lot on your overall approach. There are many things I’d do differently if implementing this again, but these core concepts would remain.