title: What is the reason behind this huge Performance difference in .Net 4
body: <p>I was just doing some research on RedBlack Tree. I knew that SortedSet class in .Net 4.0 uses RedBlack tree. So I took that part out as is using Reflector and created a RedBlackTree class. Now I am running some perf test on this RedBlackTree and SortedSet inserting 40000 sequential integral values (starting from 0 to 39999), I am astonished to see that there is huge perf difference as follows:</p>
  
  <pre><code> RBTree    took 9.27208   sec to insert 40000 values 
   SortedSet took 0.0253097 sec to insert 40000 values
  </code></pre>
  
  <p>What is the reason behind it? BTW I ran the test in Release configuration only and here is the small test code</p>
  
  <pre><code>            var stopWatch = new Stopwatch();
              var rbT = new RedBlackTree&lt;int&gt;();      
          stopWatch = new Stopwatch();
          stopWatch.Start();
          for (int i = 0; i &lt; 40000; i++) {
              rbT.Add(i);
          }
          stopWatch.Stop();
          Console.WriteLine(stopWatch.Elapsed);
  
          var ss = new SortedSet&lt;int&gt;();
          stopWatch = new Stopwatch();
          stopWatch.Start();
          for (int i = 0; i &lt; 40000; i++) {
              ss.Add(i);
          }
          stopWatch.Stop();
          Console.WriteLine(stopWatch.Elapsed);
  </code></pre>
  
  <p>Edit</p>
  
  <p>I would like to share the code also for RBTree what I've extracted so that you also can run the diagnostics</p>
  
  <pre><code>public class Node&lt;T&gt;
      {
          public Node(){}
  
          public Node(T value)
          {
              Item = value;
          }       
  
          public Node(T value, bool isRed)
          {
              Item = value;
              IsRed = isRed;
          }
  
          public T Item;
          public Node&lt;T&gt; Left;
          public Node&lt;T&gt; Right;
          public Node&lt;T&gt; Parent;
          public bool IsRed;
      }
  
      public class RedBlackTree&lt;T&gt;
      {
          public RedBlackTree(){} 
  
          public Node&lt;T&gt; root;
          int count, version; 
          Comparer&lt;T&gt; comparer = Comparer&lt;T&gt;.Default;     
  
          public void Add(T item)
          {
              if (this.root == null)
              {
                  this.root = new Node&lt;T&gt;(item, false);
                  this.count = 1;
                  this.version++;
                  return;
              }
  
              Node&lt;T&gt; root = this.root;
              Node&lt;T&gt; node = null;
              Node&lt;T&gt; grandParent = null;
              Node&lt;T&gt; greatGrandParent = null;
              this.version++;
  
              int num = 0;
              while (root != null)
              {
                  num = this.comparer.Compare(item, root.Item);
                  if (num == 0)
                  {
                      this.root.IsRed = false;
                      return;
                  }
                  if (Is4Node(root))
                  {
                      Split4Node(root);
                      if (IsRed(node))
                      {
                          this.InsertionBalance(root, ref node, grandParent, greatGrandParent);
                      }
                  }
                  greatGrandParent = grandParent;
                  grandParent = node;
                  node = root;
                  root = (num &lt; 0) ? root.Left : root.Right;
              }
              Node&lt;T&gt; current = new Node&lt;T&gt;(item);
              if (num &gt; 0)
              {
                  node.Right = current;
              }
              else
              {
                  node.Left = current;
              }
              if (node.IsRed)
              {
                  this.InsertionBalance(current, ref node, grandParent, greatGrandParent);
              }
              this.root.IsRed = false;
              this.count++;
          }
  
  
          private static bool IsRed(Node&lt;T&gt; node)
          {
              return ((node != null) &amp;&amp; node.IsRed);
          }
  
          private static bool Is4Node(Node&lt;T&gt; node)
          {
              return (IsRed(node.Left) &amp;&amp; IsRed(node.Right));
          }
  
          private static void Split4Node(Node&lt;T&gt; node)
          {
              node.IsRed = true;
              node.Left.IsRed = false;
              node.Right.IsRed = false;
          }
  
          private void InsertionBalance(Node&lt;T&gt; current, ref Node&lt;T&gt; parent, Node&lt;T&gt; grandParent, Node&lt;T&gt; greatGrandParent)
          {
              Node&lt;T&gt; node;
              bool flag = grandParent.Right == parent;
              bool flag2 = parent.Right == current;
              if (flag == flag2)
              {
                  node = flag2 ? RotateLeft(grandParent) : RotateRight(grandParent);
              }
              else
              {
                  node = flag2 ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
                  parent = greatGrandParent;
              }
              grandParent.IsRed = true;
              node.IsRed = false;
              ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, node);
          }
  
          private static Node&lt;T&gt; RotateLeft(Node&lt;T&gt; node)
          {
              Node&lt;T&gt; right = node.Right;
              node.Right = right.Left;
              right.Left = node;
              return right;
          }
  
          private static Node&lt;T&gt; RotateRight(Node&lt;T&gt; node)
          {
              Node&lt;T&gt; left = node.Left;
              node.Left = left.Right;
              left.Right = node;
              return left;
          }
  
          private static Node&lt;T&gt; RotateLeftRight(Node&lt;T&gt; node)
          {
              Node&lt;T&gt; left = node.Left;
              Node&lt;T&gt; right = left.Right;
              node.Left = right.Right;
              right.Right = node;
              left.Right = right.Left;
              right.Left = left;
              return right;
          }
  
          private static Node&lt;T&gt; RotateRightLeft(Node&lt;T&gt; node)
          {
              Node&lt;T&gt; right = node.Right;
              Node&lt;T&gt; left = right.Left;
              node.Right = left.Left;
              left.Left = node;
              right.Left = left.Right;
              left.Right = right;
              return left;
          }
  
          private void ReplaceChildOfNodeOrRoot(Node&lt;T&gt; parent, Node&lt;T&gt; child, Node&lt;T&gt; newChild)
          {
              if (parent != null)
              {
                  if (parent.Left == child)
                  {
                      parent.Left = newChild;
                  }
                  else
                  {
                      parent.Right = newChild;
                  }
              }
              else
              {
                  this.root = newChild;
              }
          }
      }
  </code></pre>
  
  <hr>
  
  <p>Edit</p>
  
  <hr>
  
  <p>I ran the same diagnostic on some other data structure (some created by me*, some from .net framework**) and here is the interesting results</p>
  
  <pre><code>*AATree                 00:00:00.0309294
  *AVLTree                00:00:00.0129743
  **SortedDictionary      00:00:00.0313571
  *RBTree                 00:00:09.2414156
  **SortedSet             00:00:00.0241973
  </code></pre>
  
  <p>RBTree is the same as above (stripped out from SortedSet class). <strong>I tried with 400000 values also, but RBTree seems taking FOREVER</strong>, I really don't know why.</p>