Dynamic List Sorting

• Download source and sample files - 8.91 Kb

Introduction

This article spawned from a post on the Danish site DotNetForum.dk. The poster asked how you would go about sorting a list of, say, person objects, in a dynamic fashion like SQL. At that point, somebody mentioned the IComparer and IComparer<> interfaces and that you probably could make some sort of generic comparer using those interfaces. And a link to an article by Peter Provost named “Generic Property Comparer Class” was also provided. The article explains how to make a generic comparer using IComparer in .NET 1.1. Peter’s solution is okay considering .NET 1.1 but it’s rather bad in a .NET 2.0 context for several reasons:

1. It only sorts one property at a time.
2. It only sorts in ascending order.
3. It isn’t strongly typed.
4. It is very slow!

Note: Point 3 and 4 are just an artifact of the fact that .NET 1.1 is lacking both generics and dynamic methods.

So this made me decide that I would try to come up with a better solution utilizing the new generics in .NET 2.0 plus some other very cool features of the framework.

A key point to keep in mind when starting a project like this is performance. I mean, nobody wants to wait 5 seconds while a list gets sorted. Another key point in this project was that it should be dynamic and should, if possible, enable the user to enter a string with a SQL “Order By” like syntax, e.g., “FirstName, Age DESC, LastName”.

The Solution

The first solution I jammed out was a comparer which only used generics and was able to sort ascending as well as descending on any number of properties. So this solution met most of the important requirements. However, even though I made this before I saw Peter's 1.1 solution, they were in fact very similar except mine used generics for specifying the type of objects whereas in Peter’s solution, you pass in the item type as a parameter. Unfortunately, this solution also had the performance problem. After a few performance tests, it was clear to me that this solution was not an option.

The problem is that you can’t really fulfill the requirements without dynamically generating some amount of specific code. At least, that was the conclusion I made after a while. Fortunately, .NET 2.0 has a new feature called “dynamic methods”.

A “dynamic method” is a method you create in-memory during runtime. I won’t dive deeper into this subject but I recommend that you check it out. Basically, what I do is I compile a strongly typed version of the “Compare” method in-memory and call it using a delegate. As you will see in the next section, this is a very powerful way of getting a strongly typed method while keeping it completely dynamic and very fast.

Performance Comparison

I’ve done a few performance tests of the most commonly used sorting methods along with Peter Provost’s solution. The results are listed below:

Fig. 1: Sorting times for 10 to 100000 items.

As you see in fig. 1, the dynamic comparer solution is a good way of sorting your custom entity lists. The dynamic comparer is sharing the first place with the hard-coded comparer. The hard-coded comparer seems to be starting out slowly but that is just a measuring error. This clearly shows that from the runtime's perspective, the dynamic method used to sort is pretty much like the hard-coded one except that we call it through a delegate.

On the second place, we have both the weakly and the strongly typed datasets. Both of them are following the same line which is a little steeper than the other methods. That means that they are getting slower at a faster rate compared to the other methods. Some might think that the strongly typed dataset should be sorting faster than the weakly typed dataset but think again… The strongly typed dataset is just an overloaded version of the weakly typed dataset, so in fact, it is using the same sorting methods as the weakly typed version. It is also worth mentioning that populating a dataset with 10000 items or more is much slower than populating the regular lists.

Finally, on the third place, we have the generic class comparer. As you can see, it is much slower than the other methods of sorting. Not because it is badly designed or coded, but because .NET 1.1 supports neither generics nor dynamic methods.

Usage

So how do you use this comparer? Well, it’s as easy as 1-2-3:

//Example:
string orderBy = "FirstName, LastName DESC"; // 1
DynamicComparer<Person> comparer = new DynamicComparer<Person>(orderBy); // 2
persons.Sort(comparer.Compare); // 3

1. Declare a sort string or a SortProperty array. Note: This could be created and maintained by a custom editgrid.
2. Declare an instance of the DynamicComparer class using the generic constructor.
3. Call the sort method on the List<Person>.

That’s it!

So what’s going on behind the scenes? Let’s begin at line 2 of the previous example. At the time of instantiation of the DynamicComparer, the class will first parse the input string into a SortProperty array. These SortProperties will then be validated against the type we specified when instantiating the DynamicComparer, in this case, “Person”. This validation checks if the Person class is public, if it has any public properties named “FirstName” and “LastName”, if these properties are readable, and finally, if these properties are of a type that implements the IComparable interface. If any of these validations fail, the class will throw an exception. If the validation succeeds, the class will then generate a dynamic method using the specified SortPropertyies and instantiate an internal delegate pointing to the method. The “Compare” method on the DynamicComparer will then in turn be able to invoke this delegate when called. This means that the comparer is ready for use.

Note: If you want to change the sorting of an instance of the DynamicComparer, you can call the “Initialize” method on the instance and pass in a new ORDER BY string or a SortProperty array.

At the next step, we call the “Sort” method on the “persons” list passing in a reference to the comparer.Compare method.

Conclusion

The dynamic comparer seems to be a very efficient way of getting a flexible comparer while keeping it fast, and I’ve yet to see a better or even just a different solution that has the same flexibility and performance. Still, a couple of things could be improved in the comparer but mostly in the instantiation process. I leave it to you to come up with new suggestions and ideas to improve the comparer. I'm looking forward for your feedback!