Si est谩 familiarizado con C #, lo m谩s probable es que sepa que siempre debe anular
Equals , as铆 como
GetHashCode , para evitar la
GetHashCode rendimiento. Pero, 驴qu茅 pasar谩 si esto no se hace? Hoy, comparamos el rendimiento con dos opciones de ajuste y consideramos herramientas para ayudar a evitar errores.
驴Qu茅 tan serio es este problema?
No todos los posibles problemas de rendimiento afectan el tiempo de ejecuci贸n de la aplicaci贸n. El m茅todo
Enum.HasFlag no
Enum.HasFlag muy eficiente (*), pero si no lo utiliza en un c贸digo de uso intensivo de recursos, no habr谩 problemas serios en el proyecto. Este tambi茅n es el caso de
las copias protegidas creadas por tipos de estructura no solo de lectura en el contexto de solo lectura. El problema existe, pero es poco probable que se note en aplicaciones ordinarias.
(*) Se corrigi贸 en .NET Core 2.1 y, como mencion茅 en una publicaci贸n anterior , ahora las consecuencias pueden mitigarse utilizando el HasFlag autoconfigurado para versiones anteriores.Pero el problema del que hablaremos hoy es especial. Si los m茅todos
Equals y
GetHashCode no se crean en la estructura,
System.ValueType sus versiones est谩ndar de
System.ValueType . Y pueden reducir significativamente el rendimiento de la aplicaci贸n final.
驴Por qu茅 las versiones est谩ndar son lentas?
Los autores de CLR hicieron todo lo posible para que las versiones est谩ndar de Equals y GetHashCode fueran lo m谩s eficientes posible para los tipos de valor. Pero hay varias razones por las cuales estos m茅todos pierden en la efectividad de la versi贸n del usuario, escrita para cierto tipo manualmente (o generada por el compilador).
1. Distribuci贸n de la conversi贸n de envases. El CLR est谩 dise帽ado de tal manera que cada llamada a un elemento definido en los tipos
System.ValueType o
System.Enum desencadena una transformaci贸n de
System.ValueType (**).
(**) Si el m茅todo no admite la compilaci贸n JIT. Por ejemplo, en Core CLR 2.1, el compilador JIT reconoce el m茅todo Enum.HasFlag y genera un c贸digo adecuado que no comienza a ajustarse.2. Posibles conflictos en la versi贸n est谩ndar del m茅todo
GetHashCode . Cuando implementamos una funci贸n hash, nos enfrentamos a un dilema: hacer que la distribuci贸n de la funci贸n hash sea buena o r谩pida. En algunos casos, puede hacer ambas cosas, pero en el tipo
ValueType.GetHashCode , esto suele ser dif铆cil.
Una funci贸n hash tradicional de tipo struct "combina" los c贸digos hash de todos los campos. Pero la 煤nica forma de obtener el c贸digo hash de campo en el m茅todo
ValueType es usar la reflexi贸n. Es por eso que los autores de CLR decidieron sacrificar la velocidad por el bien de la distribuci贸n, y la versi贸n est谩ndar de
GetHashCode solo devuelve el c贸digo hash del primer campo distinto de cero y lo
"estropea" con un identificador de tipo (***) (para m谩s detalles, consulte
RegularGetValueTypeHashCode en coreclr repo en github).
(***) A juzgar por los comentarios en el repositorio de CoreCLR, la situaci贸n puede cambiar en el futuro. 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();
Este es un algoritmo razonable hasta que algo sale mal. Pero si no tiene suerte y el valor del primer campo de su tipo de estructura es el mismo en la mayor铆a de los casos, entonces la funci贸n hash siempre producir谩 el mismo resultado. Como habr谩s adivinado, si guardas estas instancias en un conjunto de hash o una tabla de hash, entonces el rendimiento caer谩 en picado.
3. La velocidad de implementaci贸n basada en la reflexi贸n es baja. Muy bajo La reflexi贸n es una herramienta poderosa si se usa correctamente. Pero las consecuencias ser谩n terribles si lo ejecuta en un c贸digo de uso intensivo de recursos.
Veamos c贸mo una funci贸n hash fallida, que puede resultar de (2) y la implementaci贸n basada en la reflexi贸n, afecta el rendimiento:
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 el valor del primer campo es siempre el mismo, de manera predeterminada la funci贸n hash devuelve un valor igual para todos los elementos y el conjunto hash se convierte efectivamente en una lista vinculada con operaciones de inserci贸n y b煤squeda O (N). El n煤mero de operaciones para llenar la colecci贸n se convierte en O (N ^ 2) (donde N es el n煤mero de insertos con complejidad O (N) para cada inserto). Esto significa que insertar en un conjunto de 1000 elementos producir谩 casi 500,000 llamadas a
ValueType.Equals . 隆Aqu铆 est谩n las consecuencias de un m茅todo que usa la reflexi贸n!
Como muestra la prueba, el rendimiento ser谩 aceptable si tiene suerte y el primer elemento de la estructura es 煤nico (en el caso de
Position_Path_DefaultEquality ). Pero si esto no es as铆, entonces la productividad ser谩 extremadamente baja.
Problema real
Creo que ahora puedes adivinar qu茅 problema encontr茅 recientemente. Hace un par de semanas recib铆 un mensaje de error: el tiempo de ejecuci贸n de la aplicaci贸n en la que estoy trabajando aument贸 de 10 a 60 segundos. Afortunadamente, el informe fue muy detallado y conten铆a un rastro de eventos de Windows, por lo que el punto del problema se descubri贸 r谩pidamente:
ValueType.Equals carg贸 50 segundos.
Despu茅s de un r谩pido vistazo al c贸digo, qued贸 claro cu谩l era el problema:
private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation {
Us茅 una tupla que conten铆a un tipo de estructura personalizada con la versi贸n est谩ndar de
Equals . Y desafortunadamente, ten铆a un primer campo opcional, que casi siempre equival铆a a
String.equals . La productividad se mantuvo alta hasta que el n煤mero de elementos en el conjunto aument贸 significativamente. En cuesti贸n de minutos, se inicializ贸 una colecci贸n con decenas de miles de elementos.
驴La ValueType.Equals/GetHashCode predeterminada de ValueType.Equals/GetHashCode siempre se ejecuta lentamente?
Tanto
ValueType.Equals como
ValueType.GetHashCode tienen m茅todos de optimizaci贸n especiales. Si el tipo no tiene "punteros" y est谩 correctamente empaquetado (mostrar茅 un ejemplo en un minuto), entonces se usan versiones optimizadas: las iteraciones
GetHashCode se realizan en bloques de instancias, se usa XOR de 4 bytes, el m茅todo
Equals compara dos instancias usando
memcmp .
La comprobaci贸n en s铆 se realiza en
ValueTypeHelper::CanCompareBits , se llama tanto por la iteraci贸n de
ValueType.Equals como por la iteraci贸n de
ValueType.GetHashCode .
Pero la optimizaci贸n es una cosa muy insidiosa.
En primer lugar, es dif铆cil de entender cuando est谩 encendido; Incluso peque帽os cambios en el c贸digo pueden activarlo y desactivarlo:
public struct Case1 {
Para obtener m谩s informaci贸n sobre la estructura de la memoria, consulte mi blog,
"Elementos internos de un objeto administrado, Parte 4. Estructura del campo" .
En segundo lugar, comparar la memoria no necesariamente te da el resultado correcto. Aqu铆 hay un ejemplo simple:
public struct MyDouble { public double Value { get; } public MyDouble(double value) => Value = value; } double d1 = -0.0; double d2 = +0.0;
-0,0 y
+0,0 son iguales, pero tienen diferentes representaciones binarias. Esto significa que
Double.Equals es verdadero y
MyDouble.Equals es falso. En la mayor铆a de los casos, la diferencia no es significativa, pero imagine cu谩ntas horas pasar谩 solucionando el problema causado por esta diferencia.
驴C贸mo evitar un problema similar?
驴Puedes preguntarme c贸mo puede suceder lo anterior en una situaci贸n real? Una forma obvia de ejecutar los m茅todos
Equals y
GetHashCode en los tipos de estructura es usar la
regla FxCop
CA1815 . Pero hay un problema: este es un enfoque demasiado estricto.
Una aplicaci贸n para la que el rendimiento es cr铆tico puede tener cientos de tipos de estructura que no se usan necesariamente en conjuntos hash o diccionarios. Por lo tanto, los desarrolladores de aplicaciones pueden deshabilitar la regla, lo que causar谩 consecuencias desagradables si el tipo de estructura utiliza funciones modificadas.
Un enfoque m谩s correcto es advertir al desarrollador si la estructura de tipo "inapropiada" con los mismos valores predeterminados de elementos (definidos en la aplicaci贸n o una biblioteca de terceros) se almacena en un conjunto hash. Por supuesto, estoy hablando de
ErrorProne.NET y la regla que agregu茅 all铆 tan pronto como me encontr茅 con este problema:
La versi贸n ErrorProne.NET no es perfecta y "culpar谩" al c贸digo correcto si se utiliza un solucionador de igualdad personalizado en el constructor:
Pero sigo pensando que vale la pena advertir si una estructura con elementos iguales por defecto no se usa cuando se est谩 produciendo. Por ejemplo, cuando revis茅 mi regla, me di cuenta de que la estructura
System.Collections.Generic.KeyValuePair <TKey, TValue> definida en mscorlib no sobrescribe
Equals y
GetHashCode . Es poco probable que alguien defina una variable como
HashSet <KeyValuePair<string, int>> hoy, pero creo que incluso BCL puede romper la regla. Por lo tanto, es 煤til descubrir esto antes de que sea demasiado tarde.
Conclusi贸n
- La implementaci贸n de la igualdad predeterminada para los tipos de estructura puede tener serias consecuencias para su aplicaci贸n. Este es un problema real, no te贸rico.
- Los elementos de igualdad predeterminados para los tipos de valor se basan en la reflexi贸n.
- La distribuci贸n realizada por la versi贸n est谩ndar de
GetHashCode ser谩 muy mala si el primer campo de muchas instancias tiene el mismo valor. - Existen versiones optimizadas para los m茅todos est谩ndar
Equals y GetHashCode , pero no debe confiar en ellos porque incluso un peque帽o cambio de c贸digo puede desactivarlos. - Use la regla FxCop para asegurarse de que cada tipo de estructura anula los elementos de igualdad. Sin embargo, es mejor evitar el problema con el analizador si la estructura "inapropiada" se almacena en un conjunto hash o en una tabla hash.
Recursos Adicionales