Generating a fast sort function at runtime using Expression-Trees

Question

I have code to generate sorting functions for any type at run-time using expression trees. The example below sorts by public int or string properties, but is easily extended to include properties of other types. Generated sorting functions are approximately 4x slower than the equivalent function written by hand. Execution time vs the hand coded version was compared using benchmarkdotnet. How could the generation code be changed to generate faster sort functions?

public class SortBy
{
    public bool Ascending { get; set; }
    public string PropName {get; set;}
}

public static class SortFuncCompiler
{
    private static readonly MethodInfo _strCompareTo = typeof(string).GetMethod("CompareTo", new[] {typeof(string)});
    private static readonly MethodInfo _intCompareTo = typeof(int).GetMethod("CompareTo", new[] {typeof(int)});

    public static Func<T,T,int> MakeSortFunc<T>(IList<SortBy> sortDescriptors)
    {
        ParameterExpression param1Expr = Expression.Parameter(typeof(T));
        ParameterExpression param2Expr = Expression.Parameter(typeof(T));
        BlockExpression exprSd = MakeCompositeCompare(param1Expr, param2Expr, sortDescriptors);
        Expression<Func<T,T,int>> lambda = Expression.Lambda<Func<T,T,int>>(exprSd, param1Expr, param2Expr);
        return lambda.Compile();
    }

    private static BlockExpression MakePropertyCompareBlock(
        SortBy sortDescriptor, 
        ParameterExpression rm1, 
        ParameterExpression rm2, 
        LabelTarget labelReturn,
        ParameterExpression result)
    {
        try
        {
            MemberExpression propA = Expression.Property(rm1, sortDescriptor.PropName);
            MemberExpression propB = Expression.Property(rm2, sortDescriptor.PropName);
            var (prop1, prop2) = sortDescriptor.Ascending ? (propA, propB) : (propB, propA);

            Expression compareExpr;

            if(prop1.Type == typeof(string))
            {
                compareExpr = Expression.Call(prop1, _strCompareTo, prop2);
            }
            else if(prop1.Type == typeof(int))
            {
                compareExpr = Expression.Call(prop1, _intCompareTo, prop2);
            }
            else
            {
                throw new ApplicationException($"unsupported property type: {prop1.Type}");
            }

            IEnumerable<ParameterExpression> variables = new[] {result};

            IEnumerable<Expression> expressions = new Expression[]
            {
                Expression.Assign(result, compareExpr),
                Expression.IfThen(
                    Expression.NotEqual(Expression.Constant(0), result),
                    Expression.Goto(labelReturn, result))
            };

            return Expression.Block(variables, expressions);
        }
        catch
        {
            throw new ApplicationException($"unknown property: {sortDescriptor.PropName}");
        }       
    }

    private static BlockExpression MakeCompositeCompare(ParameterExpression param1Expr, ParameterExpression param2Expr, IEnumerable<SortBy> sortBys )
    {
        ParameterExpression result = Expression.Variable(typeof(int), "result");
        LabelTarget labelReturn = Expression.Label(typeof(int));
        LabelExpression labelExpression = Expression.Label(labelReturn, result);
        IEnumerable<Expression> compareBlocks = sortBys.Select(propName => MakePropertyCompareBlock(propName, param1Expr, param2Expr, labelReturn, result));
        return Expression.Block(new[] {result}, compareBlocks.Append(labelExpression));         
    }

}

how to use the generated sort function

public class MyComparer<T> : IComparer<T>
{
    private Func<T, T, int> _sortFunc;

    public MyComparer(Func<T, T, int> sortFunc)
    {
        _sortFunc = sortFunc;
    }

    public int Compare(T x, T y) => _sortFunc(x, y);
}


//the expression-tree generated sorting function should be of form
static int SortOneIntOneStrHC(MyClass aa, MyClass bb)
{
    int s1 = aa.IntProp1.CompareTo(bb.IntProp1);

    if (s1 != 0) return s1;

    // aa and bb flipped, as this comparison is descending
    return bb.StrProp1.CompareTo(aa.StrProp1);
}


public class MyClass
{
    public int IntProp1 { get; set; }
    public int IntProp2 { get; set; }
    public string StrProp1 { get; set; }
    public string StrProp2 { get; set; }
}


void Main()
{
    var xs = new List<MyClass>
    {
        new MyClass{IntProp1 = 99, IntProp2 = 88, StrProp1 = "aa", StrProp2 ="bb"},
        new MyClass{IntProp1 = 11, IntProp2 = 22, StrProp1 = "xx", StrProp2 ="yy"},
        new MyClass{IntProp1 = 11, IntProp2 = 22, StrProp1 = "pp", StrProp2 ="qq"},
    };

    var sortBys = new List<SortBy>
    {
        new SortBy{PropName = "IntProp2", Ascending = true},
        new SortBy{PropName = "StrProp1", Ascending = false}
    };

    Func<MyClass, MyClass, int> sortMyClass = SortFuncCompiler.MakeSortFunc<MyClass>(sortBys);

    var ys = xs.OrderBy(x => x, new MyComparer<MyClass>(sortMyClass));

    ys.Dump(); 
}

Answer 1

• First of all write benchmarks to compare your generated methods with native methods using Benchmarkdotnet. Later you can define whether your changes make your code better in terms of performance
• To run .Compile() on expression tree is quite heavy. You should create compiled delegate once for particular case Func<T,T,int> and cache it.

Answer 2

I made wrote benchmark, and results was pretty close native vs expression:

| Method |     N |       Mean |      Error |     StdDev |     Median |
|------- |------ |-----------:|-----------:|-----------:|-----------:|
|   Linq |  1000 |   196.6 us |   3.431 us |   3.209 us |   197.5 us |
| Native |  1000 |   215.8 us |   8.043 us |  21.881 us |   208.0 us |
|   Linq | 10000 | 3,094.8 us | 108.795 us | 306.857 us | 2,991.8 us |
| Native | 10000 | 3,078.2 us | 104.824 us | 107.647 us | 3,056.5 us |

Maybe you have some bugs in benchmark code itself. Here is what I used:

public class Benchmark
{
    private MyClass[] data;

    private MyComparer<MyClass> linqComparer;

    private MyComparer<MyClass> nativeComparer;

    [Params(1000, 10000)]
    public int N;

    [GlobalSetup]
    public void Setup()
    {
        var random = new Random();

        data = new MyClass[N];
        for (int i = 0; i < N; ++i)
        {
            data[i] = MyClass.Generate(random, N*10, 25);
        }

        // Compile order methods
        List<SortBy> sortBys = new List<SortBy>
        {
            new SortBy{PropName = "IntProp2", Ascending = true},
            new SortBy{PropName = "StrProp1", Ascending = false}
        };
        Func<MyClass, MyClass, int> sortMyClass = SortFuncCompiler.MakeSortFunc<MyClass>(sortBys);

        linqComparer = new MyComparer<MyClass>(sortMyClass);
        nativeComparer = new MyComparer<MyClass>(Sorters.SortOneIntOneStrHC);
    }

    [Benchmark]
    public MyClass[] Linq()
    {
        return data.OrderBy(x => x, linqComparer).ToArray();
    }

    [Benchmark]
    public MyClass[] Native()
    {
        return data.OrderBy(x => x, nativeComparer).ToArray();
    }
}

public class Program
{
    public static void Main()
    {
        var summary = BenchmarkRunner.Run<Benchmark>();
    }
}

The most important here is to compile sorter in setup method, not in benchmark.