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.
