ComparerFactory - Compile-time Performance at Runtime

• Download demo and source - 16.23 KB

Introduction

It became a sort of common knowledge that Reflection is slow. To demonstrate that fact, this article uses default sorting behavior of WPF ListCollectionView. It works fine until you have some thousands of items to sort. The technique described here shows how to use Reflection to generate classes at run time while avoiding the performance hit.

Background

My initial task was to sort a list of items in ComboBox (and that's all in WPF and there are some excellent articles showing how to do it). Easy I thought, take a CollectionView and use SortDescription on it:

 private void Sort(string sortBy, ListSortDirection direction){
    ICollectionView dataView = CollectionViewSource.GetDefaultView(lv.ItemsSource);
    dataView.SortDescriptions.Clear();
    var sd = new SortDescription("Name", direction);
    dataView.SortDescriptions.Add(sd);
    dataView.Refresh();
}   

Not so fast. Literally, not fast, but rather quite slow. The list has 20 thousand items in it. Yes, I know that twenty thousand records do not look good in a ComboBox whether sorted or not, but that's not my problem. My problem was to sort and I had to invent something. The Reflection was to blame for the slowness and the following solution worked pretty well. Creating a comparer class:

public class CustomComparer: IComparer {
    public int Compare(object x, object y) {
        return ((ComparedClass)x).Name.CompareTo(
            ((ComparedClass)y).Name);
    }
} 

Then using CustomSort property of ListCollectionView instead of the SortDescriptions above:

dataView.CustomSort = new CustomComparer(); 

That solved the performance problem, but my real assignment was to make this work for any ComboBox with any sort of objects in the list. I am way too lazy to write a custom comparer class every time, so I wrote a factory to produce them for me.

Run-time Compilation

The common use of Reflection is getting metadata about class definitions and using it at runtime. But the real magic starts when you take that metadata at runtime and construct classes right there. Those classes would behave as fast as if they would have been created at compile time. The trick is to generate code at run time with Reflection.Emit.

This is possible because .NET assembly is a binary code of IL (intermediate language) instructions. You can think of IL as a sort of Assembler language for .NET. When the assembly is executed JIT (just-in-time), the compiler translates IL into machine-specific codes. With System.Reflection.Emit namespace, we can produce dynamic assemblies with IL code at run-time and JIT compiler would not notice the difference. Let's create the assembly dynamically:

dynamicName = new AssemblyName("dynamicAssemblyName");
dynamicAssemblyBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(
    dynamicName,
    AssemblyBuilderAccess.Run);
dynamicModuleBuilder = dynamicAssemblyBuilder.DefineDynamicModule(dynamicName.Name); 

That's the prerequisite to class creation. Then we'll need a TypeBuilder instance:

TypeBuilder tb = dynamicModuleBuilder.DefineType(
    typeName,
    TypeAttributes.Public | TypeAttributes.Class,
    null, new Type[] { typeof(IComparer) }); 

To indicate that we are going to implement the IComparer interface:

tb.AddInterfaceImplementation(typeof(IComparer));
MethodBuilder methodBuilder = tb.DefineMethod("Compare",
    MethodAttributes.Public | MethodAttributes.Virtual,
    typeof(int),
    new Type[] { typeof(object), typeof(object) });
ILGenerator methodILGenerator = methodBuilder.GetILGenerator(); 

Now we can use methodILGenerator to emit the method body. But how would that method look in IL? Good question, glad you asked. There's a standard and a further reading from Microsoft that will help us on this quest.

But wait, there's much easier way. C# compiler does the task of translation to IL for us. All we need is a disassembler to translate that code back to human-readable form. ildasm (available as a part of free Windows SDK download) does just that. Here's what a method definition looks like deciphered by ildasm:

.method public hidebysig newslot virtual final 
        instance int32  Compare(object x,
                                object y) cil managed
{
  // Code size       28 (0x1c)
  .maxstack  8
  IL_0000:  ldarg.1
  IL_0001:  castclass  tevton.ComparerFactoryTests.ComparerFactoryTest/CustomComparer
  IL_0006:  callvirt   instance string 
	tevton.ComparerFactoryTests.ComparerFactoryTest/CustomComparer::get_Name()
  IL_000b:  ldarg.2
  IL_000c:  castclass  tevton.ComparerFactoryTests.ComparerFactoryTest/CustomComparer
  IL_0011:  callvirt   instance string 
	tevton.ComparerFactoryTests.ComparerFactoryTest/CustomComparer::get_Name()
  IL_0016:  callvirt   instance int32 [mscorlib]System.IComparable::CompareTo(object)
  IL_001b:  ret
} // end of method CustomComparer::Compare 

With a very little effort and some experimenting (the value-type property comparer will look a bit different), this translates into the following C# code:

var getAccessor = propertyInfo.GetAccessors()
                      .Where(mi => mi.Name.StartsWith("get_")).SingleOrDefault();
methodILGenerator.Emit(OpCodes.Ldarg_1);
methodILGenerator.Emit(OpCodes.Castclass, propertyInfo.DeclaringType);
methodILGenerator.Emit(OpCodes.Callvirt, getAccessor);
if(propertyInfo.PropertyType.IsValueType) {
    methodILGenerator.Emit(OpCodes.Box, propertyInfo.PropertyType);
}
                
methodILGenerator.Emit(OpCodes.Ldarg_2);
methodILGenerator.Emit(OpCodes.Castclass, propertyInfo.DeclaringType);
methodILGenerator.Emit(OpCodes.Callvirt, getAccessor);
if(propertyInfo.PropertyType.IsValueType) {
    methodILGenerator.Emit(OpCodes.Box, propertyInfo.PropertyType);
}
                
methodILGenerator.Emit(OpCodes.Callvirt, typeof(IComparable).GetMethod("CompareTo"));
methodILGenerator.Emit(OpCodes.Ret); 

That takes care about the method body. Just one finishing touch - overriding IComparer.Compare() with the method built:

MethodInfo compareInfo = typeof(IComparer).GetMethod("Compare");
tb.DefineMethodOverride(methodBuilder, compareInfo);
Type t = tb.CreateType();
IComparer res = Activator.CreateInstance(t) as IComparer;  

and the class instance is ready! The factory I mentioned earlier wraps all those dynamic comparers into one convenient package.

Using the Code

Whenever you are in need of IComparer class such as the one shown above, you could just get an instance from the factory:

dataView.CustomSort = 
	ComparerFactory.Instance.GetComparer(typeof(ComparedClass), "Name");  

That's it, all the benefits of reflection (a sort of "late binding") with the performance of strongly typed class. The source code comes with a demo project and NUnit test library to make the usage clear.

Do try this at home. Reflection is more powerful than I used to think, but be aware that there are some drawbacks such as the difficulty to debug dynamic code, troubles making GC to dispose dynamically created types and sporadic exceptions here and there if you got your IL code wrong.

History

• Feb 2010 - Initial release