Comparando dos matrices de bytes en .NET
https://stackoverflow.com/questions/43289
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo puedo hacer esto rápido?
Claro que puedo hacer esto:
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;
}
Pero estoy buscando un BCL función o alguna forma probada altamente optimizada de hacer esto.
java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);
funciona bien, pero no parece que funcione para x64.
Tenga en cuenta mi respuesta súper rápida aquí.
Solución 4
Usuario gil código inseguro sugerido que generó esta solución:
// 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;
}
}
que realiza una comparación basada en 64 bits para la mayor cantidad posible de la matriz.Este tipo de cuenta con el hecho de que las matrices comienzan con qword alineada.Funcionará si no está alineado con qword, pero no tan rápido como si lo estuviera.
Funciona alrededor de siete temporizadores más rápido que el simple for bucle.El uso de la biblioteca J# se realizó de manera equivalente al original for bucle.El uso de .SequenceEqual se ejecuta aproximadamente siete veces más lento;Creo que solo porque usa IEnumerator.MoveNext.Me imagino que las soluciones basadas en LINQ serán al menos así de lentas o peores.
Otros consejos
Puedes usar Enumerable.SequenceEqual método.
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
Si no puede utilizar .NET 3.5 por algún motivo, su método está bien.
El entorno de tiempo de ejecución del compilador optimizará su bucle para que no tenga que preocuparse por el rendimiento.
P/Invocar ¡Se activan los poderes!
[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;
}
Hay una nueva solución integrada para esto en .NET 4: IEstructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
Si no se opone a hacerlo, puede importar el ensamblado J# "vjslib.dll" y utilizar su Método Arrays.equals (byte [], byte [])...
No me culpes si alguien se ríe de ti...
EDITAR:Por lo poco que vale, utilicé Reflector para desmontar el código y así es como se ve:
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> ofrece una alternativa extremadamente competitiva sin tener que agregar tonterías confusas y/o no portátiles al código base de su propia aplicación:
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
return a1.SequenceEqual(a2);
}
Se pueden encontrar las (tripas) implementación a partir de .NET Core 2.2.3 aquí.
He revisado La esencia de @EliArbel para agregar este método como SpansEqual, elimine la mayoría de los artistas menos interesantes en los puntos de referencia de otros, ejecútelo con diferentes tamaños de matriz, gráficos de salida y marque SpansEqual como línea de base para que informe cómo se comparan los diferentes métodos con SpansEqual.
Los números siguientes provienen de los resultados, ligeramente editados para eliminar la columna "Error".
| 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 |
Me sorprendió ver SpansEqual No estoy a la cabeza de los métodos de tamaño máximo de matriz, pero la diferencia es tan pequeña que no creo que importe nunca.
Información de mi sistema:
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 y versiones posteriores tienen un nuevo tipo público, System.Data.Linq.Binary que encapsula byte[].implementa IEquatable<Binary> que (en efecto) compara dos matrices de bytes.Tenga en cuenta que System.Data.Linq.Binary también tiene un operador de conversión implícito de byte[].
Documentación de MSDN:Sistema.Datos.Linq.Binario
Descompilación del reflector del método 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;
}
Un giro interesante es que solo proceden al ciclo de comparación byte por byte si los hashes de los dos objetos binarios son los mismos.Esto, sin embargo, tiene el costo de calcular el hash en el constructor de Binary objetos (atravesando la matriz con for bucle :-) ).
La implementación anterior significa que, en el peor de los casos, es posible que tengas que atravesar las matrices tres veces:primero para calcular el hash de la matriz1, luego para calcular el hash de la matriz2 y finalmente (porque este es el peor de los casos, las longitudes y los hashes son iguales) para comparar los bytes de la matriz1 con los bytes de la matriz 2.
En general, aunque System.Data.Linq.Binary está integrado en BCL, no creo que sea la forma más rápida de comparar dos matrices de bytes :-|.
publiqué una pregunta similar sobre comprobar si el byte [] está lleno de ceros.(El código SIMD fue superado, así que lo eliminé de esta respuesta). Aquí está el código más rápido de mis comparaciones:
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;
}
}
Medido en dos matrices de bytes de 256 MB:
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");
}
¡Agreguemos uno más!
Recientemente, Microsoft lanzó un paquete especial de NuGet, System.Runtime.CompilerServices.Unsafe.Es especial porque está escrito en ILLINOIS, y proporciona funcionalidad de bajo nivel que no está disponible directamente en C#.
Uno de sus métodos, Unsafe.As<T>(object) permite convertir cualquier tipo de referencia a otro tipo de referencia, omitiendo cualquier control de seguridad.Esto suele ser un muy Mala idea, pero si ambos tipos tienen la misma estructura, puede funcionar.Entonces podemos usar esto para lanzar un byte[] a un 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;
}
Tenga en cuenta que long1.Length aún devolvería la longitud de la matriz original, ya que está almacenada en un campo en la estructura de memoria de la matriz.
Este método no es tan rápido como otros métodos demostrados aquí, pero es mucho más rápido que el método ingenuo, no utiliza código inseguro ni P/Invoke ni fijación, y la implementación es bastante sencilla (en mi opinión).Aquí están algunas Punto de referenciaDotNet resultados de mi máquina:
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 |
También he creado un esencia con todas las pruebas.
Desarrollé un método que supera ligeramente memcmp() (respuesta del pedestal) y late muy ligeramente EqualBytesLongUnrolled() (La respuesta de Arek Bulski) en mi PC.Básicamente, desenrolla el bucle en 4 en lugar de 8.
Actualización 30 de marzo.2019:
¡A partir de .NET core 3.0, tenemos soporte SIMD!
Esta solución es la más rápida por un margen considerable en mi PC:
#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;
}
Usaría código inseguro y ejecutaría el for bucle que compara punteros Int32.
Quizás también debería considerar verificar que las matrices no sean nulas.
Si observa cómo .NET hace string.Equals, verá que utiliza un método privado llamado EqualsHelper que tiene una implementación de puntero "insegura". Reflector .NET Es tu amigo para ver cómo se hacen las cosas internamente.
Esto se puede utilizar como plantilla para la comparación de matrices de bytes, cuya implementación realicé en la publicación del blog. Comparación rápida de matrices de bytes en C#.También hice algunos puntos de referencia rudimentarios para ver cuándo una implementación segura es más rápida que una insegura.
Dicho esto, a menos que realmente necesites un rendimiento excelente, optaría por una simple comparación del bucle fr.
No pude encontrar una solución con la que esté completamente satisfecho (rendimiento razonable, pero sin código/pinvoke inseguro), así que se me ocurrió esto, nada realmente original, pero funciona:
/// <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;
}
Rendimiento comparado con algunas de las otras soluciones en esta página:
Bucle simple:19837 tics, 1,00
*Convertidor de bits:4886 tics, 4,06
InseguroComparar:1636 tics, 12,12
EqualBytesLongUnrolled:637 tics, 31,09
P/Invocar memcmp:369 tics, 53,67
Probado en linqpad, matrices idénticas de 1000000 bytes (en el peor de los casos), 500 iteraciones cada una.
Parece que EqualBytesLongDesenrollado es lo mejor de lo sugerido anteriormente.
Los métodos omitidos (Enumerable.SequenceEqual,StructuralComparisons.StructuralEqualityComparer.Equals) no eran lentos.En matrices de 265 MB he medido esto:
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 |
No he visto muchas soluciones linq aquí.
No estoy seguro de las implicaciones en el rendimiento, sin embargo, generalmente me quedo con linq como regla general y luego optimizar más tarde si es necesario.
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
return !array1.Where((t, i) => t != array2[i]).Any();
}
Tenga en cuenta que esto solo funciona si son matrices del mismo tamaño.una extensión podría verse así
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
if (array1.Length != array2.Length) return false;
return !array1.Where((t, i) => t != array2[i]).Any();
}
Hice algunas mediciones usando el programa adjunto .net 4.7 versión versión sin el depurador adjunto.Creo que la gente ha estado usando la métrica incorrecta ya que lo que te importa aquí, si te importa la velocidad, es cuánto tiempo lleva determinar si dos matrices de bytes son iguales.es decir.rendimiento en bytes.
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
Como puedes ver, no hay mejor manera que memcmp y es órdenes de magnitud más rápido.Un simple for loop es la segunda mejor opción.Y todavía me desconcierta por qué Microsoft no puede simplemente incluir un Buffer.Compare método.
[Programa.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);
});
}
}
}
Para comparar matrices de bytes cortos, el siguiente es un truco interesante:
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);
Entonces probablemente elegiría la solución enumerada en la pregunta.
Sería interesante hacer un análisis de rendimiento de este código.
Pensé en los métodos de aceleración de transferencia en bloques integrados en muchas tarjetas gráficas.Pero luego tendría que copiar todos los datos byte a bit, por lo que esto no le ayudará mucho si no desea implementar una parte completa de su lógica en código no administrado y dependiente del hardware...
Otra forma de optimización similar al enfoque mostrado arriba sería almacenar la mayor cantidad posible de datos en un long[] en lugar de un byte[] desde el principio, por ejemplo, si los está leyendo secuencialmente desde un archivo binario, o si utiliza un archivo asignado en memoria, lea los datos como valores largos[] o valores largos únicos.Entonces, su ciclo de comparación solo necesitará 1/8 del número de iteraciones que tendría que hacer para un byte[] que contenga la misma cantidad de datos.Es una cuestión de cuándo y con qué frecuencia es necesario comparar vs.cuándo y con qué frecuencia necesita acceder a los datos byte a byte, p.usarlo en una llamada API como parámetro en un método que espera un byte [].Al final, sólo podrás saberlo si realmente conoces el caso de uso...
Es casi seguro que es mucho más lento que cualquier otra versión proporcionada aquí, pero fue divertido escribirla.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
Me decidí por una solución inspirada en el método EqualBytesLongUnrolled publicado por ArekBulski con una optimización adicional.En mi caso, las diferencias entre matrices tienden a estar cerca de la cola de las matrices.En las pruebas, descubrí que cuando este es el caso de matrices grandes, poder comparar elementos de la matriz en orden inverso le da a esta solución una enorme ganancia de rendimiento con respecto a la solución basada en memcmp.Aquí está esa solución:
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;
}
Lo siento, si está buscando una forma administrada, ya lo está haciendo correctamente y, que yo sepa, no hay ningún método integrado en BCL para hacer esto.
Debe agregar algunas comprobaciones nulas iniciales y luego simplemente reutilizarlas como si estuvieran en BCL.
Usar SequenceEquals para esto a comparación.
La respuesta corta es esta:
public bool Compare(byte[] b1, byte[] b2)
{
return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
}
De esta manera, puede utilizar la comparación de cadenas .NET optimizada para comparar una matriz de bytes sin la necesidad de escribir código inseguro.Así se hace en el fondo:
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);
}
}
Dado que muchas de las sofisticadas soluciones anteriores no funcionan con UWP y porque me encanta Linq y los enfoques funcionales, les presento mi versión de este problema.Para escapar de la comparación cuando ocurre la primera diferencia, elegí .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);
Si está buscando un comparador de igualdad de matrices de bytes muy rápido, le sugiero que consulte este artículo de STSdb Labs: Comparador de igualdad de matriz de bytes. Presenta algunas de las implementaciones más rápidas para comparar la igualdad de matrices de bytes[], que se presentan, se prueban el rendimiento y se resumen.
También puede centrarse en estas implementaciones:
BigEndianByteArrayComparer - Comparador rápido de matrices de bytes [] de izquierda a derecha (BigEndian)BigEndianByteArrayEqualityComparer - - comparador de igualdad de byte rápido [] de izquierda a derecha (BigEndian)LittleEndianByteArrayComparer - Comparador rápido de matrices de bytes [] de derecha a izquierda (LittleEndian)LittleEndianByteArrayEqualityComparer - Comparador rápido de igualdad de bytes[] de derecha a izquierda (LittleEndian)
En caso de que tenga una matriz de bytes enorme, puede compararlos convirtiéndolos en cadenas.
Puedes usar algo como
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
He usado esto y he visto un gran impacto en el rendimiento.
