【C#,検証】高速な回文判定処理を求めて。

# はじめに
今回はタイトルの通り、C#における回文判定の手法で最も高速な処理は何かを検証します。
動機はコーディング問題で回文の設問を解いていて、回文判定は色々あるけどどれが一番早いのだろう……ともやもやしたことです。
さくっと検証します。

# テスト環境
- **C#(.NET 8.0.14 )**
- **BenchmarkDotNet**

# 検証内容
今回は七つの方法を比較します。
検証の前に軽く紹介をさせてください。
小見出しの名前は対応するテストメソッドの名前です。

### Method1_SpanReverse

まずはSpanのReverse()とSequenceEqual()を利用した判定です。
一応いつも使っている方法です。
これが一番早い、と思っていましたが根拠は特にないんですねこれが。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static bool IsPalindromeUsingSpan(string input)
        {

            ReadOnlySpan<char> original = input.AsSpan();
            Span<char> reversed = stackalloc char[original.Length];
            original.CopyTo(reversed);
            reversed.Reverse();

            return original.SequenceEqual(reversed);
        }

```
</details>

### Method2_ArrayReverse

次は最初の手法を配列で再現したものになります。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static bool IsPalindromeUsingArray(string input)
        {

            char[] charArray = input.ToCharArray();
            Array.Reverse(charArray);
            string reversed = new string(charArray);

            return input.Equals(reversed, StringComparison.Ordinal);
        }

```
</details>

### Method3_DirectComparison

続いて最後尾と先頭から対応するインデックスの文字を比較していく処理になります。
地味に計算量O(N/2)ですから隠れた強豪ではないかと目しております。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static bool IsPalindromeUsingDirectComparison(string input)
        {

            int left = 0;
            int right = input.Length - 1;

            while ( left < right )
            {
                if ( input[left] != input[right] )
                    return false;

                left++;
                right--;
            }

            return true;
        }

```
</details>

### Method4_Linq

個人的には遅いと予想しますが、念のためLINQも入れました。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static bool IsPalindromeUsingLinq(string input)
        {

            return input.SequenceEqual(input.Reverse());
        }

```
</details>

### Method5_StringBuilder 

StringBuilderで新しい文字列を作ってみます。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static bool IsPalindromeUsingStringBuilder(string input)
        {

            var sb = new StringBuilder(input.Length);
            for ( int i = input.Length - 1; i >= 0; i-- )
            {
                sb.Append(input[i]);
            }

            return input.Equals(sb.ToString(), StringComparison.Ordinal);
        }

```
</details>

### Method6_SpanHalves

SpanでMethod3_DirectComparisonと同じことをしています。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static bool IsPalindromeUsingSpanHalves(string input)
        {

            ReadOnlySpan<char> span = input.AsSpan();
            int length = span.Length;

            for ( int i = 0; i < length / 2; i++ )
            {
                if ( span[i] != span[length - 1 - i] )
                    return false;
            }

            return true;
        }

```
</details>

### Method7_UnsafePointers

最後にUnsafeコードです。
ポインターでMethod3_DirectComparisonと同じことをしています。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private static unsafe bool IsPalindromeUsingUnsafeCode(string input)
        {

            fixed ( char* pInput = input )
            {
                char* pStart = pInput;
                char* pEnd = pInput + input.Length - 1;

                while ( pStart < pEnd )
                {
                    if ( *pStart != *pEnd )
                        return false;

                    pStart++;
                    pEnd--;
                }
            }

            return true;
        }

```
</details>

## 検証対象の文字列

また、各テストケースに判定させる文字列は以下になります。
これらは文字列型のリストである **```_testStrings```** に格納しています。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        private readonly List<string> _testStrings = new();
        private readonly List<string> _largePalindromes = new();

        [GlobalSetup]
        public void Setup()
        {
            // 短い回文
            _testStrings.Add("level");
            _testStrings.Add("radar");
            _testStrings.Add("civic");
            _testStrings.Add("deified");
            _testStrings.Add("racecar");

            // 非回文
            _testStrings.Add("hello");
            _testStrings.Add("world");
            _testStrings.Add("benchmark");
            _testStrings.Add("dotnet");

            // 長い回文
            var longPalindrome1 = "a".PadRight(1000, 'a');
            var longPalindrome2 = "abcdefg" + new string('x', 10000) + "gfedcba";
            _largePalindromes.Add(longPalindrome1);
            _largePalindromes.Add(longPalindrome2);
            _testStrings.AddRange(_largePalindromes);
        }

```
</details>

