cue: (constrained) lists of values disproportionately increase evaluation time

[cueckoo]

Originally opened by @myitcv in https://github.com/cuelang/cue/issues/756

What version of CUE are you using (cue version)?

$ cue version
cue version +760aa115 linux/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

I've linked to a non-minimal repro here because otherwise the timing differences are imperceivable.

The example is based on the CUE repo's own GitHub workflow definitions.

https://gist.github.com/myitcv/b61bc5dbc67ebafd76fa6c7c93c0f229

The base timing value is a pure cue eval of the workflow declarations themselves. These correspond to the fields test, repository_dispatch, release, rebuild_tip_cuelang_org and mirror.

> exec time -p cue eval --out cue -o tmp/out
[stderr]
real 0.18

If we now add the following:

workflows: [
	{
		file:   "test.yml"
		schema: test
	},
	{
		file:   "repository_dispatch.yml"
		schema: repository_dispatch
	},
	{
		file:   "release.yml"
		schema: release
	},
	{
		file:   "rebuild_tip_cuelang_org.yml"
		schema: rebuild_tip_cuelang_org
	},
	{
		file:   "mirror.yml"
		schema: mirror
	},
]

i.e. a simple list that contains those values, execution time jumps by almost 100%!:(MISSING)

> exec time -p cue eval --out cue -o tmp/out
[stderr]
real 0.31

If we further constrain workflows as follows:

package ci

import (
	"github.com/SchemaStore/schemastore/src/schemas/json"
)

workflows: [...{file: string, schema: (json.#Workflow & {})}]

then the execution time jumps massively:

> exec time -p cue eval --out cue -o tmp/out
[stderr]
real 0.90

These three timings are given by the script in the txtar:

exec time -p cue eval --out cue -o tmp/out
cp a.cue.simple_list a.cue
exec time -p cue eval --out cue -o tmp/out
cp a.cue.constrained_list a.cue
exec time -p cue eval --out cue -o tmp/out

What did you expect to see?

Not dissimilar execution times in all three scenarios.

What did you see instead?

As above.

[mpvl]

@myitcv this should be verified against the https://review.gerrithub.io/c/cue-lang/cue/+/532656.

[myitcv]

Still appears to be an issue as of 8a7ebf930b080ab9d14d8d23755d2ec39d1194b1. However, I will note that this test is somewhat limited.

[myitcv]

Dropping the now-defunct v0.4.x milestone from this issue, but leaving the zGarden label such that we come round to considering what milestone this should sit in.