Desempenho de expressões C # Lambda compiladas

Considere a seguinte manipulação simples sobre uma coleção:

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);

Agora vamos usar Expressões. O código a seguir é aproximadamente equivalente:

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);
}

Mas eu quero construir a expressão em tempo real, então aqui está um novo teste:

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);
}

Claro que não é exatamente como o anterior, então, para ser justo, eu modifico ligeiramente o primeiro:

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);
}

Agora vêm os resultados para MAX = 100000, VS2008, depuração ON:

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

E com depuração DESLIGADA:

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

Surpresa . A expressão compilada é cerca de 17x mais lenta do que as outras alternativas. Agora vem a pergunta:

1. Estou comparando expressões não equivalentes?
2. Existe um mecanismo para fazer o .NET "otimizar" a expressão compilada?
3. Como expresso a mesma chamada em cadeia de maneira l.Where(i => i % 2 == 0).Where(i => i > 5);programática?

Mais algumas estatísticas. Visual Studio 2010, depuração ATIVADA, otimizações DESATIVADAS:

Using lambda:           1093974
Using lambda compiled: 15315636
Using lambda combined:   781410

Depuração ATIVADA, otimizações ATIVADAS:

Using lambda:            781305
Using lambda compiled: 15469839
Using lambda combined:   468783

Depuração DESATIVADA, otimizações ATIVADAS:

Using lambda:            625020
Using lambda compiled: 14687970
Using lambda combined:   468765

Nova surpresa. Mudar de VS2008 (C # 3) para VS2010 (C # 4) torna o UsingLambdaCombinedmais rápido do que o lambda nativo.

Ok, descobri uma maneira de melhorar o desempenho do lambda compilado em mais de uma ordem de magnitude. Aqui vai uma dica; depois de executar o criador de perfil, 92% do tempo é gasto em:

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

Hmmmm ... Por que está criando um novo delegado a cada iteração? Não tenho certeza, mas a solução segue em uma postagem separada.

Será que os lambdas internos não estão sendo compilados?!? Aqui está uma prova de conceito:

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);
    }

E agora os horários são:

Using lambda:                            625020
Using lambda compiled:                 14687970
Using lambda combined:                   468765
Using lambda compiled with MethodCall:   468765

Uau! Além de ser rápido, é mais rápido que o lambda nativo. ( Cabeça coçada ).

Claro que o código acima é simplesmente muito doloroso de escrever. Vamos fazer uma mágica simples:

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);
}

E alguns tempos, VS2010, otimizações ativadas, depuração desativada:

Using lambda:                            781260
Using lambda compiled:                 14687970
Using lambda combined:                   468756
Using lambda compiled with MethodCall:   468756
Using lambda compiled constant:          468756

Agora você pode argumentar que não estou gerando toda a expressão dinamicamente; apenas as invocações em cadeia. Mas no exemplo acima eu gero toda a expressão. E os horários combinam. Este é apenas um atalho para escrever menos código.

Do meu entendimento, o que está acontecendo é que o método .Compile () não propaga as compilações para lambdas internas e, portanto, a invocação constante de CreateDelegate . Mas, para realmente entender isso, adoraria que um guru do .NET comentasse um pouco sobre as coisas internas que estão acontecendo.

E por que , oh, por que isso agora é mais rápido do que um lambda nativo !?

Recentemente, fiz uma pergunta quase idêntica:

Desempenho da expressão compilada para delegar

A solução para mim foi que eu não deveria chamar Compileo Expression, mas deveria chamá CompileToMethod-lo e compilar o Expressionpara umstatic método em um assembly dinâmico.

Igual a:

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"));

Porém, não é o ideal. Não tenho certeza de quais tipos isso se aplica exatamente, mas acho que os tipos que são tomados como parâmetros pelo delegado ou retornados pelo delegado precisam ser publicnão genéricos. Tem que ser não genérico porque os tipos genéricos aparentemente acessam System.__Canonque é um tipo interno usado pelo .NET nos bastidores para tipos genéricos e isso viola o "tem que ser umpublic regra de tipo).

Para esses tipos, você pode usar o aparentemente mais lento Compile. Eu os detecto da seguinte maneira:

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;
  }
}

Mas, como eu disse, isso não é o ideal e ainda gostaria de saber por que compilar um método para uma montagem dinâmica às vezes é uma ordem de magnitude mais rápida. E digo às vezes porque também vi casos em que um Expressioncompilado comCompile que um método é tão rápido quanto um método normal. Veja minha pergunta para isso.

Ou se alguém souber uma maneira de contornar a publicrestrição " não- tipos" com o assembly dinâmico, isso também é bem-vindo.

Suas expressões não são equivalentes e, portanto, você obtém resultados distorcidos. Eu escrevi uma bancada de teste para testar isso. Os testes incluem a chamada lambda regular, a expressão compilada equivalente, uma expressão compilada equivalente feita à mão, bem como versões compostas. Esses devem ser números mais precisos. Curiosamente, não estou vendo muita variação entre as versões simples e compostas. E as expressões compiladas são mais lentas naturalmente, mas apenas um pouco. Você precisa de uma entrada grande o suficiente e uma contagem de iterações para obter alguns bons números. Faz diferença.

Quanto à sua segunda pergunta, não sei como você conseguiria obter mais desempenho com isso, então não posso ajudá-lo. Parece tão bom quanto vai ficar.

Você encontrará minha resposta para sua terceira pergunta no HandMadeLambdaExpression()método. Não é a expressão mais fácil de construir devido aos métodos de extensão, mas é factível.

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);
        }
    }
}

E os resultados na minha máquina:

Lambda:
  Decorrido: 340971948 123230 (ms)
  Média: 340,971948 0,12323 (ms)
Expressão Lambda:
  Decorrido: 357077202 129051 (ms)
  Média: 357,077202 0,129051 (ms)
Expressão Lambda Feita à Mão:
  Decorrido: 345029281 124696 (ms)
  Média: 345,029281 0,124696 (ms)

Composto:
  Decorrido: 340409238 123027 (ms)
  Média: 340,409238 0,123027 (ms)
Expressão composta:
  Decorrido: 350800599 126782 (ms)
  Média: 350,800599 0,126782 (ms)
Expressão composta feita à mão:
  Decorrido: 352811359 127509 (ms)
  Média: 352,811359 0,127509 (ms)

O desempenho lambda compilado sobre delegados pode ser mais lento porque o código compilado em tempo de execução pode não ser otimizado, no entanto, o código que você escreveu manualmente e que compilou por meio do compilador C # é otimizado.

Em segundo lugar, várias expressões lambda significam vários métodos anônimos, e chamar cada um deles leva pouco tempo extra para avaliar um método direto. Por exemplo, ligando

Console.WriteLine(x);

e

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

são diferentes e, com o segundo, um pouco mais de sobrecarga é necessário da perspectiva do compilador, na verdade, são duas chamadas diferentes. Primeiro chamando o próprio x e, em seguida, dentro da declaração de x chamando

Portanto, seu Lambda combinado certamente terá um desempenho pouco lento sobre uma única expressão lambda.

E isso é independente do que está sendo executado internamente, porque você ainda está avaliando a lógica correta, mas está adicionando etapas adicionais para que o compilador execute.

Mesmo após a árvore de expressão ser compilada, ela não terá otimização e ainda preservará sua pequena estrutura complexa, avaliando e chamando pode ter validação extra, verificação nula etc, o que pode diminuir o desempenho de expressões lambda compiladas.