performance regression in v0.30.0

[miparnisari]

Describe the bug

interpreter.MatchesRegexOptimization compiles a matches() pattern once, at plan time. As of cel-go v0.30.0 that stops happening for programs built by protovalidate: the generic stdlib matches overload runs instead, so every evaluation recompiles the pattern.

To Reproduce

Check which components this affects:

• parser
• checker
• interpreter

Sample expression and input that reproduces the issue:

^[a-z][a-z0-9_]{1,62}[a-z0-9]$

Test setup here https://github.com/miparnisari/celgo-repro:

go test ./...     # passes on v0.29.2, fails on v0.30.0

and

$ sh run.sh
=== cel-go v0.29.2 ===
  OneRule               406.1 ns/op          96 B/op       5 allocs/op
  ThreeRules             1213 ns/op         289 B/op      15 allocs/op
  Nested                 2579 ns/op         592 B/op      30 allocs/op
  regexp.compile:  515kB (4.56% of allocated bytes)
  callers of String.Match / MatchString:
                                                 515kB   100% |   github.com/google/cel-go/interpreter.init.func4 (inline)
             0     0%     0%      515kB  4.56%                | regexp.Compile
                                                 515kB   100% |   regexp.compile

=== cel-go v0.30.0 ===
  OneRule               23113 ns/op       45251 B/op     241 allocs/op
  ThreeRules            81346 ns/op      132748 B/op    1449 allocs/op
  Nested               155523 ns/op      266863 B/op    2899 allocs/op
  regexp.compile:  1985.39MB (95.34% of allocated bytes)
  callers of String.Match / MatchString:
                                             1984.89MB   100% |   regexp.MatchString (inline)
                                                0.50MB 0.025% |   regexp.MustCompile (inline)
             0     0%     0%  1985.39MB 95.34%                | regexp.Compile
                                             1985.39MB   100% |   regexp.compile
                                             2062.47MB   100% |   github.com/google/cel-go/common/types.String.Match
             0     0%     0%  2062.47MB 99.04%                | regexp.MatchString
                                             1984.89MB 96.24% |   regexp.Compile (inline)
                                               77.58MB  3.76% |   regexp.(*Regexp).MatchString (inline)

Expected behavior

No regression in performance in v0.30.0

Additional context

N/A

[TristonianJones]

Hi @miparnisari, I've run the following benchmark against HEAD, v0.30.0, and v0.29.2. I'm not seeing an issue:

func BenchmarkRegexProgramOptimization(b *testing.B) {
	env, err := NewEnv(
		Variable("input", StringType),
	)
	if err != nil {
		b.Fatalf("NewEnv() failed: %v", err)
	}

	expr := `input.matches('^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}$')`
	ast, iss := env.Compile(expr)
	if iss.Err() != nil {
		b.Fatalf("env.Compile() failed: %v", iss.Err())
	}

	vars := map[string]any{"input": "test.user@example.com"}

	prgOpt, err := env.Program(ast, EvalOptions(OptOptimize))
	if err != nil {
		b.Fatalf("env.Program(OptOptimize) failed: %v", err)
	}

	prgUnopt, err := env.Program(ast)
	if err != nil {
		b.Fatalf("env.Program() failed: %v", err)
	}

	b.Run("Optimized", func(b *testing.B) {
		b.ReportAllocs()
		b.ResetTimer()
		for i := 0; i < b.N; i++ {
			prgOpt.Eval(vars)
		}
	})

	b.Run("Unoptimized", func(b *testing.B) {
		b.ReportAllocs()
		b.ResetTimer()
		for i := 0; i < b.N; i++ {
			prgUnopt.Eval(vars)
		}
	})
}

Tag / Revision	Mode	Time (ns/op)	Bytes (B/op)	Allocs (allocs/op)
v0.29.2	Optimized (cel.OptOptimize)	473.4 ns/op	64 B/op	3 allocs/op
	Unoptimized (default)	4,723.0 ns/op	5,945 B/op	67 allocs/op
v0.30.0	Optimized (cel.OptOptimize)	150.3 ns/op	0 B/op	0 allocs/op
	Unoptimized (default)	8,812.0 ns/op	45,025 B/op	241 allocs/op
HEAD	Optimized (cel.OptOptimize)	150.1 ns/op	0 B/op	0 allocs/op
	Unoptimized (default)	8,812.0 ns/op	45,025 B/op	241 allocs/op

For security reasons, I'm reluctant to open a .zip file. It looks like maybe the OptOptimize flag is off? Could you share a snippet of source in reply instead of a .zip file?

[miparnisari]

Could you share a snippet of source in reply instead of a .zip file?

I put it here: https://github.com/miparnisari/celgo-repro

[miparnisari]

I'm actually not sure if this is something that broke in cel-go or in protovalidate 😬 it could also be that something that protovalidate depended on behavior that changed in 0.30.0

[TristonianJones]

Thank you, I figured out the cause, and it's actually related to how protovalidate-go does expression-pruning. It's fixable, but let me explain what's happening.

There was a bug in CEL which would eagerly evaluate arguments even if it knew when it knew the error argument would make the function uncallable. This was fixed to ensure that upcoming async extensions like #1402 wouldn't unnecessarily execute in unrecoverable error paths.

Where this surfaces as a problem is that some libraries were depending on this bug during expression pruning, including protovalidate-go, where instead of doing a partial evaluation using CEL's built-in PartialEval and using an expression that marks this as unknown, a standard evaluation is being performed and this is not supplied, resulting in this becoming an error and halting the evaluation, thus resulting in fewer expressions pruned

Here's the fix:

// buf.build/go/protovalidate / ast.go
func (set astSet) ReduceResiduals(rules protoreflect.Message, opts ...cel.ProgramOption) (programSet, error) {
	residuals := make(astSet, 0, len(set))
	options := append([]cel.ProgramOption{
		cel.EvalOptions(
			cel.OptTrackState,
			cel.OptExhaustiveEval,
			cel.OptOptimize,
			cel.OptPartialEval,
		),
	}, opts...)
	activation := getBindings()
	defer putBindings(activation)
	activation.Rules = rules.Interface()
	for _, ast := range set {
		activation.Rule = ast.Value.Interface()
		program, err := ast.toProgram(ast.Env, options...)
		if err != nil {
			residuals = append(residuals, ast)
			continue
		}
-		val, details, _ := program.Program.Eval(activation)
+		partialAct, err := cel.PartialVars(activation, cel.AttributePattern("this"))
+		if err != nil {
+			residuals = append(residuals, ast)
+			continue
+		}
+		val, details, _ := program.Program.Eval(partialAct)

I'm working on a PR for buf.build to make sure the library calls CEL in a way where CEL clearly understands the intent is partial eval. It happened to work before by accident rather than intention.