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. However, I find. I have lots of binary tree data structures to implement, and I wanted move some common methods into in a base binary tree class.
Unfortunately, classes which derive from the base class are abysmally slow. Non-derived classes perform adequately. Here are two nearly identical implementations of an AVL tree to demonstrate:
AvlTree: http://pastebin.com/V4WWUAyT
DerivedAvlTree: http://pastebin.com/PussQDmN
The two trees have the exact same code, but I've moved the DerivedAvlTree.Insert method in base class. Here's a test app:
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<int, int> f)
{
var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 };
var times = new List<double>();
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<double>.Create((x, y) => x.CompareTo(y));
for (int i = 0; i < 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<double>.Create((x, y) => x.CompareTo(y));
for (int i = 0; i < VALUE_COUNT; i++)
{
avlTree2 = avlTree2.Insert(rnd.NextDouble());
}
return avlTree2.Count;
}
}
}
AvlTree: inserts 5000 items in 121 ms
DerivedAvlTree: inserts 5000 items in 2182 ms
My profiler indicates that the program spends an inordinate amount of time in BaseBinaryTree.Insert. Anyone whose interested can see the EQATEC log file I've created with the code above (you'll need EQATEC profiler to make sense of file).
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.
What causes my DerivedAvlTree to perform so badly, and what can I do to fix it?
