c# - ¿Por qué los HashSets de estructuras con valores anulables son increíblemente lentos?

.net performance

Question

Investigué la degradación del rendimiento y lo rastreé para ralentizar HashSets.
Tengo estructuras con valores anulables que se utilizan como clave principal. Por ejemplo:

public struct NullableLongWrapper
{
    private readonly long? _value;

    public NullableLongWrapper(long? value)
    {
        _value = value;
    }
}

Noté que crear un HashSet<NullableLongWrapper> es excepcionalmente lento.

Aquí hay un ejemplo usando BenchmarkDotNet : ( Install-Package BenchmarkDotNet )

using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

public class Program
{
    static void Main()
    {
        BenchmarkRunner.Run<HashSets>();
    }
}

public class Config : ManualConfig
{
    public Config()
    {
        Add(Job.Dry.WithWarmupCount(1).WithLaunchCount(3).WithTargetCount(20));
    }
}

public struct NullableLongWrapper
{
    private readonly long? _value;

    public NullableLongWrapper(long? value)
    {
        _value = value;
    }

    public long? Value => _value;
}

public struct LongWrapper
{
    private readonly long _value;

    public LongWrapper(long value)
    {
        _value = value;
    }

    public long Value => _value;
}

[Config(typeof (Config))]
public class HashSets
{
    private const int ListSize = 1000;

    private readonly List<long?> _nullables;
    private readonly List<long> _longs;
    private readonly List<NullableLongWrapper> _nullableWrappers;
    private readonly List<LongWrapper> _wrappers;

    public HashSets()
    {
        _nullables = Enumerable.Range(1, ListSize).Select(i => (long?) i).ToList();
        _longs = Enumerable.Range(1, ListSize).Select(i => (long) i).ToList();
        _nullableWrappers = Enumerable.Range(1, ListSize).Select(i => new NullableLongWrapper(i)).ToList();
        _wrappers = Enumerable.Range(1, ListSize).Select(i => new LongWrapper(i)).ToList();
    }

    [Benchmark]
    public void Longs() => new HashSet<long>(_longs);

    [Benchmark]
    public void NullableLongs() => new HashSet<long?>(_nullables);

    [Benchmark(Baseline = true)]
    public void Wrappers() => new HashSet<LongWrapper>(_wrappers);

    [Benchmark]
    public void NullableWrappers() => new HashSet<NullableLongWrapper>(_nullableWrappers);
}

Resultado:

Method | Median | Scaled ----------------- |---------------- |--------- Longs | 22.8682 us | 0.42 NullableLongs | 39.0337 us | 0.62 Wrappers | 62.8877 us | 1.00 NullableWrappers | 231,993.7278 us | 3,540.34

¡Usar una estructura con un Nullable<long> comparación con una estructura con un long es 3540 veces más lento!
En mi caso, marcó la diferencia entre 800ms y <1ms.

Aquí está la información del entorno de BenchmarkDotNet:

SO = Microsoft Windows NT 6.1.7601 Service Pack 1
Procesador = Intel (R) Core (TM) i7-5600U CPU 2.60GHz, ProcessorCount = 4
Frecuencia = 2536269 ticks, Resolución = 394.2799 ns, Temporizador = TSC
CLR = MS.NET 4.0.30319.42000, Arch = LIBERACIÓN de 64 bits [RyuJIT]
GC = Estación de trabajo concurrente
JitModules = clrjit-v4.6.1076.0

¿Cuál es la razón por la cual el rendimiento es tan pobre?

Answer 1

Esto se debe al comportamiento de estructura GetHashCode (). Si encuentra tipos de referencia, intenta obtener hash del primer campo de tipo sin referencia. En su caso, se encontró, y Nullable <> también es struct, por lo que simplemente expuso su valor booleano privado (4 bytes)

Answer 2

Esto sucede porque cada uno de los elementos de _nullableWrappers tiene el mismo código hash devuelto por GetHashCode() , lo que hace que el hash se degenere en acceso O (N) en lugar de O (1).

Puede verificar esto imprimiendo todos los códigos hash.

Si modifica su estructura así:

public struct NullableLongWrapper
{
    private readonly long? _value;

