cmd/cue: unifying many values is slow

[cueckoo]

Originally opened by @rogpeppe in https://github.com/cuelang/cue/issues/572

commit 1a2105ebef3420a3d9b3e3c384c6e91c1170160c

The following code takes about a minute for me to run. It shouldn't be that slow!

import "list"
entries: [for i in list.Range(1, 6300, 1) {key: "\(i)", value: "hello\(i)"}]
unified: {
	for entry in entries {
		"\(entry.key)": entry
	}
}

[cueckoo]

Original reply by @myitcv in https://github.com/cuelang/cue/issues/572#issuecomment-831167446

As of 3ef90b326d489a6bf02c0a9527641fd44ae1c319 still takes ~5s.

[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.

[mvdan]

As of 655236e96e9f447948b8669263da98c5700c147d it seems like we're under a second with the new evaluator, so I think we can mark this as resolved:

$ time CUE_EXPERIMENT=evalv3=0 cue eval test.cue >/dev/null

real	0m1.827s
user	0m1.981s
sys	0m0.007s
$ time CUE_EXPERIMENT=evalv3=1 cue eval test.cue >/dev/null

real	0m0.445s
user	0m0.789s
sys	0m0.062s

@mpvl do you think we should add one more performance test case with the code that Roger shared above, or is that scenario already covered by our existing test suite?

[mpvl]

I'm not entirely sure what the issue was there, so adding a test seems prudent.

[mvdan]

Below is a reproducer which still shows a sigificant slow-down with a version of CUE very close to Roger's origial report, and then how the old evaluator at master is fast enough, and how the new evaluator is even faster:

# With an ancient version of CUE.
exec cue-v0.3.0-alpha5 vet -c

# With the old evaluator.
env CUE_EXPERIMENT=evalv3=0
exec cue vet -c

# With the new evaluator.
env CUE_EXPERIMENT=evalv3=1
exec cue vet -c

-- input.cue --
package p

import "list"

_entries: [for i in list.Range(1, 1500, 1) {i}]
unified: {
	for entry in _entries {
		"\(entry)": true
	}
}

# With an ancient version of CUE. (1.235s)
> exec cue-v0.3.0-alpha5 vet -c
# With the old evaluator. (0.109s)
> env CUE_EXPERIMENT=evalv3=0
> exec cue vet -c
# With the new evaluator. (0.063s)
> env CUE_EXPERIMENT=evalv3=1
> exec cue vet -c

I reduced the example a bit so that the regression test in the CUE repo is not as verbose. The original test caused the cue/testdata txtar to blow up to 113k lines, which is unnecessary; the reduced test case results in just 3k lines of txtar.