Pourquoi HashSet <Point> est-il tellement plus lent que HashSet <string>?

Je voulais stocker certains emplacements de pixels sans autoriser les doublons, donc la première chose qui me vient à l'esprit est HashSet<Point>ou des classes similaires. Cependant, cela semble être très lent par rapport à quelque chose comme HashSet<string>.

Par exemple, ce code:

HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(new Point(x, y));
        }
    }
}

prend environ 22,5 secondes.

Alors que le code suivant (qui n'est pas un bon choix pour des raisons évidentes) ne prend que 1,6 seconde:

HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(x + "," + y);
        }
    }
}

Donc, mes questions sont:

• Y at-il une raison à cela? J'ai vérifié cette réponse , mais 22,5 secondes est bien plus que les chiffres indiqués dans cette réponse.
• Existe-t-il une meilleure façon de stocker des points sans doublons?

Il y a deux problèmes de perf induits par la structure Point. Quelque chose que vous pouvez voir lorsque vous ajoutez Console.WriteLine(GC.CollectionCount(0));au code de test. Vous verrez que le test Point nécessite ~ 3720 collections, mais le test de chaîne n'a besoin que d'environ 18 collections. Pas gratuitement. Quand vous voyez un type de valeur induire autant de collections, vous devez conclure "euh-oh, trop de boxe".

Le problème est qu'il a HashSet<T>besoin d'un IEqualityComparer<T>pour faire son travail. Puisque vous n'en avez pas fourni, il doit revenir à celui renvoyé par EqualityComparer.Default<T>(). Cette méthode peut faire du bon travail pour la chaîne, elle implémente IEquatable. Mais pas pour Point, c'est un type qui provient de .NET 1.0 et n'a jamais eu l'amour des génériques. Tout ce qu'il peut faire est d'utiliser les méthodes Object.

L'autre problème est que Point.GetHashCode () ne fait pas un travail stellaire dans ce test, trop de collisions, donc il martèle Object.Equals () assez lourdement. String a une excellente implémentation GetHashCode.

Vous pouvez résoudre les deux problèmes en fournissant au HashSet un bon comparateur. Comme celui-ci:

class PointComparer : IEqualityComparer<Point> {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y << 16) ^ obj.X;
    }
}

Et utilisez-le:

HashSet<Point> list = new HashSet<Point>(new PointComparer());

Et il est maintenant environ 150 fois plus rapide, surpassant facilement le test des cordes.

La principale raison de la baisse des performances est toute la boxe en cours (comme déjà expliqué dans la réponse de Hans Passant ).

En dehors de cela, l'algorithme de code de hachage aggrave le problème, car il provoque plus d'appels pour Equals(object obj)augmenter ainsi le nombre de conversions de boxe.

Notez également que le code de hachage dePoint est calculé par x ^ y. Cela produit très peu de dispersion dans votre plage de données, et par conséquent, les compartiments du HashSetsont surpeuplés - ce qui ne se produit pas avec string, où la dispersion des hachages est beaucoup plus grande.

Vous pouvez résoudre ce problème en implémentant votre propre Pointstruct (trivial) et en utilisant un meilleur algorithme de hachage pour votre plage de données attendue, par exemple en décalant les coordonnées:

(x << 16) ^ y

Pour de bons conseils en matière de codes de hachage, lisez le billet de blog d'Eric Lippert sur le sujet .