どうすればこれを速く行うことができますか？
確かに私はこれを行うことができます：
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
if (a1.Length != a2.Length)
return false;
for (int i=0; i<a1.Length; i++)
if (a1[i]!=a2[i])
return false;
return true;
}
しかし、私はこれを行うためのBCL関数または高度に最適化された実証済みの方法のいずれかを探しています。
java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);
うまく機能しますが、x64では機能しないようです。
ここで私の超高速の答えに注意してください。
Enumerable.SequenceEqualメソッドを使用できます。
using System;
using System.Linq;
...
var a1 = new int[] { 1, 2, 3};
var a2 = new int[] { 1, 2, 3};
var a3 = new int[] { 1, 2, 4};
var x = a1.SequenceEqual(a2); // true
var y = a1.SequenceEqual(a3); // false
なんらかの理由で.NET3.5を使用できない場合は、この方法で問題ありません。
コンパイラ\ランタイム環境はループを最適化するため、パフォーマンスについて心配する必要はありません。
P / Invokeパワーがアクティブになります！
[DllImport("msvcrt.dll", CallingConvention=CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);
static bool ByteArrayCompare(byte[] b1, byte[] b2)
{
// Validate buffers are the same length.
// This also ensures that the count does not exceed the length of either buffer.
return b1.Length == b2.Length && memcmp(b1, b2, b1.Length) == 0;
}
.NET 4 には、このための新しい組み込みソリューションがあります - IStructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
ユーザーgilは、このソリューションを生み出した安全でないコードを提案しました。
// Copyright (c) 2008-2013 Hafthor Stefansson
// Distributed under the MIT/X11 software license
// Ref: http://www.opensource.org/licenses/mit-license.php.
static unsafe bool UnsafeCompare(byte[] a1, byte[] a2) {
if(a1==a2) return true;
if(a1==null || a2==null || a1.Length!=a2.Length)
return false;
fixed (byte* p1=a1, p2=a2) {
byte* x1=p1, x2=p2;
int l = a1.Length;
for (int i=0; i < l/8; i++, x1+=8, x2+=8)
if (*((long*)x1) != *((long*)x2)) return false;
if ((l & 4)!=0) { if (*((int*)x1)!=*((int*)x2)) return false; x1+=4; x2+=4; }
if ((l & 2)!=0) { if (*((short*)x1)!=*((short*)x2)) return false; x1+=2; x2+=2; }
if ((l & 1)!=0) if (*((byte*)x1) != *((byte*)x2)) return false;
return true;
}
}
これは、可能な限り多くの配列に対して 64 ビット ベースの比較を行います。この種のことは、配列が qword で整列して開始されるという事実に基づいています。qwordが整列していなくても機能しますが、そうであった場合ほど速くはありません。
forこれは、単純なループよりも約 7 タイマー速く実行されます。forJ# ライブラリを使用すると、元のループと同等のパフォーマンスが得られます。.SequenceEqual を使用すると、約 7 倍遅くなります。IEnumerator.MoveNextを使用しているからだと思います。LINQ ベースのソリューションは、少なくともそれほど遅いか、それよりも悪いと思います。
反対しない場合は、J＃アセンブリ "vjslib.dll"をインポートし、そのArrays.equals（byte []、byte []）メソッドを使用できます...
誰かがあなたを笑っても私を責めないでください...
編集：少しの価値があるので、私はそのためのコードを分解するためにReflectorを使用しました、そしてこれはそれがどのように見えるかです：
public static bool equals(sbyte[] a1, sbyte[] a2)
{
if (a1 == a2)
{
return true;
}
if ((a1 != null) && (a2 != null))
{
if (a1.Length != a2.Length)
{
return false;
}
for (int i = 0; i < a1.Length; i++)
{
if (a1[i] != a2[i])
{
return false;
}
}
return true;
}
return false;
}
System.Data.Linq.Binary.NET 3.5 以降には、.NETをカプセル化する新しい public 型がありますbyte[]。IEquatable<Binary>(実際には) 2 つのバイト配列を比較することを実装します。System.Data.Linq.Binaryからの暗黙の変換演算子もあることに注意してくださいbyte[]。
MSDN ドキュメント: System.Data.Linq.Binary
Equals メソッドの Reflector 逆コンパイル:
private bool EqualsTo(Binary binary)
{
if (this != binary)
{
if (binary == null)
{
return false;
}
if (this.bytes.Length != binary.bytes.Length)
{
return false;
}
if (this.hashCode != binary.hashCode)
{
return false;
}
int index = 0;
int length = this.bytes.Length;
while (index < length)
{
if (this.bytes[index] != binary.bytes[index])
{
return false;
}
index++;
}
}
return true;
}
興味深いひねりは、2 つの Binary オブジェクトのハッシュが同じである場合にのみ、バイトごとの比較ループに進むことです。ただし、これには、オブジェクトのコンストラクターでハッシュを計算するという代償が伴いBinaryます (ループで配列をトラバースすることによりfor:-) )。
上記の実装は、最悪の場合、配列を 3 回トラバースする必要がある可能性があることを意味します。最初に array1 のハッシュを計算し、次に array2 のハッシュを計算し、最後に (これは最悪のシナリオであるため、長さとハッシュが等しいため) 比較します。配列 1 のバイトと配列 2 のバイト。
全体として、System.Data.Linq.BinaryBCL に組み込まれていますが、2 つのバイト配列を比較する最速の方法ではないと思います :-|。
byte[] がゼロでいっぱいかどうかの確認について、同様の質問を投稿しました。（SIMDコードは打ち負かされたので、この回答から削除しました。）これが私の比較からの最速のコードです：
static unsafe bool EqualBytesLongUnrolled (byte[] data1, byte[] data2)
{
if (data1 == data2)
return true;
if (data1.Length != data2.Length)
return false;
fixed (byte* bytes1 = data1, bytes2 = data2) {
int len = data1.Length;
int rem = len % (sizeof(long) * 16);
long* b1 = (long*)bytes1;
long* b2 = (long*)bytes2;
long* e1 = (long*)(bytes1 + len - rem);
while (b1 < e1) {
if (*(b1) != *(b2) || *(b1 + 1) != *(b2 + 1) ||
*(b1 + 2) != *(b2 + 2) || *(b1 + 3) != *(b2 + 3) ||
*(b1 + 4) != *(b2 + 4) || *(b1 + 5) != *(b2 + 5) ||
*(b1 + 6) != *(b2 + 6) || *(b1 + 7) != *(b2 + 7) ||
*(b1 + 8) != *(b2 + 8) || *(b1 + 9) != *(b2 + 9) ||
*(b1 + 10) != *(b2 + 10) || *(b1 + 11) != *(b2 + 11) ||
*(b1 + 12) != *(b2 + 12) || *(b1 + 13) != *(b2 + 13) ||
*(b1 + 14) != *(b2 + 14) || *(b1 + 15) != *(b2 + 15))
return false;
b1 += 16;
b2 += 16;
}
for (int i = 0; i < rem; i++)
if (data1 [len - 1 - i] != data2 [len - 1 - i])
return false;
return true;
}
}
2 つの 256MB バイト配列で測定:
UnsafeCompare : 86,8784 ms
EqualBytesSimd : 71,5125 ms
EqualBytesSimdUnrolled : 73,1917 ms
EqualBytesLongUnrolled : 39,8623 ms
もう1つ追加しましょう！
最近、Microsoft は特別な NuGet パッケージSystem.Runtime.CompilerServices.Unsafeをリリースしました。これはILで記述されており、C# では直接利用できない低レベルの機能を提供するため、特別です。
そのメソッドの 1 つは、Unsafe.As<T>(object)任意の参照型を別の参照型にキャストし、安全性チェックをスキップできるようにします。これは通常、非常に悪い考えですが、両方のタイプが同じ構造を持っている場合は機能します。したがって、これを使用して abyte[]を aにキャストできlong[]ます。
bool CompareWithUnsafeLibrary(byte[] a1, byte[] a2)
{
if (a1.Length != a2.Length) return false;
var longSize = (int)Math.Floor(a1.Length / 8.0);
var long1 = Unsafe.As<long[]>(a1);
var long2 = Unsafe.As<long[]>(a2);
for (var i = 0; i < longSize; i++)
{
if (long1[i] != long2[i]) return false;
}
for (var i = longSize * 8; i < a1.Length; i++)
{
if (a1[i] != a2[i]) return false;
}
return true;
}
long1.Length配列のメモリ構造のフィールドに格納されているため、元の配列の長さが返されることに注意してください。
このメソッドは、ここで示した他のメソッドほど高速ではありませんが、単純なメソッドよりもはるかに高速であり、安全でないコードや P/Invoke または固定を使用せず、実装は非常に簡単です (IMO)。私のマシンからのBenchmarkDotNetの結果は次のとおりです。
BenchmarkDotNet=v0.10.3.0, OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4870HQ CPU 2.50GHz, ProcessorCount=8
Frequency=2435775 Hz, Resolution=410.5470 ns, Timer=TSC
[Host] : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
DefaultJob : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
Method | Mean | StdDev |
----------------------- |-------------- |---------- |
UnsafeLibrary | 125.8229 ns | 0.3588 ns |
UnsafeCompare | 89.9036 ns | 0.8243 ns |
JSharpEquals | 1,432.1717 ns | 1.3161 ns |
EqualBytesLongUnrolled | 43.7863 ns | 0.8923 ns |
NewMemCmp | 65.4108 ns | 0.2202 ns |
ArraysEqual | 910.8372 ns | 2.6082 ns |
PInvokeMemcmp | 52.7201 ns | 0.1105 ns |
また、すべてのテストを含む Gist を作成しました。
using System.Linq; //SequenceEqual
byte[] ByteArray1 = null;
byte[] ByteArray2 = null;
ByteArray1 = MyFunct1();
ByteArray2 = MyFunct2();
if (ByteArray1.SequenceEqual<byte>(ByteArray2) == true)
{
MessageBox.Show("Match");
}
else
{
MessageBox.Show("Don't match");
}
安全でないコードを使用して、forInt32ポインターを比較するループを実行します。
たぶん、配列がnullでないことを確認することも検討する必要があります。
.NET がどのように string.Equals を実行するかを見ると、"安全でない" ポインター実装を持つ EqualsHelper というプライベート メソッドを使用していることがわかります。.NET Reflectorは、物事が内部でどのように行われているかを確認するのに役立ちます。
これは、ブログ投稿Fast byte array comparison in C# で実装したバイト配列比較のテンプレートとして使用できます。また、安全な実装が安全でない実装よりも速い場合を確認するために、いくつかの基本的なベンチマークも行いました。
とはいえ、本当にキラーなパフォーマンスが必要な場合を除き、単純な fr ループの比較を行います。
順序を気にする人 (つまり、何も返さないのではなく、似memcmpたようなものを返したい) のために、.NET Core 3.0 (およびおそらく .NET Standard 2.1 aka .NET 5.0)には、次のことができる拡張メソッド(および a )が含まれます。 2 つのインスタンスを比較するために使用されます ( )。intSpan.SequenceCompareTo(...)Span.SequenceEqualToReadOnlySpan<T>where T: IComparable<T>
元の GitHub 提案では、ディスカッションには、ジャンプ テーブル計算によるアプローチの比較、byte[]asの読み取りlong[]、SIMD の使用、および CLR 実装の への p/invoke が含まれていましたmemcmp。
今後、これはバイト配列またはバイト範囲を比較するための頼りになる方法 ( .NET Standard 2.1 APISpan<byte>の代わりに使用する必要があるbyte[]ため) であり、十分に高速であるため、最適化を気にする必要はありません (およびいいえ、名前の類似性にもかかわらず、それは恐ろしいほどひどく機能しませんEnumerable.SequenceEqual）。
#if NETCOREAPP3_0_OR_GREATER
// Using the platform-native Span<T>.SequenceEqual<T>(..)
public static int Compare(byte[] range1, int offset1, byte[] range2, int offset2, int count)
{
var span1 = range1.AsSpan(offset1, count);
var span2 = range2.AsSpan(offset2, count);
return span1.SequenceCompareTo(span2);
// or, if you don't care about ordering
// return span1.SequenceEqual(span2);
}
#else
// The most basic implementation, in platform-agnostic, safe C#
public static bool Compare(byte[] range1, int offset1, byte[] range2, int offset2, int count)
{
// Working backwards lets the compiler optimize away bound checking after the first loop
for (int i = count - 1; i >= 0; --i)
{
if (range1[offset1 + i] != range2[offset2 + i])
{
return false;
}
}
return true;
}
#endif
上記の提案からEqualBytesLongUnrolledが最適のようです。
スキップされたメソッド (Enumerable.SequenceEqual,StructuralComparisons.StructuralEqualityComparer.Equals) は、遅すぎるとは言えませんでした。265MB アレイでこれを測定しました。
Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-3770 CPU 3.40GHz, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0
Type=CompareMemoriesBenchmarks Mode=Throughput
Method | Median | StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
NewMemCopy | 30.0443 ms | 1.1880 ms | 1.00 | 0.00 |
EqualBytesLongUnrolled | 29.9917 ms | 0.7480 ms | 0.99 | 0.04 |
msvcrt_memcmp | 30.0930 ms | 0.2964 ms | 1.00 | 0.03 |
UnsafeCompare | 31.0520 ms | 0.7072 ms | 1.03 | 0.04 |
ByteArrayCompare | 212.9980 ms | 2.0776 ms | 7.06 | 0.25 |
OS=Windows
Processor=?, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=CORE, Arch=64-bit ? [RyuJIT]
GC=Concurrent Workstation
dotnet cli version: 1.0.0-preview2-003131
Type=CompareMemoriesBenchmarks Mode=Throughput
Method | Median | StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
NewMemCopy | 30.1789 ms | 0.0437 ms | 1.00 | 0.00 |
EqualBytesLongUnrolled | 30.1985 ms | 0.1782 ms | 1.00 | 0.01 |
msvcrt_memcmp | 30.1084 ms | 0.0660 ms | 1.00 | 0.00 |
UnsafeCompare | 31.1845 ms | 0.4051 ms | 1.03 | 0.01 |
ByteArrayCompare | 212.0213 ms | 0.1694 ms | 7.03 | 0.01 |
短いバイト配列を比較するには、次の興味深いハックがあります。
if(myByteArray1.Length != myByteArray2.Length) return false;
if(myByteArray1.Length == 8)
return BitConverter.ToInt64(myByteArray1, 0) == BitConverter.ToInt64(myByteArray2, 0);
else if(myByteArray.Length == 4)
return BitConverter.ToInt32(myByteArray2, 0) == BitConverter.ToInt32(myByteArray2, 0);
次に、質問に記載されている解決策に陥る可能性があります。
このコードのパフォーマンス分析を行うことは興味深いでしょう。
多くのグラフィックカードに組み込まれているブロック転送アクセラレーション方式について考えました。ただし、すべてのデータをバイト単位でコピーする必要があるため、ロジックの全体を管理されていないハードウェア依存のコードで実装したくない場合は、これはあまり役に立ちません...
上に示したアプローチと同様の最適化の別の方法は、たとえば、バイナリファイルから順次読み取る場合、最初からbyte[]ではなくlong[]にできるだけ多くのデータを格納することです。または、メモリマップトファイルを使用する場合は、long[]または単一のlong値としてデータを読み込みます。次に、比較ループに必要なのは、同じ量のデータを含むbyte[]に対して実行する必要がある反復回数の1/8だけです。いつ、どのくらいの頻度でデータにアクセスする必要があるのか、いつ、どのくらいの頻度でデータにアクセスする必要があるのかが問題になります。バイト[]。結局、ユースケースを本当に知っているかどうかしかわかりません...
申し訳ありませんが、管理された方法を探している場合は、すでに正しく実行しています。私の知る限り、これを実行するための組み込みメソッドはBCLにありません。
最初のnullチェックをいくつか追加してから、BCLのどこにあるかのように再利用する必要があります。
これは他のものと似ていますが、ここでの違いは、一度にチェックできる次の最大バイト数までフォールスルーがないことです。たとえば、63 バイトがある場合 (私の SIMD の例では)、最初のバイトの等価性をチェックできます。これは、32 バイト、16 バイト、8 バイトなどをチェックするよりも高速です。入力する最初のチェックは、すべてのバイトを比較するために必要な唯一のチェックです。
これは私のテストでは一番上に出てきますが、髪の毛だけです.
次のコードは、私が airbreather/ArrayComparePerf.cs でテストした方法とまったく同じです。
public unsafe bool SIMDNoFallThrough() #requires System.Runtime.Intrinsics.X86
{
if (a1 == null || a2 == null)
return false;
int length0 = a1.Length;
if (length0 != a2.Length) return false;
fixed (byte* b00 = a1, b01 = a2)
{
byte* b0 = b00, b1 = b01, last0 = b0 + length0, last1 = b1 + length0, last32 = last0 - 31;
if (length0 > 31)
{
while (b0 < last32)
{
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0), Avx.LoadVector256(b1))) != -1)
return false;
b0 += 32;
b1 += 32;
}
return Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(last0 - 32), Avx.LoadVector256(last1 - 32))) == -1;
}
if (length0 > 15)
{
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0), Sse2.LoadVector128(b1))) != 65535)
return false;
return Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(last0 - 16), Sse2.LoadVector128(last1 - 16))) == 65535;
}
if (length0 > 7)
{
if (*(ulong*)b0 != *(ulong*)b1)
return false;
return *(ulong*)(last0 - 8) == *(ulong*)(last1 - 8);
}
if (length0 > 3)
{
if (*(uint*)b0 != *(uint*)b1)
return false;
return *(uint*)(last0 - 4) == *(uint*)(last1 - 4);
}
if (length0 > 1)
{
if (*(ushort*)b0 != *(ushort*)b1)
return false;
return *(ushort*)(last0 - 2) == *(ushort*)(last1 - 2);
}
return *b0 == *b1;
}
}
SIMD が優先されない場合は、同じ方法が既存の LongPointers アルゴリズムに適用されます。
public unsafe bool LongPointersNoFallThrough()
{
if (a1 == null || a2 == null || a1.Length != a2.Length)
return false;
fixed (byte* p1 = a1, p2 = a2)
{
byte* x1 = p1, x2 = p2;
int l = a1.Length;
if ((l & 8) != 0)
{
for (int i = 0; i < l / 8; i++, x1 += 8, x2 += 8)
if (*(long*)x1 != *(long*)x2) return false;
return *(long*)(x1 + (l - 8)) == *(long*)(x2 + (l - 8));
}
if ((l & 4) != 0)
{
if (*(int*)x1 != *(int*)x2) return false; x1 += 4; x2 += 4;
return *(int*)(x1 + (l - 4)) == *(int*)(x2 + (l - 4));
}
if ((l & 2) != 0)
{
if (*(short*)x1 != *(short*)x2) return false; x1 += 2; x2 += 2;
return *(short*)(x1 + (l - 2)) == *(short*)(x2 + (l - 2));
}
return *x1 == *x2;
}
}
SequenceEqualsこれを比較に使います。
非常に高速なバイト配列等価比較器をお探しの場合は、STSdb Labs の記事「バイト配列等価比較器」をご覧になることをお勧めします。これは、バイト [] 配列の等価性比較の最速の実装のいくつかを特徴としており、それらは提示され、パフォーマンスがテストされ、要約されています。
これらの実装に集中することもできます。
BigEndianByteArrayComparer - 左から右への高速 byte[] 配列比較 (BigEndian) BigEndianByteArrayEqualityComparer - - 左から右への高速 byte[] 等値比較 (BigEndian) LittleEndianByteArrayComparer - 右から左への高速 byte[] 配列比較 (LittleEndian) LittleEndianByteArrayEqualityComparer - 高速 byte [] 右から左への等価比較子 (LittleEndian)
上記の凝ったソリューションの多くは UWP では機能せず、Linq と関数型アプローチが大好きなので、この問題に対する私のバージョンを紹介します。最初の違いが発生したときに比較を回避するために、.FirstOrDefault() を選択しました
public static bool CompareByteArrays(byte[] ba0, byte[] ba1) =>
!(ba0.Length != ba1.Length || Enumerable.Range(1,ba0.Length)
.FirstOrDefault(n => ba0[n] != ba1[n]) > 0);