[v10.0.x] Alerting: Improve performance of matching captures

[grafana-delivery-bot]

Backport 8dd3eb8 from #71828

---

What is this feature?

This commit updates eval.go to improve the performance of matching captures in the general case. In some cases we have reduced the runtime of the function from 10s of minutes to a couple 100ms. In the case where no capture matches the exact labels, we revert to the current subset/superset match, but with a reduced search space due to grouping captures.

Benchmarks

All benchmarks are show as before and after benchmarks.

100 alerts

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	   35728	    997875 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	46.346s

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	  199930	    180568 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	38.337s

500 alerts

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	    1627	  22169211 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	38.737s

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	   40276	    911248 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	46.170s

5000 alerts

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	      16	2133231219 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	36.677s

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	    3922	   9225236 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	37.556s

10,000 alerts

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	       4	8555365688 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	68.640s

go test -bench=. -benchtime=30s
goos: darwin
goarch: arm64
pkg: github.com/grafana/grafana/pkg/services/ngalert/eval
BenchmarkEvaluate-8   	    1882	  18879993 ns/op
PASS
ok  	github.com/grafana/grafana/pkg/services/ngalert/eval	37.919s

Why do we need this feature?

[Add a description of the problem the feature is trying to solve.]

Who is this feature for?

[Add information on what kind of user the feature is for.]

Which issue(s) does this PR fix?:

Fixes #

Special notes for your reviewer:

Please check that:

• It works as expected from a user's perspective.
• If this is a pre-GA feature, it is behind a feature toggle.
• The docs are updated, and if this is a notable improvement, it's added to our What's New doc.