FillPath Performance Declines Linearly

[cueckoo]

Originally opened by @rawkode in cuelang/cue#899

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

0.3.2

Problem

FillPath performance starts really strong, at 27µs. However, as the number of increases, FillPath takes around 500ms at 1k entries. Sporadically throughout there are 1-2s FillPath calls also.

Video

https://i.rawko.de/jkuLe9l9

Reproduction

package main

import (
	"fmt"
	"os"
	"os/signal"
	"time"

	"cuelang.org/go/cue"
)

func main() {
	var cueRuntime cue.Runtime
	cueInstance, err := cueRuntime.Compile("", "")
	if err != nil {
		panic("No Cue Runtime")
	}
	cueValue := cueInstance.Value()

	c := make(chan os.Signal, 1)
	signal.Notify(c, os.Interrupt)

	go func() {
		for _ = range c {
			fmt.Println(cueValue)
			panic("Done")
		}
	}()

	i := 0
	for {
		start := time.Now()
		cueValue = cueValue.FillPath(cue.ParsePath(fmt.Sprintf("i_%!d(MISSING)", i)), i)
		now := time.Now()
		elapsed := now.Sub(start)
		fmt.Printf("FillPath %!d(MISSING) took %!v(MISSING)\n", i, elapsed)
		i++
	}
}

[cueckoo]

Original reply by @rawkode in cuelang/cue#899 (comment)

Relevant #804 ?

[cueckoo]

Original reply by @mpvl in cuelang/cue#899 (comment)

FTR: this comment already exists in internal/core/adt/closed.go and is related to exactly this issue:

	// TODO(perf): more aggressively determine whether a struct is open or
	// closed: open structs do not have to be checked, yet they can particularly
	// be the ones with performance issues, for instanced as a result of
	// embedded for comprehensions.

It basically is quadratic slowdown, thought the constant is higher than I expected.