【C#】最速の文字列操作を考える。

はじめに

競プロでおなじみ、文字列操作の最も高速な方式を探る記事を書きました。
実行環境はC# になります。
そして検証内容は以下の二つです。

• 文頭から末尾まで、ループ文による検査終了までの速度
• 要素の追加や削除の速度

ループ速度検証

ループ文を回す速度が最も早いデータ型について検証します。
エントリーしたデータ型は以下になります。
選手入場です。

String

文字列といえばString！

Hello Worldの頃からの絆！

あなたの初めての代入、メモリ確保、変数定義、全てがオレだ…。最古にして最高の"伝統"が参戦！！

StringBuilder

もう休め、String…

お前の時代は終わったのだ。

お前ができること、全部できますよ？　Length自在、不遜なる挑戦者、StringBuilder！

List

世界で最も使用されているコレクション！ （偏見）

最も良いものとは、最も使用されているものである。

民意に選ばれた王の降臨、約束されし勝者！　List参戦！

配列

諦めろ、私のメモリ領域は連続している。

戦慄の連続参照マシーン！　理論上最速の男、配列！

Span

リスト？　配列？　そいつら、オレがいないから使われてただけだろ？笑

全て過去にした。最新にして最強。

C# 7.2からの刺客、文句なしの優勝候補！

新鋭なる"怪物"、それこそがSpan。

はい！　やっていきます！

以下は検証コードです。

ループ速度検証コード(展開)

Program.cs

    /// <summary>
    /// テストコード。
    /// </summary>
    private void Test()
    {
        // 文字列の長さ
        const int stLength = 5000000;

        // ストリングビルダー、リスト、配列、Spanで走査速度を検証。
        StringBuilder builder;
        List<char> list;
        char[] cArray;
        Span<char> cSpan;
        string s;

        // 初期化処理
        s = Console.ReadLine();
        builder = new StringBuilder(s);
        for ( int i = 0; i < (stLength / s.Length) - 1; i++ )
        {
            builder.Append(s);
        }
        s = builder.ToString();
        list = s.ToCharArray().ToList();
        cArray = s.ToCharArray();
        cSpan = cArray.AsSpan();


        // ブレークポイント設定用の行。
        ;

        // Stringの走査テスト
        for ( int i = 0; i < s.Length; i++ )
        {
            TestMethod(s[i]);
        }

        // ブレークポイント設定。
        ;

        // 以下同じようにブレークポイントでコードを挟んでいく。

    }

    /// <summary>
    /// テスト用のメソッド。
    /// </summary>
    /// <param name="a"></param>
    static bool TestMethod(char a)
    {
        return a == 'a';
    }

このように、ブレークポイントで各検証コードを挟んでそれぞれのループ開始から終了までの経過時間を見ていきます。
ちなみに使用する文字列は五百万文字です。

結果

五つのデータ型で五百万文字の走査をした結果は次のようになりました。

速度計測結果(上の型ほど高速)

型名	1回目(ms)	2回目(ms)	3回目(ms)
配列	18	18	18
String	25	25	25
Span	28	26	25
List	26	28	26
StringBuilder	8771	8926	8866

以上です。
まず、一番下に化け物いますね。
文字通り桁が違う結果になりました。
これを見る限り、StringBuilderの文字列をcharのListみたいな使い方すると終わります。
TLEがイヤなら避けたほうがよさそうですね。
それから、Spanがかなり遅く見えます。
他の人の記事だと大体ループの速度がかなり早いのですが。
charは値型な（はずである）ので、参照型に弱いというSpanの弱点にも該当しない気がします。
なぜこんなに遅いのでしょうか？
もしご存じの方いましたらコメントで教えてくれると嬉しいです。
コメントなかったらいつか自分で検証してみたいです。

