Сравнение двух байтовых массивов в .NET
https://stackoverflow.com/questions/43289
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как я могу сделать это быстро?
Конечно, я могу это сделать:
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.
Обратите внимание на мой сверхбыстрый ответ здесь.
Решение 4
Пользователь джил предложенный небезопасный код, который породил это решение:
// 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 петля.Использование библиотеки J # выполняется эквивалентно оригиналу for петля.Использование .SequenceEqual выполняется примерно в семь раз медленнее;Я думаю, просто потому, что он использует IEnumerator.MoveNext.Я полагаю, что решения на основе LINQ, по крайней мере, такие же медленные или еще хуже.
Другие советы
Вы можете использовать Перечислимый.Последовательность одинаковая способ.
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
Если вы по какой-то причине не можете использовать .NET 3.5, ваш метод подходит.
Compiler \ среда выполнения оптимизирует ваш цикл, так что вам не нужно беспокоиться о производительности.
P/Вызывать силы активируются!
[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 есть новое встроенное решение для этого - Иструктурно приемлемый
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
Если вы не против этого, вы можете импортировать сборку J # "vjslib.dll" и использовать ее Массивы.метод equals(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;
}
Span<T> предлагает чрезвычайно конкурентоспособную альтернативу без необходимости добавлять запутанный и / или непереносимый материал в кодовую базу вашего собственного приложения:
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
return a1.SequenceEqual(a2);
}
(Основную часть) реализации начиная с .NET Core 2.2.3 можно найти здесь.
Я уже пересмотренный вариант Суть @EliArbel в том, чтобы добавить этот метод следующим образом SpansEqual, удалите большинство менее интересных исполнителей из чужих бенчмарков, запустите его с различными размерами массива, выведите графики и отметьте SpansEqual в качестве базовой линии, чтобы в ней сообщалось, как различные методы сравниваются с SpansEqual.
Приведенные ниже цифры взяты из результатов, слегка отредактированных для удаления столбца "Ошибка".
| Method | ByteCount | Mean | StdDev | Ratio |
|-------------- |----------- |-------------------:|------------------:|------:|
| SpansEqual | 15 | 3.813 ns | 0.0043 ns | 1.00 |
| LongPointers | 15 | 4.768 ns | 0.0081 ns | 1.25 |
| Unrolled | 15 | 17.763 ns | 0.0319 ns | 4.66 |
| PInvokeMemcmp | 15 | 12.280 ns | 0.0221 ns | 3.22 |
| | | | | |
| SpansEqual | 1026 | 29.181 ns | 0.0461 ns | 1.00 |
| LongPointers | 1026 | 63.050 ns | 0.0785 ns | 2.16 |
| Unrolled | 1026 | 39.070 ns | 0.0412 ns | 1.34 |
| PInvokeMemcmp | 1026 | 44.531 ns | 0.0581 ns | 1.53 |
| | | | | |
| SpansEqual | 1048585 | 43,838.865 ns | 56.7144 ns | 1.00 |
| LongPointers | 1048585 | 59,629.381 ns | 194.0304 ns | 1.36 |
| Unrolled | 1048585 | 54,765.863 ns | 34.2403 ns | 1.25 |
| PInvokeMemcmp | 1048585 | 55,250.573 ns | 49.3965 ns | 1.26 |
| | | | | |
| SpansEqual | 2147483591 | 247,237,201.379 ns | 2,734,143.0863 ns | 1.00 |
| LongPointers | 2147483591 | 241,535,134.852 ns | 2,720,870.8915 ns | 0.98 |
| Unrolled | 2147483591 | 240,170,750.054 ns | 2,729,935.0576 ns | 0.97 |
| PInvokeMemcmp | 2147483591 | 238,953,916.032 ns | 2,692,490.7016 ns | 0.97 |
Я был удивлен, увидев SpansEqual методы с максимальным размером массива не выходят на первое место, но разница настолько незначительна, что я не думаю, что это когда-нибудь будет иметь значение.
Информация о моей системе:
BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17134.706 (1803/April2018Update/Redstone4)
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
Frequency=3515626 Hz, Resolution=284.4444 ns, Timer=TSC
.NET Core SDK=2.2.202
[Host] : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
DefaultJob : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
.NET 3.5 и новее имеют новый общедоступный тип, System.Data.Linq.Binary это инкапсулирует byte[].Это реализует IEquatable<Binary> это (по сути) сравнивает два байтовых массива.Обратите внимание , что System.Data.Linq.Binary также имеет неявный оператор преобразования из byte[].
Документация MSDN:System.Data.Linq.Двоичный файл
Декомпиляция рефлектора метода Equals:
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;
}
Интересный поворот заключается в том, что они переходят к циклу сравнения побайтов только в том случае, если хэши двух двоичных объектов совпадают.Это, однако, происходит за счет вычисления хэша в конструкторе Binary объекты (путем обхода массива с помощью for петля :-) ).
Приведенная выше реализация означает, что в худшем случае вам, возможно, придется обойти массивы три раза:сначала вычислить хэш массива 1, затем вычислить хэш массива 2 и, наконец (поскольку это наихудший сценарий, длины и хэши равны) сравнить байты в массиве 1 с байтами в массиве 2.
В целом, даже несмотря на System.Data.Linq.Binary встроен в BCL, я не думаю, что это самый быстрый способ сравнить два байтовых массива:-|.
Я опубликовал аналогичный вопрос о проверке, не заполнен ли 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;
}
}
Измеряется на двух массивах по 256 Мбайт:
UnsafeCompare : 86,8784 ms
EqualBytesSimd : 71,5125 ms
EqualBytesSimdUnrolled : 73,1917 ms
EqualBytesLongUnrolled : 39,8623 ms
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");
}
Давайте добавим еще один!
Недавно Microsoft выпустила специальный пакет NuGet, Система.Среда выполнения.Службы компилятора.Небезопасно.Она особенная, потому что написана на IL, и предоставляет низкоуровневую функциональность, недоступную непосредственно в C #.
Один из его методов, Unsafe.As<T>(object) позволяет преобразовать любой ссылочный тип в другой ссылочный тип, пропуская любые проверки безопасности.Обычно это очень плохая идея, но если оба типа имеют одинаковую структуру, это может сработать.Таким образом, мы можем использовать это для приведения byte[] к 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 все равно вернет исходную длину массива, поскольку она хранится в поле в структуре памяти массива.
Этот метод не такой быстрый, как другие методы, продемонстрированные здесь, но он намного быстрее, чем метод naive, не использует небезопасный код, P / Invoke или закрепление, и реализация довольно проста (IMO).Вот некоторые из них Бенчмаркдотнет результаты с моего компьютера:
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 |
Я также создал суть всех тестов.
Я разработал метод, который слегка превосходит memcmp() (ответ плинтуса) и очень слабо бьет EqualBytesLongUnrolled() (Ответ Арека Бульски) на моем компьютере.По сути, он разворачивает цикл на 4 вместо 8.
Обновление от 30 марта.2019:
Начиная с .NET core 3.0, у нас есть поддержка SIMD!
Это решение является самым быстрым со значительным отрывом на моем компьютере:
#if NETCOREAPP3_0
using System.Runtime.Intrinsics.X86;
#endif
…
public static unsafe bool Compare(byte[] arr0, byte[] arr1)
{
if (arr0 == arr1)
{
return true;
}
if (arr0 == null || arr1 == null)
{
return false;
}
if (arr0.Length != arr1.Length)
{
return false;
}
if (arr0.Length == 0)
{
return true;
}
fixed (byte* b0 = arr0, b1 = arr1)
{
#if NETCOREAPP3_0
if (Avx2.IsSupported)
{
return Compare256(b0, b1, arr0.Length);
}
else if (Sse2.IsSupported)
{
return Compare128(b0, b1, arr0.Length);
}
else
#endif
{
return Compare64(b0, b1, arr0.Length);
}
}
}
#if NETCOREAPP3_0
public static unsafe bool Compare256(byte* b0, byte* b1, int length)
{
byte* lastAddr = b0 + length;
byte* lastAddrMinus128 = lastAddr - 128;
const int mask = -1;
while (b0 < lastAddrMinus128) // unroll the loop so that we are comparing 128 bytes at a time.
{
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0), Avx.LoadVector256(b1))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 32), Avx.LoadVector256(b1 + 32))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 64), Avx.LoadVector256(b1 + 64))) != mask)
{
return false;
}
if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 96), Avx.LoadVector256(b1 + 96))) != mask)
{
return false;
}
b0 += 128;
b1 += 128;
}
while (b0 < lastAddr)
{
if (*b0 != *b1) return false;
b0++;
b1++;
}
return true;
}
public static unsafe bool Compare128(byte* b0, byte* b1, int length)
{
byte* lastAddr = b0 + length;
byte* lastAddrMinus64 = lastAddr - 64;
const int mask = 0xFFFF;
while (b0 < lastAddrMinus64) // unroll the loop so that we are comparing 64 bytes at a time.
{
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0), Sse2.LoadVector128(b1))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 16), Sse2.LoadVector128(b1 + 16))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 32), Sse2.LoadVector128(b1 + 32))) != mask)
{
return false;
}
if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 48), Sse2.LoadVector128(b1 + 48))) != mask)
{
return false;
}
b0 += 64;
b1 += 64;
}
while (b0 < lastAddr)
{
if (*b0 != *b1) return false;
b0++;
b1++;
}
return true;
}
#endif
public static unsafe bool Compare64(byte* b0, byte* b1, int length)
{
byte* lastAddr = b0 + length;
byte* lastAddrMinus32 = lastAddr - 32;
while (b0 < lastAddrMinus32) // unroll the loop so that we are comparing 32 bytes at a time.
{
if (*(ulong*)b0 != *(ulong*)b1) return false;
if (*(ulong*)(b0 + 8) != *(ulong*)(b1 + 8)) return false;
if (*(ulong*)(b0 + 16) != *(ulong*)(b1 + 16)) return false;
if (*(ulong*)(b0 + 24) != *(ulong*)(b1 + 24)) return false;
b0 += 32;
b1 += 32;
}
while (b0 < lastAddr)
{
if (*b0 != *b1) return false;
b0++;
b1++;
}
return true;
}
Я бы использовал небезопасный код и запустил for цикл сравнения указателей Int32.
Возможно, вам также следует рассмотреть возможность проверки ненулевых массивов.
Если вы посмотрите, как .NET выполняет string.Equals , вы увидите, что он использует частный метод с именем EqualsHelper, который имеет "небезопасную" реализацию указателя. .NET Отражатель это ваш друг, чтобы посмотреть, как все делается внутри компании.
Это может быть использовано в качестве шаблона для сравнения байтовых массивов, реализацию которого я описал в сообщении в блоге Быстрое сравнение массивов байтов в C#.Я также выполнил несколько элементарных тестов, чтобы увидеть, когда безопасная реализация выполняется быстрее, чем небезопасная.
Тем не менее, если вам действительно не нужна убойная производительность, я бы предпочел простое сравнение циклов fr.
Не удалось найти решение, которым я полностью доволен (разумная производительность, но без небезопасного кода / pinvoke), поэтому я придумал это, ничего действительно оригинального, но работает:
/// <summary>
///
/// </summary>
/// <param name="array1"></param>
/// <param name="array2"></param>
/// <param name="bytesToCompare"> 0 means compare entire arrays</param>
/// <returns></returns>
public static bool ArraysEqual(byte[] array1, byte[] array2, int bytesToCompare = 0)
{
if (array1.Length != array2.Length) return false;
var length = (bytesToCompare == 0) ? array1.Length : bytesToCompare;
var tailIdx = length - length % sizeof(Int64);
//check in 8 byte chunks
for (var i = 0; i < tailIdx; i += sizeof(Int64))
{
if (BitConverter.ToInt64(array1, i) != BitConverter.ToInt64(array2, i)) return false;
}
//check the remainder of the array, always shorter than 8 bytes
for (var i = tailIdx; i < length; i++)
{
if (array1[i] != array2[i]) return false;
}
return true;
}
Производительность по сравнению с некоторыми другими решениями на этой странице:
Простой Цикл:19837 тиков, 1,00
* Преобразователь битов:4886 тиков, 4,06
Небезопасное сравнение:1636 тиков, 12.12
Равное количество запущенных байтов:637 тиков, 31.09
P/Вызвать memcmp:369 тиков, 53,67
Протестировано в linqpad, 1000000 байт идентичных массивов (наихудший сценарий), по 500 итераций в каждом.
Кажется , что Равное количество запущенных байтов является лучшим из предложенных выше.
Пропущенные методы (Enumerable.SequenceEqual, StructuralComparisons.StructuralEqualityComparer.Equals) не были терпеливыми из-за медлительности.На массивах размером 265 МБ я измерил это:
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 |
Я не видел здесь много решений linq.
Я не уверен в последствиях для производительности, однако я обычно придерживаюсь linq как правило, а затем при необходимости оптимизируйте позже.
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
return !array1.Where((t, i) => t != array2[i]).Any();
}
Пожалуйста, обратите внимание, что это работает только в том случае, если это массивы одинакового размера.расширение может выглядеть следующим образом
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
if (array1.Length != array2.Length) return false;
return !array1.Where((t, i) => t != array2[i]).Any();
}
Я выполнил некоторые измерения, используя прилагаемую программу .net 4.7 release build без прилагаемого отладчика.Я думаю, что люди использовали неправильную метрику, поскольку то, о чем вы говорите, если вас волнует скорость, заключается в том, сколько времени требуется, чтобы выяснить, равны ли два байтовых массива.т. е.пропускная способность в байтах.
StructuralComparison : 4.6 MiB/s
for : 274.5 MiB/s
ToUInt32 : 263.6 MiB/s
ToUInt64 : 474.9 MiB/s
memcmp : 8500.8 MiB/s
Как вы можете видеть, нет лучшего способа, чем memcmp и это на порядки быстрее.Простой for цикл - это второй лучший вариант.И у меня до сих пор в голове не укладывается, почему Microsoft не может просто включить Buffer.Compare способ.
[Program.cs] [Программа.cs]:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;
namespace memcmp
{
class Program
{
static byte[] TestVector(int size)
{
var data = new byte[size];
using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
{
rng.GetBytes(data);
}
return data;
}
static TimeSpan Measure(string testCase, TimeSpan offset, Action action, bool ignore = false)
{
var t = Stopwatch.StartNew();
var n = 0L;
while (t.Elapsed < TimeSpan.FromSeconds(10))
{
action();
n++;
}
var elapsed = t.Elapsed - offset;
if (!ignore)
{
Console.WriteLine($"{testCase,-16} : {n / elapsed.TotalSeconds,16:0.0} MiB/s");
}
return elapsed;
}
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);
static void Main(string[] args)
{
// how quickly can we establish if two sequences of bytes are equal?
// note that we are testing the speed of different comparsion methods
var a = TestVector(1024 * 1024); // 1 MiB
var b = (byte[])a.Clone();
// was meant to offset the overhead of everything but copying but my attempt was a horrible mistake... should have reacted sooner due to the initially ridiculous throughput values...
// Measure("offset", new TimeSpan(), () => { return; }, ignore: true);
var offset = TimeZone.Zero
Measure("StructuralComparison", offset, () =>
{
StructuralComparisons.StructuralEqualityComparer.Equals(a, b);
});
Measure("for", offset, () =>
{
for (int i = 0; i < a.Length; i++)
{
if (a[i] != b[i]) break;
}
});
Measure("ToUInt32", offset, () =>
{
for (int i = 0; i < a.Length; i += 4)
{
if (BitConverter.ToUInt32(a, i) != BitConverter.ToUInt32(b, i)) break;
}
});
Measure("ToUInt64", offset, () =>
{
for (int i = 0; i < a.Length; i += 8)
{
if (BitConverter.ToUInt64(a, i) != BitConverter.ToUInt64(b, i)) break;
}
});
Measure("memcmp", offset, () =>
{
memcmp(a, b, a.Length);
});
}
}
}
Для сравнения массивов коротких байтов ниже приведен интересный способ взлома:
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);
Тогда я, вероятно, пришел бы к решению, указанному в вопросе.
Было бы интересно провести анализ производительности этого кода.
Я подумал о методах ускорения передачи блоков, встроенных во многие видеокарты.Но тогда вам пришлось бы копировать все данные по байтам, так что это вам не сильно поможет, если вы не хотите реализовывать целую часть своей логики в неуправляемом и аппаратно-зависимом коде...
Другим способом оптимизации, подобным показанному выше подходу, было бы сохранить как можно больше ваших данных в виде long[], а не в виде byte[] с самого начала, например, если вы считываете их последовательно из двоичного файла, или если вы используете файл с отображением в памяти, считывайте данные как long[] или отдельные длинные значения.Тогда вашему циклу сравнения потребуется всего 1/8 от числа итераций, которые он должен был бы выполнить для byte[], содержащего тот же объем данных.Это вопрос того, когда и как часто вам нужно сравниватькогда и как часто вам необходимо получать доступ к данным побайтовым способом, напримериспользовать его при вызове API в качестве параметра в методе, который ожидает байт[].В конце концов, вы можете сказать, только если вы действительно знаете вариант использования...
Это почти наверняка намного медленнее, чем любая другая версия, приведенная здесь, но писать ее было весело.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
Я остановился на решении, вдохновленном методом EqualBytesLongUnrolled, опубликованным ArekBulski, с дополнительной оптимизацией.В моем случае различия в массивах, как правило, находятся ближе к хвосту массивов.В ходе тестирования я обнаружил, что, когда это имеет место для больших массивов, возможность сравнивать элементы массива в обратном порядке дает этому решению огромный прирост производительности по сравнению с решением на основе memcmp.Вот это решение:
public enum CompareDirection { Forward, Backward }
private static unsafe bool UnsafeEquals(byte[] a, byte[] b, CompareDirection direction = CompareDirection.Forward)
{
// returns when a and b are same array or both null
if (a == b) return true;
// if either is null or different lengths, can't be equal
if (a == null || b == null || a.Length != b.Length)
return false;
const int UNROLLED = 16; // count of longs 'unrolled' in optimization
int size = sizeof(long) * UNROLLED; // 128 bytes (min size for 'unrolled' optimization)
int len = a.Length;
int n = len / size; // count of full 128 byte segments
int r = len % size; // count of remaining 'unoptimized' bytes
// pin the arrays and access them via pointers
fixed (byte* pb_a = a, pb_b = b)
{
if (r > 0 && direction == CompareDirection.Backward)
{
byte* pa = pb_a + len - 1;
byte* pb = pb_b + len - 1;
byte* phead = pb_a + len - r;
while(pa >= phead)
{
if (*pa != *pb) return false;
pa--;
pb--;
}
}
if (n > 0)
{
int nOffset = n * size;
if (direction == CompareDirection.Forward)
{
long* pa = (long*)pb_a;
long* pb = (long*)pb_b;
long* ptail = (long*)(pb_a + nOffset);
while (pa < ptail)
{
if (*(pa + 0) != *(pb + 0) || *(pa + 1) != *(pb + 1) ||
*(pa + 2) != *(pb + 2) || *(pa + 3) != *(pb + 3) ||
*(pa + 4) != *(pb + 4) || *(pa + 5) != *(pb + 5) ||
*(pa + 6) != *(pb + 6) || *(pa + 7) != *(pb + 7) ||
*(pa + 8) != *(pb + 8) || *(pa + 9) != *(pb + 9) ||
*(pa + 10) != *(pb + 10) || *(pa + 11) != *(pb + 11) ||
*(pa + 12) != *(pb + 12) || *(pa + 13) != *(pb + 13) ||
*(pa + 14) != *(pb + 14) || *(pa + 15) != *(pb + 15)
)
{
return false;
}
pa += UNROLLED;
pb += UNROLLED;
}
}
else
{
long* pa = (long*)(pb_a + nOffset);
long* pb = (long*)(pb_b + nOffset);
long* phead = (long*)pb_a;
while (phead < pa)
{
if (*(pa - 1) != *(pb - 1) || *(pa - 2) != *(pb - 2) ||
*(pa - 3) != *(pb - 3) || *(pa - 4) != *(pb - 4) ||
*(pa - 5) != *(pb - 5) || *(pa - 6) != *(pb - 6) ||
*(pa - 7) != *(pb - 7) || *(pa - 8) != *(pb - 8) ||
*(pa - 9) != *(pb - 9) || *(pa - 10) != *(pb - 10) ||
*(pa - 11) != *(pb - 11) || *(pa - 12) != *(pb - 12) ||
*(pa - 13) != *(pb - 13) || *(pa - 14) != *(pb - 14) ||
*(pa - 15) != *(pb - 15) || *(pa - 16) != *(pb - 16)
)
{
return false;
}
pa -= UNROLLED;
pb -= UNROLLED;
}
}
}
if (r > 0 && direction == CompareDirection.Forward)
{
byte* pa = pb_a + len - r;
byte* pb = pb_b + len - r;
byte* ptail = pb_a + len;
while(pa < ptail)
{
if (*pa != *pb) return false;
pa++;
pb++;
}
}
}
return true;
}
Извините, если вы ищете управляемый способ, вы уже делаете это правильно, и, насколько мне известно, в BCL нет встроенного метода для этого.
Вы должны добавить несколько начальных проверок null, а затем просто повторно использовать его, как если бы оно было где-то в BCL.
Использование SequenceEquals для сравнения.
Короткий ответ таков:
public bool Compare(byte[] b1, byte[] b2)
{
return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
}
Таким образом, вы можете использовать оптимизированное сравнение строк .NET для сравнения массива байтов без необходимости написания небезопасного кода.Вот как это делается в предыстория:
private unsafe static bool EqualsHelper(String strA, String strB)
{
Contract.Requires(strA != null);
Contract.Requires(strB != null);
Contract.Requires(strA.Length == strB.Length);
int length = strA.Length;
fixed (char* ap = &strA.m_firstChar) fixed (char* bp = &strB.m_firstChar)
{
char* a = ap;
char* b = bp;
// Unroll the loop
#if AMD64
// For the AMD64 bit platform we unroll by 12 and
// check three qwords at a time. This is less code
// than the 32 bit case and is shorter
// pathlength.
while (length >= 12)
{
if (*(long*)a != *(long*)b) return false;
if (*(long*)(a+4) != *(long*)(b+4)) return false;
if (*(long*)(a+8) != *(long*)(b+8)) return false;
a += 12; b += 12; length -= 12;
}
#else
while (length >= 10)
{
if (*(int*)a != *(int*)b) return false;
if (*(int*)(a+2) != *(int*)(b+2)) return false;
if (*(int*)(a+4) != *(int*)(b+4)) return false;
if (*(int*)(a+6) != *(int*)(b+6)) return false;
if (*(int*)(a+8) != *(int*)(b+8)) return false;
a += 10; b += 10; length -= 10;
}
#endif
// This depends on the fact that the String objects are
// always zero terminated and that the terminating zero is not included
// in the length. For odd string sizes, the last compare will include
// the zero terminator.
while (length > 0)
{
if (*(int*)a != *(int*)b) break;
a += 2; b += 2; length -= 2;
}
return (length <= 0);
}
}
Поскольку многие из приведенных выше модных решений не работают с 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);
Если вы ищете очень быстрый компаратор равенства байтовых массивов, я предлагаю вам ознакомиться с этой статьей STSdb Labs: Устройство сравнения равенства байтовых массивов. В нем представлены некоторые из самых быстрых реализаций сравнения равенства массивов байт [], которые проверены на производительность и обобщены.
Вы также можете сосредоточиться на этих реализациях:
BigEndianByteArrayComparer - вычислитель - быстрое сравнение массива байт[] слева направо (BigEndian) BigEndianByteArrayEqualityComparer Сравнитель - - быстрый байтовый[] компаратор равенства слева направо (бигендиан) LittleEndianByteArrayComparer - сравнитель - быстрое сравнение массива байт[] справа налево (LittleEndian) LittleEndianByteArrayEqualityComparer Сравнитель - быстрый байтовый[] компаратор равенства справа налево (LittleEndian)
Если у вас огромный массив байтов, вы можете сравнить их, преобразовав в строку.
Вы можете использовать что-то вроде
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
Я использовал это и увидел огромное влияние на производительность.
