Improve contains check done by FastRegexMatcher#14173
Merged
bboreham merged 3 commits intoprometheus:mainfrom Jun 6, 2024
Merged
Improve contains check done by FastRegexMatcher#14173bboreham merged 3 commits intoprometheus:mainfrom
bboreham merged 3 commits intoprometheus:mainfrom
Conversation
1f8a9b0 to
8846088
Compare
Signed-off-by: Marco Pracucci <marco@pracucci.com>
Signed-off-by: Marco Pracucci <marco@pracucci.com>
Signed-off-by: Marco Pracucci <marco@pracucci.com>
9981034 to
d966ae6
Compare
Contributor
Author
@bboreham suggested me to try to run the benchmark with an higher number of strings, so I've done the following change: @@ -1101,9 +1106,9 @@ func generateRandomValues() []string {
randGenerator := rand.New(rand.NewSource(1))
// Generate variable lengths random texts to match against.
- texts := append([]string{}, randStrings(randGenerator, 10, 10)...)
- texts = append(texts, randStrings(randGenerator, 5, 30)...)
- texts = append(texts, randStrings(randGenerator, 1, 100)...)
+ texts := append([]string{}, randStrings(randGenerator, 25000, 10)...)
+ texts = append(texts, randStrings(randGenerator, 25000, 30)...)
+ texts = append(texts, randStrings(randGenerator, 25000, 100)...)
texts = append(texts, "foo"+randString(randGenerator, 50))
texts = append(texts, randString(randGenerator, 50)+"foo")The resulting benchmark is: We still have some variance, for different cases now. The variance is smaller than previous benchmark run tho. |
Member
|
To explain my thinking: previously the test used 18 strings, total about 456 bytes. This is small enough that most branches could fit in the prediction cache of the cpu, and adding one more branch could tip that change. It's unrealistically small compared to any real-world Prometheus. Increasing to 75,000 strings and 3.5MB makes it unlikely the CPU can predict every branch, and pushes out from L1 to L2/L3 cache. |
bboreham
approved these changes
Jun 5, 2024
Member
bboreham
left a comment
There was a problem hiding this comment.
Code changes seem straightforward enough. Thanks!
bboreham
pushed a commit
that referenced
this pull request
Jan 8, 2026
…17707) #14173 introduced an optimisation to better handle regex patterns like .*-.*-.*. It identifies strings the pattern cannot possibly match (because they do not contain all of the literal values) and returns false from MatchString early. However, if the string does contain all literal values, then the Go regex engine is used to confirm that the string does match the pattern. But this is not necessary in the case where the start and end of the pattern is .* and everything in between is either a literal or .*: if the string contains all of the literals in order, then it matches the pattern, and invoking Go's regex engine to confirm this is unnecessary and quite slow. * Add some more test cases * Add benchmark, since existing benchmark doesn't show much impact given most of the random test strings will not match the patterns. Signed-off-by: Charles Korn <charles.korn@grafana.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
I recently saw a production regexp pattern like
(.+)-(.+)-(.+)-(.+)-(.+). Currently, this pattern is loosely optimised in theFastRegexMatcher: we only check if the input string contains 1 occurence of-(in any position) and, if yes, we run the full regexp engine, while if it doesn't we skip the regexp engine.A simple way to further optimise it is to check for all literals in the pattern instead of just the first one, which is what I'm proposing in this PR.
Benchmark
The benchmark shows some performance change to few patterns that are not expected to change. I've re-run the benchmarks multiple times and they're consistent, which I don't fully understand. I thought it was the change to
compileMatchStringFunction()so I've commented the change there (essentially skipping the "contains" check), but I still get such difference withmain.(I omitted memory benchmark results because there's no diff)