Wenn Sie mit C # vertraut sind, wissen Sie höchstwahrscheinlich, dass Sie
Equals und
GetHashCode immer überschreiben
GetHashCode , um Leistungseinbußen zu vermeiden. Aber was passiert, wenn dies nicht getan wird? Heute vergleichen wir die Leistung mit zwei Optimierungsoptionen und betrachten Tools, um Fehler zu vermeiden.
Wie ernst ist dieses Problem?
Nicht jedes potenzielle Leistungsproblem wirkt sich auf die Laufzeit der Anwendung aus. Die
Enum.HasFlag Methode
Enum.HasFlag nicht sehr effizient (*). Wenn Sie sie jedoch nicht für einen ressourcenintensiven Code verwenden, treten im Projekt keine ernsthaften Probleme auf. Dies ist auch bei
geschützten Kopien der Fall, die von nicht schreibgeschützten Strukturtypen im schreibgeschützten Kontext erstellt wurden. Das Problem besteht, ist jedoch bei normalen Anwendungen wahrscheinlich nicht erkennbar.
(*) In .NET Core 2.1 behoben. Wie bereits in einer früheren Veröffentlichung erwähnt , können die Konsequenzen jetzt mithilfe des selbstkonfigurierten HasFlag für ältere Versionen gemindert werden.Aber das Problem, über das wir heute sprechen werden, ist etwas Besonderes. Wenn die Methoden
Equals und
GetHashCode nicht in der Struktur erstellt werden, werden ihre Standardversionen von
System.ValueType . Und sie können die Leistung der endgültigen Anwendung erheblich reduzieren.
Warum sind Standardversionen langsam?
Die CLR-Autoren haben ihr Bestes getan, um die Standardversionen von Equals und GetHashCode für Werttypen so effizient wie möglich zu gestalten. Es gibt jedoch mehrere Gründe, warum diese Methoden an Effektivität der Benutzerversion verlieren, die für einen bestimmten Typ manuell geschrieben (oder vom Compiler generiert) wurde.
1. Verteilung der Verpackungsumwandlung. Die CLR ist so konzipiert, dass jeder Aufruf eines Elements, das in den Typen
System.ValueType oder
System.Enum definiert ist, eine Wrapping-Transformation (**) auslöst.
(**) Wenn die Methode die JIT-Kompilierung nicht unterstützt. In Core CLR 2.1 erkennt der JIT-Compiler beispielsweise die Enum.HasFlag Methode und generiert geeigneten Code, der nicht mit dem Enum.HasFlag beginnt.2. Mögliche Konflikte in der Standardversion der
GetHashCode Methode. Bei der Implementierung einer Hash-Funktion stehen wir vor einem Dilemma: Die Verteilung der Hash-Funktion muss gut oder schnell sein. In einigen Fällen können Sie beides tun, aber beim Typ
ValueType.GetHashCode ist dies normalerweise schwierig.
Eine traditionelle Hash-Funktion vom Typ struct "kombiniert" die Hash-Codes aller Felder. Die einzige Möglichkeit, den Feld-Hash-Code in der
ValueType Methode
ValueType , ist die Verwendung von Reflection. Aus diesem Grund haben die CLR-Autoren beschlossen, die Geschwindigkeit für die Verteilung zu opfern. Die Standardversion von
GetHashCode nur den Hash-Code des ersten Felds ungleich Null zurück und
„verdirbt“ ihn mit einer RegularGetValueTypeHashCode (***) (weitere Informationen finden Sie unter
RegularGetValueTypeHashCode in coreclr repo auf github).
(***) Gemessen an den Kommentaren im CoreCLR-Repository kann sich die Situation in Zukunft ändern. 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();
Dies ist ein vernünftiger Algorithmus, bis etwas schief geht. Wenn Sie jedoch kein Glück haben und der Wert des ersten Felds Ihres Strukturtyps in den meisten Fällen gleich ist, führt die Hash-Funktion immer zum gleichen Ergebnis. Wie Sie vielleicht vermutet haben, sinkt die Leistung, wenn Sie diese Instanzen in einem Hash-Set oder einer Hash-Tabelle speichern.
3. Die auf Reflexion basierende Implementierungsgeschwindigkeit ist gering. Sehr niedrig. Reflexion ist ein mächtiges Werkzeug, wenn es richtig eingesetzt wird. Die Konsequenzen sind jedoch schrecklich, wenn Sie es auf einem ressourcenintensiven Code ausführen.
Mal sehen, wie sich eine fehlgeschlagene Hash-Funktion, die sich aus (2) und einer reflexionsbasierten Implementierung ergeben kann, auf die Leistung auswirkt:
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 |
Wenn der Wert des ersten Felds immer gleich ist, gibt die Hash-Funktion standardmäßig einen gleichen Wert für alle Elemente zurück und die Hash-Menge wird effektiv in eine verknüpfte Liste mit O (N) Einfüge- und Suchoperationen konvertiert. Die Anzahl der Operationen zum Füllen der Sammlung wird zu O (N ^ 2) (wobei N die Anzahl der Einfügungen mit der Komplexität O (N) für jede Einfügung ist). Dies bedeutet, dass das Einfügen in einen Satz von 1000 Elementen fast 500.000 Aufrufe von
ValueType.Equals . Hier sind die Konsequenzen einer Methode mit Reflexion!
Wie der Test zeigt, ist die Leistung akzeptabel, wenn Sie Glück haben und das erste Element der Struktur eindeutig ist (im Fall von
Position_Path_DefaultEquality ). Ist dies jedoch nicht der Fall, ist die Produktivität äußerst gering.
Echtes Problem
Ich denke, jetzt können Sie erraten, auf welches Problem ich kürzlich gestoßen bin. Vor einigen Wochen erhielt ich eine Fehlermeldung: Die Laufzeit der Anwendung, an der ich arbeite, wurde von 10 auf 60 Sekunden erhöht. Glücklicherweise war der Bericht sehr detailliert und enthielt eine Spur von Windows-Ereignissen, sodass der Problempunkt schnell
ValueType.Equals -
ValueType.Equals 50 Sekunden
ValueType.Equals geladen.
Nach einem kurzen Blick auf den Code wurde klar, wo das Problem lag:
private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation {
Ich habe ein Tupel verwendet, das einen benutzerdefinierten Strukturtyp mit der Standardversion von
Equals enthielt. Und leider hatte es ein optionales erstes Feld, das fast immer gleich
String.equals . Die Produktivität blieb hoch, bis die Anzahl der Elemente im Satz signifikant anstieg. Innerhalb weniger Minuten wurde eine Sammlung mit Zehntausenden von Elementen initialisiert.
ValueType.Equals/GetHashCode die Standardimplementierung von ValueType.Equals/GetHashCode immer langsam?
Sowohl
ValueType.Equals als auch
ValueType.GetHashCode verfügen über spezielle Optimierungsmethoden. Wenn der Typ keine „Zeiger“ hat und korrekt gepackt ist (ich werde in einer Minute ein Beispiel zeigen), werden optimierte Versionen verwendet:
GetHashCode Iterationen werden für
GetHashCode ausgeführt, XOR von 4 Bytes wird verwendet, die
Equals Methode vergleicht zwei Instanzen mit
memcmp .
Die Prüfung selbst wird in
ValueTypeHelper::CanCompareBits . Sie wird sowohl aus der Iteration von
ValueType.Equals als auch aus der Iteration von
ValueType.GetHashCode .
Aber Optimierung ist eine sehr heimtückische Sache.
Erstens ist es schwer zu verstehen, wann es eingeschaltet ist; Selbst geringfügige Änderungen am Code können ihn ein- und ausschalten:
public struct Case1 {
Weitere Informationen zur Speicherstruktur finden Sie in meinem Blog
„Interne Elemente eines verwalteten Objekts, Teil 4. Feldstruktur“ .
Zweitens führt ein Vergleich des Speichers nicht unbedingt zum richtigen Ergebnis. Hier ist ein einfaches Beispiel:
public struct MyDouble { public double Value { get; } public MyDouble(double value) => Value = value; } double d1 = -0.0; double d2 = +0.0;
-0,0 und
+0,0 sind gleich, haben aber unterschiedliche binäre Darstellungen. Dies bedeutet, dass
Double.Equals wahr und
MyDouble.Equals falsch ist. In den meisten Fällen ist der Unterschied nicht signifikant, aber stellen Sie sich vor, wie viele Stunden Sie damit verbringen werden, das durch diesen Unterschied verursachte Problem zu beheben.
Wie vermeide ich ein ähnliches Problem?
Können Sie mich fragen, wie das oben genannte in einer realen Situation passieren kann? Eine naheliegende Möglichkeit, die Methoden
Equals und
GetHashCode in Strukturtypen
GetHashCode , ist die Verwendung der FxCop
CA1815-Regel . Es gibt jedoch ein Problem: Dies ist ein zu strenger Ansatz.
Eine Anwendung, für die die Leistung entscheidend ist, kann Hunderte von Strukturtypen haben, die nicht unbedingt in Hash-Sets oder Wörterbüchern verwendet werden. Daher können Anwendungsentwickler die Regel deaktivieren, was unangenehme Folgen hat, wenn der Strukturtyp geänderte Funktionen verwendet.
Ein korrekterer Ansatz besteht darin, den Entwickler zu warnen, wenn die Struktur vom Typ "unangemessen" mit gleichen Standardwerten von Elementen (in der Anwendung oder in einer Bibliothek eines Drittanbieters definiert) in einem Hash-Set gespeichert ist. Natürlich spreche ich über
ErrorProne.NET und die Regel, die ich dort hinzugefügt habe, sobald ich auf dieses Problem
gestoßen bin:
Die ErrorProne.NET-Version ist nicht perfekt und gibt dem korrekten Code die Schuld, wenn im Konstruktor ein benutzerdefinierter Gleichheitsauflöser verwendet wird:
Ich denke jedoch immer noch, dass es eine Warnung wert ist, wenn eine Struktur mit gleichen Elementen standardmäßig nicht verwendet wird, wenn sie erstellt wird. Als ich beispielsweise meine Regel überprüfte, stellte ich fest, dass die in mscorlib definierte
System.Collections.Generic.KeyValuePair <TKey, TValue> -Struktur
Equals und
GetHashCode nicht überschreibt. Es ist unwahrscheinlich, dass heute jemand eine Variable wie
HashSet <KeyValuePair<string, int>> , aber ich glaube, dass sogar BCL die Regel brechen kann. Daher ist es nützlich, dies zu entdecken, bevor es zu spät ist.
Fazit
- Das Implementieren der Standardgleichheit für Strukturtypen kann schwerwiegende Folgen für Ihre Anwendung haben. Dies ist ein reales, kein theoretisches Problem.
- Die Standardgleichheitselemente für Werttypen basieren auf Reflexion.
- Die von der Standardversion von
GetHashCode durchgeführte Verteilung ist sehr schlecht, wenn das erste Feld vieler Instanzen denselben Wert hat. - Es gibt optimierte Versionen für die Standardmethoden
Equals und GetHashCode , aber Sie sollten sich nicht auf sie verlassen, da sie bereits durch eine kleine Codeänderung GetHashCode werden können. - Verwenden Sie die FxCop-Regel, um sicherzustellen, dass jeder Strukturtyp Gleichheitselemente überschreibt. Es ist jedoch besser, das Problem mit dem Analysator zu vermeiden, wenn die „unangemessene“ Struktur in einem Hash-Set oder in einer Hash-Tabelle gespeichert ist.
Zusätzliche Ressourcen