All entries for Saturday 05 August 2006

August 05, 2006

BindingListView speedy sorting

I received some feedback about my BindingListView library saying it was very slow for sorting large lists. At first I thought 20,000 objects in a view was a bit extreme, but I tested with a DataView object and it worked OK. So I decided to hunt down the bottleneck in BindingListView sorting.
Using the CLR Profiler I determined it was reflection calls taking most of the execution time (no suprises there, reflection is very slow!)
When sorting the BLV used reflection to read the sorted property value from each object. The sorting 20,000 objects means and lot of calls to "GetValue", resulting in crippled performance.
The solution came from .NET 2.0's System.Reflection.Emit.DynamicMethod class. Using this class I was able to emit the IL (Microsoft .NET Intermediate Language) that directly accessed an object's property. (Of course the name of the property is supplied at runtime.)
I actually generate a few different methods depending on it the property is a value type or reference type. Since a value type needs to be boxed before we can compare using IComparable.
Here is one of the methods:
private static Comparison BuildRefTypeComparison(PropertyInfo pi, ListSortDirection direction)
{
MethodInfo getMethod = pi.GetGetMethod();
Debug.Assert(getMethod != null);

DynamicMethod dm = new DynamicMethod("Get" + pi.Name, typeof(int), new Type[] { typeof(T), typeof(T) }, typeof(T));
ILGenerator il = dm.GetILGenerator();

// Get the value of the first object's property.
il.Emit(OpCodes.Ldarg_0);
il.EmitCall(OpCodes.Call, getMethod, null);

// Get the value of the second object's property.
il.Emit(OpCodes.Ldarg_1);
il.EmitCall(OpCodes.Call, getMethod, null);

// Cast the first value to IComparable and call CompareTo,
// passing the second value as the argument.
il.Emit(OpCodes.Castclass, typeof(IComparable));
il.EmitCall(OpCodes.Call, typeof(IComparable).GetMethod("CompareTo"), null);

// If descending then multiply comparison result by -1
// to reverse the ordering.
if (direction == ListSortDirection.Descending)
{
il.Emit(OpCodes.Ldc_I4_M1);
il.Emit(OpCodes.Mul);
}

// Return the result of the comparison.
il.Emit(OpCodes.Ret);

// Create the delegate pointing at the dynamic method.
return (Comparison)dm.CreateDelegate(typeof(Comparison));
}

Emitting IL by hand is not pretty (see my previous post for an idea to improve this problem). Using Reflector (or ILdasm) certainly is a must if, like me, you are an IL newbie. I wrote some simple example methods in C#, compiled them, then viewed in Reflector to see the IL they produced.

The end result in my speed test harness was BindingListView sort actually out performing the DataView!
Using 200,000 objects (10x more than the reported amount). Sorting on an Int32 property.
Old BindingListView took 146,823ms
New BindingListView took 16,564ms
DataView took 20,654ms

All the code is online at Source Forge


Google Ads

Search this blog

Most recent comments

  • I scratched my eye while i was holding some kind of plastic packaging.. Anyways the corner of the pl… by Ercan on this entry
  • About a year ago my contacts that i was wearing, i guess were fautly, because shortly after they wer… by Jon on this entry
  • I got shower gel in my eye 4 and a half days ago, and becasue i rubbed my eyes a lot, i have scratch… by Chris on this entry
  • This website may help http://www.webmd.com/eye–health/tc/Eye–Injuries–Home–Treatment by S on this entry
  • I somehow got dirt, or debris in my eye. The terrible pain sent me in a tailspin. I was afraid of sa… by Bobbi on this entry

Tags

August 2006

Mo Tu We Th Fr Sa Su
Jul |  Today  | Sep
   1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31         

Galleries

Blog archive

Loading…
Not signed in
Sign in

Powered by BlogBuilder
© MMXXI