Si vous connaissez C #, vous savez très probablement que vous devez toujours remplacer
Equals , ainsi que
GetHashCode , pour éviter une
GetHashCode performances. Mais que se passera-t-il si cela n'est pas fait? Aujourd'hui, nous comparons les performances avec deux options de réglage et envisageons des outils pour éviter les erreurs.
Quelle est la gravité de ce problème?
Tous les problèmes de performances potentiels n'affectent pas l'exécution des applications. La méthode
Enum.HasFlag pas très efficace (*), mais si vous ne l'utilisez pas sur un morceau de code gourmand en ressources, il n'y aura pas de problèmes graves dans le projet. C'est également le cas avec
les copies protégées créées par des types de structure non en lecture seule dans le contexte en lecture seule. Le problème existe, mais il est peu probable qu'il soit perceptible dans les applications ordinaires.
(*) Corrigé dans .NET Core 2.1, et, comme je l'ai mentionné dans une publication précédente , maintenant les conséquences peuvent être atténuées en utilisant le HasFlag auto-configuré pour les anciennes versions.Mais le problème dont nous allons parler aujourd'hui est particulier. Si les méthodes
Equals et
GetHashCode ne sont pas créées dans la structure, leurs versions standard de
System.ValueType . Et ils peuvent réduire considérablement les performances de l'application finale.
Pourquoi les versions standard sont-elles lentes?
Les auteurs du CLR ont fait de leur mieux pour rendre les versions standard d'Equals et GetHashCode aussi efficaces que possible pour les types de valeur. Mais il y a plusieurs raisons pour lesquelles ces méthodes perdent en efficacité de la version utilisateur, écrite pour un certain type manuellement (ou générée par le compilateur).
1. Distribution de la conversion des emballages. Le CLR est conçu de telle manière que chaque appel à un élément défini dans les types
System.ValueType ou
System.Enum déclenche une transformation d'habillage (**).
(**) Si la méthode ne prend pas en charge la compilation JIT. Par exemple, dans Core CLR 2.1, le compilateur JIT reconnaît la méthode Enum.HasFlag et génère un code approprié qui ne démarre pas le wrapping.2. Conflits potentiels dans la version standard de la méthode
GetHashCode . Lors de la mise en œuvre d'une fonction de hachage, nous sommes confrontés à un dilemme: rendre la distribution de la fonction de hachage bonne ou rapide. Dans certains cas, vous pouvez faire les deux, mais dans le type
ValueType.GetHashCode , cela est généralement difficile.
Une fonction de hachage traditionnelle de type struct "combine" les codes de hachage de tous les champs. Mais la seule façon d'obtenir le code de hachage de champ dans la méthode
ValueType est d'utiliser la réflexion. C'est pourquoi les auteurs du CLR ont décidé de sacrifier la vitesse à des fins de distribution, et la version standard de
GetHashCode ne renvoie que le code de hachage du premier champ non nul et le
«gâte» avec un identifiant de type (***) (pour plus de détails, voir
RegularGetValueTypeHashCode dans le repo de coreclr sur github).
(***) À en juger par les commentaires dans le référentiel CoreCLR, la situation pourrait changer à l'avenir. public readonly struct Location { public string Path { get; } public int Position { get; } public Location(string path, int position) => (Path, Position) = (path, position); } var hash1 = new Location(path: "", position: 42).GetHashCode(); var hash2 = new Location(path: "", position: 1).GetHashCode(); var hash3 = new Location(path: "1", position: 42).GetHashCode();
Il s'agit d'un algorithme raisonnable jusqu'à ce que quelque chose se passe mal. Mais si vous n'avez pas de chance et que la valeur du premier champ de votre type de structure est la même dans la plupart des cas, la fonction de hachage produira toujours le même résultat. Comme vous l'avez peut-être deviné, si vous enregistrez ces instances dans un ensemble de hachage ou une table de hachage, les performances chuteront.
3. La vitesse de mise en œuvre basée sur la réflexion est faible. Très faible. La réflexion est un outil puissant s'il est utilisé correctement. Mais les conséquences seront terribles si vous l'exécutez sur un morceau de code gourmand en ressources.
Voyons comment une fonction de hachage défaillante, qui peut résulter de (2) et d'une implémentation basée sur la réflexion, affecte les performances:
public readonly struct Location1 { public string Path { get; } public int Position { get; } public Location1(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location2 {
Method | NumOfElements | Mean | Gen 0 | Allocated | -------------------------------- |------ |--------------:|--------:|----------:| Path_Position_DefaultEquality | 1 | 885.63 ns | 0.0286 | 92 B | Position_Path_DefaultEquality | 1 | 127.80 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1 | 47.99 ns | - | 0 B | Path_Position_DefaultEquality | 10 | 6,214.02 ns | 0.2441 | 776 B | Position_Path_DefaultEquality | 10 | 130.04 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 10 | 47.67 ns | - | 0 B | Path_Position_DefaultEquality | 1000 | 589,014.52 ns | 23.4375 | 76025 B | Position_Path_DefaultEquality | 1000 | 133.74 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1000 | 48.51 ns | - | 0 B |
Si la valeur du premier champ est toujours la même, la fonction de hachage renvoie par défaut une valeur égale pour tous les éléments et l'ensemble de hachage est effectivement converti en une liste liée avec des opérations d'insertion et de recherche O (N). Le nombre d'opérations pour remplir la collection devient O (N ^ 2) (où N est le nombre d'inserts de complexité O (N) pour chaque insert). Cela signifie que l'insertion dans un ensemble de 1 000 éléments générera près de 500 000 appels à
ValueType.Equals . Voici les conséquences d'une méthode utilisant la réflexion!
Comme le montre le test, les performances seront acceptables si vous êtes chanceux et que le premier élément de la structure est unique (dans le cas de
Position_Path_DefaultEquality ). Mais si ce n'est pas le cas, la productivité sera extrêmement faible.
Vrai problème
Je pense que vous pouvez maintenant deviner quel problème j'ai rencontré récemment. Il y a quelques semaines, j'ai reçu un message d'erreur: le temps d'exécution de l'application sur laquelle je travaille est passé de 10 à 60 secondes. Heureusement, le rapport était très détaillé et contenait une trace des événements Windows, donc le problème a été découvert rapidement -
ValueType.Equals chargé 50 secondes.
Après un rapide coup d'œil au code, il est devenu clair quel était le problème:
private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation {
J'ai utilisé un tuple qui contenait un type de structure personnalisé avec la version standard d'
Equals . Et malheureusement, il avait un premier champ facultatif, qui égalait presque toujours
String.equals . La productivité est restée élevée jusqu'à ce que le nombre d'éléments de l'ensemble augmente de manière significative. En quelques minutes, une collection de dizaines de milliers d'éléments a été initialisée.
L'implémentation ValueType.Equals/GetHashCode par défaut s'exécute-t-elle toujours lentement?
ValueType.Equals et
ValueType.GetHashCode ont des méthodes d'optimisation spéciales. Si le type n'a pas de «pointeurs» et qu'il est correctement compressé (je vais montrer un exemple dans une minute), alors des versions optimisées sont utilisées: les itérations
GetHashCode sont effectuées sur des blocs d'instance, XOR de 4 octets est utilisé, la méthode
Equals compare deux instances à l'aide de
memcmp .
La vérification elle-même est effectuée dans
ValueTypeHelper::CanCompareBits , elle est appelée à la fois à partir de l'itération de
ValueType.Equals et à partir de l'itération de
ValueType.GetHashCode .
Mais l'optimisation est une chose très insidieuse.
Premièrement, il est difficile de comprendre quand il est allumé; même des modifications mineures du code peuvent l'activer et le désactiver:
public struct Case1 {
Pour plus d'informations sur la structure de la mémoire, consultez mon blog,
«Éléments internes d'un objet géré, partie 4. Structure de champ» .
Deuxièmement, comparer la mémoire ne vous donne pas nécessairement le bon résultat. Voici un exemple simple:
public struct MyDouble { public double Value { get; } public MyDouble(double value) => Value = value; } double d1 = -0.0; double d2 = +0.0;
+0,0 et
+0,0 sont égaux, mais ont des représentations binaires différentes. Cela signifie que
Double.Equals est vrai et
MyDouble.Equals est faux. Dans la plupart des cas, la différence n'est pas significative, mais imaginez combien d'heures vous passerez à résoudre le problème causé par cette différence.
Comment éviter un problème similaire?
Pouvez-vous me demander comment cela peut se produire dans une situation réelle? Une façon évidente d'exécuter les méthodes
Equals et
GetHashCode dans les types de structure consiste à utiliser la
règle FxCop
CA1815 . Mais il y a un problème: c'est une approche trop stricte.
Une application pour laquelle les performances sont critiques peut avoir des centaines de types de structures qui ne sont pas nécessairement utilisés dans les ensembles de hachage ou les dictionnaires. Par conséquent, les développeurs d'applications peuvent désactiver la règle, ce qui entraînera des conséquences désagréables si le type de structure utilise des fonctions modifiées.
Une approche plus correcte consiste à avertir le développeur si la structure de type «inapproprié» avec des valeurs par défaut égales d'éléments (définies dans l'application ou une bibliothèque tierce) est stockée dans un ensemble de hachage. Bien sûr, je parle d'
ErrorProne.NET et de la règle que j'ai ajoutée là-bas dès que j'ai rencontré ce problème:
La version ErrorProne.NET n'est pas parfaite et «blâmera» le code correct si un résolveur d'égalité personnalisé est utilisé dans le constructeur:
Mais je pense toujours qu'il vaut la peine d'être averti si une structure avec des éléments égaux par défaut n'est pas utilisée lors de sa production. Par exemple, lorsque j'ai vérifié ma règle, j'ai réalisé que la structure
System.Collections.Generic.KeyValuePair <TKey, TValue> définie dans mscorlib ne remplace pas
Equals et
GetHashCode . Il est peu probable que quiconque définisse une variable comme
HashSet <KeyValuePair<string, int>> aujourd'hui, mais je pense que même BCL peut enfreindre la règle. Par conséquent, il est utile de le découvrir avant qu'il ne soit trop tard.
Conclusion
- L'implémentation de l'égalité par défaut pour les types de structure peut avoir de graves conséquences pour votre application. Il s'agit d'un problème réel et non théorique.
- Les éléments d'égalité par défaut pour les types de valeur sont basés sur la réflexion.
- La distribution effectuée par la version standard de
GetHashCode sera très mauvaise si le premier champ de nombreuses instances a la même valeur. - Il existe des versions optimisées pour les méthodes standard
Equals et GetHashCode , mais vous ne devez pas vous fier à elles, car même une petite modification de code peut les désactiver. - Utilisez la règle FxCop pour vous assurer que chaque type de structure remplace les éléments d'égalité. Cependant, il est préférable d'éviter le problème avec l'analyseur si la structure «inappropriée» est stockée dans un ensemble de hachage ou dans une table de hachage.
Ressources supplémentaires