expressions - linq with lambda expression in c#

Rendimiento compilado de C#Lambda Expressions

Question

Considere la siguiente manipulación simple sobre una colección:

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

Ahora usemos Expresiones. El siguiente código es más o menos 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);
}

Pero quiero construir la expresión sobre la marcha, así que aquí hay una nueva prueba:

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

Por supuesto, no es exactamente como lo anterior, por lo que para ser justos, modifico ligeramente el primero:

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

Ahora vienen los resultados para MAX = 100000, VS2008, depuración ON:

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

Y con la depuración desactivada:

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

Sorpresa La expresión compilada es aproximadamente 17 veces más lenta que las otras alternativas. Ahora aquí vienen las preguntas:

1. ¿Estoy comparando expresiones no equivalentes?
2. ¿Hay algún mecanismo para hacer que .NET "optimice" la expresión compilada?
3. ¿Cómo expreso la misma llamada en cadena l.Where(i => i % 2 == 0).Where(i => i > 5); programáticamente?

Algunas estadísticas más Visual Studio 2010, depuración activada, optimizaciones desactivadas:

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

Depuración ON, optimizaciones ON:

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

Depuración OFF, optimizaciones ON:

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

Nueva sorpresa. El cambio de VS2008 (C # 3) a VS2010 (C # 4) hace que UsingLambdaCombined más rápido que el lambda nativo.

Bien, he encontrado una manera de mejorar el rendimiento compilado de lambda en más de un orden de magnitud. Aquí tienes un consejo; después de ejecutar el generador de perfiles, el 92% del tiempo se usa en:

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

Hmmmm ... ¿Por qué está creando un nuevo delegado en cada iteración? No estoy seguro, pero la solución sigue en una publicación separada.

Answer 1

¿Podría ser que las lambdas internas no se compilan? Aquí hay una prueba de concepto:

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

Y ahora los tiempos son:

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

¡Woot! No solo es rápido, es más rápido que el lambda nativo. ( Cabeza de arañazo ).

Por supuesto, el código anterior es demasiado doloroso para escribir. Hagamos algo de magia simple:

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

Y algunos tiempos, VS2010, optimizaciones activadas, depuración desactivada:

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

Ahora podría argumentar que no estoy generando toda la expresión de forma dinámica; solo las invocaciones de encadenamiento. Pero en el ejemplo anterior, genero toda la expresión. Y los tiempos coinciden. Esto es solo un atajo para escribir menos código.

Según entiendo, lo que está sucediendo es que el método .Compile () no propaga las compilaciones a lambdas internas, y por lo tanto la invocación constante de CreateDelegate . Pero para comprender realmente esto, me gustaría que un gurú de .NET comenten un poco acerca de las cosas internas que están sucediendo.

Y por qué , ¡ ¿por qué ahora esto es más rápido que un lambda nativo ?!

Answer 2

El rendimiento de lambda compilado sobre delegados puede ser más lento porque el código compilado en tiempo de ejecución no se puede optimizar, sin embargo, el código que escribió manualmente y el compilado a través del compilador de C # está optimizado.

En segundo lugar, múltiples expresiones lambda significan múltiples métodos anónimos, y llamar a cada uno de ellos toma poco tiempo adicional sobre la evaluación de un método directo. Por ejemplo, llamar

Console.WriteLine(x);

y

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

son diferentes, y con el segundo se requiere un poco más de sobrecarga desde la perspectiva del compilador, en realidad son dos llamadas diferentes. Llamando primero x mismo y luego dentro de esa declaración de x llamada.

Por lo tanto, su combinación de Lambda ciertamente tendrá un rendimiento lento bajo sobre una sola expresión lambda.

Y esto es independiente de lo que se está ejecutando en el interior, porque aún está evaluando la lógica correcta, pero está agregando pasos adicionales para que el compilador realice.

Incluso después de compilar el árbol de expresiones, no tendrá optimización, y aún conservará su pequeña estructura compleja, evaluarla y llamarla puede tener validación adicional, verificación nula, etc., lo que podría ralentizar el rendimiento de las expresiones lambda compiladas.

Answer 3

Recientemente hice una pregunta casi idéntica:

Rendimiento de la expresión compilado a delegado

La solución para mí fue no llamar a Compile on the Expression , sino que debería llamar a CompileToMethod y compilar Expression a un método static en un ensamblado dinámico.

Al igual que:

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

Sin embargo, no es ideal. No estoy seguro de qué tipos se aplican exactamente, pero creo que los tipos que el delegado toma como parámetros o que los devuelve el delegado tienen que ser public y no genéricos. Tiene que ser no genérico porque los tipos genéricos aparentemente tienen acceso al System.__Canon que es un tipo interno utilizado por .NET bajo el capó para los tipos genéricos y esto viola la regla "tiene que ser de tipo public ".

Para esos tipos, puede usar la Compile aparentemente más lenta. Los detecto de la siguiente manera:

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

Pero como dije, esto no es ideal y me gustaría saber por qué compilar un método para un ensamblaje dinámico a veces es un orden de magnitud más rápido. Y digo algunas veces porque también he visto casos en los que una Expression compilada con Compile es tan rápida como un método normal. Vea mi pregunta para eso.

O si alguien conoce una forma de eludir la restricción de "no tipos no public " con el ensamblaje dinámico, eso también es bienvenido.

Answer 4

Tus expresiones no son equivalentes y obtienes resultados sesgados. Escribí un banco de pruebas para probar esto. Las pruebas incluyen la llamada regular lambda, la expresión compilada equivalente, una expresión compilada equivalente hecha a mano, así como las versiones compuestas. Estos deberían ser números más precisos. Curiosamente, no veo mucha variación entre las versiones simples y compuestas. Y las expresiones compiladas son más lentas naturalmente pero solo por muy poco. Necesita un conteo de entrada e iteración lo suficientemente grande para obtener algunos buenos números. Hace una diferencia.

En cuanto a su segunda pregunta, no sé cómo podría obtener más rendimiento de esto, así que no puedo ayudarlo allí. Se ve tan bien como se va a poner.

Encontrarás mi respuesta a tu tercera pregunta en el método HandMadeLambdaExpression() . No es la expresión más fácil de construir debido a los métodos de extensión, pero es factible.

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

Y los resultados en mi máquina:

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)