Desempenho de expressões C # Lambda compiladas

91

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.

Hugo Sereno Ferreira
fonte
3
Esses intervalos são de execução no Visual Studio? Em caso afirmativo, repita os tempos usando uma compilação de modo de lançamento e execute sem depuração (ou seja, Ctrl + F5 no Visual Studio ou a partir da linha de comando). Além disso, considere usar Stopwatchpara horários em vez de DateTime.Now.
Jim Mischel,
12
Não sei por que é mais lento, mas sua técnica de benchmark não é muito boa. Em primeiro lugar, DateTime.Now tem precisão de apenas 1/64 de segundo, portanto, o erro de arredondamento da medição é grande. Em vez disso, use o cronômetro; tem precisão de alguns nanossegundos. Em segundo lugar, você está medindo o tempo para inserir o código (a primeira chamada) e cada chamada subsequente; isso pode prejudicar as médias. (Embora, neste caso, um MAX de cem mil seja provavelmente o suficiente para afastar a média da carga de jit, ainda assim, é uma má prática incluí-la na média.)
Eric Lippert,
7
@Eric, o erro de arredondamento só pode ocorrer se em cada operação DateTime.Now.Ticks for usada, antes do início e após o fim, as contagens de milissegundos forem altas o suficiente para mostrar a diferença de desempenho.
Akash Kava
1
se estiver usando cronômetro, recomendo seguir este artigo para garantir resultados precisos: codeproject.com/KB/testing/stopwatch-measure-precise.aspx
Zach Green
1
@Eric, embora eu concorde que não é a técnica de medição mais precisa disponível, estamos falando sobre uma ordem de magnitude de diferença. MAX é alto o suficiente para reduzir desvios significativos.
Hugo Sereno Ferreira

Respostas:

43

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 !?

Hugo Sereno Ferreira
fonte
1
Estou pensando em aceitar minha própria resposta, já que é a que tem mais votos. Devo esperar um pouco mais?
Hugo Sereno Ferreira
Sobre o que acontece com você obter código mais rápido do que o lambda nativo, você pode querer dar uma olhada nesta página sobre microbenchmarks (que não tem nada realmente específico de Java, apesar do nome): code.google.com/p/caliper/wiki / JavaMicrobenchmarks
Blaisorblade
Quanto ao motivo pelo qual o lambda compilado dinamicamente é mais rápido, suspeito que "usar lambda", sendo executado primeiro, está sendo penalizado com a necessidade de fazer JIT de algum código.
Oskar Berggren
Eu não sei o que está acontecendo, uma vez que eu testei a expressão compilada e criei o legado para definir e obter os campos e propriedades, o createdelegate foi muito mais rápido para as propriedades, mas compilado foi um pouco mais rápido para os campos
nawfal
10

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.

JulianR
fonte
4

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)
Jeff Mercado
fonte
3

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.

Akash Kava
fonte
2
Se você olhar de perto, o UsingLambdaCombinedteste está combinando várias funções lambda e seu desempenho está muito próximo de UsingLambda. Com relação às otimizações, estava convencido de que elas eram manipuladas pelo mecanismo JIT e, portanto, o código gerado em tempo de execução (após a compilação) também seria alvo de quaisquer otimizações JIT.
Hugo Sereno Ferreira
1
A otimização JIT e a otimização do tempo de compilação são duas coisas diferentes que você pode desativar a otimização do tempo de compilação nas configurações do projeto. Em segundo lugar, a compilação de expressão provavelmente emitirá MSIL dinâmico que, novamente, será um pouco mais lento, pois sua lógica e sequência de operação conterão verificações de nulos e validade de acordo com as necessidades. Você pode olhar no refletor sobre como ele é compilado.
Akash Kava
2
Embora seu raciocínio seja correto, tenho que discordar de você neste problema específico (ou seja, a diferença de ordem de magnitude não se deve à compilação estática). Primeiro, porque se você realmente desabilitar as otimizações de tempo de compilação, a diferença ainda será considerável. Em segundo lugar, porque já encontrei uma maneira de otimizar a geração dinâmica para ser um pouco mais lenta. Deixe-me tentar entender o "porquê" e postarei os resultados.
Hugo Sereno Ferreira