Consider the following simple manipulation over a collection:
static List<int> x = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var result = x.Where(i => i % 2 == 0).Where(i => i > 5);
Now let's use Expressions. The following code is roughly equivalent:
static void UsingLambda() {
Func<IEnumerable<int>, IEnumerable<int>> lambda = l => l.Where(i => i % 2 == 0).Where(i => i > 5);
var t0 = DateTime.Now.Ticks;
for (int j = 1; j < MAX; j++)
var sss = lambda(x).ToList();
var tn = DateTime.Now.Ticks;
Console.WriteLine("Using lambda: {0}", tn - t0);
}
But I want to build the expression on-the-fly, so here's a new test:
static void UsingCompiledExpression() {
var f1 = (Expression<Func<IEnumerable<int>, IEnumerable<int>>>)(l => l.Where(i => i % 2 == 0));
var f2 = (Expression<Func<IEnumerable<int>, IEnumerable<int>>>)(l => l.Where(i => i > 5));
var argX = Expression.Parameter(typeof(IEnumerable<int>), "x");
var f3 = Expression.Invoke(f2, Expression.Invoke(f1, argX));
var f = Expression.Lambda<Func<IEnumerable<int>, IEnumerable<int>>>(f3, argX);
var c3 = f.Compile();
var t0 = DateTime.Now.Ticks;
for (int j = 1; j < MAX; j++)
var sss = c3(x).ToList();
var tn = DateTime.Now.Ticks;
Console.WriteLine("Using lambda compiled: {0}", tn - t0);
}
Of course it isn't exactly like the above, so to be fair, I modify the first one slightly:
static void UsingLambdaCombined() {
Func<IEnumerable<int>, IEnumerable<int>> f1 = l => l.Where(i => i % 2 == 0);
Func<IEnumerable<int>, IEnumerable<int>> f2 = l => l.Where(i => i > 5);
Func<IEnumerable<int>, IEnumerable<int>> lambdaCombined = l => f2(f1(l));
var t0 = DateTime.Now.Ticks;
for (int j = 1; j < MAX; j++)
var sss = lambdaCombined(x).ToList();
var tn = DateTime.Now.Ticks;
Console.WriteLine("Using lambda combined: {0}", tn - t0);
}
Now comes the results for MAX = 100000, VS2008, debugging ON:
Using lambda compiled: 23437500
Using lambda: 1250000
Using lambda combined: 1406250
And with debugging OFF:
Using lambda compiled: 21718750
Using lambda: 937500
Using lambda combined: 1093750
Surprise. The compiled expression is roughly 17x slower than the other alternatives. Now here comes the questions:
l.Where(i => i % 2 == 0).Where(i => i > 5);
programatically?Some more statistics. Visual Studio 2010, debugging ON, optimizations OFF:
Using lambda: 1093974
Using lambda compiled: 15315636
Using lambda combined: 781410
Debugging ON, optimizations ON:
Using lambda: 781305
Using lambda compiled: 15469839
Using lambda combined: 468783
Debugging OFF, optimizations ON:
Using lambda: 625020
Using lambda compiled: 14687970
Using lambda combined: 468765
New Surprise. Switching from VS2008 (C#3) to VS2010 (C#4), makes the UsingLambdaCombined
faster than the native lambda.
Ok, I've found a way to improve the lambda compiled performance by more than an order of magnitude. Here's a tip; after running the profiler, 92% of the time is spent on:
System.Reflection.Emit.DynamicMethod.CreateDelegate(class System.Type, object)
Hmmmm... Why is it creating a new delegate in every iteration? I'm not sure, but the solution follows in a separate post.
Could it be that the inner lambdas are not being compiled?!? Here's a proof of concept:
static void UsingCompiledExpressionWithMethodCall() {
var where = typeof(Enumerable).GetMember("Where").First() as System.Reflection.MethodInfo;
where = where.MakeGenericMethod(typeof(int));
var l = Expression.Parameter(typeof(IEnumerable<int>), "l");
var arg0 = Expression.Parameter(typeof(int), "i");
var lambda0 = Expression.Lambda<Func<int, bool>>(
Expression.Equal(Expression.Modulo(arg0, Expression.Constant(2)),
Expression.Constant(0)), arg0).Compile();
var c1 = Expression.Call(where, l, Expression.Constant(lambda0));
var arg1 = Expression.Parameter(typeof(int), "i");
var lambda1 = Expression.Lambda<Func<int, bool>>(Expression.GreaterThan(arg1, Expression.Constant(5)), arg1).Compile();
var c2 = Expression.Call(where, c1, Expression.Constant(lambda1));
var f = Expression.Lambda<Func<IEnumerable<int>, IEnumerable<int>>>(c2, l);
var c3 = f.Compile();
var t0 = DateTime.Now.Ticks;
for (int j = 1; j < MAX; j++)
{
var sss = c3(x).ToList();
}
var tn = DateTime.Now.Ticks;
Console.WriteLine("Using lambda compiled with MethodCall: {0}", tn - t0);
}
And now the timings are:
Using lambda: 625020
Using lambda compiled: 14687970
Using lambda combined: 468765
Using lambda compiled with MethodCall: 468765
Woot! Not only it is fast, it is faster than the native lambda. (Scratch head).
Of course the above code is simply too painful to write. Let's do some simple magic:
static void UsingCompiledConstantExpressions() {
var f1 = (Func<IEnumerable<int>, IEnumerable<int>>)(l => l.Where(i => i % 2 == 0));
var f2 = (Func<IEnumerable<int>, IEnumerable<int>>)(l => l.Where(i => i > 5));
var argX = Expression.Parameter(typeof(IEnumerable<int>), "x");
var f3 = Expression.Invoke(Expression.Constant(f2), Expression.Invoke(Expression.Constant(f1), argX));
var f = Expression.Lambda<Func<IEnumerable<int>, IEnumerable<int>>>(f3, argX);
var c3 = f.Compile();
var t0 = DateTime.Now.Ticks;
for (int j = 1; j < MAX; j++) {
var sss = c3(x).ToList();
}
var tn = DateTime.Now.Ticks;
Console.WriteLine("Using lambda compiled constant: {0}", tn - t0);
}
And some timings, VS2010, Optimizations ON, Debugging OFF:
Using lambda: 781260
Using lambda compiled: 14687970
Using lambda combined: 468756
Using lambda compiled with MethodCall: 468756
Using lambda compiled constant: 468756
Now you could argue that I'm not generating the whole expression dynamically; just the chaining invocations. But in the above example I generate the whole expression. And the timings match. This is just a shortcut to write less code.
From my understanding, what is going on is that the .Compile() method does not propagate the compilations to inner lambdas, and thus the constant invocation of CreateDelegate
. But to truly understand this, I would love to have a .NET guru comment a little about the internal stuff going on.
And why, oh why is this now faster than a native lambda!?
Recently I asked an almost identical question:
Performance of compiled-to-delegate Expression
The solution for me was that I shouldn't call Compile
on the Expression
, but that I should call CompileToMethod
on it and compile the Expression
to a static
method in a dynamic assembly.
Like so:
var assemblyBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(
new AssemblyName("MyAssembly_" + Guid.NewGuid().ToString("N")),
AssemblyBuilderAccess.Run);
var moduleBuilder = assemblyBuilder.DefineDynamicModule("Module");
var typeBuilder = moduleBuilder.DefineType("MyType_" + Guid.NewGuid().ToString("N"),
TypeAttributes.Public));
var methodBuilder = typeBuilder.DefineMethod("MyMethod",
MethodAttributes.Public | MethodAttributes.Static);
expression.CompileToMethod(methodBuilder);
var resultingType = typeBuilder.CreateType();
var function = Delegate.CreateDelegate(expression.Type,
resultingType.GetMethod("MyMethod"));
It's not ideal however. I'm not quite certain to which types this applies exactly, but I think that types that are taken as parameters by the delegate, or returned by the delegate have to be public
and non-generic. It has to be non-generic because generic types apparently access System.__Canon
which is an internal type used by .NET under the hood for generic types and this violates the "has to be a public
type rule).
For those types, you can use the apparently slower Compile
. I detect them in the following way:
private static bool IsPublicType(Type t)
{
if ((!t.IsPublic && !t.IsNestedPublic) || t.IsGenericType)
{
return false;
}
int lastIndex = t.FullName.LastIndexOf('+');
if (lastIndex > 0)
{
var containgTypeName = t.FullName.Substring(0, lastIndex);
var containingType = Type.GetType(containgTypeName + "," + t.Assembly);
if (containingType != null)
{
return containingType.IsPublic;
}
return false;
}
else
{
return t.IsPublic;
}
}
But like I said, this isn't ideal and I would still like to know why compiling a method to a dynamic assembly is sometimes an order of magnitude faster. And I say sometimes because I've also seen cases where an Expression
compiled with Compile
is just as fast as a normal method. See my question for that.
Or if someone knows a way to bypass the "no non-public
types" constraint with the dynamic assembly, that's welcome as well.