# Deterministic Anonymous Attribute Lifetimes

The purpose of this document is to provide some context to the anonymous attributes lifetimes refactor.

## What are anonymous attributes?

Anonymous attributes are one of the two key concepts that were introduced in Geometry Nodes in Blender 3.0. Together with fields they were originally proposed on [devtalk](https://devtalk.blender.org/t/fields-and-anonymous-attributes-proposal/19450) as a solution to severe usability problems.

Anonymous attributes are attributes that don't have a name (that's visible to the user). This has a couple of benefits:
* Users don't have to specify the name to use an attribute created by a node.
* Attribute name collisions can be avoided automatically.
* It's possible to detect where they are used and their creation and deletion can therefore be automated. Note that this is not generally possible with named attributes, because they may even be used after export in other software. Named attributes are expected to stay around when they are not removed explicitely.

Numerous built-in nodes create anonymous attributes and output fields that reference them. In the image below are a few. All the non-geometry output sockets reference anonymous attributes.

## What is their lifetime and why do we care?

Since anonymous attributes are created and removed automatically, the question arises where that actually happens in practice. The lifetime is essentially the set of geometry sockets when contain the anonymous attribute. It begins when the attribute is created and ends where the attribute is removed. Note that while there is a single node that creates the attribute, there can be multiple that delete it.

The general goal is to make anonymous attribute lifetimes as short as possible, because unnecessary attributes on a geometry are just wasteful. That's because they take up memory and might have to be processed by later nodes.

For example, the _expected_ lifetime of the Top attribute in the image below ends at the input of the extrude node. The attribute should not be propagated to the extruded mesh, because it's not required anymore. As we'll see, the _expected_ lifetimes does not match the _actual_ lifetime of anonymous attributes currently. Often the _actual_ lifetime is (a bit) longer than the _expected_ lifetime.


## Why are their lifetimes not deterministic currently?

To get the field and anonymous attributes systems up and running quickly, we used a relatively simple approach to deal with the lifetimes: reference counting. Essentially, for every anonymous attribute a reference count is allocated, that keeps track of how many geometries contain the attribute, and how many fields reference the attribute. Whenever a node propagates attributes from one geometry to another, it checks whether any field still references anonymous attributes. If one is found that is not referenced anymore, it is not propagated.

While this approach is relatively simple to implement, it has some issues:
* It is not deterministic. The same node may sometimes propagate an anonymous attribute in one evaluation, but not in the next, even though nothing else changed. That's because the order in which nodes are evaluated is not deterministic (nodes are evaluated on multiple threads). This has the effect that sometimes a field that references an attribute has or has not been freed before the node is executed.
* The actual lifetimes of attributes is almost always a too long. For example, in the image above, the extrude node currently does propagate the Top selection from the Cylinder node, even though it's not necessary (the Subdivide Mesh node does not though). That's because the field referencing the attribute still exists while the extrude node is evaluated.

Another issue is that it can happen that (non-deterministically) an anonymous attribute is created sometimes, but sometimes not. For example, in the image below the Normal output might be created sometimes, even if the Switch input is true (and hence it would not be needed). That's again caused by non-deterministic node evaluation order. If the Distribute Points on Faces node is executed before the Switch node, it does not know yet whether the Normal output will be required or not. Therefore, it has to create the attribute, because adding it later is not possible.


## Why do we want them to be deterministic?

Deterministic lifetimes are necessary for different kinds of caching. That is because, non-deterministic lifetimes lead to nodes doing different things even when the inputs are exactly the same. Cache invalidation is already hard enough when you know all the data that feeds into the computation of a geometry. It's essentially impossible when not all data sources are known and they are non-deterministic.

This applies to planned automated caching in geometry nodes, as well as simulation caching that is being worked on.

There are other benefits to deterministic attribute lifetimes:
* We can debug and visualize them. Showing them to users may make it easier to understand the benefit of anonymous attributes over named attributes. We can also show hints to users when a link does not make sense because an attribute referenced by a field does not exist on the geometry it is evaluated on.
* Solving the problem deterministically also means that we can make sure the expected and actual lifetimes match always or at least more often.

## Naive Solution

There is one very simple solution that would make anonymous attributes lifetimes deterministic: always create all anonymous attributes possible and never delete them before during geometry nodes evaluation. While this works, it causes a lot of overhead that can make geometry nodes much slower than necessary.

Knowing about this solution is useful, even though it is not practical. That's because it is still _correct_ in the sense that the user-observable behavior of geometry nodes (except for performance) is the same as before. This shows that better anonymous attribute lifetimes are just an (important) optimization. Therefore, the actual lifetimes don't always have to be perfect if they are at least as long as the expected lifetimes. In common cases it should be possible to achieve perfect lifetimes, but it's not obvious that it is always possible. Some times it may be hard to analyse node groups which contain many switch nodes.

