The Importance of C#'s GetHashCode()

Every once in a while I get a reminder of how important the use of object's GetHashCode() is for efficient lookups. Today I had a painful reminder of that, so I decided to write about it so you can avoid the same fate or at least know where to look.

If you're coming from C++, you are probably familiar with how you implement the less than operator to make sure things play nicely with std::map and the like. In C#, there are more options of things to implement for testing equality, etc. (see IEquatable<T> for example) but if you want to make sure that something plays well with Dictionary<K,V>, you need to override GetHashCode().

So here's the scenario. I was using the excellent SFML library (Thanks Laurent Gomila!) and implementing a texture atlas for tiles in my RPG. I was making the transition from editing the tilemaps in a WinForms/SFML mashup to packing resources and using them in my game. After working through the usual bugs, it was up and running...

Slowly. At a truly dismal 30 FPS. This was not how I envisioned my texture atlas performing. I had not looked at performance in my editor because it was far from the number one concern, but this was just disappointing.

So I started digging in all the usual places, starting with my core data structures and access patterns around them. I did make a few modest gains, but nothing major since I had already designed around a spatial-range friendly data structure. However, I did notice something strange: performance seemed better or worse depending on which tiles I was showing. In theory, you wouldn't think this would make a difference because they're all just texture coordinates, so it must be something with the access pattern.

Finally, after many deadends checking for differences between different tile inputs, I found the bottleneck to be in the texture atlas itself. The code there was very minimal, consisting primarily of a lookup in a Dictionary. Specifically, I was uniquely identifying tiles from source bitmaps as a custom struct StaticTile that looked like this:

    //SSSSXXYY - The breakdown of the fields
    //S - Source Id
    //X, Y - coordinates
    [StructLayout(LayoutKind.Explicit)]
    public struct StaticTile : IEquatable<StaticTile>, IEqualityComparer<StaticTile>
    {
        public static readonly StaticTile Null = new StaticTile() { Value = UInt64.MaxValue };
        public const int Size = 16;
 
        [FieldOffset(0)] public UInt32 SourceId;
        [FieldOffset(4)] public Int16 X;
        [FieldOffset(6)] public Int16 Y;
 
        [FieldOffset(0)] public UInt64 Value;

...

    } 

Internally, Value is the UInt64 representation of the SourceId (the source bitmap id) and the tile coordinates X and Y. (If you're not familiar with LayoutKind.Explicit and [FieldOffset], that's basically a way to make a C++ union when storing serializing/deserializing your data.)
The lookup was simply in a Dictionary<StaticTile,Vector2i> to get to something to map to texture coordinates.
So I started with a simple GetHashCode implementation:

        public override int GetHashCode()
        {
            return (int)Value;
        }

This still had poor performance. But then I realized that the return was using only 32 bits, so likely only X and Y's information to disambiguate hash buckets, which was far from ideal. So I tried again:

        public override int GetHashCode()
        {
            return (int)((SourceId<<8) | (X<<4) | (Y));
        }

Success! This one small change removed the performance bottleneck and caused performance to go back up to 60 FPS. Talk about one hot loop!

So in summary:
Key point #1: Override GetHashCode when using a custom struct in a Dictionary.
Key point #2: Pick your implementation to be as unique as possible. It makes a real difference.