ちなみに、Spanに関しては実はstackallocキーワードでメモリを確保した場合の検証もしました。
これは若干遅くなっていた気がします。
stackallocの仕様上、そんなに多くの文字数を確保できなかったので違いがわかりにくい部分はあったのですが。(通常:3ms → stackalloc:4ms)
メモリの確保と解放だけが高速なんでしょうかね。
しかしスタックメモリはアクセスも速い認識でしたが。

とにかく、これから文字列の走査は配列でやることにします。

要素追加、削除の速度検証

この検証で取り扱う型は以下の二つのみです。
ガチンコ勝負です。

• StringBuilder
• char型のList

検証コードは以下になります。

追加/削除計測コード(展開)

Program.cs

        // ブレークポイント設定。
        ;

        // StringBuilderの追加/削除テスト
        for ( int i = 0; i < cArray.Length; i++ )
        {
            // 500万要素の配列の末尾まで追加し続けて、だいたい10回に一回削除もする。
            builder.Append(cArray[i]);
            if ( i % 10 == 0 && i > 0 )
            {
                builder.Remove(0, 1);
            }
        }

        // ブレークポイント設定。
        ;

        // Listの追加/削除テスト
        for ( int i = 0; i < cArray.Length; i++ )
        {
            // 500万要素の配列の末尾まで追加し続けて、だいたい10回に一回削除もする。
            list.Add(cArray[i]);
            if ( i % 10 == 0 && i > 0 )
            {
                list.RemoveAt(0);
            }
        }
        // ブレークポイント設定。
        ;

そして結果は以下です。

速度計測結果

型名	1回目(ms)	2回目(ms)	3回目(ms)
List	198344	195930	195935
StringBuilder	196156	196773	198795

一回目はStringBuilderの勝利、二回目はリストの勝利、三回目もリストの勝利。
だいぶ微妙ですね。
正直500万でこれならそこまで差がなさそうです。
ですから少し検証コードを変えて見ます。

文字列結合コード(展開)

Program.cs

        // ブレークポイント設定。
        ;

        // StringBuilderの追加/削除テスト
        for ( int i = 0; i < cArray.Length; i++ )
        {
            // 配列をジャグ配列にして範囲追加。
            // 配列の末尾まで追加し続けて、だいたい10回に一回削除もする。
            builder.Append(cArray[i]);
            if ( i % 10 == 0 && i > 0 )
            {
                builder.Remove(0, s.Length);
            }
        }

        // ブレークポイント設定。
        ;

        // Listの追加/削除テスト
        for ( int i = 0; i < cArray.Length; i++ )
        {
          　// 配列をジャグ配列にして範囲追加。
            // 配列の末尾まで追加し続けて、だいたい10回に一回削除もする。
            list.AddRange(cArray[i]);
            if ( i % 10 == 0 && i > 0 )
            {
                list.RemoveRange(0,s.Length);
            }
        }
        // ブレークポイント設定。
        ;

コメントにもあるように、追加と削除に使用する配列をジャグ配列にして、文字追加/削除ではなく文字列追加/削除の形にしてみました。
そして結果です。

文字列操作計測結果

型名	1回目(ms)	2回目(ms)	3回目(ms)
List	190	203	205
StringBuilder	8	9	9

StringBuilderの圧勝です。
思っていたより圧倒的でしたね。
やはり本領はこちらですか。
文字単位の操作もそうそう差があるようには見えなかったので、文字列の組み換えはStringBuilderが最適解のようですね。

StringBuilderの中身を見て見よう

StringBuilderについてですが、なぜあんなにもループ文の速度が遅かったのでしょうか。
疑問だったので、軽くStringBuilderのコードを見ると答えはすぐに分かりました。

それは、StringBuilderがIEnumerableを実装していないからです。

思い返すと、StringBuilderの文字の要素には builder[i] といった形でアクセス可能でした。
ですからすっかりIEnumerableのお仲間と思っていましたが、そんなことはありませんでした。
単に配列っぽくアクセスできるインデクサを実装しているというだけでした。

StringBuilderの公式ドキュメント

そしてこれも初めて知ったのですが、String型も実は IEnumerable インターフェイスを実装しています。

