Lightweight Code Generation with Linq Expressions

16 November 2007 Kris-Vandermotten LINQ

Linq expressions are the key ingredient behind the IQueryable<T> interface. One aspect of them, largely underestimated if you ask me, is the fact they can be compiled into executable code at runtime.

Let's look at a concrete example: a generic comparer, which compares objects based on one of their properties. Take a Person class, with a Name property (amongst others), and you want to sort a List<Person> by Name. Sure, if you statically know, at compile time that is, the property on which to sort, you can simply use the Linq orderby operator and pass it the Lambda to extract the property value. But what if you don't know the property statically? What if you need to be able to sort any type on any of its properties?

In that case you need a way to extract the property dynamically. Reflection can do the job, but it's slow. With Reflection.Emit you can generate a DynamicMethod, but Expressions provide an easier alternative.

The function I need will have three parameters:

var x = Expression.Parameter(typeof(TObject), "x");
var y = Expression.Parameter(typeof(TObject), "y");
var c = Expression.Parameter(typeof(IComparer<TProperty>), "c");

Given a PropertyInfo (or just a name) for the property, I can generate and expression for the function and compile it:

compare = Expression.Lambda<Func<TObject, TObject, IComparer<TProperty>, int>>
     (
         Expression.Call(
             c,
             "Compare", null,
             Expression.Property(x, propertyInfo),
             Expression.Property(y, propertyInfo)),
         x, y, c
     ).Compile();


That's really all there is to it. I can then wrap this function into an IComparer<TObject>, as shown below.

Why bother? Sure, generation of the comparer will take its fair share of CPU cycles. But execution of the comparer will be a lot faster. When I need to sort, say, 10 objects, it doesn't matter, that will be done quickly enough either way. But when I need to sort thousands of objects, this technique can offer a significant speedup.

And what alternatives do I have? I could use DynamicMethod, which is what I used to do before .NET 3.5. In fact, that's exactly what the Compile() method on an expression is doing. The generated function would be no different, but the generation code definitely is more difficult and error prone to write. Both options share the fact that I'm doing a delegate call for every comparison. I could get rid of that delegate call by generating a full assembly using Reflection.Emit. But then I need to worry about memory leaks, because I can't unload the assembly.

Expressions aren't as powerful as the raw DynamicMethod, but they're easier to use. That's why I prefer them over DynamicMethod whenever I can.

Full source code for the example, including a SortedBindingList<T> that uses PropertyComparer<T>:

using System; 
using System.Collections.Generic; 
using System.ComponentModel;
using System.Linq.Expressions; 
using System.Reflection;  
 
namespace Vandermotten.Collections.Generic 
{
    public class PropertyComparer<TObject>
    {
        public static IComparer<TObject> Create(string propertyName)
        {
            return Create(propertyName, ListSortDirection.Ascending);
        }
 
        public static IComparer<TObject> Create(string propertyName, ListSortDirection direction)
        {
             return Create(typeof(TObject).GetProperty(propertyName), direction);
        }
 
        public static IComparer<TObject> Create(PropertyInfo propertyInfo)
        {
            return Create(propertyInfo, ListSortDirection.Ascending);
        }
 
        public static IComparer<TObject> Create(PropertyInfo propertyInfo, ListSortDirection direction)
        {
            if (propertyInfo == null)
            {
                throw new ArgumentNullException("propertyInfo");
            }
            if (!propertyInfo.CanRead)
            {
                throw new ArgumentException("Cannot read property " + propertyInfo.Name);
            }
            Type cT = typeof(Comp<>).MakeGenericType(typeof(TObject), propertyInfo.PropertyType);
            return (IComparer<TObject>)Activator.CreateInstance(cT, propertyInfo, direction);
        }
 
        private class Comp<TProperty> : IComparer<TObject>
        {
            private Comparer<TProperty> comparer;
 
            public Comp(PropertyInfo propertyInfo, ListSortDirection direction)
            {
                comparer = Comparer<TProperty>.Default;
 
                var x = Expression.Parameter(typeof(TObject), "x");
                var y = Expression.Parameter(typeof(TObject), "y");
                var c = Expression.Parameter(typeof(IComparer<TProperty>), "c");
 
                if (direction == ListSortDirection.Ascending)
                {
                    compare = Expression.Lambda<Func<TObject, TObject, IComparer<TProperty>, int>>
                        (
                            Expression.Call(
                                c,
                                "Compare", null,
                                Expression.Property(x, propertyInfo),
                                Expression.Property(y, propertyInfo)),
                            x, y, c
                        ).Compile();
                }
                else
                {
                    compare = Expression.Lambda<Func<TObject, TObject, IComparer<TProperty>, int>>
                        (
                            Expression.Call(
                                c,
                                "Compare", null,
                                Expression.Property(y, propertyInfo),
                                Expression.Property(x, propertyInfo)),
                            x, y, c
                        ).Compile();
                }
            }
 
            Func<TObject, TObject, IComparer<TProperty>, int> compare;
 
            public int Compare(TObject x, TObject y)
            {
                return compare(x, y, comparer);
            }
        }
    } 
 
    public class SortedBindingList<T> : BindingList<T>
    { 
        private bool sorted; 
        private ListSortDirection sortDirection = ListSortDirection.Ascending; 
        private PropertyDescriptor sortProperty; 
 
        public SortedBindingList() 
        { 
        }  
 
        public SortedBindingList(List<T> list) 
            : base (list) 
        { 
        }
 
        protected override void ApplySortCore(PropertyDescriptor prop, ListSortDirection direction) 
        { 
            List<T> items = Items as List<T>; 
            if (items != null) 
            { 
                sortDirection = direction; 
                sortProperty = prop; 
                IComparer<T> pc = PropertyComparer<T>.Create(prop.Name, direction); 
                items.Sort(pc); 
                sorted = true; 
            } 
            else 
            { 
                sorted = false; 
            } 
        } 
 
        protected override void RemoveSortCore() 
        { 
            sorted = false; 
        } 
 
        protected override bool SupportsSortingCore 
        { 
            get { return true; } 
        } 
 
        protected override bool IsSortedCore 
        { 
            get { return sorted; } 
        } 
 
        protected override ListSortDirection SortDirectionCore 
        { 
            get { return sortDirection; } 
        } 
 
        protected override PropertyDescriptor SortPropertyCore 
        { 
            get { return sortProperty; } 
        } 
    } 
}

 

Tags : ,