Improve performance of #Lineage and BindLineage

[sdboyer]

Performance of lineage loading and binding declined significantly with lineage flattening (#82). Preliminary profiling (I've attached a - lol - screenshot) indicates that most of the problem occurs during calls to cue.Context.BuildInstance(), which indicates that it's the CUE evaluator struggling with working out all the new internal structures within the native CUE definition of #Lineage.

(Note that the profiler has erroneously put cue.Value.Unify under load.Instances - the main cost there is incurred during the BuildInstance() call).)

My guess is that we have some low-hanging fruit here related to some of the new disjunctions introduced. I suspect we can express the same constraints in a different way and improve performance here ocnsiderably.

[sdboyer]

We'll definitely want to add some benchmark tests as part of this. And i see that https://pkg.go.dev/golang.org/x/perf/cmd/benchstat exists, which could be useful in helping us track progress against this over time.

[joanlopez]

We'll definitely want to add some benchmark tests as part of this. And i see that https://pkg.go.dev/golang.org/x/perf/cmd/benchstat exists, which could be useful in helping us track progress against this over time.

Related with that, I've just discovered gobenchdata, and it looks really nice!

Example demo: https://gobenchdata.bobheadxi.dev/

[sdboyer]

oh amazing, that looks like the path of least resistance

[joanlopez]

Some initial insights from BindLineage: looks like most of the time is spent on this line.

[sdboyer]

My guess is that AppendSplit is still just a symptom of an underlying structure that the evaluator is tripping over - it's the call to cue.Value.Expr() that's expensive, as this bit of the profile shows:

So it's still looking like something in the pure CUE definitions that's causing the basic churn. But having the different benchmark cases does also help us differentiate a bit...lots of good info to go through.