evaluator: general performance enhancements #804
Description
Originally opened by @mpvl in cuelang/cue#804
This Issue is an umbrella issue for all performance-related issues. Below is a small selection of the type of performance improvements that are being considered.
Background
Graph unification at its core approaches O(n) (in the same way a hash table lookup approaches O(1)). CUE, however, introduces a few concepts that make it more expensive: comprehensions and disjunctions. There is little one can do for comprehensions (especially list comprehensions), but at least they visually stand out and clearly signal complexity visually.
Another one is disjunctions. Naive evaluation of disjunctions can lead to exponential evaluation time. We observed, however, that for most applications, including Protobuf oneofs and disjunctions of Kubernetes types, for instance, the evaluation is still linear. We will discuss possible optimizations below.
Note that CUE also allows references, which makes it, like YAML and XML, susceptible to the “billion laughs” attack. However, although this is not implemented yet in CUE, graph unification allows for an algorithmic trick called structure sharing which would allow to evaluate such configurations in O(n) time again. The current algorithm of CUE is compatible with structure sharing and thus implementing this should not be a stretch.
Disjunctions
Disjunction performance improvements have been extracted to #2002
General evaluation
Keep sorted lists of arcs
Currently arcs are maintained as lists and matching on labels is done by looping over them. This can be slow for structs with large sets of arcs. Merging sorted lists, on the other hand, allows for O(n) operation and is clearly more scalable and necessary to approximate a O(n) time complexity (note that a merge sort on sorted input is O(n)).
Reuse of computation
Right now, updating specific values in a configuration, for instance with Fill, triggers a reevaluation of the entire tree. The plan is to make incremental updates possible. One possibility is to keep track of dependencies, mark nodes a “dirty” upon changes, and recompute the tree, while reusing the values that remained unmarked.
Research in the field of spreadsheet computation and propagator networks can be helpful in this regard.
Delayed error computation
Generating an error can be quite expensive in CUE, as it compiles a lot of information in the message. This is especially an issue in the case of disjunctions, where errors are used for detecting elimination. The v0.3 data structures allow for a different error model where an error would just consist of a few pointers to the point of origin, delaying this computation until the error is actually printed or analysed by the user.
Aside from improving performance, this delayed error computation also allows for better error reporting, as it allows for more expensive computations, such as more advanced error filtering and showing more detailed context.
Warren Abstract Machine
This is an optimization that only makes sense once the above optimizations have been addressed.
A Warren Abstract Machine is a concept originating from Prolog to make the evaluation of Prolog more efficient. In the context of CUE it could especially be useful for reducing memory allocations. Right now CUE needs considerable amounts of allocation. v0.3 already greatly reduces this by keeping reusable per-node buffers. But there is still considerable room for further reducing allocations.
Other improvements
- special-case list processing
- reduce size of
adt.Vertex - optimize boolean computation (now always creates an adt.Bool, but is often not needed)
- special-case arithmetic of small numbers
- less memory allocation