Stringの公式ドキュメント

これがStringBuilderのループ文だけがえげつなく遅くなった理由でしょう。

まとめ

今回の結論として、連続アクセスなら配列、要素の追加/削除であればStringBuilder と言える結果になったかと思います。
しかし本気で分からないのが Span<> の速度が全然早くなかったことです。
優秀な安全チェックが搭載されており、高速にループ文が回せるはずではなかったのでしょうか？

どなたかご存じの方いらっしゃいましたらご教授いただけると幸いです。
また、検証方法のダメ出しなどあれば、こちらも教えていただけると助かります。

記事を読んでくださりありがとうございました。

おまけ・置き換え処理の速度について。

置き換え、いわゆるstring型での Replace(char a ,char b) にあたる操作の速度についても調べました。

検証コードは以下です。

置き換え速度検証コード(展開)

Program.cs

        // ブレークポイント設定。
        ;

        // 配列の置き換え処理
        for ( int i = 0; i < cArray.Length; i++ )
        {
            if ( cArray[i] == 'a' )
                cArray[i] = 'A';
        }

        // ブレークポイント設定。
        ;

        // リストの置き換え処理。
        list.ForEach(n => n = n == 'a' ? 'b' : n);

        // ブレークポイント設定。
        ;

        // Spanの置き換え処理。
        cSpan.Replace<char>('a', 'b');

        ;

        // stringの置き換え処理。
        s.Replace('a', 'b');

        ;

        // StringBuilderの置き換え処理。
        builder.Replace('a', 'b');

        ;

結果は次のようになりました。

速度計測結果(上の型ほど高速)

型名	1回目(ms)	2回目(ms)
Span	2	2
StringBuilder	2	2
String	4	6
配列	14	14
List	16	16

ここはSpanが優勝でしたね。
自分もよく Fill() や Replace() を使う行でのみAsSpan()するような手は使いますが、このあたりの操作に関してはそれが一番速そうです。

追記：再度検証してみた。

@ruccho_vector 様 の ご指摘を受けて再度検証を行いました。
色々考えた結果、反省点は以下の二つでした。

• コンパイラの動作を考慮したコードを書けていなかったこと。
  　→　コンパイラの最適化により、意図した検証を行えない。

• Debugビルドで検証を行ったこと。（十分に最適化されない）
  　→　生成されたアセンブリを確認したところ、生成される処理が別物レベルに違うと分かった。

DebugとReleaseの違い

そこで、VisualStudioのビルドをReleaseに切り替えて検証を行いました。
テストコードは以下です。

再検証コード(展開)

Program.cs

    private void Test()
    {
        // 文字列の長さ
        const int sLength = 5000000;

        // Spanで走査速度を検証。
        Span<char> cSpan= new char[sLength];

        // TestMethodの結果格納用
        long result = 0;

        // ブレークポイント設定用。
        result++;

        // Spanの速度計測。
        for ( int i = 0; i < cSpan.Length; i++ )
        {
            result += TestMethod(cSpan[i]) ? 1 : -1;
        }

        // ブレークポイント設定用。
        result++;

        // テスト処理の結果を出力。
        Console.WriteLine(result);
    }

    /// <summary>
    /// テスト用のメソッド。
    /// </summary>
    /// <param name="a"></param>
    static bool TestMethod(char a)
    {
        return a == 'a';
    }

そしてこの結果、リリースビルドでも処理が実行されていることを値のウォッチで result を監視して確認しました。（　アセンブリに　それらしき処理もありましたが、ちゃんと解説できる自信がまだないです）

ウォッチ結果
TestMethod()の処理により値が変化している。

そして、上記の内容で再度検証を行ったところ以下のようになりました。

速度再計測結果(上の型ほど高速)

型名	1回目(ms)
配列	26
String	33
List	37
Span	41

