Скомпилированные выражения С# Lambda Expressions
Рассмотрим следующие простые манипуляции над коллекцией:
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);
Теперь позвольте использовать выражения. Следующий код примерно эквивалентен:
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);
}
Но я хочу построить выражение "на лету", поэтому здесь новый тест:
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);
}
Конечно, это не совсем так, как указано выше, поэтому, чтобы быть справедливым, я немного изменяю первый:
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);
}
Теперь идут результаты для MAX = 100000, VS2008, отладка ON:
Using lambda compiled: 23437500
Using lambda: 1250000
Using lambda combined: 1406250
И с отладкой OFF:
Using lambda compiled: 21718750
Using lambda: 937500
Using lambda combined: 1093750
Surprise. Скомпилированное выражение примерно на 17 раз медленнее, чем другие альтернативы. Теперь возникают вопросы:
- Я сравниваю неэквивалентные выражения?
- Есть ли механизм, позволяющий .NET "оптимизировать" скомпилированное выражение?
- Как выражать один и тот же цепной вызов
l.Where(i => i % 2 == 0).Where(i => i > 5); программно?
Еще несколько статистических данных. Visual Studio 2010, отладка включена, оптимизация выключена:
Using lambda: 1093974
Using lambda compiled: 15315636
Using lambda combined: 781410
Отладка включена, оптимизация включена:
Using lambda: 781305
Using lambda compiled: 15469839
Using lambda combined: 468783
Отладка выключена, оптимизация включена:
Using lambda: 625020
Using lambda compiled: 14687970
Using lambda combined: 468765
Новый сюрприз. Переключение с VS2008 (С# 3) на VS2010 (С# 4) делает UsingLambdaCombined быстрее, чем родной лямбда.
Хорошо, я нашел способ улучшить производительность, скомпилированную лямбдой, более чем на порядок. Вот кончик; после запуска профилировщика 92% времени тратится на:
System.Reflection.Emit.DynamicMethod.CreateDelegate(class System.Type, object)
Хмммм... Почему он создает нового делегата на каждой итерации? Я не уверен, но решение следует в отдельном сообщении.
Ответы
Ответ 1
Может ли быть, что внутренние лямбды не компилируются?!? Здесь доказательство понятия:
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);
}
И теперь тайминг:
Using lambda: 625020
Using lambda compiled: 14687970
Using lambda combined: 468765
Using lambda compiled with MethodCall: 468765
Woot! Это не только быстро, но и быстрее, чем родная лямбда. (Царапина).
Конечно, вышеуказанный код просто слишком болезнен для написания. Позвольте сделать простую магию:
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);
}
И некоторые тайминги, VS2010, Оптимизация включена, Отладка отключена:
Using lambda: 781260
Using lambda compiled: 14687970
Using lambda combined: 468756
Using lambda compiled with MethodCall: 468756
Using lambda compiled constant: 468756
Теперь вы можете утверждать, что я не генерирую все выражение динамически; просто цепочки вызовов. Но в приведенном выше примере я генерирую все выражение. И тайминги совпадают. Это просто ярлык, чтобы писать меньше кода.
Из моего понимания, что происходит, метод .Compile() не распространяет компиляции на внутренние lambdas и, следовательно, постоянный вызов CreateDelegate. Но для того, чтобы по-настоящему понять это, я хотел бы немного прокомментировать .NET-гуру о том, что происходит внутри.
И почему, о, почему это сейчас быстрее, чем родной лямбда!?
Ответ 2
Недавно я задал почти одинаковый вопрос:
Выполнение компилированного выражения для делегата
Решение для меня состояло в том, что я не должен называть Compile на Expression, но я должен называть его CompileToMethod и компилировать метод Expression в static в динамической сборке.
Так же:
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"));
Это не идеально. Я не совсем уверен, какие типы это применимы в точности, но я думаю, что типы, которые передаются делегатом в качестве параметров или возвращаются делегатом, должны быть public и неэквивалентными. Он должен быть не общим, потому что типичные типы, по-видимому, получают доступ к System.__Canon, который является внутренним типом, используемым .NET под капотом для общих типов, и это нарушает "должно быть правило типа public).
Для этих типов вы можете использовать, по-видимому, медленнее Compile. Я обнаруживаю их следующим образом:
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;
}
}
Но, как я уже сказал, это не идеально, и мне все равно хотелось бы знать, почему компиляция метода для динамической сборки иногда на порядок быстрее. И я иногда говорю, потому что я также видел случаи, когда Expression, скомпилированный с Compile, так же быстро, как и обычный метод. См. Мой вопрос.
Или, если кто-то знает способ обхода ограничения "не без public" с динамической сборкой, это также приветствуется.
Ответ 3
Скомпилированная производительность лямбда над делегатами может быть медленнее, потому что скомпилированный код во время выполнения не может быть оптимизирован, однако оптимизирован код, написанный вручную, и который скомпилирован с помощью компилятора С#.
Во-вторых, множественные лямбда-выражения означают множество анонимных методов, и вызов каждого из них занимает немного времени, прежде чем оценивать прямой метод. Например, вызов
Console.WriteLine(x);
и
Action x => Console.WriteLine(x);
x(); // this means two different calls..
отличаются друг от друга, и со вторым требуется немного дополнительных затрат, как из перспективы компилятора, а фактически двух разных вызовов. Первый вызов x сам, а затем внутри этого вызывающего оператора x.
Таким образом, ваша объединенная Лямбда, безусловно, будет иметь небольшую медленную производительность по сравнению с одним выражением лямбда.
И это не зависит от того, что выполняется внутри, потому что вы все еще оцениваете правильную логику, но добавляете дополнительные шаги для выполнения компилятором.
Даже после того, как дерево выражений скомпилировано, у него не будет оптимизации, и он все равно сохранит свою небольшую сложную структуру, оценивая и вызывая ее, может иметь дополнительную проверку, проверку нуля и т.д., что может замедлить производительность скомпилированных лямбда-выражений.
Ответ 4
Ваши выражения не эквивалентны, и вы получаете искаженные результаты. Я написал тестовый стенд, чтобы проверить это. Тесты включают обычный лямбда-вызов, эквивалентное скомпилированное выражение, эквивалентное скомпилированное выражение вручную, а также составленные версии. Это должны быть более точные цифры. Интересно, что я не вижу большого различия между равными и составленными версиями. И скомпилированные выражения медленнее, но очень мало. Вам нужно достаточно большое количество ввода и итераций, чтобы получить хорошие цифры. Это имеет значение.
Что касается вашего второго вопроса, я не знаю, как вы сможете получить больше производительности, поэтому я не могу вам помочь. Он выглядит так же хорошо, как и будет.
Вы найдете ответ на свой третий вопрос в методе HandMadeLambdaExpression(). Не самое легкое выражение для построения из-за методов расширения, но выполнимо.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Linq.Expressions;
namespace ExpressionBench
{
class Program
{
static void Main(string[] args)
{
var values = Enumerable.Range(0, 5000);
var lambda = GetLambda();
var lambdaExpression = GetLambdaExpression().Compile();
var handMadeLambdaExpression = GetHandMadeLambdaExpression().Compile();
var composed = GetComposed();
var composedExpression = GetComposedExpression().Compile();
var handMadeComposedExpression = GetHandMadeComposedExpression().Compile();
DoTest("Lambda", values, lambda);
DoTest("Lambda Expression", values, lambdaExpression);
DoTest("Hand Made Lambda Expression", values, handMadeLambdaExpression);
Console.WriteLine();
DoTest("Composed", values, composed);
DoTest("Composed Expression", values, composedExpression);
DoTest("Hand Made Composed Expression", values, handMadeComposedExpression);
}
static void DoTest<TInput, TOutput>(string name, TInput sequence, Func<TInput, TOutput> operation, int count = 1000000)
{
for (int _ = 0; _ < 1000; _++)
operation(sequence);
var sw = Stopwatch.StartNew();
for (int _ = 0; _ < count; _++)
operation(sequence);
sw.Stop();
Console.WriteLine("{0}:", name);
Console.WriteLine(" Elapsed: {0,10} {1,10} (ms)", sw.ElapsedTicks, sw.ElapsedMilliseconds);
Console.WriteLine(" Average: {0,10} {1,10} (ms)", decimal.Divide(sw.ElapsedTicks, count), decimal.Divide(sw.ElapsedMilliseconds, count));
}
static Func<IEnumerable<int>, IList<int>> GetLambda()
{
return v => v.Where(i => i % 2 == 0).Where(i => i > 5).ToList();
}
static Expression<Func<IEnumerable<int>, IList<int>>> GetLambdaExpression()
{
return v => v.Where(i => i % 2 == 0).Where(i => i > 5).ToList();
}
static Expression<Func<IEnumerable<int>, IList<int>>> GetHandMadeLambdaExpression()
{
var enumerableMethods = typeof(Enumerable).GetMethods();
var whereMethod = enumerableMethods
.Where(m => m.Name == "Where")
.Select(m => m.MakeGenericMethod(typeof(int)))
.Where(m => m.GetParameters()[1].ParameterType == typeof(Func<int, bool>))
.Single();
var toListMethod = enumerableMethods
.Where(m => m.Name == "ToList")
.Select(m => m.MakeGenericMethod(typeof(int)))
.Single();
// helpers to create the static method call expressions
Func<Expression, ParameterExpression, Func<ParameterExpression, Expression>, Expression> WhereExpression =
(instance, param, body) => Expression.Call(whereMethod, instance, Expression.Lambda(body(param), param));
Func<Expression, Expression> ToListExpression =
instance => Expression.Call(toListMethod, instance);
//return v => v.Where(i => i % 2 == 0).Where(i => i > 5).ToList();
var exprParam = Expression.Parameter(typeof(IEnumerable<int>), "v");
var expr0 = WhereExpression(exprParam,
Expression.Parameter(typeof(int), "i"),
i => Expression.Equal(Expression.Modulo(i, Expression.Constant(2)), Expression.Constant(0)));
var expr1 = WhereExpression(expr0,
Expression.Parameter(typeof(int), "i"),
i => Expression.GreaterThan(i, Expression.Constant(5)));
var exprBody = ToListExpression(expr1);
return Expression.Lambda<Func<IEnumerable<int>, IList<int>>>(exprBody, exprParam);
}
static Func<IEnumerable<int>, IList<int>> GetComposed()
{
Func<IEnumerable<int>, IEnumerable<int>> composed0 =
v => v.Where(i => i % 2 == 0);
Func<IEnumerable<int>, IEnumerable<int>> composed1 =
v => v.Where(i => i > 5);
Func<IEnumerable<int>, IList<int>> composed2 =
v => v.ToList();
return v => composed2(composed1(composed0(v)));
}
static Expression<Func<IEnumerable<int>, IList<int>>> GetComposedExpression()
{
Expression<Func<IEnumerable<int>, IEnumerable<int>>> composed0 =
v => v.Where(i => i % 2 == 0);
Expression<Func<IEnumerable<int>, IEnumerable<int>>> composed1 =
v => v.Where(i => i > 5);
Expression<Func<IEnumerable<int>, IList<int>>> composed2 =
v => v.ToList();
var exprParam = Expression.Parameter(typeof(IEnumerable<int>), "v");
var exprBody = Expression.Invoke(composed2, Expression.Invoke(composed1, Expression.Invoke(composed0, exprParam)));
return Expression.Lambda<Func<IEnumerable<int>, IList<int>>>(exprBody, exprParam);
}
static Expression<Func<IEnumerable<int>, IList<int>>> GetHandMadeComposedExpression()
{
var enumerableMethods = typeof(Enumerable).GetMethods();
var whereMethod = enumerableMethods
.Where(m => m.Name == "Where")
.Select(m => m.MakeGenericMethod(typeof(int)))
.Where(m => m.GetParameters()[1].ParameterType == typeof(Func<int, bool>))
.Single();
var toListMethod = enumerableMethods
.Where(m => m.Name == "ToList")
.Select(m => m.MakeGenericMethod(typeof(int)))
.Single();
Func<ParameterExpression, Func<ParameterExpression, Expression>, Expression> LambdaExpression =
(param, body) => Expression.Lambda(body(param), param);
Func<Expression, ParameterExpression, Func<ParameterExpression, Expression>, Expression> WhereExpression =
(instance, param, body) => Expression.Call(whereMethod, instance, Expression.Lambda(body(param), param));
Func<Expression, Expression> ToListExpression =
instance => Expression.Call(toListMethod, instance);
var composed0 = LambdaExpression(Expression.Parameter(typeof(IEnumerable<int>), "v"),
v => WhereExpression(
v,
Expression.Parameter(typeof(int), "i"),
i => Expression.Equal(Expression.Modulo(i, Expression.Constant(2)), Expression.Constant(0))));
var composed1 = LambdaExpression(Expression.Parameter(typeof(IEnumerable<int>), "v"),
v => WhereExpression(
v,
Expression.Parameter(typeof(int), "i"),
i => Expression.GreaterThan(i, Expression.Constant(5))));
var composed2 = LambdaExpression(Expression.Parameter(typeof(IEnumerable<int>), "v"),
v => ToListExpression(v));
var exprParam = Expression.Parameter(typeof(IEnumerable<int>), "v");
var exprBody = Expression.Invoke(composed2, Expression.Invoke(composed1, Expression.Invoke(composed0, exprParam)));
return Expression.Lambda<Func<IEnumerable<int>, IList<int>>>(exprBody, exprParam);
}
}
}
И результаты на моей машине:
Lambda:
Elapsed: 340971948 123230 (ms)
Average: 340.971948 0.12323 (ms)
Lambda Expression:
Elapsed: 357077202 129051 (ms)
Average: 357.077202 0.129051 (ms)
Hand Made Lambda Expression:
Elapsed: 345029281 124696 (ms)
Average: 345.029281 0.124696 (ms)
Composed:
Elapsed: 340409238 123027 (ms)
Average: 340.409238 0.123027 (ms)
Composed Expression:
Elapsed: 350800599 126782 (ms)
Average: 350.800599 0.126782 (ms)
Hand Made Composed Expression:
Elapsed: 352811359 127509 (ms)
Average: 352.811359 0.127509 (ms)
