Thoughts on Incrementalization

[viridia]

In my previous post #20821, I tried to narrow the discussion to just reactions, avoiding any discussion of incrementalization. However, since @JMS55 brought up incrementalization, I figured I would write a post that explores this topic.

What is incrementalization?

I first heard the phrase, "Every modern UI framework contains an incrementalization strategy" in one of Raph Levien's talks, although he didn't originate the saying.

In a nutshell, incrementalization refers to a way of dynamically updating a UI hierarchy (or any display hierarchy for that matter) via patching:

• Display hierarchies are trees of nodes
• Trees are patched rather than being replaced wholesale
• Essential state - like text cursor position, selection, IME state, etc. - is preserved between updates.
• Dynamic elements are defined declaratively: we aren't just writing code to manually mutate nodes. (While technically manual mutations are "incremental", they aren't considered a "framework".)
• Dynamic elements are controlled by input parameters; changes happen in response to submitting new parameters.

In effect, incrementalization is a way to implement the following formula: old_tree + new_parameters => new_tree, such that new_tree re-uses the parts of old_tree that didn't change.

A key requirement is that incremental updates should produce results that are indistinguishable from rebuilding everything from scratch: that is, given the same input parameter values, it shouldn't matter whether this is an incremental update or an initial construction. It should look like a "pure function" even when it isn't.

As pointed out in the comment, you can have incrementalization without reactivity: it just means that you have to change the input parameters manually.

Various Strategies

The display tree - what the user actually sees - is the output of an algorithm, however we need more than just the output in order to construct that tree. We need some kind of template or blueprint: a data structure that describes the output we want to generate.

We also need to store some kind of parameter state: the value of the parameters from the previous update, along with any intermediate values derived from them. There might also be local state.

Different UI frameworks approach this problem in different ways. Some of the ones I have seen are:

Long-lived scaffolding that exist separately from the output tree but are connected to it (React, Dioxus). In this approach, the user constructs some alternate tree (the "component hierarchy") that is not the output itself, but rather a scaffolding for building the output. This tree has roughly the same shape as the output.

The user usually doesn't reference the output directly - that is, the user doesn't keep around a reference to the DOM node or entity, instead they hold on to a reference to the scaffolding (an instantiated template), which in turn holds a reference to the output roots. Updating the parameters of this template causes a regeneration of the output.

In this approach, the parameter state is typically stored as properties within the scaffolding nodes.

Temporary scaffolding is a tree that is newly constructed each time (Xylem). In this approach, we regenerate the scaffolding every time from code, throwing it away as soon as we are done. In order for this approach to work, we need three for things to be true:

• The construction of the scaffolding has to be very cheap, it shouldn't involve a lot of memory allocations. There are different ways to do this in Rust, either by using a bump allocator, or by building the tree out of nested tuples.
• The parameter state has to be held external to the scaffolding, in a separate data structure, so that it can be longer-lived.
• The output tree can't radically change shape independently from the scaffolding. The scaffolding expects the shape of the output will match the shape from the previous run, so that it knows where to patch.

