Pourquoi HashSet <Point> tellement plus lent que HashSet <string> ?

Question

Je voulais garder quelques pixels endroits sans permettre les doublons, donc la première chose qui vient à l'esprit est - HashSet<Point> ou des catégories similaires. Toutefois, cela semble être très lente 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) prend seulement 1,6 secondes:

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 les suivantes:

• Est-il une raison pour que? J'ai vérifié cette réponse, mais 22.5 sec est beaucoup plus que le nombre indiqué dans cette réponse.
• Est-il une meilleure façon de stocker les points sans les doublons?

Answer 1

Il y a deux perf problèmes induits par le Point de struct. Quelque chose que vous pouvez voir lorsque vous ajoutez Console.WriteLine(GC.CollectionCount(0)); pour le code de test. Vous verrez que le Point de test nécessite ~3720 collections, mais la chaîne de tester uniquement les besoins de ~18 collections. Pas gratuitement. Quand vous voyez un type de valeur induire donc de nombreuses collections ensuite, vous devez conclure "uh-oh, trop de boxe".

L'enjeu est que l' HashSet<T> besoin d'un IEqualityComparer<T> d'obtenir de son travail. Puisque vous n'avez pas fourni, il doit revenir à celui retourné par EqualityComparer.Default<T>(). Cette méthode peut faire un bon travail pour la chaîne, il met en œuvre IEquatable. Mais pas pour le Point, c'est un type qui fait écho à partir .NET 1.0 et n'a jamais eu les génériques de l'amour. Tout ce qu'il peut faire est d'utiliser les méthodes de l'Objet.

L'autre problème est que Point de.GetHashCode() ne prend pas en faire un excellent travail dans ce test, un trop grand nombre de collisions, de sorte qu'il marteaux Objet.Equals() assez fortement. La chaîne dispose d'un excellent GetHashCode mise en œuvre.

Vous pouvez résoudre ces deux problèmes en fournissant le HashSet avec 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 de l'utiliser:

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

Et il est maintenant d'environ 150 fois plus rapide, facilement battre la chaîne de test.

Answer 2

La raison principale de la chute des performances est tout la boxe va (comme déjà expliqué dans Hans Passant de réponse).

En dehors de cela, le code de hachage de l'algorithme s'aggrave le problème, car il provoque plus d'appels à l' Equals(object obj) portant ainsi le montant de la boxe conversions.

Notez également que le code de hachage de l' Point est calculée en x ^ y. Ce produit très peu de dispersion dans votre plage de données, et, par conséquent, les seaux de l' HashSet sont surpeuplées — quelque chose qui ne se produit pas avec string, où la dispersion des hachages est beaucoup plus grande.

Vous pouvez résoudre ce problème par la mise en œuvre de votre propre Point struct (trivial) et à l'aide d'un meilleur algorithme de hachage pour votre plage de données, par exemple en déplaçant les coordonnées:

(x << 16) ^ y

Pour certains de bons conseils quand il s'agit de codes de hachage, lire Eric Lippert blog post sur le sujet.