nyarly
commented
3 years ago I'm really concerned by "There is little one can do for comprehensions (especially list comprehensions), but at least they visually stand out and clearly signal complexity visually."
Our use case for CUE is to simplify and abstract a "large" Kubernetes configuration. (Large here means ~100kloc).
We're using Kustomize as an intermediary, and building out CUE defs that we can unify in order to select features for different clusters. One of the abstraction targets has been to automate away the coupling of file names as written to disk and as referenced in kustomize.yaml files. Consequently, the contents of our kustomize.yaml is build up out of list comprehensions.
Performance has been an ongoing challenge for us, with builds in the 5-15 minute range. If they get much higher than 15 minutes, they quickly spiral into "build for an hour before the OOMKiller notices." Each release of CUE has been a significant improvement for us, but list comprehensions being a permanent limiting factor definitely gives me pause.
mpvl
mvdan
Originally opened by @mpvl in https://github.com/cuelang/cue/issues/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 https://github.com/cue-lang/cue/issues/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
adt.Vertex