Performances des expressions Lambda C # compilées

Considérez la manipulation simple suivante sur une collection:

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

Utilisons maintenant des expressions. Le code suivant est à peu près équivalent:

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

Mais je veux créer l'expression à la volée, voici donc un nouveau test:

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

Bien sûr, ce n'est pas exactement comme ce qui précède, donc pour être honnête, je modifie légèrement le premier:

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

Viennent maintenant les résultats pour MAX = 100000, VS2008, débogage ON:

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

Et avec le débogage désactivé:

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

Surprise . L'expression compilée est environ 17 fois plus lente que les autres alternatives. Maintenant, voici les questions:

1. Est-ce que je compare des expressions non équivalentes?
2. Existe-t-il un mécanisme pour que .NET «optimise» l'expression compilée?
3. Comment exprimer le même appel en chaîne par l.Where(i => i % 2 == 0).Where(i => i > 5);programme?

Quelques statistiques supplémentaires. Visual Studio 2010, débogage activé, optimisations désactivées:

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

Débogage ON, optimisations ON:

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

Débogage OFF, optimisations ON:

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

Nouvelle surprise. Le passage de VS2008 (C # 3) à VS2010 (C # 4), rend le UsingLambdaCombinedplus rapide que le lambda natif.

Ok, j'ai trouvé un moyen d'améliorer les performances compilées lambda de plus d'un ordre de grandeur. Voici une astuce; après l'exécution du profileur, 92% du temps est consacré à:

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

Hmmmm ... Pourquoi crée-t-il un nouveau délégué à chaque itération? Je ne suis pas sûr, mais la solution suit dans un article séparé.

Se pourrait-il que les lambdas internes ne soient pas compilés?!? Voici une preuve de concept:

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

Et maintenant, les horaires sont:

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

Woot! Non seulement il est rapide, mais il est plus rapide que le lambda natif. ( Tête à gratter ).

Bien sûr, le code ci-dessus est tout simplement trop pénible à écrire. Faisons de la magie 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);
}

Et quelques timings, VS2010, optimisations ON, débogage OFF:

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

Vous pouvez maintenant affirmer que je ne génère pas l'expression entière de manière dynamique; juste les invocations de chaînage. Mais dans l'exemple ci-dessus, je génère l'expression entière. Et les horaires correspondent. Ceci est juste un raccourci pour écrire moins de code.

D'après ce que j'ai compris, ce qui se passe, c'est que la méthode .Compile () ne propage pas les compilations aux lambdas internes, et donc l'invocation constante de CreateDelegate. Mais pour vraiment comprendre cela, je serais ravi d'avoir un commentaire d'un gourou .NET sur les choses internes en cours.

Et pourquoi , oh pourquoi est-ce maintenant plus rapide qu'un lambda natif !?

Récemment, j'ai posé une question presque identique:

Performances de l'expression compilée pour déléguer

La solution pour moi était que je ne devais pas appeler Compilele Expression, mais que je devais l'appeler CompileToMethodet le compiler Expressionen une staticméthode dans un assembly dynamique.

Ainsi:

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

Ce n'est cependant pas idéal. Je ne suis pas tout à fait certain à quels types cela s'applique exactement, mais je pense que les types qui sont pris comme paramètres par le délégué ou renvoyés par le délégué doivent être publicet non génériques. Il doit être non générique parce que les types génériques accèdent apparemment System.__Canonqui est un type interne utilisé par .NET sous le capot pour les types génériques et cela viole la publicrègle "doit être une règle de type).

Pour ces types, vous pouvez utiliser le plus lent Compile. Je les détecte de la manière suivante:

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

Mais comme je l'ai dit, ce n'est pas l'idéal et j'aimerais quand même savoir pourquoi la compilation d'une méthode en un assemblage dynamique est parfois un ordre de grandeur plus rapide. Et je dis parfois parce que j'ai aussi vu des cas où un Expressioncompilé avec Compileest tout aussi rapide qu'une méthode normale. Voir ma question pour cela.

Ou si quelqu'un connaît un moyen de contourner la publiccontrainte «pas de non- types» avec l'assembly dynamique, c'est également le bienvenu.

Vos expressions ne sont pas équivalentes et vous obtenez ainsi des résultats biaisés. J'ai écrit un banc d'essai pour tester cela. Les tests incluent l'appel lambda régulier, l'expression compilée équivalente, une expression compilée équivalente faite à la main, ainsi que des versions composées. Ces chiffres devraient être plus précis. Fait intéressant, je ne vois pas beaucoup de variation entre les versions simples et composées. Et les expressions compilées sont naturellement plus lentes mais seulement de très peu. Vous avez besoin d'une entrée et d'un nombre d'itérations suffisamment importants pour obtenir de bons nombres. Cela fait une différence.

En ce qui concerne votre deuxième question, je ne sais pas comment vous pourriez en tirer plus de performances, donc je ne peux pas vous aider. Ça a l'air aussi beau que ça va l'être.

Vous trouverez ma réponse à votre troisième question dans la HandMadeLambdaExpression()méthode. Ce n'est pas l'expression la plus facile à construire en raison des méthodes d'extension, mais c'est faisable.

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

Et les résultats sur ma machine:

Lambda:
  Temps écoulé: 340971948 123230 (ms)
  Moyenne: 340.971948 0.12323 (ms)
Expression Lambda:
  Temps écoulé: 357077202 129051 (ms)
  Moyenne: 357.077202 0.129051 (ms)
Expression Lambda faite à la main:
  Temps écoulé: 345029281 124696 (ms)
  Moyenne: 345.029281 0.124696 (ms)

Composé:
  Temps écoulé: 340409238 123027 (ms)
  Moyenne: 340.409238 0.123027 (ms)
Expression composée:
  Temps écoulé: 350800599 126782 (ms)
  Moyenne: 350.800599 0.126782 (ms)
Expression composée à la main:
  Temps écoulé: 352811359 127509 (ms)
  Moyenne: 352.811359 0.127509 (ms)

Les performances lambda compilées sur les délégués peuvent être plus lentes car le code compilé lors de l'exécution peut ne pas être optimisé, mais le code que vous avez écrit manuellement et celui compilé via le compilateur C # est optimisé.

Deuxièmement, plusieurs expressions lambda signifient plusieurs méthodes anonymes, et l'appel de chacune d'elles prend peu de temps supplémentaire par rapport à l'évaluation d'une méthode simple. Par exemple, appeler

Console.WriteLine(x);

et

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

sont différents, et avec une seconde, un peu plus de surcharge est nécessaire car du point de vue du compilateur, il s'agit en fait de deux appels différents. Appelez d'abord x lui-même, puis dans l'instruction d'appel de x.

Ainsi, votre Lambda combiné aura certainement peu de performances lentes par rapport à une seule expression lambda.

Et cela est indépendant de ce qui s'exécute à l'intérieur, car vous évaluez toujours la logique correcte, mais vous ajoutez des étapes supplémentaires à exécuter par le compilateur.

Même après la compilation de l'arbre d'expression, il n'aura pas d'optimisation, et il conservera toujours sa petite structure complexe, son évaluation et son appel peuvent avoir une validation supplémentaire, une vérification nulle, etc., ce qui pourrait ralentir les performances des expressions lambda compilées.