おかしいですね……。
なぜなら、Spanが最下位です。
実はアセンブリを見た感じだと、Listが一番遅いだろうと思っていました。
コレクションの次の要素にアクセスする式が乗算を含んでいたので、アクセス速度が遅そうと感じたからです。（ふわふわしていて申し訳ありません）
以下にそのアセンブリのループ部分を抜き出した物を記します。

配列のアセンブリコード(展開)

Program.cs

L0060: movzx edi, word ptr [esi]
L0063: cmp edi, 0x61
L0066: je short L008d
L0068: mov edi, 0xffffffff
L006d: mov ebx, edi
L006f: sar ebx, 0x1f
L0072: add eax, edi
L0074: adc edx, ebx
L0076: add esi, 2
L0079: dec ecx
L007a: jne short L0060

Spanのアセンブリコード(展開)

Program.cs

L0080: movzx ebx, word ptr [eax+esi]
L0084: cmp ebx, 0x61
L0087: je short L00b2
L0089: mov ebx, 0xffffffff
L008e: mov eax, ebx
L0090: sar eax, 0x1f
L0093: add edx, ebx
L0095: adc ecx, eax
L0097: add esi, 2
L009a: dec edi
L009b: mov eax, [ebp-0x10]
L009e: jne short L0080

Listのアセンブリコード(展開)

Program.cs

L0060: mov edx, [edi+8]
L0063: test edx, edx
L0065: jle short L0099
L0067: cmp eax, edx
L0069: jb short L0071
L006b: jmp short L00ae
L0071: mov ecx, [edi+4]
L0074: cmp eax, [ecx+4]
L0077: jae short L00b5
L0079: movzx ecx, word ptr [ecx+eax*2+8]
L007e: cmp ecx, 0x61
L0081: je short L00a7
L0083: mov ecx, 0xffffffff
L0088: mov edi, ecx
L008a: sar edi, 0x1f
L008d: add esi, ecx
L008f: adc ebx, edi
L0091: inc eax
L0092: cmp eax, edx
L0094: mov edi, [ebp-0x10]
L0097: jl short L0067

Stringのアセンブリコード(展開)

Program.cs

L0065: movzx ecx, word ptr [edi+eax*2+8]
L006a: cmp ecx, 0x61
L006d: je short L009a
L006f: mov ecx, 0xffffffff
L0074: mov edx, ecx
L0076: sar edx, 0x1f
L0079: add esi, ecx
L007b: adc ebx, edx
L007d: inc eax
L007e: mov edx, [ebp-0x10]
L0081: cmp edx, eax
L0083: mov [ebp-0x10], edx
L0086: jg short L0065

そして次に遅いのがStringかなと思っていました。
何故なら、ループの継続判定がレジスタに保存した値同士の比較であり、コード内の mov命令 の数も多かったからです。
続いてSpanは配列とほぼ同じ動作に見えたので、二番目に早いかなと予想していました。
しかし結果はSpanが最下位です。
もうどうしていいのか分からなくなってきたので、最後の手段を使うことにしました。

最後の手段

AtCorderのコードテストで実行速度を見ることにしました。
競技プログラミングのサイトで、TLE（提出コードが実行時間制限を超えること）が点数に関わる以上、かなり厳密に実行時間を取得する仕組みがあるだろうと考えたからです。
そして結果は以下の通りでした。

速度再々計測結果(上の型ほど高速)

型名	1回目(ms)	2回目(ms)	3回目(ms)
配列	81	79	83
String	87	80	82
Span	82	88	88
List	102	103	104

見た感じ納得性は上がりましたが、まさかのStringが二位です。
AtCorderのコードテストの時間計測には信頼性がある（というよりないとコンテストが成り立たない）、という認識なので一旦これを再検証の結果といたします。

しかし他の方の記事での検証の環境を見たり、アセンブリの読み方をもっと勉強する必要があると自覚せざるを得ない結果となってしまいました。
もちろんStringの実装についても掘り下げる必要があるでしょう。
それはまた別の日にすることにして、今回の検証はひとまず閉じたいと思います。

最後になりますが、コメント欄での指摘に改めて感謝いたします。