Производительность скомпилированных лямбда-выражений C #

Рассмотрим следующую простую операцию над коллекцией:

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, отладка включена:

Using lambda compiled: 23437500
Using lambda:           1250000
Using lambda combined:  1406250

И с выключенной отладкой:

Using lambda compiled: 21718750
Using lambda:            937500
Using lambda combined:  1093750

Сюрприз . Скомпилированное выражение примерно в 17 раз медленнее, чем другие альтернативы. А теперь вопросы:

1. Я сравниваю неэквивалентные выражения?
2. Есть ли механизм, позволяющий .NET «оптимизировать» скомпилированное выражение?
3. Как программно выразить один и тот же цепной вызов 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 (C # 3) на VS2010 (C # 4) делает его UsingLambdaCombinedбыстрее, чем нативная лямбда.

Хорошо, я нашел способ улучшить производительность скомпилированной лямбда-выражения более чем на порядок. Вот подсказка; после запуска профилировщика 92% времени уходит на:

System.Reflection.Emit.DynamicMethod.CreateDelegate(class System.Type, object)

Хммм ... Почему на каждой итерации создается новый делегат? Я не уверен, но решение будет опубликовано в отдельном посте.

Может быть, внутренние лямбды не компилируются?!? Вот доказательство концепции:

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 () не распространяет компиляции на внутренние лямбды и, следовательно, постоянный вызов CreateDelegate. Но чтобы по-настоящему понять это, я хотел бы, чтобы гуру .NET немного прокомментировал происходящее внутри.

И почему , почему это теперь быстрее, чем родная лямбда !?

Недавно я задал почти идентичный вопрос:

Производительность выражения, скомпилированного в делегат

Решение для меня было то , что я не должна вызывать 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ограничение «нет типов» с помощью динамической сборки, это тоже приветствуется.

Ваши выражения не эквивалентны, и поэтому вы получите искаженные результаты. Я написал тестовый стенд, чтобы проверить это. Тесты включают в себя обычный лямбда-вызов, эквивалентное скомпилированное выражение, эквивалентное скомпилированное выражение, созданное вручную, а также составные версии. Это должны быть более точные числа. Что интересно, я не вижу особых различий между простой и составной версиями. И скомпилированные выражения естественно медленнее, но очень немного. Вам нужен достаточно большой ввод и количество итераций, чтобы получить хорошие числа. Это имеет значение.

Что касается вашего второго вопроса, я не знаю, как вы могли бы добиться от этого большей производительности, поэтому я не могу вам помочь. Выглядит настолько хорошо, насколько это возможно.

Вы найдете мой ответ на свой третий вопрос в 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);
        }
    }
}

И результаты на моей машине:

Лямбда:
  Истекло: 340971948 123230 (мс)
  Среднее значение: 340,971948 0,12323 (мс)
Лямбда-выражение:
  Истекло: 357077202 129051 (мс)
  Среднее значение: 357,077202 0,129051 (мс)
Лямбда-выражение, сделанное вручную:
  Истекло: 345029281 124696 (мс)
  Среднее значение: 345,029281 0,124696 (мс)

В составе:
  Истекло: 340409238 123027 (мс)
  Среднее значение: 340,409238 0,123027 (мс)
Составное выражение:
  Истекло: 350800599 126782 (мс)
  Среднее значение: 350,800599 0,126782 (мс)
Выражение, сделанное вручную:
  Истекло: 352811359 127509 (мс)
  Среднее значение: 352,811359 0,127509 (мс)

Производительность скомпилированной лямбда-выражения по сравнению с делегатами может быть ниже, поскольку скомпилированный код во время выполнения может быть не оптимизирован, однако код, который вы написали вручную и скомпилированный с помощью компилятора C #, оптимизирован.

Во-вторых, несколько лямбда-выражений означают несколько анонимных методов, и вызов каждого из них требует немного больше времени по сравнению с вычислением прямого метода. Например, позвонив

Console.WriteLine(x);

а также

Action x => Console.WriteLine(x);
x(); // this means two different calls..

разные, и со вторым требуется еще немного накладных расходов, поскольку с точки зрения компилятора это фактически два разных вызова. Сначала вызывается сам x, а затем внутри этого вызывающего оператора x.

Таким образом, ваша комбинированная лямбда, безусловно, будет иметь немного медленную производительность по сравнению с одним лямбда-выражением.

И это не зависит от того, что выполняется внутри, потому что вы все еще оцениваете правильную логику, но вы добавляете дополнительные шаги для выполнения компилятором.

Даже после того, как дерево выражений скомпилировано, оно не будет оптимизировано и по-прежнему сохранит свою небольшую сложную структуру, при его оценке и вызове может потребоваться дополнительная проверка, проверка на null и т. Д., Что может замедлить производительность скомпилированных лямбда-выражений.