internal/core/adt: improve performance for repeated calls to Unify/Fill
This is done by skipping SpawnRef for computed vertices.
Repeatedly applying unification caused a new closedInfo to
be inserted at the node's position, resulting in a growing
list to process when calling Accept (called by Unify, which
is called by Fill). This caused processing time to become
quadratic for that node.
There are more gains to be made, but this should be a big
help already.
Issue #899
Change-Id: I96ec77bb4bd09b69b9da023e0fb2b8ed5c297080
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/9462
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cmd/cue/cmd/testdata/script/vet_embed.txt b/cmd/cue/cmd/testdata/script/vet_embed.txt
index f8c0995..9b4a60a 100644
--- a/cmd/cue/cmd/testdata/script/vet_embed.txt
+++ b/cmd/cue/cmd/testdata/script/vet_embed.txt
@@ -32,7 +32,6 @@
-- expect-foo --
field c not allowed:
- ./foo.yaml:1:2
./foo.yaml:2:2
./schema.cue:1:1
./schema.cue:3:7
@@ -42,12 +41,10 @@
./schema.cue:1:1
./schema.cue:3:7
./schema.cue:7:1
- ./stream.yaml:1:2
./stream.yaml:2:2
-- expect-stream --
field d not allowed:
./schema.cue:1:1
./schema.cue:3:7
./schema.cue:7:1
- ./stream.yaml:1:2
./stream.yaml:2:2
diff --git a/cmd/cue/cmd/testdata/script/vet_expr.txt b/cmd/cue/cmd/testdata/script/vet_expr.txt
index 0d3cbdf..9ce3349 100644
--- a/cmd/cue/cmd/testdata/script/vet_expr.txt
+++ b/cmd/cue/cmd/testdata/script/vet_expr.txt
@@ -4,7 +4,6 @@
-- expect-stderr --
translations.hello.lang: incomplete value string
field skip not allowed:
- ./data.yaml:16:1
./data.yaml:20:1
./vet.cue:1:1
./vet.cue:1:8
diff --git a/internal/core/adt/eval.go b/internal/core/adt/eval.go
index fa00b20..416d515 100644
--- a/internal/core/adt/eval.go
+++ b/internal/core/adt/eval.go
@@ -1359,7 +1359,15 @@
defer func() { arc.SelfCount-- }()
}
- closeInfo = closeInfo.SpawnRef(arc, IsDef(x), x)
+ // Performance: the following if check filters cases that are not strictly
+ // necessary for correct functioning. Not updating the closeInfo may cause
+ // some position information to be lost for top-level positions of merges
+ // resulting form APIs. These tend to be fairly uninteresting.
+ // At the same time, this optimization may prevent considerable slowdown
+ // in case an API does many calls to Unify.
+ if !inline || arc.IsClosedStruct() || arc.IsClosedList() {
+ closeInfo = closeInfo.SpawnRef(arc, IsDef(x), x)
+ }
if arc.status == 0 && !inline {
// This is a rare condition, but can happen in certain
diff --git a/internal/core/adt/eval_test.go b/internal/core/adt/eval_test.go
index f095be1..0356e33 100644
--- a/internal/core/adt/eval_test.go
+++ b/internal/core/adt/eval_test.go
@@ -22,6 +22,8 @@
"github.com/rogpeppe/go-internal/txtar"
+ "cuelang.org/go/cue"
+ "cuelang.org/go/cue/cuecontext"
"cuelang.org/go/internal/core/adt"
"cuelang.org/go/internal/core/debug"
"cuelang.org/go/internal/core/eval"
@@ -135,3 +137,17 @@
t.Log(ctx.Stats())
}
+
+func BenchmarkUnifyAPI(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ b.StopTimer()
+ ctx := cuecontext.New()
+ v := ctx.CompileString("")
+ for j := 0; j < 500; j++ {
+ if j == 400 {
+ b.StartTimer()
+ }
+ v = v.FillPath(cue.ParsePath(fmt.Sprintf("i_%d", i)), i)
+ }
+ }
+}
