はじめに
今回はタイトルの通り、C#における回文判定の手法で最も高速な処理は何かを検証します。
動機はコーディング問題で回文の設問を解いていて、回文判定は色々あるけどどれが一番早いのだろう……ともやもやしたことです。
さくっと検証します。
テスト環境
- C#(.NET 8.0.14 )
- BenchmarkDotNet
検証内容
今回は七つの方法を比較します。
検証の前に軽く紹介をさせてください。
小見出しの名前は対応するテストメソッドの名前です。
Method1_SpanReverse
まずはSpanのReverse()とSequenceEqual()を利用した判定です。
一応いつも使っている方法です。
これが一番早い、と思っていましたが根拠は特にないんですねこれが。
コード(展開)
.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);
}
Method2_ArrayReverse
次は最初の手法を配列で再現したものになります。
コード(展開)
.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);
}
Method3_DirectComparison
続いて最後尾と先頭から対応するインデックスの文字を比較していく処理になります。
地味に計算量O(N/2)ですから隠れた強豪ではないかと目しております。
コード(展開)
.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;
}
Method4_Linq
個人的には遅いと予想しますが、念のためLINQも入れました。
コード(展開)
.cs
private static bool IsPalindromeUsingLinq(string input)
{
return input.SequenceEqual(input.Reverse());
}
Method5_StringBuilder
StringBuilderで新しい文字列を作ってみます。
コード(展開)
.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);
}
Method6_SpanHalves
SpanでMethod3_DirectComparisonと同じことをしています。
コード(展開)
.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;
}
Method7_UnsafePointers
最後にUnsafeコードです。
ポインターでMethod3_DirectComparisonと同じことをしています。
コード(展開)
.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;
}
検証対象の文字列
また、各テストケースに判定させる文字列は以下になります。
これらは文字列型のリストである _testStrings に格納しています。
コード(展開)
.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);
}
検証結果
| 検証結果 |
|---|
 |
ちょっと分かりにくいので速い順に並べますね。
| メソッド | 平均実行時間 |
|---|---|
| Method7_UnsafePointers (Unsafeコード) | 1.807 μs |
| Method1_SpanReverse (Spanによる反転) | 2.007 μs |
| Method6_SpanHalves (Spanによる直接比較) | 3.202 μs |
| Method2_ArrayReverse (配列による反転) | 3.309 μs |
| Method3_DirectComparison (直接比較) | 3.800 μs |
| Method5_StringBuilder (StringBuilder) | 15.641 μs |
| Method4_Linq (LINQ) | 51.121 μs |
感想&まとめ
今回の結果としてはUnsafeコードが一番早いということになりました。
正直Unsafeで回文判定を行う処理を比較対象に加えた時点で、こうなることはうすうす分かっていました。
しかし思ったより全然Method1_SpanReverse（いつも使っていた処理）が肉薄していることが嬉しかったですね。
とはいえ少しでも早いに越したことはないので、Unsafeの回文判定メソッドを競プロライブラリに追加しようと思います。
また、遅い方を見るとLINQはただ遅いだけではなく、メモリ効率も悪いですね。
競技プログラミングでは使わない方がいいでしょう。
それでは今回の記事を終わります。
ご指摘、ご意見などあればコメントいただけると嬉しいです。
追加検証
@radian-jp 様からの提案を受けて再度検証しました。
SpanのReverseは内部でSIMD処理（VectorXXX.Shuffleとか）使ってたりするので、単純に反転させるだけであれば速そうです。
(以下略)
詳しいやり取りはコメントにてご確認ください。
ともかく色々教えていただいた結果、 Span<T>.Reverse() を参考にして、SIMD処理とVectorXXX.EqualsAllを活用した回文判定処理を試してみることになりました。
実装コードとSpan.Reverse()について
結論から言うと、実装コードは当初の想定とは異なる形になりました。
具体的には以下のような変化がありました。
- 最初の予定
- 複製した文字SpanをSpan.Reverse()と同じように反転した後にVectorXXX.EqualsAllを使う。
- 実装コード
- 文字Spanを複製せずに、先頭と末尾からVectorで同じ文字数取得し、末尾の文字列を逆向きにした上でVectorXXX.EqualsAllを使う。
簡単に言うとMethod3_DirectComparisonに近いやり方に変えたということです。
このようにした理由は以下になります。
- 複製する必要がないこと。
- VectorXXX.EqualsAllによる比較の回数が単純に半分になること。
- StoreUnsafe()による書き込みが必要なくなること。
また、実装にあたってはご提供いただいたソースに加えて以下のコードも参考にしました。
そして今回追加したMethod8_CompareReverseVectorのコードは以下です。
ほぼ参考元のReverse()とReverseInternal()のパクリですが……。
コード(展開)
.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;
}
結果
| Method8追加後の処理 |
|---|
 |
例によって見にくいので速度順に表にしました。
| メソッド | 平均実行時間 |
|---|---|
| Method8_CompareReverseVector (Vector比較) | 345.6 ns |
| Method7_UnsafePointers (Unsafeコード) | 1,939.3 ns |
| Method1_SpanReverse (Spanによる反転) | 1,976.9 ns |
| Method6_SpanHalves (Spanによる半分比較) | 3,507.6 ns |
| Method3_DirectComparison (直接比較) | 3,547.7 ns |
| Method2_ArrayReverse (配列による反転) | 3,610.1 ns |
| Method5_StringBuilder (StringBuilder) | 15,863.2 ns |
| Method4_Linq (LINQ) | 50,591.1 ns |
わーーーーーーい！！！！
すごい結果です！！
Method8_CompareReverseVectorがぶっちぎりです！
この手の検証でナノ秒なんて見たことない！！
こんなすごい速さなら競プロでどんなくそくそアルゴリズム組んでもACできるはず。
二位のMethod7_UnsafePointersと比較しても6倍くらいの差があります。
これは地球と月の重力の差と同じくらい違うということです。
@radian-jp 様にあらためて感謝申し上げます。
あとついでにこのVector比較の回文判定の動作確認用の証跡を取ったので置いておきます。
処理結果をクイックウォッチしたところ、テストに使用した_testStringsの中で非回文の四つについてもきちんと正しい結果を出力していました。
| Vector |
|---|
 |