Want to show your appreciation? Please to my charity.

Tuesday, January 19, 2010

Always Override Equals of Your Value Type

ReSharper had been reminding me to override the Equals method and operator for value types that I have created. Every time I took the advice and let ReSharper do the work for me.

But I kept wondering how bad is the default implementation? The default implementation of Equals method is in the ValueType abstract class that every .Net value type inherits from. Initially I though it must use some sort of native memory comparison so it got to be fast. But after I looked at the code in Reflector, I’m no longer sure how true is this. It calls a native method CanCompareBits to check if current instance eligible for FastEqualsCheck. If yes great, otherwise it falls back to reflection. I don’t know what qualifies for fast equals check, but I start to realized that members with Equals method overridden cannot not use bit comparison. The reflection code told me that it uses Equals to compare members.

Enough talk, lets test the performance with two simplest value types, one has Equals overridden and another relays on the default implementation.

I used NUnit test case for simplicity but the code below can be easily changed to a console application.

   1:  private const int _sampleSize = 100;
   2:   
   3:  [Test] public static void Main()
   4:  {
   5:      var defaultEqualsStruct = new DefaultEqualsStruct[_sampleSize];
   6:      var overriddenEqualsStruct = new OverriddenEqualsStruct[_sampleSize];
   7:      for (int i = 0; i < _sampleSize; i++)
   8:      {
   9:          defaultEqualsStruct[i] = new DefaultEqualsStruct { Foo = i };
  10:          overriddenEqualsStruct[i] = new OverriddenEqualsStruct { Foo = i };
  11:      }
  12:      RunBenchMark(defaultEqualsStruct, new DefaultEqualsStruct { Foo = _sampleSize });
  13:      RunBenchMark(overriddenEqualsStruct, new OverriddenEqualsStruct { Foo = _sampleSize });
  14:  }
  15:   
  16:  public static void RunBenchMark<T>(T[] items, T e)
  17:  {
  18:      Console.WriteLine("==========" + typeof(T).Name + "=========");
  19:      // Warn up
  20:      Assert.IsTrue(ArrayIndexOf(items, items[5]));
  21:      Assert.IsTrue(LoopEquals(items, items[5]));
  22:      Clock(null, 1, () => Assert.IsFalse(ArrayIndexOf(items, e)));
  23:      Clock(null, 1, () => Assert.IsFalse(LoopEquals(items, e)));
  24:      // Run benchmark.
  25:      const int repeat = 100000;
  26:      Clock("Array.IndexOf", repeat, () => ArrayIndexOf(items, e));
  27:      Clock("Loop + Equals", repeat, () => LoopEquals(items, e));
  28:  }
  29:   
  30:  private static void Clock(string message, int repeat, Action a)
  31:  {
  32:      Stopwatch stopwatch = new Stopwatch();
  33:      stopwatch.Start();
  34:      for (int i = 0; i < repeat; i++) a();
  35:      stopwatch.Stop();
  36:      if (message != null)
  37:          Console.WriteLine(message + ": " + stopwatch.ElapsedTicks);
  38:  }
  39:   
  40:  private static bool ArrayIndexOf<T>(T[] items, T element)
  41:  {
  42:      return (Array.IndexOf(items, element) >= 0);
  43:  }
  44:   
  45:  private static bool LoopEquals<T>(T[] items, T element)
  46:  {
  47:      int size = items.Length;
  48:      for (int i = 0; i < size; i++)
  49:      {
  50:          if (Equals(element, items[i])) return true; // found
  51:      }
  52:      return false;
  53:  }
  54:   
  55:  public struct DefaultEqualsStruct
  56:  {
  57:      public int Foo { get; set; }
  58:  }
  59:   
  60:  public struct OverriddenEqualsStruct
  61:  {
  62:      public int Foo { get; set; }
  63:   
  64:      public bool Equals(OverriddenEqualsStruct other)
  65:      {
  66:          return other.Foo == Foo;
  67:      }
  68:   
  69:      public override bool Equals(object obj)
  70:      {
  71:          if (ReferenceEquals(null, obj)) return false;
  72:          if (obj.GetType() != typeof(OverriddenEqualsStruct)) return false;
  73:          return Equals((OverriddenEqualsStruct)obj);
  74:      }
  75:   
  76:      public override int GetHashCode()
  77:      {
  78:          return Foo;
  79:      }
  80:  }

And here goes the test result in release build:

   1:  ==========DefaultEqualsStruct=========
   2:  Array.IndexOf: 2863736
   3:  Loop + Equals: 1424624
   4:  ==========OverriddenEqualsStruct=========
   5:  Array.IndexOf: 289861
   6:  Loop + Equals: 509123

That’s really a lot of difference! Thanks ReSharper!

No comments:

Post a Comment