172

I wanted to store some pixels locations without allowing duplicates, so the first thing comes to mind is HashSet<Point> or similar classes. However this seems to be very slow compared to something like HashSet<string>.

For example, this 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));
        }
    }
}

takes about 22.5 seconds.

While the following code (which is not a good choice for obvious reasons) takes only 1.6 seconds:

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);
        }
    }
}

So, my questions are:

  • Is there a reason for that? I checked this answer, but 22.5 sec is way more than the numbers shown in that answer.
  • Is there a better way to store points without duplicates?
2

2 Answers 2

302

There are two perf problems induced by the Point struct. Something you can see when you add Console.WriteLine(GC.CollectionCount(0)); to the test code. You'll see that the Point test requires ~3720 collections but the string test only needs ~18 collections. Not for free. When you see a value type induce so many collections then you need to conclude "uh-oh, too much boxing".

At issue is that HashSet<T> needs an IEqualityComparer<T> to get its job done. Since you did not provide one, it needs to fall back to one returned by EqualityComparer.Default<T>(). That method can do a good job for string, it implements IEquatable. But not for Point, it is a type that harks from .NET 1.0 and never got the generics love. All it can do is use the Object methods.

The other issue is that Point.GetHashCode() does not do a stellar job in this test, too many collisions, so it hammers Object.Equals() pretty heavily. String has an excellent GetHashCode implementation.

You can solve both problems by providing the HashSet with a good comparer. Like this one:

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;
    }
}

And use it:

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

And it is now about 150 times faster, easily beating the string test.

16
  • 26
    +1 for providing GetHashCode method implementation. Just for curiosity, how did you come with particular obj.X << 16 | obj.Y; implementation.
    – Akash KC
    Sep 11, 2017 at 2:54
  • 35
    It was inspired by the way the mouse passes its position in windows. It is a perfect hash for any bitmap you'd ever want to display. Sep 11, 2017 at 6:53
  • 2
    Good to know that. Any documentation or best guideline to write hashcode like yours ? Actually, I still would like to know whether above hashcode comes with your experience or any guideline which you follow.
    – Akash KC
    Sep 11, 2017 at 18:15
  • 7
    @AkashKC I'm not very experiences with C# but as far as I know integers are generally 32bits. In this case you want the hash of 2 numbers and by left-shifting one 16bits you make sure the "lower" 16 bits of each number don't "affect" the other with |. For 3 numbers it could make sense to use 22 and 11 as shift. For 4 numbers it would be 24, 16, 8. However there will be still collisions but only if the numbers get large. But it also crucially depends on the HashSet implementation. If it uses open-adressing with "bit truncation" (I don't think it does!) the left-shift approach might be bad.
    – MSeifert
    Sep 12, 2017 at 7:07
  • 3
    @HansPassant: I wonder if using XOR rather than OR in GetHashCode might be slightly better - in the event that point coordinates might exceed 16 bits (perhaps not on common displays, but near future). // XOR is usually better in hash functions than OR, since it loses less information, is reversibke, etc. // e.g. If negative coordinates are allowed, consider what happens to the X contribution if Y is negative.
    – Krazy Glew
    Sep 13, 2017 at 1:18
86

The main reason for the performance drop is all the boxing going on (as already explained in Hans Passant's answer).

Apart from that, the hash code algorithm worsens the problem, because it causes more calls to Equals(object obj) thus increasing the amount of boxing conversions.

Also note that the hash code of Point is computed by x ^ y. This produces very little dispersion in your data range, and therefore the buckets of the HashSet are overpopulated — something that doesn't happen with string, where the dispersion of the hashes is much larger.

You can solve that problem by implementing your own Point struct (trivial) and using a better hash algorithm for your expected data range, e.g. by shifting the coordinates:

(x << 16) ^ y

For some good advice when it comes to hash codes, read Eric Lippert's blog post on the subject.

15
  • 2
    @MartinSmith because there is no other good reason, if a hash set is slow for one type and not another under the same circumstances then it has to be due to the hash code implementation of the slow type not producing enough dispersion.
    – InBetween
    Sep 10, 2017 at 16:32
  • 4
    Looking at the reference source of Point the GetHashCode performs: unchecked(x ^ y) while for string it looks much more complicated.. Sep 10, 2017 at 16:33
  • 4
    @AhmedAbdelhameed that's probably because you are adding way less members to your hash set than you realize (again due to the horrible dispersion of the hash code algorithm). What's the count of list when you've finished populating it?
    – InBetween
    Sep 10, 2017 at 16:55
  • 4
    @AhmedAbdelhameed Your test is wrong. You are adding the same longs over and over, so actually there are just few elements you are inserting. When inserting point, the HashSet will internally call GetHashCode and for each of those points with the same hashcode, will call Equals to determine if it's already exists Sep 10, 2017 at 16:56
  • 49
    There's no need to implement Point when you can create a class that implements IEqualityComparer<Point> and keep compatibility with other things that work with Point while getting the benefit of not having the poor GetHashCode and the need to box in Equals().
    – Jon Hanna
    Sep 10, 2017 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.