Rendimiento compilado de expresiones Lambda de C #

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

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 que no es exactamente como el anterior, así 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. ¿Existe un 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 activada, optimizaciones activadas:

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

Depuración desactivada, optimizaciones activadas:

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 sea UsingLambdaCombinedmás rápido que el lambda nativo.

Ok, encontré 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 dedica a:

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.

¿¡¿Podría ser que las lambdas internas no se estén compilando?!? Aquí tienes 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. ( Rascarse la cabeza ).

Por supuesto, el código anterior es simplemente demasiado doloroso de 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 encadenadas. Pero en el ejemplo anterior genero la expresión completa. Y los tiempos coinciden. Este es solo un atajo para escribir menos código.

Según tengo entendido, 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 entender realmente esto, me encantaría que un gurú de .NET comentara un poco sobre las cosas internas que están sucediendo.

¿ Y por qué , oh, por qué ahora es más rápido que una lambda nativa?

Recientemente hice una pregunta casi idéntica:

Rendimiento de expresión compilada para delegar

La solución para mí fue que no debería llamar Compileal Expression, sino que debería llamarlo CompileToMethody compilarlo Expressionen un staticmétodo 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 muy seguro de a qué tipos se aplica esto exactamente, pero creo que los tipos que el delegado toma como parámetros o devuelve el delegado tienen que ser publicy no genéricos. Tiene que ser no genérico porque los tipos genéricos aparentemente acceden, System.__Canonque es un tipo interno utilizado por .NET bajo el capó para tipos genéricos y esto viola la publicregla "tiene que ser un tipo".

Para esos tipos, puede usar el aparentemente más lento Compile. 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 aún me gustaría saber por qué compilar un método en un ensamblado dinámico a veces es un orden de magnitud más rápido. Y lo digo a veces porque también he visto casos en los que un Expressioncompilado con Compilees tan rápido como un método normal. Vea mi pregunta para eso.

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

Tus expresiones no son equivalentes y, por lo tanto, obtienes resultados sesgados. Escribí un banco de pruebas para probar esto. Las pruebas incluyen la llamada lambda regular, la expresión compilada equivalente, una expresión compilada equivalente hecha a mano, así como versiones compuestas. Deben 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 muy poco. Necesita una entrada y un recuento de iteraciones lo suficientemente grandes para obtener buenos números. Hace una diferencia.

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

Encontrarás mi respuesta a tu tercera pregunta en el HandMadeLambdaExpression()método. 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:
  Respondido: 340971948 123230 (ms)
  Promedio: 340.971948 0.12323 (ms)
Expresión Lambda:
  Respondido: 357077202 129051 (ms)
  Promedio: 357.077202 0.129051 (ms)
Expresión Lambda hecha a mano:
  Respondido: 345029281 124696 (ms)
  Promedio: 345.029281 0.124696 (ms)

Compuesto:
  Respondido: 340409238 123027 (ms)
  Promedio: 340.409238 0.123027 (ms)
Expresión compuesta:
  Respondido: 350800599 126782 (ms)
  Promedio: 350.800599 0.126782 (ms)
Expresión compuesta hecha a mano:
  Respondido: 352811359 127509 (ms)
  Promedio: 352.811359 0.127509 (ms)

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

En segundo lugar, múltiples expresiones lambda significan múltiples métodos anónimos, y llamar a cada uno de ellos requiere un poco más de tiempo que evaluar un método directo. Por ejemplo, llamando

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, ya que desde la perspectiva del compilador, en realidad son dos llamadas diferentes. Primero llamando a la x misma y luego dentro de esa declaración de llamada x.

Por lo tanto, su Lambda combinado ciertamente tendrá un rendimiento poco lento sobre una expresión lambda única.

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

Incluso después de que se compile el árbol de expresiones, no tendrá optimización y aún conservará su estructura poco compleja, evaluarlo y llamarlo puede tener validación adicional, verificación nula, etc., lo que podría ralentizar el rendimiento de las expresiones lambda compiladas.