Speed up single-value SearchValues<string> candidate verification #108365

MihaZupan · 2024-09-29T07:59:33Z

This PR does 2 related changes to speed up the verification of potential matches:

Adds another specialization for values with lengths [9, 16] chars.
We already had groups [2, 3] [4, 7] [8, ∞], this PR changes that to [2, 3] [4, 8] [9, 16] [17, ∞].
We precompute more data about the value to make confirmations cheaper later, like the case conversion mask (see code comments around SingleValueState for more details).

These optimizations logically help more the more verifications we must perform.
As such it particularly helps with early matches, or where the anchor selection was poor such that we must rule out many false positives. In benchmarks like SliceSlice, it barely matters since matches are relatively rare.

It also gives us more options in the future to experiment with using fewer anchor characters (e.g. 2 instead of 3), trading higher scanning throughput for more false positive candidates, but where ruling those out is now cheaper.

public class EarlyMatches
{
    private const string Needle = "Sherlock Holmes";
    private static readonly string s_haystack = string.Concat(Enumerable.Repeat(Needle, 10_000));
    private static readonly SearchValues<string> s_values = SearchValues.Create([Needle], StringComparison.OrdinalIgnoreCase);

    [Benchmark]
    public int Count()
    {
        int count = 0;
        ReadOnlySpan<char> haystack = s_haystack;
        while (true)
        {
            int pos = haystack.IndexOfAny(s_values);
            if (pos < 0) break;
            count++;
            haystack = haystack.Slice(Needle.Length);
        }
        return count;
    }
}

Method	Toolchain	Mean	Error	Ratio
Count	main	69.63 us	1.385 us	1.00
Count	pr	27.90 us	0.320 us	0.40

public class FalsePositives
{
    private const string Needle = "Sherlock Holmes";
    private static readonly string s_haystack = string.Concat(Enumerable.Repeat("Sherlock Holme?", 10_000));
    private static readonly SearchValues<string> s_values = SearchValues.Create([Needle], StringComparison.OrdinalIgnoreCase);

    [Benchmark]
    public bool ContainsAny() => s_haystack.AsSpan().ContainsAny(s_values);
}

Method	Toolchain	Mean	Error	Ratio
ContainsAny	main	44.65 us	0.838 us	1.00
ContainsAny	pr	12.60 us	0.100 us	0.28

dotnet-policy-service · 2024-09-29T08:00:09Z

Tagging subscribers to this area: @dotnet/area-system-memory
See info in area-owners.md if you want to be subscribed.

Copilot

Copilot reviewed 5 out of 8 changed files in this pull request and generated 1 comment.

Files not reviewed (3)

src/libraries/System.Private.CoreLib/src/System/Collections/Generic/RandomizedStringEqualityComparer.cs: Evaluated as low risk
src/libraries/System.Private.CoreLib/src/System/String.cs: Evaluated as low risk
src/libraries/System.Private.CoreLib/src/System/String.Comparison.cs: Evaluated as low risk

...System.Private.CoreLib/src/System/SearchValues/Strings/SingleStringSearchValuesThreeChars.cs

...s/System.Private.CoreLib/src/System/SearchValues/Strings/Helpers/StringSearchValuesHelper.cs

src/libraries/System.Private.CoreLib/src/System/String.cs

MihaZupan · 2025-03-05T14:29:51Z

@MihuBot benchmark Sherlock https://github.com/MihaZupan/performance/tree/compiled-regex-only -medium

MihuBot · 2025-03-05T15:43:31Z

System.Text.RegularExpressions.Tests.Perf_Regex_Industry_RustLang_Sherlock

BenchmarkDotNet v0.14.1-nightly.20250107.205, Linux Ubuntu 22.04.5 LTS (Jammy Jellyfish)
AMD EPYC 9V74, 1 CPU, 8 logical and 4 physical cores
MediumRun : .NET 10.0.0 (42.42.42.42424), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI
Job=MediumRun  OutlierMode=DontRemove  IterationCount=15
LaunchCount=2  MemoryRandomization=True  WarmupCount=10

Method	Toolchain	Pattern	Mean	Error	Ratio	Allocated	Alloc Ratio
Count	Main	.*	607,043.91 ns	2,528.545 ns	1.00	2 B	1.00
Count	PR	.*	605,868.17 ns	804.840 ns	1.00	2 B	1.00

Count	Main	(?i)Holmes	50,418.33 ns	99.369 ns	1.00	-	NA
Count	PR	(?i)Holmes	50,762.42 ns	75.522 ns	1.01	2 B	NA

