はじめに
突然ですが、二つのstring や配列の内容が同じかどうか調べるのに何を使っていますか？
今回は最速の比較手法とその仕組みを探っていきたいと思います
string の比較
はじめの検証
まずはstringの比較を見てみましょう。一般的にありそうな比較方法は以下の３つではないでしょうか。
-
==で比べる -
forで１文字ずつ比べる - Linqの
SequenceEqualを使う
では早速Benchmark.NETで測定してみます。
検証コード
public class Benchmark
{
private readonly string str1;
private readonly string str2;
public Benchmark()
{
const int size = 100000;
var rep = size / 26;
var rem = size % 26;
var unit = Enumerable.Range(0, 26).Select(i => (char)('a' + i));
var str = Enumerable.Repeat(unit, rep)
.SelectMany(x => x).Concat(Enumerable.Range(0, rem).Select(i => (char)('a' + i)));
str1 = new string(str.Concat(new[] { '1' }).ToArray());
str2 = new string(str.Concat(new[] { '2' }).ToArray());
}
[Benchmark]
public bool Linq()
{
return str1.SequenceEqual(str2);
}
[Benchmark]
public bool For()
{
for(int i = 0; i < str1.Length; i++)
{
if(str1[i] != str2[i])
{
return false;
}
}
return true;
}
[Benchmark]
public bool Operator()
{
return str1 == str2;
}
}
はじめの結果
| Method | Mean | Error | StdDev |
|---|---|---|---|
| Linq | 935.212 μs | 14.4288 μs | 13.4967 μs |
| For | 72.634 μs | 0.1364 μs | 0.1209 μs |
| Operator | 3.028 μs | 0.0106 μs | 0.0088 μs |
結果は == の圧勝でした。forでの比較より20倍も速く、本当に比較しているのか不安になるくらい高速です。
果たしてどこに元々シンプルな for を20倍も高速化できる余地があったのでしょうか。
==の速度を目指して オーバーヘッド改善編
for による列挙処理のパフォーマンス上のオーバーヘッドと聞いて、まず思いつくのは次の2点です。
- stringへの
[]はstring::get_Chars仮想メソッドの呼び出しにコンパイルされるため、仮想メソッド呼び出しのコストがかかる。 - 境界値チェックが各列挙ごとに行われる。
C#では[]をプロパティとしてユーザー定義できるため、色々な型に[]が使えます。しかし、(1次元)配列型とポインタ型への[]は特殊でメソッド呼び出しではなくIL専用命令での実装(ldelem.?命令やldind.?命令)となり、パフォーマンス上のオーバーヘッドが少なくすみます。
また、for(int i=0;i<array.length;i++)のように、配列へのアクセスで境界値超えをしないことが静的に自明な場合も、JIT時に境界値チェックが生成されず、オーバーヘッドがなくなります。
逆に言うと、それ以外のケースではオーバーヘッドがある ということですから、これを削ってみたいと思います。ポインタでアクセスすればよいのです。
[Benchmark]
public unsafe bool Pointer()
{
fixed (char* ptr1 = str1)
{
fixed (char* ptr2 = str2)
{
for (int i = 0; i < str1.Length; i++)
{
if (ptr1[i] != ptr2[i])
{
return false;
}
}
}
}
return true;
}
オーバーヘッド改善の効果
| Method | Mean | Error | StdDev |
|---|---|---|---|
| Linq | 934.469 μs | 2.6165 μs | 2.4475 μs |
| For | 72.854 μs | 0.2009 μs | 0.1879 μs |
| Pointer | 36.473 μs | 0.2323 μs | 0.1813 μs |
| Operator | 3.090 μs | 0.0117 μs | 0.0110 μs |
for + [] より2倍高速になりました。仮想メソッド呼び出しのコストは結構大きかったみたいですね。
しかし依然として == より12倍遅いです。オーバーヘッドがありそうな箇所はもう改善し尽くした感がありますが、どこがいけないのでしょうか。
比較する型の最適化
nuintずつ読み出す
実は、最後のポイントは「比較単位」です。charを1文字ずつ、つまり2バイトずつちまちま比較するのは無駄なのです。
char でも int でも long でも1計算にかかる時間は同じ、それどころか char のほうが遅いのです。
一番はやい整数型は何bitのCPUかなどに依存で、C#ではIntPtr や nint として扱え、現代ならば大抵64bitになります。char の4倍のサイズです。
では、string を nuint(符号なし) として読み出し、比較するコードを書いてみましょう。
ちょうど割り切れる保証はないのでコード行が増えます。メンドクサイ。
[Benchmark]
public unsafe bool PointerInt64()
{
int width = sizeof(nuint) / sizeof(char);
var count = str1.Length / width;
var rem = str1.Length % 4;
fixed (void* ptr1 = str1)
{
fixed (void* ptr2 = str2)
{
nuint* lPtr1 = (nuint*)ptr1;
nuint* lPtr2 = (nuint*)ptr2;
for (int i = 0; i < count; i++)
{
if (lPtr1[i] != lPtr2[i])
{
return false;
}
}
for (int i = 0; i < rem; i++)
{
if (((char*)ptr1)[count * width + i] != ((char*)ptr2)[count * width + i])
{
return false;
}
}
}
}
return true;
}
nuintの効果
| Method | Mean | Error | StdDev |
|---|---|---|---|
| Linq | 934.469 μs | 2.6165 μs | 2.4475 μs |
| For | 72.854 μs | 0.2009 μs | 0.1879 μs |
| Pointer | 36.473 μs | 0.2323 μs | 0.1813 μs |
| PointerInt64 | 6.806 μs | 0.0149 μs | 0.0124 μs |
| Operator | 3.090 μs | 0.0117 μs | 0.0110 μs |
普通にポインタを用いた場合より6倍も早くなりました。2byte => 8byte なのでループが回る回数は四分の一にしかなりませんが、char を扱うより nuint を扱うほうが高速であることによる最適化も結構効いているようです。
しかし、まだ == より2倍以上遅いです。nuint 比較戦略は完璧に見えますが、何が足りないのでしょうか。
Hardware Intrinsicsによる高速化
Hardware Intrinsicsとは
Hardware Intrinsics、聞き慣れない言葉だと思います。というかC#界隈でしか使われないっぽいです。
C#コードは特定のCPUや実行環境に依存しない中間言語にコンパイルされ...とはいいつつCPUの特定の命令に紐付いた構文です。.NET core 3系で初導入のようで、比較的新しい機能っぽいです。
現代のCPUでは、普段使う汎用的な命令に加え、特定の処理・用途のための拡張命令を備えています。汎用的な命令を高速にするのは頭打ち感があり結構大変な中、拡張命令を用意するのは現実的でお手軽なCPU高速化手法なのです。このような拡張命令の中に、今回使用するSIMD命令があります。single instruction multiple data、一命令で複数のデータを同時に演算できる命令で、ベクトル演算などと呼ばれることもあります。
新し目のx86系CPUの場合、AVX/AVX2命令というものが使えます。この命令では256bit長のベクトルを1命令で処理できます。long が64bitですから、longなら4つ、intなら8つ...とかなり大量に処理ができます1。Hardware Intrinsicsではこうした命令をほぼ直接呼び出すことができます。C#らしからずめっちゃ低レベルです。
しかし、「新し目のCPU」と書いたように環境依存性が強いのが難点で、その命令に対応していない場合の処理も記述せねばならず二度手間、三度手間...となりかなりメンドクサイです。
Vector<T> 構造体
Vector<T> 構造体を使うことで、ある程度の抽象化が可能です。Vector クラスという別物もありますので混ざらないように。あとUnityの Vectorなんちゃら とも違います。
実行環境が対応している最速の命令で演算が処理されます。ただし、最大公約数的な機能しか使えないのが難点です。
Vector256<T> 構造体
AVX命令を叩くときに、引数や戻り値として使うのがVector256<T> 構造体です。Vector256(非ジェネリック) 静的クラスや前述の色々な Vector とはやっぱり別物です。名前がややこしい。その名の通り256bit長のベクトルです。
使ってみる
[Benchmark]
public unsafe bool Vector()
{
int width = sizeof(Vector<short>) / sizeof(char);
var count = str1.Length / width;
var rem = str1.Length % 4;
fixed (void* ptr1 = str1)
{
fixed (void* ptr2 = str2)
{
var lPtr1 = (Vector<short>*)ptr1;
var lPtr2 = (Vector<short>*)ptr2;
for (int i = 0; i < count; i++)
{
if (lPtr1[i] != lPtr2[i])
{
return false;
}
}
for (int i = 0; i < rem; i++)
{
if (((char*)ptr1)[count * width + i] != ((char*)ptr2)[count * width + i])
{
return false;
}
}
}
}
return true;
}
[Benchmark]
public unsafe bool AVX256()
{
const int width = 32 / sizeof(char);
var count = str1.Length / width;
var rem = str1.Length % 4;
fixed (void* ptr1 = str1)
{
fixed (void* ptr2 = str2)
{
var lPtr1 = (Vector256<byte>*)ptr1;
var lPtr2 = (Vector256<byte>*)ptr2;
for (int i = 0; i < count; i++)
{
var vecEq = Avx2.CompareEqual(lPtr1[i], lPtr2[i]);
if (Avx2.MoveMask(vecEq) == 1)
{
return false;
}
}
for (int i = 0; i < rem; i++)
{
if (((char*)ptr1)[count * width + i] != ((char*)ptr2)[count * width + i])
{
return false;
}
}
}
}
return true;
}
最終結果
| Method | Mean | Error | StdDev |
|---|---|---|---|
| Linq | 934.469 μs | 2.6165 μs | 2.4475 μs |
| For | 72.854 μs | 0.2009 μs | 0.1879 μs |
| Pointer | 36.473 μs | 0.2323 μs | 0.1813 μs |
| PointerInt64 | 6.806 μs | 0.0149 μs | 0.0124 μs |
| Vector | 3.177 μs | 0.0174 μs | 0.0163 μs |
| AVX256 | 3.185 μs | 0.0157 μs | 0.0147 μs |
| Operator | 3.090 μs | 0.0117 μs | 0.0110 μs |
VectorとAVX256の結果はテストを回すごとに入れ替わったりします。ほぼ同じ速度です。
微妙に == より遅いですが、ほぼ == と同じパフォーマンスが出せました。
stringの==の実装
stringの == ではおそらくHardware Intrinsicsが使われているのだろうな、と検討はついたわけですが念の為ソースコードを見てみましょう。
ちょっと長くなるので折りたたんでおきました。見たい人は展開して見て下さい。
ソースコード
// Optimized byte-based SequenceEquals. The "length" parameter for this one is declared a nuint rather than int as we also use it for types other than byte
// where the length can exceed 2Gb once scaled by sizeof(T).
public static unsafe bool SequenceEqual(ref byte first, ref byte second, nuint length)
{
bool result;
// Use nint for arithmetic to avoid unnecessary 64->32->64 truncations
if (length >= (nuint)sizeof(nuint))
{
// Conditional jmp foward to favor shorter lengths. (See comment at "Equal:" label)
// The longer lengths can make back the time due to branch misprediction
// better than shorter lengths.
goto Longer;
}
#if TARGET_64BIT
// On 32-bit, this will always be true since sizeof(nuint) == 4
if (length < sizeof(uint))
#endif
{
uint differentBits = 0;
nuint offset = (length & 2);
if (offset != 0)
{
differentBits = LoadUShort(ref first);
differentBits -= LoadUShort(ref second);
}
if ((length & 1) != 0)
{
differentBits |= (uint)Unsafe.AddByteOffset(ref first, offset) - (uint)Unsafe.AddByteOffset(ref second, offset);
}
result = (differentBits == 0);
goto Result;
}
#if TARGET_64BIT
else
{
nuint offset = length - sizeof(uint);
uint differentBits = LoadUInt(ref first) - LoadUInt(ref second);
differentBits |= LoadUInt(ref first, offset) - LoadUInt(ref second, offset);
result = (differentBits == 0);
goto Result;
}
#endif
Longer:
// Only check that the ref is the same if buffers are large,
// and hence its worth avoiding doing unnecessary comparisons
if (!Unsafe.AreSame(ref first, ref second))
{
// C# compiler inverts this test, making the outer goto the conditional jmp.
goto Vector;
}
// This becomes a conditional jmp foward to not favor it.
goto Equal;
Result:
return result;
// When the sequence is equal; which is the longest execution, we want it to determine that
// as fast as possible so we do not want the early outs to be "predicted not taken" branches.
Equal:
return true;
Vector:
if (Sse2.IsSupported)
{
if (Avx2.IsSupported && length >= (nuint)Vector256<byte>.Count)
{
Vector256<byte> vecResult;
nuint offset = 0;
nuint lengthToExamine = length - (nuint)Vector256<byte>.Count;
// Unsigned, so it shouldn't have overflowed larger than length (rather than negative)
Debug.Assert(lengthToExamine < length);
if (lengthToExamine != 0)
{
do
{
vecResult = Avx2.CompareEqual(LoadVector256(ref first, offset), LoadVector256(ref second, offset));
if (Avx2.MoveMask(vecResult) != -1)
{
goto NotEqual;
}
offset += (nuint)Vector256<byte>.Count;
} while (lengthToExamine > offset);
}
// Do final compare as Vector256<byte>.Count from end rather than start
vecResult = Avx2.CompareEqual(LoadVector256(ref first, lengthToExamine), LoadVector256(ref second, lengthToExamine));
if (Avx2.MoveMask(vecResult) == -1)
{
// C# compiler inverts this test, making the outer goto the conditional jmp.
goto Equal;
}
// This becomes a conditional jmp foward to not favor it.
goto NotEqual;
}
// Use Vector128.Size as Vector128<byte>.Count doesn't inline at R2R time
// https://github.com/dotnet/runtime/issues/32714
else if (length >= Vector128.Size)
{
Vector128<byte> vecResult;
nuint offset = 0;
nuint lengthToExamine = length - Vector128.Size;
// Unsigned, so it shouldn't have overflowed larger than length (rather than negative)
Debug.Assert(lengthToExamine < length);
if (lengthToExamine != 0)
{
do
{
// We use instrincs directly as .Equals calls .AsByte() which doesn't inline at R2R time
// https://github.com/dotnet/runtime/issues/32714
vecResult = Sse2.CompareEqual(LoadVector128(ref first, offset), LoadVector128(ref second, offset));
if (Sse2.MoveMask(vecResult) != 0xFFFF)
{
goto NotEqual;
}
offset += Vector128.Size;
} while (lengthToExamine > offset);
}
// Do final compare as Vector128<byte>.Count from end rather than start
vecResult = Sse2.CompareEqual(LoadVector128(ref first, lengthToExamine), LoadVector128(ref second, lengthToExamine));
if (Sse2.MoveMask(vecResult) == 0xFFFF)
{
// C# compiler inverts this test, making the outer goto the conditional jmp.
goto Equal;
}
// This becomes a conditional jmp foward to not favor it.
goto NotEqual;
}
}
//else if (AdvSimd.Arm64.IsSupported)
//{
// // This API is not optimized with ARM64 intrinsics because there is not much performance win seen
// // when compared to the vectorized implementation below. In addition to comparing the bytes in chunks of
// // 16-bytes, the only check that is done is if there is a mismatch and if yes, return false. This check
// // done with Vector<T> will generate same code by JIT as that if used ARM64 intrinsic instead.
//}
else if (Vector.IsHardwareAccelerated && length >= (nuint)Vector<byte>.Count)
{
nuint offset = 0;
nuint lengthToExamine = length - (nuint)Vector<byte>.Count;
// Unsigned, so it shouldn't have overflowed larger than length (rather than negative)
Debug.Assert(lengthToExamine < length);
if (lengthToExamine > 0)
{
do
{
if (LoadVector(ref first, offset) != LoadVector(ref second, offset))
{
goto NotEqual;
}
offset += (nuint)Vector<byte>.Count;
} while (lengthToExamine > offset);
}
// Do final compare as Vector<byte>.Count from end rather than start
if (LoadVector(ref first, lengthToExamine) == LoadVector(ref second, lengthToExamine))
{
// C# compiler inverts this test, making the outer goto the conditional jmp.
goto Equal;
}
// This becomes a conditional jmp foward to not favor it.
goto NotEqual;
}
#if TARGET_64BIT
if (Sse2.IsSupported)
{
Debug.Assert(length <= (nuint)sizeof(nuint) * 2);
nuint offset = length - (nuint)sizeof(nuint);
nuint differentBits = LoadNUInt(ref first) - LoadNUInt(ref second);
differentBits |= LoadNUInt(ref first, offset) - LoadNUInt(ref second, offset);
result = (differentBits == 0);
goto Result;
}
else
#endif
{
Debug.Assert(length >= (nuint)sizeof(nuint));
{
nuint offset = 0;
nuint lengthToExamine = length - (nuint)sizeof(nuint);
// Unsigned, so it shouldn't have overflowed larger than length (rather than negative)
Debug.Assert(lengthToExamine < length);
if (lengthToExamine > 0)
{
do
{
// Compare unsigned so not do a sign extend mov on 64 bit
if (LoadNUInt(ref first, offset) != LoadNUInt(ref second, offset))
{
goto NotEqual;
}
offset += (nuint)sizeof(nuint);
} while (lengthToExamine > offset);
}
// Do final compare as sizeof(nuint) from end rather than start
result = (LoadNUInt(ref first, lengthToExamine) == LoadNUInt(ref second, lengthToExamine));
goto Result;
}
}
// As there are so many true/false exit points the Jit will coalesce them to one location.
// We want them at the end so the conditional early exit jmps are all jmp forwards so the
// branch predictor in a uninitialized state will not take them e.g.
// - loops are conditional jmps backwards and predicted
// - exceptions are conditional fowards jmps and not predicted
NotEqual:
return false;
}
やってることがすごいです。各環境に合わせて最適な拡張命令を叩き、さらにJIT時によりよい結果がでるようにgotoしてます。
先程のベンチマークからもわかる通り拡張命令によるパフォーマンス改善効果は凄まじく、JITだから、GCだからとかそんなの一瞬で超えてしまいます。
結局、こういう地道で細かいところがちゃんとできてる言語が速いです。
オープンソース化された.NET core以降、こういう地道な改善があちこちに入っていて、C#全体のパフォーマンスが改善しています。意識することはなくても、こうした高度に最適化されたクラスライブラリの恩恵を普段からうけているわけです。サマサマですね。
配列への応用
検証
string の研究により、普通にforで比較するとかなり遅いということがわかりました。となると配列の比較のベストプラクティスがなにか気になります。配列は==では比べられませんから。先程のstringの同じメモリサイズのbyte[]でベンチマークを取ってみましょう。
}検証コード
public unsafe class ArrayBenchmark
{
private readonly byte[] bin1;
private readonly byte[] bin2;
public ArrayBenchmark()
{
const int size = 200000;
var bin = Enumerable.Range(0, size).Select(i => (byte)(i & 0xFF));
bin1 = bin.Concat(new byte[] { 1 }).ToArray();
bin2 = bin.Concat(new byte[] { 2 }).ToArray();
}
[Benchmark]
public bool Linq()
{
return bin1.SequenceEqual(bin2);
}
[Benchmark]
public bool For()
{
for (int i = 0; i < bin1.Length; i++)
{
if (bin1[i] != bin2[i])
{
return false;
}
}
return true;
}
[Benchmark]
public unsafe bool Pointer()
{
fixed (byte* ptr1 = bin1)
{
fixed (byte* ptr2 = bin2)
{
for (int i = 0; i < bin1.Length; i++)
{
if (ptr1[i] != ptr2[i])
{
return false;
}
}
}
}
return true;
}
[Benchmark]
public unsafe bool PointerInt64()
{
int width = sizeof(nuint) / sizeof(byte);
var count = bin1.Length / width;
var rem = bin1.Length % 4;
fixed (void* ptr1 = bin1)
{
fixed (void* ptr2 = bin2)
{
nuint* lPtr1 = (nuint*)ptr1;
nuint* lPtr2 = (nuint*)ptr2;
for (int i = 0; i < count; i++)
{
if (lPtr1[i] != lPtr2[i])
{
return false;
}
}
for (int i = 0; i < rem; i++)
{
if (((byte*)ptr1)[count * width + i] != ((byte*)ptr2)[count * width + i])
{
return false;
}
}
}
}
return true;
}
[Benchmark]
public unsafe bool Vector()
{
int width = sizeof(Vector<byte>) / sizeof(byte);
var count = bin1.Length / width;
var rem = bin1.Length % 4;
fixed (void* ptr1 = bin1)
{
fixed (void* ptr2 = bin2)
{
var lPtr1 = (Vector<byte>*)ptr1;
var lPtr2 = (Vector<byte>*)ptr2;
for (int i = 0; i < count; i++)
{
if (lPtr1[i] != lPtr2[i])
{
return false;
}
}
for (int i = 0; i < rem; i++)
{
if (((byte*)ptr1)[count * width + i] != ((byte*)ptr2)[count * width + i])
{
return false;
}
}
}
}
return true;
}
[Benchmark]
public unsafe bool AVX256()
{
const int width = 32 / sizeof(byte);
var count = bin1.Length / width;
var rem = bin1.Length % 4;
fixed (void* ptr1 = bin1)
{
fixed (void* ptr2 = bin2)
{
var lPtr1 = (Vector256<byte>*)ptr1;
var lPtr2 = (Vector256<byte>*)ptr2;
for (int i = 0; i < count; i++)
{
var vecEq = Avx2.CompareEqual(lPtr1[i], lPtr2[i]);
if (Avx2.MoveMask(vecEq) == 1)
{
return false;
}
}
for (int i = 0; i < rem; i++)
{
if (((byte*)ptr1)[count * width + i] != ((byte*)ptr2)[count * width + i])
{
return false;
}
}
}
}
return true;
}
| Method | Mean | Error | StdDev |
|---|---|---|---|
| Linq | 3.191 μs | 0.0459 μs | 0.0430 μs |
| For | 148.009 μs | 0.6337 μs | 0.5927 μs |
| Pointer | 97.069 μs | 0.3636 μs | 0.3401 μs |
| PointerInt64 | 6.225 μs | 0.0445 μs | 0.0416 μs |
| Vector | 3.384 μs | 0.0311 μs | 0.0276 μs |
| AVX256 | 3.310 μs | 0.0578 μs | 0.0540 μs |
考察
for はやっぱり遅いです。配列2つを比べるので配列へのfor最適化が入りきらないのか、ポインタのほうが速いですが、string ほど効果は大きくありません。
自分で比較単位を決めるものは、string と実行時間が(当たり前ですが)変わらず、型に依存せずメモリサイズのみに依存する結果になります。
そして何よりLinqのSequenceEqualが速いです。というのも、Linqでは珍しいことではないですが、受け取ったIEnumerable<T>の型を見て特殊処理するコードが入っています。SequenceEqualの場合、本当に型が配列そのものかどうかだけ見てるので、stringには特殊処理が入らなかったのでかなり遅かったわけです。特殊処理の行き先はstringの==と同じで、System.SpanHelpers.SequenceEqualです。
一応の結論として、stringだと==の300倍遅かったSequenceEqualが下剋上で配列では最速ということになります。
MemoryExtention
結局配列でも、stringの==の内部実装のセクションで示したSystem.SpanHelpers.SequenceEqualを用いるものが最速になります。しかしこちらはinternal指定で普通に呼び出すことはできません。
その代わりに、内部でSystem.SpanHelpers.SequenceEqualを呼ぶSystem.MemoryExtensions.SequenceEqualを使いましょう。
こちらは、2つのSpan<T> ( またはReadOnlySpan<T> ) を比較するもので、拡張メソッドとしても呼べます。一応、配列も string も ReadOnlySpan<T> に暗黙的に型変換できますのでこれで対応できます。最も、stringには==、配列にはLinqとおぼえておけばそれでいいがいいのですが。
最後に
「配列 比較」とかでググるとforで比べよう！とか出てくるけど、for で比較だけはやめよう。めっちゃ遅いので。
-
整数型を扱えるのはAVX2命令です。Skylake(第6)世代くらいから導入された気がします。AMDならzenアーキテクチャで分割対応、zen2アーキテクチャでネイティブ対応です。 ↩