# 検証結果

|<font color=""> **検証結果** </font>|
|:-:|
|![alt](https://github.com/cushionA/ImageStrage/blob/main/%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A/%E3%83%86%E3%82%B9%E3%83%88%E7%B5%90%E6%9E%9C.png?raw=true)|


ちょっと分かりにくいので速い順に並べますね。

<table>
  <caption><strong>回文判定メソッドのパフォーマンス比較（平均実行時間順）</strong></caption>
  <thead>
    <tr>
      <th>メソッド</th> <th>平均実行時間</th>
    </tr>
  </thead>
  <tr>
    <td>Method7_UnsafePointers (Unsafeコード)</td> <td>1.807 μs</td>
  </tr>
  <tr>
    <td>Method1_SpanReverse (Spanによる反転)</td> <td>2.007 μs</td>
  </tr>
  <tr>
    <td>Method6_SpanHalves (Spanによる直接比較)</td> <td>3.202 μs</td>
  </tr>
  <tr>
    <td>Method2_ArrayReverse (配列による反転)</td> <td>3.309 μs</td>
  </tr>
  <tr>
    <td>Method3_DirectComparison (直接比較)</td> <td>3.800 μs</td>
  </tr>
  <tr>
    <td>Method5_StringBuilder (StringBuilder)</td> <td>15.641 μs</td>
  </tr>
  <tr>
    <td>Method4_Linq (LINQ)</td> <td>51.121 μs</td>
  </tr>
</table>


# 感想&まとめ
今回の結果としてはUnsafeコードが一番早いということになりました。
正直Unsafeで回文判定を行う処理を比較対象に加えた時点で、こうなることはうすうす分かっていました。
しかし思ったより全然Method1_SpanReverse（いつも使っていた処理）が肉薄していることが嬉しかったですね。
とはいえ少しでも早いに越したことはないので、Unsafeの回文判定メソッドを競プロライブラリに追加しようと思います。

また、遅い方を見るとLINQはただ遅いだけではなく、メモリ効率も悪いですね。
競技プログラミングでは使わない方がいいでしょう。

それでは今回の記事を終わります。
ご指摘、ご意見などあればコメントいただけると嬉しいです。

# 追加検証

@radian-jp 様からの提案を受けて再度検証しました。

> SpanのReverseは内部でSIMD処理（VectorXXX.Shuffleとか）使ってたりするので、単純に反転させるだけであれば速そうです。
(以下略)

詳しいやり取りはコメントにてご確認ください。
ともかく色々教えていただいた結果、 ```Span<T>.Reverse()``` を参考にして、SIMD処理とVectorXXX.EqualsAllを活用した回文判定処理を試してみることになりました。

## 実装コードとSpan<T>.Reverse()について
結論から言うと、実装コードは当初の想定とは異なる形になりました。
具体的には以下のような変化がありました。

<dl>
  <dt><strong>最初の予定</strong></dt>
  <dd><strong><font color="">複製した文字SpanをSpan<T>.Reverse()と同じように反転した後にVectorXXX.EqualsAllを使う。</font></strong></dd>
</dl>

<dl>
  <dt><strong>実装コード</strong></dt>
  <dd><strong><font color="">文字Spanを複製せずに、先頭と末尾からVectorで同じ文字数取得し、末尾の文字列を逆向きにした上でVectorXXX.EqualsAllを使う。</font></strong></dd>
</dl>

簡単に言うとMethod3_DirectComparisonに近いやり方に変えたということです。
このようにした理由は以下になります。

- **複製する必要がないこと。**
- **VectorXXX.EqualsAllによる比較の回数が単純に半分になること。**
- **StoreUnsafe()による書き込みが必要なくなること。**

また、実装にあたってはご提供いただいたソースに加えて以下のコードも参考にしました。

[.NetのSpanHelpers.Charのソース](https://github.com/dotnet/runtime/blob/f303e13199f0df0947612abf0c90f1f231e6641e/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Char.cs)

そして今回追加したMethod8_CompareReverseVectorのコードは以下です。
ほぼ参考元のReverse()とReverseInternal()のパクリですが……。

<!-- open属性なし -->
<details><summary><font color="skyblue"><strong>コード(展開)</strong></font></summary>

```C#:.cs
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static bool IsPalindromeVectorized(string input)
        {
            ReadOnlySpan<char> span = input.AsSpan();

            int length = span.Length;
            if ( length <= 1 )
                return true;

            nint elementsToCheck = length / 2;
            nint offset = 0;

            ref char buf = ref Unsafe.AsRef(ref MemoryMarshal.GetReference(span));

            // Vector512が利用可能かつ十分な長さがある場合
            if ( Vector512.IsHardwareAccelerated && elementsToCheck >= Vector512<ushort>.Count )
            {
                while ( offset + Vector512<ushort>.Count <= elementsToCheck )
                {
                    // 先頭側からのVectorロード
                    ref ushort first = ref Unsafe.As<char, ushort>(ref Unsafe.Add(ref buf, offset));
                    Vector512<ushort> forwardVector = Vector512.LoadUnsafe(ref first);

                    // 末尾側からのVectorロード
                    nint lastOffset = length - offset - Vector512<ushort>.Count;
                    ref ushort last = ref Unsafe.As<char, ushort>(ref Unsafe.Add(ref buf, lastOffset));
                    Vector512<ushort> reverseVector = Vector512.LoadUnsafe(ref last);

                    // 末尾側のVectorを内部で反転
                    reverseVector = Vector512.Shuffle(reverseVector, Vector512.Create(
                        (ushort)31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
                        15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0));

                    // 両者が一致するか確認
                    if ( !Vector512.EqualsAll(forwardVector, reverseVector) )
                        return false;

                    offset += Vector512<ushort>.Count;
                }
            }
            // Vector256 (AVX2) が利用可能かつ十分な長さがある場合
            else if ( Avx2.IsSupported && elementsToCheck >= Vector256<ushort>.Count )
            {
                Vector256<byte> reverseMask = Vector256.Create(
                    (byte)14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1,
                    14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1);

                while ( offset + Vector256<ushort>.Count <= elementsToCheck )
                {
                    // 先頭側からのVectorロード
                    ref byte first = ref Unsafe.As<char, byte>(ref Unsafe.Add(ref buf, offset));
                    Vector256<byte> forwardVector = Vector256.LoadUnsafe(ref first);

                    // 末尾側からのVectorロード
                    nint lastOffset = length - offset - Vector256<ushort>.Count;
                    ref byte last = ref Unsafe.As<char, byte>(ref Unsafe.Add(ref buf, lastOffset));
                    Vector256<byte> reverseVector = Vector256.LoadUnsafe(ref last);

                    // 末尾側のVectorをAVX2命令で反転
                    reverseVector = Avx2.Shuffle(reverseVector, reverseMask);
                    reverseVector = Avx2.Permute2x128(reverseVector, reverseVector, 0b00_01);

                    // 両者が一致するか確認
                    if ( !Vector256.EqualsAll(forwardVector, reverseVector) )
                        return false;

                    offset += Vector256<ushort>.Count;
                }
            }
            // Vector128が利用可能かつ十分な長さがある場合
            else if ( Vector128.IsHardwareAccelerated && elementsToCheck >= Vector128<ushort>.Count )
            {
                while ( offset + Vector128<ushort>.Count <= elementsToCheck )
                {
                    // 先頭側からのVectorロード
                    ref ushort first = ref Unsafe.As<char, ushort>(ref Unsafe.Add(ref buf, offset));
                    Vector128<ushort> forwardVector = Vector128.LoadUnsafe(ref first);

                    // 末尾側からのVectorロード
                    nint lastOffset = length - offset - Vector128<ushort>.Count;
                    ref ushort last = ref Unsafe.As<char, ushort>(ref Unsafe.Add(ref buf, lastOffset));
                    Vector128<ushort> reverseVector = Vector128.LoadUnsafe(ref last);

                    // 末尾側のVectorを内部で反転
                    reverseVector = Vector128.Shuffle(reverseVector, Vector128.Create(
                        (ushort)7, 6, 5, 4, 3, 2, 1, 0));

                    // 両者が一致するか確認
                    if ( !Vector128.EqualsAll(forwardVector, reverseVector) )
                        return false;

                    offset += Vector128<ushort>.Count;
                }
            }

            // Vectorからあふれた要素を比較
            int remaining = (int)(elementsToCheck - offset);

            if ( remaining > 1 )
            {
                ref char first = ref Unsafe.Add(ref buf, offset);
                ref char last = ref Unsafe.Add(ref buf, length - offset - 1);

                do
                {
                    if ( last != first )
                    {
                        return false;
                    }

                    first = ref Unsafe.Add(ref first, 1);
                    last = ref Unsafe.Subtract(ref last, 1);
                } while ( Unsafe.IsAddressLessThan(ref first, ref last) );
            }

            return true;
        }

```
</details>

## 結果

|<font color=""> **Method8追加後の処理** </font>|
|:-:|
|![alt](https://github.com/cushionA/ImageStrage/blob/main/%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A/%E3%83%99%E3%82%AF%E3%82%BF%E3%83%BC%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A%E8%BF%BD%E5%8A%A0%E7%B5%90%E6%9E%9C.png?raw=true)|

例によって見にくいので速度順に表にしました。

<table>
  <caption>回文判定メソッドのパフォーマンス比較（平均実行時間順）</caption>
  <thead>
    <tr>
      <th>メソッド</th> <th>平均実行時間</th>
    </tr>
  </thead>
  <tr>
    <td>Method8_CompareReverseVector (Vector比較)</td> <td>345.6 ns</td>
  </tr>
  <tr>
    <td>Method7_UnsafePointers (Unsafeコード)</td> <td>1,939.3 ns</td>
  </tr>
  <tr>
    <td>Method1_SpanReverse (Spanによる反転)</td> <td>1,976.9 ns</td>
  </tr>
  <tr>
    <td>Method6_SpanHalves (Spanによる半分比較)</td> <td>3,507.6 ns</td>
  </tr>
  <tr>
    <td>Method3_DirectComparison (直接比較)</td> <td>3,547.7 ns</td>
  </tr>
  <tr>
    <td>Method2_ArrayReverse (配列による反転)</td> <td>3,610.1 ns</td>
  </tr>
  <tr>
    <td>Method5_StringBuilder (StringBuilder)</td> <td>15,863.2 ns</td>
  </tr>
  <tr>
    <td>Method4_Linq (LINQ)</td> <td>50,591.1 ns</td>
  </tr>
</table>

### わーーーーーーい！！！！

すごい結果です！！
Method8_CompareReverseVectorがぶっちぎりです！
この手の検証でナノ秒なんて見たことない！！
こんなすごい速さなら競プロでどんなくそくそアルゴリズム組んでもACできるはず。
二位のMethod7_UnsafePointersと比較しても6倍くらいの差があります。
**これは地球と月の重力の差と同じくらい違うということです。**

@radian-jp 様にあらためて感謝申し上げます。


あとついでにこのVector比較の回文判定の動作確認用の証跡を取ったので置いておきます。
処理結果をクイックウォッチしたところ、テストに使用した_testStringsの中で非回文の四つについてもきちんと正しい結果を出力していました。

|<font color=""> **Vector** </font>|
|:-:|
|![alt](https://github.com/cushionA/ImageStrage/blob/main/%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A/%E3%83%99%E3%82%AF%E3%82%BF%E3%83%BC%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A%E3%81%AE%E6%AD%A3%E7%A2%BA%E6%80%A7%E8%A8%BC%E8%B7%A1.png?raw=true)|