Performance: Repeated evaluation of incomplete expressions

[myitcv]

Field evaluations may depend on full evaluation of other fields. This means that, ideally, they need to be evaluated in a certain order. The current evaluator requeues an expression for evaluation if a dependency cannot immediately be evaluated. It then keeps reevaluating until a fixed point is reached.

The way CUE has evolved, this now means that an expression may sometimes be evaluated several times. This is especially bad when these expressions are expensive, such as large comprehensions.

The new evaluator, instead of simply requeuing, builds a dependency graph that ensures that a blocked expression will only be restarted if a dependency is resolved. This reduces the time complexity for processing a list of expressions for a node from $O(n^2)$ to $O(n)$.

This performance sub-issue captures details and narrative specific to performance issues related to unnecessary reevaluation of dependencies. We will post updates and commentary related to this topic below.

The umbrella performance issue captures higher-level performance updates.

Existing comprehension-related bug reports/issues

• Performance: Repeated evaluation of incomplete expressions #2852