Wednesday, February 15, 2006

Dynamic sorting of objects using lightweight code generation.

UPDATE: This project is hosted on CodePlex as the Dynamic Reflection Library for all further updates.

I looked into the cool Dynamic List Sorting package on CodeProject. It's pretty good, but I wanted to get the absolute best performance for my framework, so I optimized the generated IL some [download here]. I've eliminated the local variable used to track the comparison- thus-far as it is always zero until we've got a mismatch. I've also added the ability to reference fields (as well as properties), and added flags to the DynamicMethod constructor to bypass accessiablity checks (allows access to private members).

This new version is very fast. In debug builds, property access is around 5-25% slower than field access, the cost of delegate invocation is about 15% and the cost of element-by-element versus using the object's ICompare method is 4%.

Here's the chart for sorting 500,000 Person objects (in seconds):

Sort ByFieldPropertyCost of propertyCost of dynamic
Age (double)2.172.7024.42%
LastName (string)2.602.766.15%
LastName,FirstName,Age7.177.9911.44%3.21%
Dynamic whole object7.4015.09%
Built-in whole object6.43

Sorting by "FirstName, lastName, Age" [property,field,property respectively] results in this generated IL (through the cool DebuggerVisualizer mentioned here)

IL_0000: ldarg.0  
IL_0001: callvirt   System.String get_FirstName()/DynamicComparerSample.Person
IL_0006: ldarg.1  
IL_0007: callvirt   System.String get_FirstName()/DynamicComparerSample.Person
IL_000c: callvirt   Int32 CompareTo(System.String)/System.String
IL_0011: dup      
IL_0012: brtrue.s   IL_0046
IL_0014: pop      
IL_0015: ldarg.0  
IL_0016: ldfld      System.String lastName/DynamicComparerSample.Person
IL_001b: ldarg.1  
IL_001c: ldfld      System.String lastName/DynamicComparerSample.Person
IL_0021: callvirt   Int32 CompareTo(System.String)/System.String
IL_0026: dup      
IL_0027: brtrue.s   IL_0046
IL_0029: pop      
IL_002a: ldarg.0  
IL_002b: callvirt   Double get_Age()/DynamicComparerSample.Person
IL_0030: stloc      V_0
IL_0034: nop      
IL_0035: nop      
IL_0036: ldloca.s   V_0
IL_0038: nop      
IL_0039: nop      
IL_003a: nop      
IL_003b: ldarg.1  
IL_003c: callvirt   Double get_Age()/DynamicComparerSample.Person
IL_0041: callvirt   Int32 CompareTo(Double)/System.Double
IL_0046: ret

Edit: I forgot the call to .Compare in the benchmark, which saves a LOT of time because then the object isn't wrapped in another delegate deep in the guts of the FCL. Numbers above have been updated.

UPDATE: Revised extensively to handle nulls and faster performance. See this.

UPDATE: Revised links to point to GooglePages so I'm not serving the files from my DSL.

10 comments:

IDisposable said...

Rich reported a bug (oops, deleted the comment) when comparing Enum values. I've updated the DynamicComparer and Utilities zips to have the fix. Seems you need to box Enum(s) before calling System.Enum.CompareTo() -- odd...

Vlado said...

Hi Marc, I'm trying to sort strings where some of them are null and I am getting NullReferenceException. Is it by design? I don't have any experience in IL. How should I change IL code to enable sorting of null strings too? Thanks!

Vlado said...

I've got it! I implemented there my custom Compare method instead of CompareTo method and changed Callvirt to Call. Thanks anyway for great DynamicComparer!

IDisposable said...

Updated the code (extensively) to handle reference-types that are nullable. This adds a little to the overhead, but prevents you from having to special-case the CompareTo methods. See this post.

IDisposable said...

Revisions are here

Anonymous said...

Any idea how to make this work with a list of structs instead of a list of classes? It throws an AccessViolation ever time I try.

IDisposable said...

If you've got a class (or list) that shows this error, I'll extend it to handle that situation. BTW, I can't contact you if you post anonymously!

If desired, mail me directly at IDisposable@gmail.com

IDisposable said...

The class now handles structs just fine, see download link at top of the post.

mtsu_bravo said...

Are you still working on this? I am using nhibernate to populate my objects and works fine as long as the object is completely populated. I modified your code to accept nested objects and that works. but now if an object has a nested object that has a value of null but is not a nullable object it blows up when tring to compair the two. Any suggestions?

IDisposable said...

I've put this project up on CodePlex for further development, so it would be best to open an issue there. If you can give me a simple (not full NHibernate) example that I can include in the test suite, I will happily fix it.