Thursday, March 09, 2006

Extending dynamic sorting of objects using lightweight code generation.

UPDATE: This project is hosted on CodePlex as the Dynamic Reflection Library for all further updates.
RE: Dynamic sorting of objects using lightweight code generation.

I got a report of issues sorting objects that have null (not Nullable<T>) values. In the previous implementation, I blindly call down to the CompareTo method associated with the property's Type. This obviously doesn't work with virtual methods. For some types (like String) it was enough to simply make the emitted code a Call instead of a CallVirt, but I didn't want to be half-right. So the new version does the right thing and handles the null-checks for the left and right filed/property values.

The emitted code is slightly more complex, but still about as fast as I now check for IsFinal methods and use Call instead of CallVirt when possible. This optimization is in place for property get calls, and the call the CompareTo, so it is a bit faster.

I also fixed an issue if you compared a whole bunch of attributes and blew the generate IL so large that the loop-break label wasn't reachable by a short branch (nobody reported this, just noticed in code review).

I've updated both the DynamicSorter.zip file and the Utilites.zip file (the latter has other updates to improve fxCop compliance).

The emitted code for "FirstName, lastName, Gender" [String property, double field, Enum property, respectively] now looks like this:

IL_0000:  ldarg.0 
IL_0001:  callvirt   System.String get_FirstName()/DynamicComparerSample.Person
IL_0006:  dup     
IL_0007:  brtrue.s   IL_0018
IL_0009:  pop     
IL_000a:  ldarg.1 
IL_000b:  callvirt   System.String get_FirstName()/DynamicComparerSample.Person
IL_0010:  brtrue.s   IL_0015
IL_0012:  ldc.i4.0
IL_0013:  br.s       IL_0023
IL_0015:  ldc.i4.m1
IL_0016:  br.s       IL_0023
IL_0018:  ldarg.1 
IL_0019:  callvirt   System.String get_FirstName()/DynamicComparerSample.Person
IL_001e:  call       Int32 CompareTo(System.String)/System.String
IL_0023:  dup     
IL_0024:  brtrue     IL_0060
IL_0029:  pop     
IL_002a:  ldarg.0 
IL_002b:  ldfld      Double age/DynamicComparerSample.Person
IL_0030:  stloc.0 
IL_0031:  ldloca.s   V_0
IL_0033:  ldarg.1 
IL_0034:  ldfld      Double age/DynamicComparerSample.Person
IL_0039:  call       Int32 CompareTo(Double)/System.Double
IL_003e:  dup     
IL_003f:  brtrue     IL_0060
IL_0044:  pop     
IL_0045:  ldarg.0 
IL_0046:  callvirt   DynamicComparerSample.Gender get_Gender()/DynamicComparerSample.Person
IL_004b:  box        DynamicComparerSample.Gender
IL_0050:  ldarg.1 
IL_0051:  callvirt   DynamicComparerSample.Gender get_Gender()/DynamicComparerSample.Person
IL_0056:  box        DynamicComparerSample.Gender
IL_005b:  call       Int32 CompareTo(System.Object)/System.Enum
IL_0060:  ret

4 comments:

Joe Duffy said...

Hi Marc,

I received your question from my blog. Emitting an ordinary 'call' for final methods, and 'callvirt' for others, is OK. However, you could actually just use 'callvirt's for all methods, and the CLR's JIT compiler will be intelligent enough to use a static dispatch when it knows it's safe to do so. This is what the C# 2.0 compiler does.

Cheers,
joe

IDisposable said...

Thanks for the input. I realized that the callvirt was safe in either case, but my benchmarks actually showed a bit better performance for call. Odd. Is checking IsFinal the best way to know it's safe, since I know the type of the variable, it seems safe.

Ryan Boud at hotmail dot com said...

We have a list objects with a property that we are trying to sort by. The propery in question is another list of objects.

The first list made of an object with a property:

Property Offices as List(of MarketingOffice)
...

MarketingOffice
Property Branch as Office
Property IsPrimary as Boolean
...
Office
Property Code as Char
...

We need to be able to sort by offices. The original list has two objects in.

Object 1
Offices=
{MarketingOffice, Primary=True, Branch = Office, Code = H}
{MarketingOffice, Primary=False, Branch = Office, Code = M}

Object 2
Offices=
{MarketingOffice, Primary=True, Branch = Office, Code = M}

We need to able to do a sort by Offices and have the results come out:

H,M
M

When use the dynamic comparer we get the following:

GenericArguments[0], 'Business.Entities.MarketingOffice', on 'System.Nullable`1[T]' violates the constraint of type parameter 'T'.

It is throwing an exception at:
public static bool IsComparable(Type valueType, out bool isNullable)
{
isNullable = valueType.IsGenericType
&& !valueType.IsGenericTypeDefinition
&& valueType.IsAssignableFrom(typeof(Nullable<>).MakeGenericType(valueType.GetGenericArguments()[0]));

return (typeof(IComparable).IsAssignableFrom(valueType)
|| typeof(IComparable<>).MakeGenericType(valueType).IsAssignableFrom(valueType)
|| isNullable);
}

Please help...

IDisposable said...

If you can send me a simple class that has the properties you are trying to use, I'll happily fix it. You can attach it up on CodePlex.