Performance Quiz #5: The performance cost of the garbage collector

It's been a while, so it's time for another exciting Performance Quiz!

Here are two implementations of a management algorithm that creates and destroys trees. The first implementation uses the garbage collector to do all of the memory management (even freeing is done via periodic collections, we just drop the nodes on the floor). The second implementation is more like what you would write if you had to do a malloc/free style solution that managed your own memory. However after the first iteration there will be no collections at all -- allocations come out a high-speed free list and the freelist is created via a fast recursive algorithm.

The Question: How much faster is Test2() than Test1()?

Warning: There's already spoilers in the feedback

------------------------------------------

using System;

namespace Test
{
public class Quiz5
{
        public static void Main()
{
            // try running the tests in the other order too, or just one per run
Test1();
Test2();
}

        public static void Test1()
{
Random r = new Random();

            Tree1.Reset();

            for (int i = 0; i < 50; i++)
{
for (int j = 0; j < 100000; j++)
{
int k = (int)r.Next();
Tree1.Insert(k);
}
Tree1.Reset();
}
        }

        public static void Test2()
{
Random r = new Random();

            Tree2.Reset();

            for (int i = 0; i < 50; i++)
{
for (int j = 0; j < 100000; j++)
{
int k = (int)r.Next();
Tree2.Insert(k);
}
Tree2.Reset();
}
        }

        class Tree1
{
private int key;
private Tree1 left;
private Tree1 right;

private static Tree1 root;

            private Tree1(int _key)
{
key = _key;
}

            static public void Reset()
{
root = null; // much garbage is created
}

            static public void Insert(int key)
{
Tree1 t = root;
if (t == null)
{
root = new Tree1(key); // asking for new memory
return;
}

                for (;;)
{
if (t.key == key)
return;

                    if (key < t.key)
{
if (t.left == null)
{
t.left = new Tree1(key); // new memory again
return;
}
else
{
t = t.left;
}
}
else
{
if (t.right == null)
{
t.right = new Tree1(key); // new memory yet again
return;
}
else
{
t = t.right;
}
}
}
}
}

        class Tree2
{
private int key;
private Tree2 left;
private Tree2 right;

private static Tree2 root;
private static Tree2 freelist;

            static public Tree2 NewTree2(int _key)
{
Tree2 t = freelist;

                if (t != null)
{
freelist = t.right;
t.right = null;
}
else
{
t = new Tree2(); // on the 2nd time through this never happens
}

                t.key = _key;
return t;
}

            static public void Reset()
{
FreeTree(root);
root = null;
}

            static private void FreeTree(Tree2 t)
{

                // put the tree on the free list... no collections 

                if (t == null)
return;

FreeTree(t.right);
FreeTree(t.left);

                t.right = freelist;
t.left = null;
freelist = t;
}

            static public void Insert(int key)
{
Tree2 t = root;
if (t == null)
{
root = NewTree2(key);
return;
}

                for (;;)
{
if (t.key == key)
return;

                    if (key < t.key)
{
if (t.left == null)
{
t.left = NewTree2(key);
return;
}
else
{
t = t.left;
}
}
else
{
if (t.right == null)
{
t.right = NewTree2(key);
return;
}
else
{
t = t.right;
}
}
}
}
}
}
}