Pourquoi les HashSets de structures avec des valeurs nullables sont-ils incroyablement lents?

Question

J'ai étudié la dégradation des performances et le suivi qu'il est vers le bas pour ralentir HashSets.
J'ai structs avec nullable valeurs qui sont utilisés comme clé primaire. Par exemple:

public struct NullableLongWrapper
{
    private readonly long? _value;

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

J'ai remarqué que la création d'un HashSet<NullableLongWrapper> est extrêmement lente.

Voici un exemple d'utilisation 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);
}

Résultat:

 Méthode | Médian | Mises
----------------- |---------------- |---------
 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

À l'aide d'une structure avec un Nullable<long> par rapport à une structure avec un long est 3540 fois plus lent!
Dans mon cas, il fait la différence entre la 800ms et <1ms.

Voici les informations sur l'environnement de BenchmarkDotNet:

OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processeur=Intel(R) Core(TM) i7-5600U CPU 2.60 GHz, ProcessorCount=4
Fréquence=2536269 tiques, Résolution=394.2799 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64 bits VERSION [RyuJIT]
GC=Concurrent poste de travail
JitModules=clrjit-v4.6.1076.0

Quelle est la raison de la performance est-ce mauvais?

Answer 1

Ce qui se passe, parce que tous les éléments de l' _nullableWrappers a le même code de hachage est retourné en GetHashCode(), ce qui se traduit dans le hachage de dégénérer en O(N) l'accès plutôt que de O(1).

Vous pouvez le vérifier en imprimant tous les codes de hachage.

Si vous modifiez votre structure de la manière suivante:

public struct NullableLongWrapper
{
    private readonly long? _value;

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

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

    public long? Value => _value;
}

il fonctionne beaucoup plus rapidement.

Maintenant, la question évidente est POURQUOI le code de hachage de chaque NullableLongWrapper le même.

La réponse à cette question est discutée dans ce fil. Toutefois, il n'est pas tout à fait répondre à la question, depuis Hans réponse tourne autour de la struct avoir DEUX champs à partir de laquelle choisir lors du calcul de la valeur de hachage de code, mais dans ce code, il n'y a qu'un seul champ à choix - et c'est un type de la valeur ( struct).

Cependant, la morale de cette histoire: ne Jamais compter sur la valeur par défaut GetHashCode() pour les types de valeur!

---

Addendum

J'ai pensé que peut-être ce qui se passait était liée à Hans de réponse dans le fil, j'ai fait un lien - c'était peut-être en prenant la valeur du premier champ (bool) en Nullable<T> struct), et de mes expériences indiquent qu'il peut être lié, mais c'est compliqué:

Considérer ce code et de sa sortie:

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

Notez comment les deuxième et troisième des codes de hachage (pour 1/0 et 0/1) sont les mêmes, mais les autres sont tous différents. Je trouve cela étrange parce que clairement, la modification d'Un des changements le code de hachage, comme le fait de passer du B, mais compte tenu de deux valeurs de X et Y, le même code de hachage est généré pour A=X, B=Y et A=O, B=X.

(Qui ressemble à un XOR des choses qui se passe derrière les coulisses, mais c'est deviner.)

D'ailleurs, ce comportement où les DEUX champs peuvent être affichés à contribuer au code de hachage prouve que le commentaire dans le source de référence pour l' ValueType.GetHashType() sont inexacts ou faux:

Action: Notre algorithme pour le retour du hashcode est un peu complexe. Nous recherchons pour le premier non-champ statique et se hashcode. Si le type n'a pas de non-champs statiques, nous retourner le hashcode de la type. Nous ne pouvons pas prendre le hashcode d'un membre statique parce que si ce membre est du même type que le type d'origine, nous allons nous retrouver dans une boucle infinie.

Si ce commentaire est vrai, quatre des cinq codes de hachage dans l'exemple ci-dessus serait le même, depuis A a la même valeur, 0, pour tous ceux. (Qui suppose A est le premier champ, mais vous obtenez les mêmes résultats si vous permutez les valeurs autour de: les Deux champs contribuent clairement à la le code de hachage.)

Ensuite, j'ai essayé de changer le premier champ à 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

Wow! Afin de faire le premier champ d'un bool rend tous les codes de hachage viennent de la même manière, quelles que soient les valeurs des champs!

Cela ressemble encore à une sorte de bug pour moi.

Le bogue a été corrigé dans .NET 4, mais seulement pour les valeurs null. Types personnalisés rendement encore le mauvais comportement. source

Answer 2

Cela est dû au comportement de struct GetHashCode (). S'il trouve des types de référence, il tente d'obtenir le hachage du premier champ de type non référencé. Dans votre cas, il a été trouvé et Nullable <> est également une structure, de sorte qu'il vient d'afficher sa valeur booléenne privée (4 octets).