Improve contains check done by FastRegexMatcher #14173
Merged
Conversation
This file contains 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
pracucci
force-pushed
the
fastregexmatcher-optimize-contains
branch
from
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>
pracucci
force-pushed
the
fastregexmatcher-optimize-contains
branch
from
9981034 to
d966ae6
Compare
@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. |
|
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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)