Comparaison de deux tableaux d'octets dans .NET
https://stackoverflow.com/questions/43289
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment puis-je faire ça rapidement ?
Bien sûr, je peux faire ceci :
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;
}
Mais je recherche soit un BCL fonction ou une manière éprouvée hautement optimisée de le faire.
java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);
fonctionne bien, mais il ne semble pas que cela fonctionnerait pour x64.
Notez ma réponse ultra-rapide ici.
La solution 4
Utilisateur Gil code dangereux suggéré qui a engendré cette solution :
// 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;
}
}
qui effectue une comparaison basée sur 64 bits pour la plus grande partie possible du tableau.Ce type de compte repose sur le fait que les tableaux commencent par être alignés sur qword.Cela fonctionnera s'il n'est pas aligné sur qword, mais pas aussi vite que si c'était le cas.
Il exécute environ sept minuteries plus rapidement que le simple for boucle.Utilisation de la bibliothèque J# effectuée de manière équivalente à l'original for boucle.L'utilisation de .SequenceEqual s'exécute environ sept fois plus lentement ;Je pense simplement parce qu'il utilise IEnumerator.MoveNext.J'imagine que les solutions basées sur LINQ sont au moins aussi lentes, voire pires.
Autres conseils
Vous pouvez utiliser Enumerable.SequenceEqual méthode.
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 vous ne pouvez pas utiliser .NET 3.5 pour une raison quelconque, votre méthode est correcte.
L'environnement du compilateur\d'exécution optimisera votre boucle afin que vous n'ayez pas à vous soucier des performances.
P/Invoquer les pouvoirs s'activent !
[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;
}
Il existe une nouvelle solution intégrée pour cela dans .NET 4 : IStructuralEquatable
static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
Si cela ne vous oppose pas, vous pouvez importer l'assembly J# "vjslib.dll" et utiliser son Méthode Arrays.equals(byte[], byte[])...
Ne me blâmez pas si quelqu'un se moque de vous...
MODIFIER:Pour le peu que cela vaut, j'ai utilisé Reflector pour démonter le code pour cela, et voici à quoi il ressemble :
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> offre une alternative extrêmement compétitive sans avoir à ajouter des éléments confus et/ou non portables dans la base de code de votre propre application :
// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
return a1.SequenceEqual(a2);
}
L'implémentation (des tripes de) à partir de .NET Core 2.2.3 peut être trouvée ici.
j'ai modifié L'essentiel de @EliArbel pour ajouter cette méthode comme SpansEqual, supprimez la plupart des performances les moins intéressantes dans les tests des autres, exécutez-le avec différentes tailles de tableau, graphiques de sortie et marquez SpansEqual comme référence afin qu'il indique comment les différentes méthodes se comparent à SpansEqual.
Les chiffres ci-dessous proviennent des résultats, légèrement modifiés pour supprimer la colonne « Erreur ».
| 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 |
J'ai été surpris de voir SpansEqual Je ne suis pas en tête pour les méthodes max-array-size, mais la différence est si mineure que je ne pense pas que cela aura jamais d'importance.
Informations sur mon système :
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 et versions ultérieures ont un nouveau type public, System.Data.Linq.Binary qui encapsule byte[].Il met en œuvre IEquatable<Binary> qui (en fait) compare deux tableaux d'octets.Noter que System.Data.Linq.Binary a également un opérateur de conversion implicite de byte[].
Documentation MSDN :Système.Data.Linq.Binary
Décompilation Reflector de la méthode 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;
}
La particularité intéressante est qu'ils ne procèdent à une boucle de comparaison octet par octet que si les hachages des deux objets binaires sont identiques.Cependant, cela se fait au prix du calcul du hachage dans le constructeur de Binary objets (en parcourant le tableau avec for boucle :-) ).
L'implémentation ci-dessus signifie que dans le pire des cas, vous devrez peut-être parcourir les tableaux trois fois :d'abord pour calculer le hachage du tableau1, puis pour calculer le hachage du tableau2 et enfin (car c'est le pire des cas, longueurs et hachages égaux) pour comparer les octets du tableau1 avec les octets du tableau 2.
Dans l'ensemble, même si System.Data.Linq.Binary est intégré à BCL, je ne pense pas que ce soit le moyen le plus rapide de comparer deux tableaux d'octets :-|.
Je posté une question similaire sur la vérification si byte[] est plein de zéros.(Le code SIMD a été battu, je l'ai donc supprimé de cette réponse.) Voici le code le plus rapide de mes comparaisons :
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;
}
}
Mesuré sur deux tableaux d'octets de 256 Mo :
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");
}
Ajoutons-en un de plus !
Microsoft a récemment publié un package NuGet spécial, System.Runtime.CompilerServices.Unsafe.C'est spécial parce que c'est écrit IL, et fournit des fonctionnalités de bas niveau non directement disponibles en C#.
Une de ses méthodes, Unsafe.As<T>(object) permet de convertir n'importe quel type de référence en un autre type de référence, en ignorant tous les contrôles de sécurité.Il s'agit généralement d'un très mauvaise idée, mais si les deux types ont la même structure, cela peut fonctionner.Nous pouvons donc l'utiliser pour lancer un byte[] à 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;
}
Noter que long1.Length renverrait toujours la longueur du tableau d'origine, puisqu'elle est stockée dans un champ de la structure mémoire du tableau.
Cette méthode n'est pas aussi rapide que les autres méthodes démontrées ici, mais elle est beaucoup plus rapide que la méthode naïve, n'utilise pas de code dangereux, ni P/Invoke ni épinglage, et la mise en œuvre est assez simple (OMI).Voilà quelque RéférenceDotNet résultats de ma machine :
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 |
J'ai également créé un l'essentiel avec tous les tests.
J'ai développé une méthode qui bat légèrement memcmp() (réponse du socle) et bat très légèrement EqualBytesLongUnrolled() (Réponse d'Arek Bulski) sur mon PC.En gros, ça déroule la boucle par 4 au lieu de 8.
Mise à jour du 30 mars.2019:
À partir de .NET Core 3.0, nous prenons en charge SIMD !
Cette solution est de loin la plus rapide sur mon 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;
}
J'utiliserais du code dangereux et exécuterais le for boucle comparant les pointeurs Int32.
Peut-être devriez-vous également envisager de vérifier que les tableaux ne sont pas nuls.
Si vous regardez comment .NET fait string.Equals, vous voyez qu'il utilise une méthode privée appelée EqualsHelper qui a une implémentation de pointeur "dangereuse". Réflecteur .NET est votre ami pour voir comment les choses se font en interne.
Cela peut être utilisé comme modèle pour la comparaison de tableaux d'octets sur laquelle j'ai fait une implémentation dans un article de blog. Comparaison rapide de tableaux d'octets en C#.J'ai également effectué quelques benchmarks rudimentaires pour voir quand une implémentation sûre est plus rapide qu'une implémentation non sécurisée.
Cela dit, à moins que vous n'ayez vraiment besoin de performances exceptionnelles, j'opterais pour une simple comparaison de boucles fr.
Je n'ai pas trouvé de solution qui me satisfasse entièrement (performances raisonnables, mais pas de code/pinvoke dangereux), j'ai donc trouvé ceci, rien de vraiment original, mais qui fonctionne :
/// <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;
}
Performances comparées à certaines des autres solutions de cette page :
Boucle simple :19837 ticks, 1,00
*BitConvertisseur :4886 ticks, 4,06
DangereuxComparer :1636 ticks, 12.12
EqualBytesLongUnrolled :637 ticks, 31.09
P/Invoquer memcmp :369 ticks, 53,67
Testé dans Linqpad, tableaux identiques de 1 000 000 octets (dans le pire des cas), 500 itérations chacun.
Il paraît que EqualBytesLongUnrolled est le meilleur parmi ceux suggérés ci-dessus.
Les méthodes ignorées (Enumerable.SequenceEqual, StructuralComparisons.StructuralEqualityComparer.Equals) n'étaient pas patientes pour la lenteur.Sur des baies de 265 Mo, j'ai mesuré ceci :
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 |
Je n'ai pas vu beaucoup de solutions Linq ici.
Je ne suis pas sûr des implications en termes de performances, mais je m'en tiens généralement à linq en règle générale, puis optimisez plus tard si nécessaire.
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
return !array1.Where((t, i) => t != array2[i]).Any();
}
Veuillez noter que cela ne fonctionne que s'il s'agit de tableaux de même taille.une extension pourrait ressembler à ceci
public bool CompareTwoArrays(byte[] array1, byte[] array2)
{
if (array1.Length != array2.Length) return false;
return !array1.Where((t, i) => t != array2[i]).Any();
}
J'ai effectué quelques mesures en utilisant le programme ci-joint version .net 4.7 sans le débogueur connecté.Je pense que les gens ont utilisé la mauvaise métrique, car si vous vous souciez de la vitesse, c'est combien de temps il faut pour déterminer si des tableaux de deux octets sont égaux.c'est à dire.débit en octets.
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
Comme vous pouvez le constater, il n'y a pas de meilleur moyen que memcmp et c'est des ordres de grandeur plus rapides.Un simple for la boucle est la deuxième meilleure option.Et je me demande encore pourquoi Microsoft ne peut pas simplement inclure un Buffer.Compare méthode.
[Programme.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);
});
}
}
}
Pour comparer des tableaux d'octets courts, ce qui suit est un hack intéressant :
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);
Ensuite, je tomberais probablement sur la solution répertoriée dans la question.
Il serait intéressant de faire une analyse des performances de ce code.
J'ai pensé aux méthodes d'accélération de transfert de blocs intégrées à de nombreuses cartes graphiques.Mais vous devrez alors copier toutes les données par octet, donc cela ne vous aide pas beaucoup si vous ne souhaitez pas implémenter toute une partie de votre logique dans du code non géré et dépendant du matériel...
Une autre méthode d'optimisation similaire à l'approche présentée ci-dessus serait de stocker autant de données que possible dans un long[] plutôt que dans un byte[] dès le début, par exemple si vous les lisez séquentiellement à partir d'un fichier binaire, ou si vous utilisez un fichier mappé en mémoire, lisez les données sous forme de valeurs longues[] ou de valeurs longues uniques.Ensuite, votre boucle de comparaison n'aura besoin que de 1/8ème du nombre d'itérations qu'elle devrait effectuer pour un octet[] contenant la même quantité de données.Il s’agit de savoir quand et à quelle fréquence vous devez comparer vs.quand et à quelle fréquence vous devez accéder aux données octet par octet, par ex.pour l'utiliser dans un appel API comme paramètre dans une méthode qui attend un octet[].En fin de compte, vous ne pouvez savoir si vous connaissez vraiment le cas d'utilisation...
C'est presque certainement beaucoup plus lent que toute autre version proposée ici, mais c'était amusant à écrire.
static bool ByteArrayEquals(byte[] a1, byte[] a2)
{
return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
J'ai opté pour une solution inspirée de la méthode EqualBytesLongUnrolled publiée par ArekBulski avec une optimisation supplémentaire.Dans mon cas, les différences entre les tableaux ont tendance à se situer près de la queue des tableaux.Lors des tests, j'ai constaté que lorsque c'est le cas pour de grands tableaux, la possibilité de comparer les éléments du tableau dans l'ordre inverse confère à cette solution un énorme gain de performances par rapport à la solution basée sur memcmp.Voici cette solution :
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;
}
Désolé, si vous recherchez une méthode gérée, vous le faites déjà correctement et, à ma connaissance, il n'existe pas de méthode intégrée dans la BCL pour ce faire.
Vous devez ajouter quelques vérifications nulles initiales, puis simplement les réutiliser comme s'ils se trouvaient dans BCL.
Utiliser SequenceEquals pour cela à comparaison.
La réponse courte est la suivante :
public bool Compare(byte[] b1, byte[] b2)
{
return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
}
De cette manière, vous pouvez utiliser la comparaison de chaînes .NET optimisée pour comparer un tableau d'octets sans avoir besoin d'écrire du code dangereux.C'est ainsi que cela se fait dans le arrière-plan:
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);
}
}
Étant donné que la plupart des solutions sophistiquées ci-dessus ne fonctionnent pas avec UWP et que j'aime Linq et les approches fonctionnelles, je vous présente ma version de ce problème.Pour échapper à la comparaison lorsque la première différence se produit, j'ai choisi .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 vous recherchez un comparateur d'égalité de tableau d'octets très rapide, je vous suggère de jeter un œil à cet article de STSdb Labs : Comparateur d'égalité de tableau d'octets. Il présente certaines des implémentations les plus rapides pour la comparaison de l'égalité des tableaux d'octets[], qui sont présentées, testées et résumées.
Vous pouvez également vous concentrer sur ces implémentations :
BigEndianByteArrayComparer - comparateur rapide de tableaux d'octets[] de gauche à droite (BigEndian)BigEndianByteArrayEqualityComparer - - comparateur d'égalité fast byte[] de gauche à droite (BigEndian)LittleEndianByteArrayComparer - comparateur de tableau fast byte[] de droite à gauche (LittleEndian)LittleEndianByteArrayEqualityComparer - comparateur d'égalité fast byte[] de droite à gauche (LittleEndian)
Si vous disposez d'un énorme tableau d'octets, vous pouvez les comparer en les convertissant en chaîne.
Vous pouvez utiliser quelque chose comme
byte[] b1 = // Your array
byte[] b2 = // Your array
string s1 = Encoding.Default.GetString( b1 );
string s2 = Encoding.Default.GetString( b2 );
Je l'ai utilisé et j'ai constaté un énorme impact sur les performances.
