title: Why does my performance slow to a crawl I move methods into a base class?
body: <p>I'm writing different implementations of immutable binary trees in C#, and I wanted my trees to inherit some common methods from a base class.</p>
  
  <p>Unfortunately, classes which derive from the base class are <em>abysmally</em> slow. Non-derived classes perform adequately. Here are two nearly identical implementations of an AVL tree to demonstrate:</p>
  
  <ul>
  <li>AvlTree: <a href="http://pastebin.com/V4WWUAyT" rel="noreferrer">http://pastebin.com/V4WWUAyT</a></li>
  <li>DerivedAvlTree: <a href="http://pastebin.com/PussQDmN" rel="noreferrer">http://pastebin.com/PussQDmN</a></li>
  </ul>
  
  <p>The two trees have the <em>exact same code</em>, but I've moved the <em>DerivedAvlTree.Insert</em> method in base class. Here's a test app:</p>
  
  <pre><code>using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Linq;
  using Juliet.Collections.Immutable;
  
  namespace ConsoleApplication1
  {
      class Program
      {
          const int VALUE_COUNT = 5000;
  
          static void Main(string[] args)
          {
              var avlTreeTimes = TimeIt(TestAvlTree);
              var derivedAvlTreeTimes = TimeIt(TestDerivedAvlTree);
  
              Console.WriteLine("avlTreeTimes: {0}, derivedAvlTreeTimes: {1}", avlTreeTimes, derivedAvlTreeTimes);
          }
  
          static double TimeIt(Func&lt;int, int&gt; f)
          {
              var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 };
  
              var times = new List&lt;double&gt;();
  
              foreach (int seed in seeds)
              {
                  var sw = Stopwatch.StartNew();
                  f(seed);
                  sw.Stop();
                  times.Add(sw.Elapsed.TotalMilliseconds);
              }
  
              // throwing away top and bottom results
              times.Sort();
              times.RemoveAt(0);
              times.RemoveAt(times.Count - 1);
              return times.Average();
          }
  
          static int TestAvlTree(int seed)
          {
              var rnd = new System.Random(seed);
  
              var avlTree = AvlTree&lt;double&gt;.Create((x, y) =&gt; x.CompareTo(y));
              for (int i = 0; i &lt; VALUE_COUNT; i++)
              {
                  avlTree = avlTree.Insert(rnd.NextDouble());
              }
  
              return avlTree.Count;
          }
  
          static int TestDerivedAvlTree(int seed)
          {
              var rnd = new System.Random(seed);
  
              var avlTree2 = DerivedAvlTree&lt;double&gt;.Create((x, y) =&gt; x.CompareTo(y));
              for (int i = 0; i &lt; VALUE_COUNT; i++)
              {
                  avlTree2 = avlTree2.Insert(rnd.NextDouble());
              }
  
              return avlTree2.Count;
          }
      }
  }
  </code></pre>
  
  <ul>
  <li>AvlTree: inserts 5000 items in 121 ms</li>
  <li>DerivedAvlTree: inserts 5000 items in 2182 ms</li>
  </ul>
  
  <p>My profiler indicates that the program spends an inordinate amount of time in <code>BaseBinaryTree.Insert</code>. Anyone whose interested can see the <a href="http://pastebin.com/NqkSJSrT" rel="noreferrer">EQATEC log file</a> I've created with the code above (you'll need <a href="http://www.eqatec.com/tools/profiler" rel="noreferrer">EQATEC profiler</a> to make sense of file).</p>
  
  <p>I really want to use a common base class for all of my binary trees, but I can't do that if performance will suffer.</p>
  
  <p><strong>What causes my DerivedAvlTree to perform so badly, and what can I do to fix it?</strong></p>