【C#】SearchValues<char> を測ったら桁違いに速かった

Youtubeの動画みたいな記事タイトル。でも実際速い。

SearchValues<T>は .NET 8 から入った効率的な検索用に最適化された型。

SearchValues.Createメソッドから生成したSearchValues<T> (.NET 8.0 現在、Tはchar/byte) を、Span<T>.IndexOfAnyメソッドなどに渡して用いる。

早速試す。
BenchmarkDotNetにて、Path.GetInvalidFileNameChars()を渡してIndexOfAny単独でベンチマークしたものを以下。

private string str = default!;
private SearchValues<char> searchValues = default!;
private char[] chars = default!;

[GlobalSetup]
public void Setup()
{
    str = "abcdefghijklmn>o";
    chars = Path.GetInvalidFileNameChars();
    searchValues = SearchValues.Create(chars);
}

[Benchmark]
public int WithSearchValues() => str.AsSpan().IndexOfAny(searchValues);

[Benchmark(Baseline = true)]
public int RegularWay() => str.IndexOfAny(chars);

 Method           | Mean      | Error     | StdDev    | Ratio | Allocated | Alloc Ratio |
----------------- |----------:|----------:|----------:|------:|----------:|------------:|
 WithSearchValues |  8.689 ns |  3.029 ns | 0.1660 ns |  0.10 |         - |          NA |
 RegularWay       | 87.153 ns | 26.049 ns | 1.4279 ns |  1.00 |         - |          NA |

ひと桁違った速さ。（記事名回収）

条件を変え、SearchValues<T>オブジェクト生成も込み、対象文字列をランダム、複数回、として確認してみる。

ベンチマークコード折りたたみ

[Params(16, 1024)]
public int N;
private string[] strs = default!;
private readonly int strLen = 16;

[GlobalSetup]
public void Setup()
{
   strs = new string[N];
   var rand = Random.Shared;
   for (int i = 0; i < strs.Length; i++)
   {
       strs[i] = string.Create(strLen, rand, static (span, rand) =>
       {
           for (int i = 0; i < span.Length; i++)
           {
               span[i] = (char)rand.Next(4096); // 4096に意図なし, 41/4096 = 1% hit
           }
       });
   }
}

[Benchmark]
public int WithSearchValues()
{
   var banned = SearchValues.Create(Path.GetInvalidFileNameChars());

   int count = 0;
   foreach (var item in strs)
   {
       if (item.AsSpan().IndexOfAny(banned) >= 0)
       {
           ++count;
       }
   }

   return count;
}

[Benchmark]
public int RegularWay()
{
   var banned = Path.GetInvalidFileNameChars();

   int count = 0;
   foreach (var item in strs)
   {
       if (item.IndexOfAny(banned) >= 0)
       {
           ++count;
       }
   }

   return count;
}

 Method           | N    | Mean         | Error        | StdDev      | Gen0   | Allocated |
----------------- |----- |-------------:|-------------:|------------:|-------:|----------:|
 WithSearchValues | 16   |     412.6 ns |      9.38 ns |     0.51 ns | 0.0610 |     192 B |
 RegularWay       | 16   |   1,461.3 ns |    249.85 ns |    13.70 ns | 0.0343 |     112 B |
 WithSearchValues | 1024 |   9,987.3 ns |  1,552.05 ns |    85.07 ns | 0.0610 |     192 B |
 RegularWay       | 1024 | 102,238.0 ns | 22,687.91 ns | 1,243.60 ns |      - |     112 B |

速い。

中身を覗く。
・Source Browser（リンク先：SearchValues.Create(ReadOnlySpan<char>)）

条件ごとに細かく異なったSearchValues<char>の具象型を返しているのが分かる。

その中で、渡したReadOnlySpan<char>がASCII文字の範囲内（でベクトル化がサポートされている環境）なら専用の型が用意されている。今回試したPath.GetInvalidFileNameChars()は範囲内。狙ったわけじゃなかったけれど最適化の恩恵が大きいケースだったよう。

また、渡すReadOnlySpanの長さが少ないような場合でも専用の型が用意されていて、劣化が起こらないよう工夫されているのが分かる。

パフォーマンスに注力している、いかにも現代C#的な型と感じた。

てくメモ

trivial な notes

【C#】SearchValues<char> を測ったら桁違いに速かった