Discussion :

[neptune]

Bonjour à tous,

Dans le cadre de mon projet actuel, je suis amené à comparer deux byte[]. J'ai régulièrement vu cette question apparaitre dans les forums et je souhaitent faire partager mon expérience à la communauté.

En ce qui me concerne, je dois uniquement savoir si les deux objets sont différents du point de vue du contenu. Cette différence est soit:
- une taille différente
- au moins un byte différent à une position donnée.

L'algorithme est plutôt simple. Voici une première méthode qui remplit les conditions:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static bool AreEqual(byte[] left, byte[] right)
{
	if ((left == null) || (right == null))
	{
		return false;
	}
 
	if (left.Length != right.Length)
	{
		return false;
	}
 
	for (int i = 0; i < left.Length; i++)
	{
		if (left[i] != right[i])
		{
			return false;
		}
	}
 
	return true;
}

La première question qui vient à l'esprit en lisant ce code est la performance. Dans le cas qui m'occupe, je n'ai aucune idée préalable sur la taille des arrays. A priori, l'algorithme est bon, je sort de la bouche dès qu'une différence est rencontrée. Mais s'il faut comparer deux arrays identiques de 200 megabytes?

J'ai alors écrit la méthode suivante, en partant de l'idée que comparer un hash serait toujours plus rapide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static bool AreEqualWithHash(byte[] left, byte[] right)
{
	if ((left == null) || (right == null))
	{
		return false;
	}
 
	if (left.Length != right.Length)
	{
		return false;
	}
 
	// md5 is a static variable defined in the Program class only once to
	// avoid instanciation on each call
	// static MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider();
 
	byte[] hashLeft = md5.ComputeHash(left);
	byte[] hashright = md5.ComputeHash(right);
 
	return AreEqual(hashLeft, hashright);
}

Sur le papier, on devrait y gagner, non? Sauf dans le cas le plus défavorable où la différence se situe en début d'array. Mais en réalité, qu'en est-il? Je décide donc d'écrire un programme de test, je génère une array et je la compare à elle-même, pour la parcourir intégralement.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static void Main(string[] args)
{
	const int MEGA = 1024 * 1024;
	byte[] array = null;
	Stopwatch stopwatch = new Stopwatch();
 
	for (int i = MEGA; i < Int32.MaxValue; i += MEGA)
	{
		// First method
		array = FillByteArray(i);
		stopwatch.Reset();
		stopwatch.Start();
		AreEqual(array, array);
		stopwatch.Stop();
		TimeSpan ts1 = stopwatch.Elapsed;
 
		// Second method
		array = FillByteArray(i);
		stopwatch.Reset();
		stopwatch.Start();
		AreEqualWithHash(array, array);
		stopwatch.Stop();
		TimeSpan ts2 = stopwatch.Elapsed;
 
		Console.WriteLine("{0} megabytes: {1} - {2}", i / MEGA, ts1.TotalSeconds, ts2.TotalSeconds);
	}
 
	Console.WriteLine("END");
	Console.Read();
}

Je constate avec stupéfaction que la seconde méthode ne gagne jamais, le coût pour calculer le hash est systématiquement plus élevé. J'avoue, je n'ai jamais laissé l'application tourner jusqu'à la fin. Après réflexion, c'est assez logique, pour calculer le hash, il faut parcourir l'array en entier et faire des opérations arithmétiques.

Voila, j'espère que ce mini-article vous aura plus et vous aura convaincus.
Neptune

[Louis-Guillaume Morand]

je me rappelle avoir lu qu'il fallait boucler à l'envers pour eviter les multiplications des tests.
Ainsi

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
for (int i = 0; i < left.Length; i++)
	{
		if (left[i] != right[i])
		{
			return false;
		}
	}

devrait être remplacé par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
for (int i = left.Length-1; i <0; i--)
	{
		if (left[i] != right[i])
		{
			return false;
		}
	}

pour éviter que "left.Length" soit recalculé. sauf que voilà, chez moi, pas de différence sur un tableau de byte de 10000bytes (je sais que c'est petit).


pire encore. j'ai une amélioration de 10% en faisant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
int temp =  left.Length;
for (int i = 0; i < temp; i++)
	{
		if (left[i] != right[i])
		{
			return false;
		}
	}

et encore mieux
j'ai une augmentation d'encore 10% avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
int temp =  left.Length;
for (int i = 0; i < left.Length; i++)
	{
		if (left[i] != right[i])
		{
			return false;
		}
	}

, ce qui est une abbération car je rajoute une ligne qui ne sert à rien.
j'ai pourtant mes boucles qui tournent 20 fois et les resultats sont stables

[neptune]

Merci pour ta réaction. Je ne comprend pas pourquoi il faudrait boucler à l'envers. Les arrays sont finis, on ne peut ajouter ou retirer d'éléments donc .Length n'est pas censé être recalculé.

Et stocker hors boucle la longueur du tableau me semble aussi une abération pour la même raison (tableau finit). J'imagine que la structure byte[] stocke cette valeure en interne et ne recalcule pas à chaque fois la longueur.

Mais je vais essayer de regarder comment ca fonctionne en interne. Et si mes assertions précédentes sont inexactes, la crédibilité du framework va y perdre :-)

[Louis-Guillaume Morand]

p-e que ca ne marchait pas sur les arrays mais sur des collections. je ne sais plus trop, je ne retrouve plus le blog (et ca date d'un an et demi facile). mais je suis sûr que l'idée parlait de boucler à l'envers (et aussi parfois de remplir à l'envers puis pouvoir dépiler en ordre "normal")

j'ai aussi découvert grâce à une collègue un truc en framework 1.1 et qui n'existe pas en fx 2.0
cf piece jointe

[neptune]

Pour les collections et les listes, je suis entièrement d'accord avec toi. Et concernant l'image, désolé je ne vois pas le rapport avec le sujet :-)

[Louis-Guillaume Morand]

Pour les collections et les listes, je suis entièrement d'accord avec toi. Et concernant l'image, désolé je ne vois pas le rapport avec le sujet :-)

aucun rapport mais juste pour dire que le Fx est étonnant parfois même sur des choses toutes simples. d'ailleurs, dans l'image, il faut savoir que 29.6 +63.6 ca marche, 29.7+63.8, ca marche mais seul avec le 63.7, ca plante
pour l'histoire du length j'ai pas le code source du fx 3.0 donc je ne peux pas vérifier si quelqu'un peut le faire, ca serait cool
par contre, je sais que dans d'autres languages, les Length sont recalculés à chaque fois et on propose donc d'instancier une variable temporaire pour éviter ce problème (cf "late binding" sur google)


edit: billet retrouvé
http://www.dotnet-project.com/Astuce...le-for.56.aspx

reste que j'ai vraiment des résultats bizarres avec des optimisations qui n'en sont pas

[neptune]

Length est extern On ne pourra pas savoir ce qui se cache réellement derrière...

http://www.dotnet-project.com/Astuce...le-for.56.aspx

Je suis 100% d'accord avec le commentaire "Fausse bonne idée" ;-)