Count	Main	(?i)Sher[a-z]+\|Hol[a-z]+	126,128.20 ns	23,409.981 ns	1.08	1 B	1.00
Count	PR	(?i)Sher[a-z]+\|Hol[a-z]+	126,792.87 ns	24,477.738 ns	1.08	1 B	1.00

Count	Main	(?i)Sherlock	42,843.70 ns	177.218 ns	1.00	-	NA
Count	PR	(?i)Sherlock	42,916.39 ns	223.364 ns	1.00	-	NA

Count	Main	(?i)Sherlock Holmes	42,646.70 ns	175.759 ns	1.00	-	NA
Count	PR	(?i)Sherlock Holmes	43,341.47 ns	268.098 ns	1.02	-	NA

Count	Main	(?i)Sherlock\|Holmes\|Watson	142,299.50 ns	39,257.891 ns	1.16	1 B	1.00
Count	PR	(?i)Sherlock\|Holmes\|Watson	128,946.38 ns	24,882.623 ns	1.05	1 B	1.00

Count	Main	(?i)Sherlock\|(...)er\|John\|Baker [49]	210,499.64 ns	24,549.789 ns	1.03	1 B	1.00
Count	PR	(?i)Sherlock\|(...)er\|John\|Baker [49]	203,619.00 ns	22,631.926 ns	1.00	1 B	1.00

Count	Main	(?i)the	283,133.73 ns	16,165.293 ns	1.01	1 B	1.00
Count	PR	(?i)the	270,216.20 ns	15,377.694 ns	0.96	1 B	1.00

Count	Main	(?m)^Sherlock(...)rlock Holmes$ [37]	54,919.05 ns	3,152.068 ns	1.01	-	NA
Count	PR	(?m)^Sherlock(...)rlock Holmes$ [37]	38,033.88 ns	229.231 ns	0.70	-	NA

Count	Main	(?s).*	41.78 ns	0.098 ns	1.00	-	NA
Count	PR	(?s).*	43.21 ns	0.368 ns	1.03	-	NA

Count	Main	[^\\n]*	605,373.34 ns	942.699 ns	1.00	2 B	1.00
Count	PR	[^\\n]*	622,004.85 ns	12,960.891 ns	1.03	2 B	1.00

Count	Main	[a-q][^u-z]{13}x	23,499.46 ns	64.628 ns	1.00	-	NA
Count	PR	[a-q][^u-z]{13}x	23,682.32 ns	117.929 ns	1.01	-	NA

Count	Main	[a-zA-Z]+ing	3,362,728.60 ns	25,348.873 ns	1.00	11 B	1.00
Count	PR	[a-zA-Z]+ing	3,356,750.67 ns	5,979.327 ns	1.00	11 B	1.00

Count	Main	\b\w+n\b	6,584,654.94 ns	7,029.878 ns	1.00	22 B	1.00
Count	PR	\b\w+n\b	6,575,110.49 ns	14,671.487 ns	1.00	22 B	1.00

Count	Main	\p{L}	10,070,529.32 ns	18,193.877 ns	1.00	35 B	1.00
Count	PR	\p{L}	10,134,707.84 ns	101,101.197 ns	1.01	35 B	1.00

Count	Main	\p{Ll}	9,670,595.60 ns	49,248.421 ns	1.00	35 B	1.00
Count	PR	\p{Ll}	9,775,580.04 ns	35,338.008 ns	1.01	35 B	1.00

Count	Main	\p{Lu}	415,488.70 ns	7,005.910 ns	1.00	1 B	1.00
Count	PR	\p{Lu}	419,618.15 ns	6,912.662 ns	1.01	1 B	1.00

Count	Main	\s[a-zA-Z]{0,12}ing\s	3,709,192.13 ns	26,094.847 ns	1.00	12 B	1.00
Count	PR	\s[a-zA-Z]{0,12}ing\s	3,716,051.15 ns	35,857.349 ns	1.00	11 B	0.92

Count	Main	\w+	4,307,852.74 ns	54,213.684 ns	1.00	21 B	1.00
Count	PR	\w+	4,374,649.98 ns	6,985.982 ns	1.02	21 B	1.00

Count	Main	\w+\s+Holmes	2,799,253.96 ns	5,629.035 ns	1.00	11 B	1.00
Count	PR	\w+\s+Holmes	2,800,715.64 ns	5,574.806 ns	1.00	11 B	1.00