## How to achieve better lifetimes determinstically?

There are multiple ways to do this which vary in their complexity and efficiency. For example, switch nodes could be ignored completely in the lifetime analysis. This would simplify the solution, but causes actual lifetimes to be much longer than necessary in many cases. One could also try to find "global" solutions, i.e. first inline all nested nodes into a single node tree and then do analysis there. This can have a very large upfront cost that's especially bad when many of the nodes aren't actually evaluated (because they are disabled with a Switch node for example). Below, I'll explain the solution I currently have in mind without wandering off into alternatives too much, to keep the document more focussed.

A key requirement for me was that the analysis can happen on the node-group level. This way it can be parallelized, and the same groups don't have to be analyised multipled times as would be necessary with "global" solutions. It's also easier to cache the results of the analysis.

### Extra Inputs for Determinism

To make the behavior of nodes deterministic (and therefore also the attribute lifetimes), two kinds of inputs are added to nodes. Note that these are not visible to users, they are just added to an internal graph data structure.
* For every output field socket that contains anonymous attributes created in the node, add a boolean input that controls whether the anonymous attributes referenced by the output should be created.
* For every geometry output that propagates attributes from input geometries, add an input that controls which anonymous attributes are propagated. (This is better than inserting nodes that remove anonymous attributes because sometimes the same node wants to use the attribute during field evaluation, but does not have to propagate it.)


These inputs are added to all relevant built-in nodes as well node groups.

### Static Analysis

The remaining and challenging part is to pass is to determine when these extra inputs are necessary and what to pass into them. For both we need more information about the behavior of nodes. More specifically, 4 main relations between sockets of a node are required.


* Green: Relation from input to output geometry that can propagate attributes.
* Yellow: Relation between field and geometry input that indicates that a field is evaluated on a specific geometry (and therefore that the geometry is expected to have all anonymous attributes referenced by the field).
* Blue: Relation between field and geometry output that indicates that the node created a new anonymous attribute that is referenced by the field and is available on the geometry.
* Orange: Relation between field input and field output that indicates that the output field might reference the same anonymous attributes that are referenced by the input.

Again, all of these relations have to exist for built-in nodes as well as node groups. These relations already allow a good amount of static analysis but it's important to keep in mind that they are not always perfect. If a node group uses many switch nodes, it's possible to essentially create all possible relations even though most of them are never used in practice. Either way, these relations offer a good starting point for further dynamic analysis (while the node tree is evaluated) and also allows building UI features.

We do not expect from users to setup these relations for node groups manually. Therefore, we have to inference these relations for node groups based on the node setup. Luckily, this seems to be possible in linear time (one has to iterate over all nodes more than once though).

With the added inputs and the inferenced relations, it is already possible to do not a terrible job at determining anonymous attribute lifetimes. However, there are still fairly simple scenarious where anonymous attributes are created/propagated unnecessarily. For example, consider the case below:


In this case, we'd only want to generate the normal attribute in the distribute node in case the `Use Normals` group input is true. However, that is not known statically. So somehow we want to let the distribute node know to respect the `Use Normals` input.

### Dynamic Analysis

To make the setup above work as expected, the `Generate` node group has tell its parent node group that the `Normals` input is only used when the `Use Normals` input is true. Note that the condition could also be more complex (e.g. the `Normals` input is only used when some integer input has a specific value and a specific output socket is used).

Generally, we want to know from a node group, which inputs it will use depending on other input values and which outputs are used. So it's easiest to just add some additional internal sockets to group nodes. For every original output socket, there is input that indicates whether the output is used. For every original input socket, there is an output that indicates whether the input used.


It's important to note that this can in fact generate cycles in the graph. In most cases, that's not a problem, because the it's not actually a data dependency, it just looks like a cycle because the node group is not inlined. The evaluator can evaluate that just fine. However, it's also possible that there are actual data dependencies. That happens e.g. when `Use Normals` is true if and only if the `Distribute Points on Faces` node outputs more than 10 points. In this case, the cycle has to be broken by always creating the anonymous attribute for the normals.

### Attribute Propagation

So far we only looked at determining whether an anonymous attribute should be created. Now, we just have to know at which point the lifetime ends. As mentioned before, there is not a single point where the lifetime ends. For example, in the node tree below, the lifetime of the cylinder top selection ands at two points. In the `Extrude Mesh` and in the `Subdivide Mesh` node. The `Dual Mesh` node is expected to propagate the attribute.


With some static analysis based on the relations from above, we can determine which attributes should be propagated in each node.


In many cases, a node has to propagate attributes referenced by multiple fields. In the example below, the `Subdivide Mesh` node should propagate the anonymous attributes referenced by the `Selection` and `Offset` group input. Furthermore, it should propagate the attributes that have to exist on the `Geometry` group output.