Сравнение двухбайтовых массивов в.NET
Как я могу сделать это быстро?
Конечно, я могу сделать это:
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.
Обратите внимание на мой супер-быстрый ответ здесь.
30 ответов
Пользователь 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 петля. Использование библиотеки J# выполняется аналогично оригиналу for петля. Использование.SequenceEqual работает в семь раз медленнее; Я думаю только потому, что он использует IEnumerator.MoveNext. Я думаю, что решения на основе LINQ, по крайней мере, такие медленные или хуже.
Вы можете использовать метод 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
Если по какой-то причине вы не можете использовать.NET 3.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;
}
Span<T> предлагает чрезвычайно конкурентоспособную альтернативу без необходимости вводить запутанный и / или непереносимый пух в базу кода вашего собственного приложения:
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
return a1.SequenceEqual(a2);
}
Реализация (кишки) может быть найдена здесь.
Я пересмотрел суть @EliArbel, чтобы добавить этот метод как SpansEqualпоместите большинство менее интересных исполнителей в тесты других пользователей, запустите его с различными размерами массивов, графиками вывода и отметкой SpansEqual в качестве базовой линии, чтобы он сообщал, как различные методы сравниваются с SpansEqual,
Приведенные ниже цифры взяты из результатов, слегка отредактированных для удаления столбца "Ошибка".
| Method | ByteCount | Mean | StdDev | Scaled |
|-------------- |----------- |-------------------:|---------------:|-------:|
| SpansEqual | 15 | 3.614 ns | 0.0069 ns | 1.00 |
| LongPointers | 15 | 4.762 ns | 0.0009 ns | 1.32 |
| Unrolled | 15 | 16.933 ns | 0.0024 ns | 4.68 |
| PInvokeMemcmp | 15 | 11.448 ns | 0.0183 ns | 3.17 |
| | | | | |
| SpansEqual | 1026 | 25.957 ns | 0.0081 ns | 1.00 |
| LongPointers | 1026 | 60.336 ns | 0.0211 ns | 2.32 |
| Unrolled | 1026 | 37.216 ns | 0.0042 ns | 1.43 |
| PInvokeMemcmp | 1026 | 43.531 ns | 0.0229 ns | 1.68 |
| | | | | |
| SpansEqual | 1048585 | 42,708.279 ns | 6.7683 ns | 1.00 |
| LongPointers | 1048585 | 57,952.010 ns | 6.0004 ns | 1.36 |
| Unrolled | 1048585 | 52,768.967 ns | 5.1800 ns | 1.24 |
| PInvokeMemcmp | 1048585 | 53,270.846 ns | 11.9056 ns | 1.25 |
| | | | | |
| SpansEqual | 2147483591 | 243,281,911.498 ns | 65,006.3172 ns | 1.00 |
| LongPointers | 2147483591 | 237,786,969.675 ns | 96,332.7202 ns | 0.98 |
| Unrolled | 2147483591 | 237,151,053.500 ns | 74,137.6513 ns | 0.97 |
| PInvokeMemcmp | 2147483591 | 235,829,644.641 ns | 50,390.2144 ns | 0.97 |
Я был удивлен, увидев SpansEqual не стоит на первом месте для методов max-array-size, но разница настолько незначительна, что я не думаю, что это когда-либо будет иметь значение.
Моя системная информация:
BenchmarkDotNet=v0.10.14, OS=Windows 10.0.17134
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
Frequency=3515619 Hz, Resolution=284.4449 ns, Timer=TSC
.NET Core SDK=2.1.300
[Host] : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT
DefaultJob : .NET Core 2.1.0 (CoreCLR 4.6.26515.07, CoreFX 4.6.26515.06), 64bit RyuJIT
Для этого в.NET 4 есть новое встроенное решение - IStructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
Если вы не против этого, вы можете импортировать сборку 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;
}
.NET 3.5 и новее имеют новый открытый тип, System.Data.Linq.Binary что заключает в капсулу byte[], Это реализует IEquatable<Binary> это (в действительности) сравнивает два байтовых массива. Обратите внимание, что System.Data.Linq.Binary также имеет оператор неявного преобразования из byte[],
Документация MSDN: System.Data.Linq.Binary
Отражатель декомпилируется методом 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 петля:-)).
Вышеприведенная реализация означает, что в худшем случае вам, возможно, придется обходить массивы три раза: сначала для вычисления хеш-массива array1, затем для вычисления хеш-массива array2 и, наконец, (поскольку это худший сценарий, длины и хеш-значения равны) для сравнения байты в массиве 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
Давайте добавим еще один!
Недавно Microsoft выпустила специальный пакет NuGet, https://www.nuget.org/packages/System.Runtime.CompilerServices.Unsafe. Он особенный, потому что он написан на IL, и предоставляет низкоуровневую функциональность, прямо недоступную в C#.
Один из его методов, Unsafe.As<T>(object) позволяет приводить любой ссылочный тип к другому ссылочному типу, пропуская любые проверки безопасности. Обычно это очень плохая идея, но если оба типа имеют одинаковую структуру, это может сработать. Таким образом, мы можем использовать это, чтобы бросить byte[] к 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 |
Я также создал суть со всеми тестами.
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");
}
Я разработал метод, который немного бьет memcmp() (ответ плинтуса) и чуть-чуть бьет EqualBytesLongUnrolled() (Ответ Арека Бульски). По сути, он развертывает цикл на 4 вместо 8.
public static unsafe bool NewMemCmp(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;
}
public static unsafe bool NewMemCmp(byte[] arr0, byte[] arr1, int length)
{
fixed (byte* b0 = arr0, b1 = arr1)
{
return b0 == b1 || NewMemCmp(b0, b1, length);
}
}
Это работает примерно на 25% быстрее, чем memcmp() и примерно на 5% быстрее, чем EqualBytesLongUnrolled() на моей машине.
Я бы использовал небезопасный код и запустить for цикл, сравнивающий указатели Int32.
Может быть, вам следует также рассмотреть проверку массивов, чтобы быть ненулевым.
Если вы посмотрите, как.NET выполняет string.Equals, вы увидите, что он использует закрытый метод EqualsHelper, который имеет "небезопасную" реализацию указателя. .NET Reflector - ваш друг, чтобы увидеть, как все происходит внутри.
Это можно использовать в качестве шаблона для сравнения байтовых массивов, о котором я рассказывал в блоге. Быстрое сравнение байтовых массивов в C#. Я также сделал несколько элементарных тестов, чтобы увидеть, когда безопасная реализация быстрее небезопасной.
Тем не менее, если вам действительно не нужна убийственная производительность, я бы пошел на простое сравнение цикла fr.
Для тех из вас, кто заботится о порядке (т.е. хочет, чтобы memcmp вернуть intкак и должно, а не ничего), .NET Core 3.0 (и, предположительно,.NET Standard 2.1, также известный как.NET 5.0) будет включатьSpan.SequenceCompareTo(...)метод расширения (плюсSpan.SequenceEqualTo), который можно использовать для сравнения двух ReadOnlySpan<T> экземпляры (where T: IComparable<T>).
В исходном предложении GitHub обсуждение включало сравнение подходов с расчетами таблиц переходов, чтениеbyte[] как long[], Использование SIMD и p/invoke в реализации CLR memcmp.
В дальнейшем это должен быть ваш метод сравнения байтовых массивов или байтовых диапазонов (как и при использовании Span<byte> вместо того byte[] для ваших API.NET Standard 2.1), и он достаточно быстр, чтобы вам больше не нужно было заботиться о его оптимизации (и нет, несмотря на сходство в названии, он не работает так ужасно, как ужасный Enumerable.SequenceEqual).
#if NETCOREAPP3_0
// 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
Я провел некоторые измерения, используя прилагаемую программу.net 4.7 Release build без отладчика. Я думаю, что люди использовали неправильную метрику, поскольку то, о чем вы говорите, если вы заботитесь о скорости, - это сколько времени нужно, чтобы выяснить, равны ли два байтовых массива. т.е. пропускная способность в байтах.
StructuralComparison : 2838.8 MiB/s
for : 30553811.0 MiB/s
ToUInt32 : 23864406.8 MiB/s
ToUInt64 : 5526595.7 MiB/s
memcmp : 1848977556.1 MiB/s
Как видите, нет лучшего способа, чем memcmp и это на порядки быстрее. Просто for цикл является вторым лучшим вариантом. И это все еще поражает, почему Microsoft не может просто включить Buffer.Compare метод.
[Program.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();
var offset = Measure("offset", new TimeSpan(), () => { return; }, ignore: true);
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);
});
}
}
}
Не смог найти решения, которым я полностью доволен (разумная производительность, но небезопасный код / пин-код), поэтому я придумал, ничего оригинального, но работает:
/// <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
* BitConverter: 4886 тиков, 4.06
UnsafeCompare: 1636 тиков, 12.12
EqualBytesLongUnrolled: 637 тиков, 31.09
P / Invoke memcmp: 369 тиков, 53,67
Протестировано в linqpad, 1000000 байтов идентичных массивов (в худшем случае), 500 итераций каждый.
Кажется, что 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 |
Я не видел много решений 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();
}
Для сравнения коротких байтовых массивов интересным является следующее:
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[] с самого начала, например, если вы последовательно читаете их из двоичного файла, или если вы используете отображенный в память файл, считывайте данные как длинные [] или одиночные длинные значения. Тогда вашему циклу сравнения потребуется только 1/8 от количества итераций, которые он должен выполнить для байта [], содержащего тот же объем данных. Речь идет о том, когда и как часто вам нужно сравнивать и когда и как часто вам нужно обращаться к данным побайтовым образом, например, чтобы использовать их в вызове API в качестве параметра в методе, который ожидает байт []. В конце концов, вы можете только сказать, действительно ли вы знаете вариант использования...
Это похоже на другие, но разница здесь в том, что нет перехода к следующему наибольшему количеству байтов, которое я могу проверить сразу, например, если у меня 63 байта (в моем примере SIMD), я могу проверить равенство первого 32 байта, а затем последние 32 байта, что быстрее, чем проверка 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;
}
}
Я остановился на решении, вдохновленном методом EqualBytesLongUnrolled, опубликованным АрекБульски, с дополнительной оптимизацией. В моем случае различия массивов в массивах, как правило, находятся рядом с хвостом массивов. В ходе тестирования я обнаружил, что в случае больших массивов возможность сравнивать элементы массива в обратном порядке дает этому решению огромный выигрыш в производительности по сравнению с решением на основе 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;
}
Это почти наверняка намного медленнее, чем любая другая версия, приведенная здесь, но писать было весело.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
Извините, если вы ищете управляемый способ, вы уже делаете это правильно, и, насколько мне известно, в BCL нет встроенного метода для этого.
Вы должны добавить несколько начальных нулевых проверок, а затем просто повторно использовать их, как если бы они были в BCL.
Краткий ответ таков:
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: Компаратор сравнения байтовых массивов. В нем представлены некоторые из самых быстрых реализаций для сравнения равенства массива byte[], которые представлены, протестированы и обобщены на производительность.
Вы также можете сосредоточиться на этих реализациях:
BigEndianByteArrayComparer - быстрое сравнение массива byte[] слева направо (BigEndian) BigEndianByteArrayEqualityComparer - быстрое сравнение байтов [] слева направо (BigEndian) LittleEndianByteArrayComparer - быстрое сравнение байтов [] массива LittleBareE LittleEareErBareE [] равенство равенства справа налево (LittleEndian)
Вид грубой силы, но легко преобразовать байтовый массив в строку Base64 и сравнить две строки. Удобно, если у вас есть большие массивы для сравнения. Или, если один из байтовых массивов уже в формате Base64.
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
string s1 = Convert.ToBase64String(a1);
string s2 = Convert.ToBase64String(a2);
if(s1 == s2) return true;
return false
}
Я полагаю, что самый быстрый способ (с лучшей производительностью для больших массивов) - это хэшировать оба байтовых массива и сравнивать хэши.
Если у вас есть огромный массив байтов, вы можете сравнить их, преобразовав их в строку.
Вы можете использовать что-то вроде
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
Я использовал это, и я видел огромное влияние на производительность.