Scaffolding embedded within the output as hidden metadata. In the case of Bevy, this can often be done by hidden components (hidden in the sense that they have no effect on the entity's appearance). However, we frequently run into cases where there's no unambiguous single entity that should "own" the scaffolding: examples are templates with multiple roots, or conditional blocks with multiple children. In these cases, we need to insert additional entities, such as ghost nodes, into the tree to hang on to this data.

Differencing

All of the solutions mentioned use some form of "diffing", in the sense that there's some code that compares the old state to the new. However, this may or may not involve actually walking the entire output tree and comparing every property.

In fact, all diffing solutions are selective to some extent: just blindly iterating over all properties (via reflection) doesn't work, because there are some properties that need to be able to update on a different schedule. This is true in React as well: popular animation libraries such as react-spring and framer-motion directly update animatable properties in the DOM, bypassing the diffing mechanism, as this is the only way they can achieve high frame rates cheaply.

This is one of the reasons why React uses a VDOM (Virtual DOM). Not only does it avoid slow DOM operations like appending a node, but the VDOM only contains properties that are meant to be diffed, and doesn't include properties that we want to mutate directly.

For a VDOM, it's pretty simple: if the user mentions a property in the template, then it's meant to be diffed; otherwise leave it alone. This requires a data structure that supports a sparse representation of properties, which entities and components certainly do not.

This has consequences for Bevy: it means that a naive approach which attempts to diff components using reflection won't work, since the diff algorithm would have no way to know which properties are suitable for diffing and which are not (particularly because this decision is highly context-sensitive). Instead, you'd have to build some separate AST-like structure which could then be transformed into entities. This is effectively how Dioxus works, if I understand things correctly.

Some frameworks (like Svelte and Solid) know at compile time which parts of the output hierarchy are static and which are dynamic (they can look for dynamic control-flow elements in the template), and avoid diffing the static parts.

You can take this even further and apply diffing at the parameter state level instead of diffing the output tree, at which point your incremental strategy becomes a kind of memoization of sub-trees rather than a classic "diff". This also avoids wasting time rebuilding parts of the tree that don't change, and which would be discarded after discovering that the diff detected no changes.

Is BSN incremental?

BSN, as currently prototyped, does involve something called a "patch". However, the patch mechanism in BSN is designed to facilitate composition, not dynamic updates. It allows you to bring together multiple sources during construction. It's not designed to modify entities once construction is completed.

Working with BSN macros right now is a little bit like the "temporary scaffolding" approach: you produce an impl Scene, this is used to construct an entity tree, and then the Scene is disposed. It doesn't have any long-lived parameter state, which would require a much different API.

There are a couple of ways that BSN could be extended to support incrementalization:

• Building incremental support into BSN's core design.
• Building incrementalization beneath BSN: using the "embedded" approach to implement incremental updates at the ECS level instead of at the level of scenes and templates.

The second approach is the one I am currently experimenting with. The basic idea is that you have components whose job it is to perform dynamic updates on the tree. As far as BSN knows, these are just components like any other, there's no special support for them. The downside is that, without any kind of special syntactic sugar for dynamism, the syntax for defining these components is a bit boilerplatey. My approach also continues to rely on the ghost nodes feature.

[alice-i-cecile]

Some observations to check my understanding. I don't have much experience with these frameworks, so please grade my answers and correct me!

1. Incrementalization is not used for immediate mode UI frameworks: by definition they just rebuild everything from scratch every frame.
2. The only inherent value of incrementalization is as a performance optimization (which may be very valuable, but there's no other reason to do this).
3. You could have a declarative UI that does not use incrementalization (in fact, this is how immediate mode UI works).
4. Declarative approaches to UI pair well with incrementalization, because they make it easier to understand the complete set of changes / behavior / input.
5. Immediate mode UI similarly needs to concern itself with persisting important state (and this is one of the major sources of complication when building and working with immediate mode UI).
6. When using a "embedded scaffolding" approach, it's better to create extra nodes (in the form of entities) rather than dumping the extra state into a resource etc because then it's easier to integrate with the rest of our tooling: entity cloning, inspection, event bubbling etc.
7. By directly animating the desired properties in the DOM, libraries like react-spring are effectively mutating causal leaf nodes, preventing further reactions.
8. In VDOM-based solutions like React, the entire DOM is a causal dead-end (in terms of incrementalization and reactivity): changes made to the DOM do not trickle down to the rest of the DOM, or back to the VDOM.
9. In a DOM / VDOM solution, only the DOM is actually used for rendering / interaction.
10. In a DOM / VDOM solution, the VDOM is effectively compressed, and stores a smaller, faster-to-work with form of the intended layout.
11. By memo-izing subtrees, you mean that we would compare the final state of subtrees, and then check for differences. In order for this to be effective, we would need some principled rules about how different parts of the UI state could effect other parts: arbitrary global side effects would render this strategy useless.
12. Dioxus works by parsing ASTs in complex ways, and then generating Rust code with the desired behavior by analyzing the actual code provided by the user (rather than sticking to the type level, like Bevy).

[alice-i-cecile]

@JMS55 has corrected me on 2 ("The only inherent value of incrementalization is as a performance optimization"). You also need some sort of strategy to avoid clobbering important state (like events or animations). Simply mass respawning everything each frame will break this (see 5).

bevy_ui currently doesn't have a unified solution for incrementalization, but because it's retained, we're not losing state like this. However, bevy_ui's current design is very hard to scalably make declarative: it requires tons of systems and marker components to update things.

[viridia]

The question that must be asked about immediate mode is, is it truly immediate, or is it just relatively immediate? A truly immediate mode API would be completely stateless, and would leave behind no artifacts other than changed pixels. However, a lot of APIs which advertise themselves as immediate actually do build a hidden, low-level retained data structure. In this, they are not much different than the "transient scaffolding" approach.

For example, in bevy_egui, how does a text widget maintain a persistent cursor position between frames? The user isn't required to manage this, or the selection range, so there must be some kind of hidden state which is "retained". I don't know enough about how this, or bevy's Gizmos, work to say much more.

Mutating DOM properties directly in React: this is the React version of "unsafe": something that is officially sanctioned, but with scary warnings in the documentation. You're free to modify properties as you like, but React will blow away your modifications if it thinks that property is one that it's supposed to manage.

An example of memoizing subtrees would be something like a switch statement: each of the various case clauses in the switch may have its own subtree, but the only thing we need to "diff" is the discriminator: the value that determines which branch we are taking. When that value changes, we despawn and recreate the entire subtree: we don't try to diff between case clauses which may have different shapes.

This brings up the issue of hot reloading, which superficially resembles dynamic switch, in that they both entail replacement of parts of the tree. The difference, though, is that in the dynamic switch case, we can assume that the template source of truth hasn't changed, only the input parameters have; the old version and new version may include different subtrees, but the subtrees that are present have the same shape as before. Whereas in a hot reload scenario all bets are off.

The metaphor I like to use is a complex rail network: dynamic switching is like changing the track switches that route trains to various destinations, whereas hot reloading is like ripping up the track and laying down rails in new locations - the former is a lot more predictable from the framework's perspective.

As a result, hot reloading scenarios tend to be more tolerant of non-incremental replacements: in React for example, touching a source file tends to replace all of the components defined in that source file, as well as any of their descendants; they don't try to do incremental updates within a changed source file.

[alice-i-cecile]

I have some implementation thoughts on this, from an ECS perspective:

In fact, all diffing solutions are selective to some extent: just blindly iterating over all properties (via reflection) doesn't work, because there are some properties that need to be able to update on a different schedule. This is true in React as well: popular animation libraries such as react-spring and framer-motion directly update animatable properties in the DOM, bypassing the diffing mechanism, as this is the only way they can achieve high frame rates cheaply.

This is one of the reasons why React uses a VDOM (Virtual DOM). Not only does it avoid slow DOM operations like appending a node, but the VDOM only contains properties that are meant to be diffed, and doesn't include properties that we want to mutate directly.

For a VDOM, it's pretty simple: if the user mentions a property in the template, then it's meant to be diffed; otherwise leave it alone. This requires a data structure that supports a sparse representation of properties, which entities and components certainly do not.

There are a number of ways we could handle this, if we wanted to :) Ultimately, this is a question of "we need to be able to reason about components, based on the properties of that component type". Some options:

1. Component metadata (possibly stored via components-as-entities), which determine whether or not a specific component should be diffed.
2. Some metadata in the Reflect trait about which fields should be diffed.
3. Trait queries (Add trait queries (by upstreaming bevy-trait-query) #15970), looking for all components that implement a Diff trait.

In most cases, we would want some custom mechanism for "how should this be diffed", to allow for flexibility in terms of which fields we care about for example. The easiest way to do that would be to use the same strategy as FromWorld: provide a blanket implementation of Diff over T: PartialEq, allowing for a nice fallback.

Unsurprisingly, the "component metadata" and "trait query" approaches lead to the same solution here. Trait queries are effectively a convenient conceptual framework to allow for the querying and usage of metadata about each component type.

I think that trait queries are the best approach here (they're more principled than just "more metadata"), and think that using Reflection to do this is likely to be both slow and leak implementation details down into the stack: bevy_reflect should not have to care about these problems, and frankly is the wrong tool for this entirely. Relying on bevy_reflect for production features like this is also bad, because that means we can't disable it (saving huge amounts of binary space) when shipping prod builds.

[alice-i-cecile]

Behavior for "do not diff this component for reactivity on this entity" could be handled fairly easily IMO, by creating opt-out generic components. This would involve a bit of engineering, but should not be treated as a blocker.

[alice-i-cecile]

Trait queries, for the record, rely on "reflection", but not bevy_reflect. In order for them to work, the type must be registered, allowing us to map information about the component type to the traits it has and the function pointers for its methods at runtime. #15030 makes that much less onerous now.

[alice-i-cecile]

My understanding of the problem space is that even if we could do this, we would still need ghost nodes (or something equivalent). There really is just no good spot to store various properties sometimes if we restrict our tree to only "physical" entities.

[nicoburns]

Some frameworks (like Svelte and Solid) know at compile time which parts of the output hierarchy are static and which are dynamic (they can look for dynamic control-flow elements in the template), and avoid diffing the static parts.

Dioxus also does this. It's a key reason for using a macro. The macro inspects the syntax tree and marks anything constant (e.g. string literals - which are pretty common for things like style properties) as not needing to be diffed.