Description
Problem
The new SearchValues<string> has incredible strategies to find candidates where it suspects there might be a match but once it finds a match, uses a simple loop to confirm. Specifically implementations of StringSearchValuesHelper.ICaseSensitivity use ScalarEquals which is a for loop comparing chars.
This is a missed opportunity as Vectorized equality would be perfect here, especially considering the implementations of ICaseSensitivity already are able to transform vectors with some clever optimizations of their own.
It would be unfortunate if basic uses of this API are actually slower compared to string.IndexOf(string) in certain cases.
Benchmark Code
Consider the following benchmark code run in my local copy of dotnet/performance. It's an extreme example designed to prove the point - discussion later.
[BenchmarkCategory(Categories.Libraries)]
public class SearchValuesStringBenchmarks
{
private SearchValues<string> _searchValuesCaseInsensitive;
private SearchValues<string> _searchValuesCaseSensitive;
private string _text = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
private string _queryUpper = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
private string _queryLower;
[GlobalSetup]
public void Setup()
{
_queryUpper = _text.ToUpperInvariant();
_queryLower = _queryUpper.ToLowerInvariant(); // Force a new string to be created
_searchValuesCaseSensitive = SearchValues.Create([_queryLower], StringComparison.Ordinal);
_searchValuesCaseInsensitive = SearchValues.Create([_queryUpper], StringComparison.OrdinalIgnoreCase);
}
[Benchmark]
public int RegularCaseInsensitive() => _text.IndexOf(_queryUpper, StringComparison.OrdinalIgnoreCase);
[Benchmark]
public int OptimizedCaseInsensitive() => _text.AsSpan().IndexOfAny(_searchValuesCaseInsensitive);
[Benchmark]
public bool EqualsCaseInsensitive() => _text.Equals(_queryUpper, StringComparison.OrdinalIgnoreCase);
[Benchmark]
public int RegularCaseSensitive() => _text.IndexOf(_queryLower, StringComparison.Ordinal);
[Benchmark]
public int OptimizedCaseSensitive() => _text.AsSpan().IndexOfAny(_searchValuesCaseSensitive);
[Benchmark]
public bool EqualsCaseSensitive() => _text.Equals(_queryLower, StringComparison.Ordinal);
}
Benchmark Results
// * Summary *
BenchmarkDotNet v0.13.11-nightly.20231126.107, Windows 11 (10.0.22621.2861/22H2/2022Update/SunValley2)
AMD Ryzen 9 5950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK 9.0.100-alpha.1.23608.3
[Host] : .NET 9.0.0 (9.0.23.57707), X64 RyuJIT AVX2
Job-ULGCAN : .NET 9.0.0 (42.42.42.42424), X64 RyuJIT AVX2
PowerPlanMode=00000000-0000-0000-0000-000000000000 Toolchain=CoreRun IterationTime=250.0000 ms
MaxIterationCount=20 MinIterationCount=15 WarmupCount=1
| Method | Mean | Error | StdDev | Median | Min | Max | Allocated |
|------------------------- |----------:|----------:|----------:|----------:|----------:|----------:|----------:|
| RegularCaseInsensitive | 15.893 ns | 0.1417 ns | 0.1184 ns | 15.849 ns | 15.815 ns | 16.195 ns | - |
| OptimizedCaseInsensitive | 46.448 ns | 0.2249 ns | 0.2104 ns | 46.425 ns | 46.060 ns | 46.764 ns | - |
| EqualsCaseInsensitive | 9.194 ns | 0.1949 ns | 0.1823 ns | 9.149 ns | 8.813 ns | 9.432 ns | - |
| RegularCaseSensitive | 9.122 ns | 0.1665 ns | 0.1558 ns | 9.166 ns | 8.922 ns | 9.363 ns | - |
| OptimizedCaseSensitive | 46.394 ns | 0.4518 ns | 0.4226 ns | 46.197 ns | 45.825 ns | 47.110 ns | - |
| EqualsCaseSensitive | 4.295 ns | 0.0433 ns | 0.0405 ns | 4.279 ns | 4.242 ns | 4.366 ns | - |
Analysis
It's clear that the new SearchValues API is slower than we would like in the above cases. This is because it's optimized to find the first candidate character position which in the benchmark is index 0 which negates the benefit. Thus the remainder of the work is verifying the candidate at the position, which I would guess is vectorized in the string.IndexOf/string.Equal approaches.
I also couldn't find any benchmarks of this API in dotnet/performance, so maybe I've done something wrong.
Please note I'm not trying to bash this amazing API, just to point out where I saw a possible improvement. The strategy selection and reading about Teddy was truly inspiring.
