evaluator: general performance enhancements

[cueckoo]

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

[nyarly]

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]

@nyarly:

"There is little one can do for comprehensions (especially list comprehensions), but at least they visually stand out and clearly signal complexity visually."

Mind you, this is not specific to CUE, but for any language that has comprehensions: it is easy to get into trouble: take a smallish list (say a 1000 elements) and then iterate over it in 5 nested for loops and you'll be hard-pressed to find a language where this will be spiffy.

There are some known performance issues that make the big-O performance considerably larger than it needs to be. Fixes for these are in the works. It will take some time, still, but they are high on the priority list.

[nyarly]

Okay - nesting 1000 element loops 5 deep is an unsurprising complexity factor.

What I'm seeing is that ~10 unified defs with something like output: { one: [ for k,v in input { ... }], two: [ for k,v in input { ... } } unified explodes with the number of defs involved.

Notionally, it seems like that should be hundreds of elements in 5 sequential loops should still be in the O(n) range, and it sounds like you're implying that's a reasonable expectation.

[mpvl]

@nyarly If you have a drilled down reproduces with such unexpected behavior, I would love to have it.

Coincidentally, I'm working on redoing some of the comprehension code that simplifies the code significantly and will allow for more improvements down the line.

[nyarly]

I haven't been able to produce a reduced case for this issue in particular. I might take another stab at something with the idea that it was unification and comprehension to trigger the issue.

I've been talking with @myitcv for a little while about hooking up with Unity, and be thrilled when I can show you what we've been doing with CUE so far.

[mvdan]

Since February 2024, we have started tracking performance issues and improvements in a more structured and hopefully useful way; we have a new top-level tracking issue at #2850, and a number of sub-issues such as #2854 to replace the "Reuse of computation" section above.

Given that we are actively updating issue 2850 with regular updates, and that the work outlined in that issue and its sub-issues reflect the current performance challenges of the evaluator, I am going to close this issue in favor of those for the sake of clarity. We hadn't used nor updated this issue in nearly three years, and all relevant issues and planned work should already be reflected in the new issues.

Please let me know if I missed anything :)