    public NullableLongWrapper(long? value)
    {
        _value = value;
    }

    public override int GetHashCode()
    {
        return _value.GetHashCode();
    }

    public long? Value => _value;
}

Funciona mucho más rápido.

Ahora, la pregunta obvia es POR QUÉ el código hash de cada NullableLongWrapper el mismo.

La respuesta a eso se discute en este hilo . Sin embargo, no responde a la pregunta, ya que la respuesta de Hans gira en torno a la estructura que tiene DOS campos para elegir al calcular el código hash, pero en este código, solo hay un campo para elegir, y es un tipo de valor (una struct ).

Sin embargo, la moraleja de esta historia es: ¡ Nunca confíe en el GetHashCode() predeterminado para los tipos de valor!

Apéndice

Pensé que tal vez lo que estaba sucediendo estaba relacionado con la respuesta de Hans en el hilo que vinculé, tal vez estaba tomando el valor del primer campo (el bool) en la Nullable<T> ), y mis experimentos indican que puede ser relacionado, pero es complicado:

Considere este código y su salida:

using System;

public class Program
{
    static void Main()
    {
        var a = new Test {A = 0, B = 0};
        var b = new Test {A = 1, B = 0};
        var c = new Test {A = 0, B = 1};
        var d = new Test {A = 0, B = 2};
        var e = new Test {A = 0, B = 3};

        Console.WriteLine(a.GetHashCode());
        Console.WriteLine(b.GetHashCode());
        Console.WriteLine(c.GetHashCode());
        Console.WriteLine(d.GetHashCode());
        Console.WriteLine(e.GetHashCode());
    }
}

public struct Test
{
    public int A;
    public int B;
}

Output:

346948956
346948957
346948957
346948958
346948959

Observe cómo los códigos hash segundo y tercero (para 1/0 y 0/1) son iguales, pero los otros son diferentes. Encuentro esto extraño porque cambiar claramente A cambia el código hash, al igual que cambiar B, pero dados dos valores X e Y, se genera el mismo código hash para A = X, B = Y y A = Y, B = X.

(Eso parece que algunas cosas XOR están sucediendo detrás de escena, pero eso es una suposición).

Por cierto, este comportamiento en el que AMBOS campos pueden mostrar que contribuyen al código hash prueba que el comentario en la fuente de referencia de ValueType.GetHashType() es incorrecto o incorrecto:

Acción: nuestro algoritmo para devolver el código hash es un poco complejo. Buscamos el primer campo no estático y obtenemos su código hash. Si el tipo no tiene campos no estáticos, devolvemos el código hash del tipo. No podemos tomar el código hash de un miembro estático porque si ese miembro es del mismo tipo que el tipo original, terminaremos en un bucle infinito.

Si ese comentario fuera verdadero, entonces cuatro de los cinco códigos hash en el ejemplo anterior serían los mismos, ya que A tiene el mismo valor, 0, para todos esos. (Eso supone que A es el primer campo, pero obtendrá los mismos resultados si cambia los valores: ambos campos contribuyen claramente al código hash).

Luego intenté cambiar el primer campo para ser un bool:

using System;

public class Program
{
    static void Main()
    {
        var a = new Test {A = false, B = 0};
        var b = new Test {A = true,  B = 0};
        var c = new Test {A = false, B = 1};
        var d = new Test {A = false, B = 2};
        var e = new Test {A = false, B = 3};

        Console.WriteLine(a.GetHashCode());
        Console.WriteLine(b.GetHashCode());
        Console.WriteLine(c.GetHashCode());
        Console.WriteLine(d.GetHashCode());
        Console.WriteLine(e.GetHashCode());
    }
}

public struct Test
{
    public bool A;
    public int  B;
}

Output

346948956
346948956
346948956
346948956
346948956

¡Guauu! Entonces, hacer que el primer campo sea bool hace que todos los códigos hash salgan iguales, ¡independientemente de los valores de CUALQUIERA de los campos!

Esto todavía me parece una especie de error.

El error se ha solucionado en .NET 4, pero solo para Nullable. Los tipos personalizados aún producen el mal comportamiento. source