evalv3 performance regression which disappears with CUE_DEBUG=opendef

[mvdan]

# evalv2
env CUE_EXPERIMENT=evalv3=0
exec cue vet -c

# evalv3
env CUE_EXPERIMENT=evalv3=1
exec cue vet -c

# evalv3 with opendef
env CUE_EXPERIMENT=evalv3=1
env CUE_DEBUG=opendef=1
exec cue vet -c

-- input.cue --
package p

import "list"

out: #Output & {#input: _input}

_input: {
	for n in list.Range(1, 300, 1) {
		"A\(n)": "B\(n)": name: "name\(n)"
	}
}
#Embed: [string]: string
#Output: {
	#Embed
	#input: _

	for _, lvlA in #input {
		for nameB, lvlB in lvlA {
			(nameB): lvlB.name
		}
	}
}

As of e058014:

# evalv2 (0.037s)
> env CUE_EXPERIMENT=evalv3=0
> exec cue vet -c
# evalv3 (0.644s)
> env CUE_EXPERIMENT=evalv3=1
> exec cue vet -c
# evalv3 with opendef (0.036s)
> env CUE_EXPERIMENT=evalv3=1
> env CUE_DEBUG=opendef=1
> exec cue vet -c

You can see that evalv2 runs in about 40ms, evalv3 runs in 650ms (more than a 10x slow-down), but evalv3 with opendef runs in 40ms once again.

Distilled from #3879.

[mvdan]

Increasing the list.Range above to 500 to get a bigger CPU profile, I see the following culprit:

(pprof) top
Showing nodes accounting for 2.18s, 96.89% of 2.25s total
Dropped 18 nodes (cum <= 0.01s)
Showing top 10 nodes out of 47
      flat  flat%   sum%        cum   cum%
     1.23s 54.67% 54.67%      1.25s 55.56%  cuelang.org/go/internal/core/adt.transitiveMapping
     0.56s 24.89% 79.56%      0.56s 24.89%  cuelang.org/go/internal/core/adt.(*reqSets).filterTop.func1 (inline)
     0.21s  9.33% 88.89%      0.77s 34.22%  cuelang.org/go/internal/core/adt.(*reqSets).filterSets (inline)

So I believe this TODO is to blame:

// TODO: this is a polynomial algorithm. At some point, if this turns out to be
// a bottleneck, we should consider filtering unnecessary entries and/or using a
// more efficient algorithm.
func transitiveMapping(buf reqSets, x reqSet, b []replaceID) reqSets {

[mvdan]

Below are the perf numbers from #3879 (cue export in https://github.com/joelMuehlena/cue-netbox-example), from which I reduced this issue above. All wall times on my Linux laptop running on battery.

• evalv2: 15s
• evalv3 before https://review.gerrithub.io/c/cue-lang/cue/+/1213607: 47s
• evalv3 after https://review.gerrithub.io/c/cue-lang/cue/+/1213607: 34s (so a ~28% improvement)
• evalv3 with CUE_DEBUG=opendef, i.e. if closedness was infinitely efficient: 3s

FYI @joelMuehlena we made some progress here, but more is clearly needed, so we're leaving this issue open for now.