Count	Main	\w+\s+Holmes\s+\w+	3,214,394.68 ns	115,157.429 ns	1.00	9 B	1.00
Count	PR	\w+\s+Holmes\s+\w+	3,124,039.86 ns	9,667.667 ns	0.97	12 B	1.33

Count	Main	aei	35,118.46 ns	280.475 ns	1.00	-	NA
Count	PR	aei	35,121.85 ns	290.377 ns	1.00	-	NA

Count	Main	aqj	35,114.56 ns	274.064 ns	1.00	-	NA
Count	PR	aqj	35,182.59 ns	392.336 ns	1.00	-	NA

Count	Main	Holmes	46,110.76 ns	204.000 ns	1.00	-	NA
Count	PR	Holmes	45,720.00 ns	81.047 ns	0.99	-	NA

Count	Main	Holmes.{0,25}(...).{0,25}Holmes [39]	47,660.99 ns	110.612 ns	1.00	-	NA
Count	PR	Holmes.{0,25}(...).{0,25}Holmes [39]	47,779.35 ns	146.024 ns	1.00	-	NA

Count	Main	Sher[a-z]+\|Hol[a-z]+	50,658.76 ns	171.144 ns	1.00	-	NA
Count	PR	Sher[a-z]+\|Hol[a-z]+	50,547.85 ns	98.522 ns	1.00	-	NA

Count	Main	Sherlock	55,262.81 ns	3,050.087 ns	1.01	-	NA
Count	PR	Sherlock	38,515.85 ns	348.779 ns	0.70	-	NA

Count	Main	Sherlock Holmes	54,743.41 ns	3,087.602 ns	1.01	-	NA
Count	PR	Sherlock Holmes	38,703.22 ns	80.738 ns	0.71	-	NA

Count	Main	Sherlock\s+Holmes	55,570.24 ns	3,052.855 ns	1.01	-	NA
Count	PR	Sherlock\s+Holmes	38,972.12 ns	373.865 ns	0.71	-	NA

Count	Main	Sherlock\|Holmes	47,453.87 ns	1,167.125 ns	1.00	-	NA
Count	PR	Sherlock\|Holmes	46,812.22 ns	80.294 ns	0.99	-	NA

Count	Main	Sherlock\|Holmes\|Watson	60,983.45 ns	326.388 ns	1.00	-	NA
Count	PR	Sherlock\|Holmes\|Watson	60,983.65 ns	154.453 ns	1.00	-	NA

Count	Main	Sherlock\|Holm(...)er\|John\|Baker [45]	90,124.31 ns	178.497 ns	1.00	-	NA
Count	PR	Sherlock\|Holm(...)er\|John\|Baker [45]	90,274.97 ns	213.911 ns	1.00	-	NA

Count	Main	Sherlock\|Street	25,487.76 ns	80.145 ns	1.00	-	NA
Count	PR	Sherlock\|Street	25,419.56 ns	98.407 ns	1.00	-	NA

Count	Main	the	188,234.22 ns	6,664.494 ns	1.00	1 B	1.00
Count	PR	the	199,707.64 ns	12,390.410 ns	1.06	1 B	1.00

Count	Main	The	50,928.50 ns	140.459 ns	1.00	-	NA
Count	PR	The	50,972.93 ns	85.929 ns	1.00	-	NA

Count	Main	the\s+\w+	316,249.04 ns	11,793.536 ns	1.00	1 B	1.00
Count	PR	the\s+\w+	318,567.78 ns	10,440.506 ns	1.01	1 B	1.00

Count	Main	zqj	35,160.43 ns	274.050 ns	1.00	-	NA
Count	PR	zqj	35,095.12 ns	290.522 ns	1.00	-	NA

MihaZupan added the area-System.Memory label Sep 29, 2024

MihaZupan added this to the 10.0.0 milestone Sep 29, 2024

MihaZupan requested a review from stephentoub September 29, 2024 07:59

MihaZupan self-assigned this Sep 29, 2024

MihaZupan force-pushed the searchvalues-singleStringLengths4 branch 2 times, most recently from 7051ac1 to bc01b11 Compare November 12, 2024 21:23

MihaZupan requested a review from Copilot December 17, 2024 16:26

Copilot AI reviewed Dec 17, 2024

View reviewed changes

...System.Private.CoreLib/src/System/SearchValues/Strings/SingleStringSearchValuesThreeChars.cs Show resolved Hide resolved