System.Drawing.Point is much faster than my simple struct

Question

What wizardry is in that System.Drawing.Point class that makes it so much faster than my simple struct?

It's quite a bit faster. I'm getting 1-5ms on Point class and 2000ms or more on my struct.

Looking at the Points.cs source, I'm not skilled enough to spot what is doing it. I made an attempt at implementing IEquatable (probably incorrectly) and couldn't make any gains.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;

class Program
{
    static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();

        int elementsInSets = 10000;
        int lookupCount = 10000;

        // Point struct from System.Drawing
        HashSet<Point> myPoints = new HashSet<Point>();
        for (int i = 0; i < elementsInSets; i++)
        {
            myPoints.Add(new Point(i, i));
        }

        // My simple struct
        HashSet<P> myPoints2 = new HashSet<P>();
        for (int i = 0; i < elementsInSets; i++)
        {
            myPoints2.Add(new P(i, i));
        }


        sw.Start();
        for (int j = 0; j < lookupCount; j++)
        {
            if (myPoints2.Contains(new P(j, j)))
            {
                //found
            }
        }
        Console.WriteLine("simple P  " + sw.ElapsedMilliseconds + "ms");

        sw.Restart();
        for (int j = 0; j < lookupCount; j++)
        {
            if (myPoints.Contains(new Point(j, j)))
            {
                // found
            }
        }
        Console.WriteLine("Point " + sw.ElapsedMilliseconds + "ms");     
    }
}
public struct P
{
    int x;
    int y;
    public P(int xCoord, int yCoord)
    {
        x = xCoord;
        y = yCoord;
    }
}

[Override `GetHashCode()` and `Equals()`](https://devblogs.microsoft.com/premier-developer/performance-implications-of-default-struct-equality-in-c/) in your struct. — GSerg, Apr 22 '20 at 14:57
The reference source you are reading is almost certainly not the 'real' code that you are looking for. — not my real name, Apr 22 '20 at 15:00
The efficiency of HashSet critically depends on the quality of the object's GetHashCode() implementation. Point [has one](https://referencesource.microsoft.com/#System.Drawing/commonui/System/Drawing/Point.cs,bf7e74c22255cc57), yours doesn't. Notes on creating a better one [are here](https://stackoverflow.com/a/46143745/17034). The PointComparer in that snippet makes it too fast to measure (0 msec). Which exposes a problem with Point.GetHashCode(), it doesn't work very well when x==y. — Hans Passant, Apr 22 '20 at 15:11
@RayWu Reference means that it is for you to reference. If you want to know the source code, you reference that page. — GSerg, Apr 22 '20 at 15:17

score 2 · Accepted Answer · answered Apr 22 '20 at 15:00

That's due to no override for GetHashCode (you should also override Equals) as in the Point source. They do it this way:

public override bool Equals(object obj) {
    if (!(obj is Point)) return false;
    Point comp = (Point)obj;
    // Note value types can't have derived classes, so we don't need 
    // to check the types of the objects here.  -- Microsoft, 2/21/2001
    return comp.X == this.X && comp.Y == this.Y;
}

public override int GetHashCode() {
    return unchecked(x ^ y);
}

If your implementation was the same you should see similar performance.

Thank you very much folks. That was indeed it. Both this and Martin's answer were spot on. I'm giving this answer the check mark only because Zer0 types faster. — , Apr 22 '20 at 19:53

Martin Liversage · Answer 2 · 2020-04-22T21:47:19.330

While a struct provides a default implementation for Equals and GetHashCode they have bad performance as they use reflection. Instead you should provide your own implementation. While you don't have to implement IEquatable<Point> I think it's worthwhile:

readonly struct Point : IEquatable<Point>
{
    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public int X { get; }
    public int Y { get; }

    public bool Equals(Point other) => X == other.X && Y == other.Y;

    public override bool Equals(object obj) => obj is Point point && Equals(point);

    public override int GetHashCode() => HashCode.Combine(X, Y);
}

I did a casual benchmark using your code and the performance of this code is similar to System.Drawing.Point or perhaps slightly slower but not thousands of times slower like the naïve approach.

System.Drawing.Point is much faster than my simple struct

2 Answers2