Skompilowana wydajność wyrażeń lambda w języku C #

Rozważmy następującą prostą operację na kolekcji:

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

Teraz użyjmy wyrażeń. Poniższy kod jest z grubsza równoważny:

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

Ale chcę tworzyć wyrażenie w locie, więc oto nowy 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);
}

Oczywiście nie jest dokładnie tak, jak powyżej, więc aby być uczciwym, nieco zmodyfikowałem pierwszy:

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

Teraz są wyniki dla MAX = 100000, VS2008, debugowanie WŁĄCZONE:

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

I przy wyłączonym debugowaniu:

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

Niespodzianka . Skompilowane wyrażenie jest około 17 razy wolniejsze niż inne alternatywy. Teraz pojawiają się pytania:

1. Czy porównuję wyrażenia nie równoważne?
2. Czy istnieje mechanizm umożliwiający .NET „optymalizację” skompilowanego wyrażenia?
3. Jak l.Where(i => i % 2 == 0).Where(i => i > 5);programowo wyrazić to samo wywołanie łańcuchowe ?

Trochę więcej statystyk. Visual Studio 2010, debugowanie włączone, optymalizacje wyłączone:

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

Debugowanie włączone, optymalizacje włączone:

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

Debugowanie wyłączone, optymalizacje włączone:

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

Nowa niespodzianka. Przełączenie z VS2008 (C # 3) na VS2010 (C # 4) sprawia, że ​​jest UsingLambdaCombinedszybszy niż natywna lambda.

Ok, znalazłem sposób na poprawienie wydajności skompilowanej lambda o więcej niż rząd wielkości. Oto wskazówka; po uruchomieniu profilera 92% czasu spędza się na:

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

Hmmmm ... Dlaczego tworzy nowego delegata w każdej iteracji? Nie jestem pewien, ale rozwiązanie znajduje się w osobnym poście.

Czy to możliwe, że wewnętrzne lambdy nie są kompilowane?!? Oto dowód słuszności koncepcji:

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

A teraz czasy są następujące:

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

Woot! Nie dość, że jest szybki, jest szybszy niż natywna lambda. ( Scratch head ).

Oczywiście powyższy kod jest po prostu zbyt bolesny do napisania. Zróbmy prostą magię:

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

I niektóre czasy, VS2010, optymalizacje włączone, debugowanie wyłączone:

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

Teraz możesz argumentować, że nie generuję całego wyrażenia dynamicznie; tylko wywołania łańcuchowe. Ale w powyższym przykładzie generuję całe wyrażenie. A czasy się zgadzają. To tylko skrót do pisania mniej kodu.

Z mojego zrozumienia wynika, że ​​metoda .Compile () nie propaguje kompilacji do wewnętrznych lambd, a tym samym ciągłego wywoływania CreateDelegate. Aby naprawdę to zrozumieć, chciałbym, aby guru .NET skomentował trochę wewnętrzne sprawy.

I dlaczego , och, dlaczego to teraz jest szybsze niż rodzima lambda !?

Ostatnio zadałem prawie identyczne pytanie:

Wydajność wyrażenia skompilowanego do delegata

Rozwiązaniem dla mnie było to, że nie powinienem wywoływać Compilemetody Expression, ale powinienem ją wywołać CompileToMethodi skompilować Expressiondo staticmetody w zestawie dynamicznym.

Tak jak to:

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

Nie jest to jednak idealne. Nie jestem do końca pewien, do których typów to się dokładnie odnosi, ale myślę, że typy, które są przyjmowane jako parametry przez delegata lub zwracane przez delegata, muszą być publici nieogólne. Musi być nieogólny, ponieważ typy ogólne najwyraźniej uzyskują dostęp, System.__Canonco jest typem wewnętrznym używanym przez .NET pod maską dla typów ogólnych, co narusza publiczasadę „musi być regułą typu”.

W przypadku tych typów możesz użyć pozornie wolniejszego Compile. Wykrywam je w następujący sposób:

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

Ale jak powiedziałem, to nie jest idealne i nadal chciałbym wiedzieć, dlaczego kompilacja metody do zestawu dynamicznego jest czasami o rząd wielkości szybsza. I mówię czasami, ponieważ widziałem również przypadki, w których Expressionkompilacja za pomocą Compilejest tak samo szybka jak normalna metoda. Zobacz moje pytanie.

Lub jeśli ktoś zna sposób na ominięcie ograniczenia „bez publictypów” w zespole dynamicznym, to również jest mile widziane.

Twoje wyrażenia nie są równoważne i dlatego otrzymujesz wypaczone wyniki. Napisałem stanowisko testowe, aby to przetestować. Testy obejmują zwykłe wywołanie lambda, równoważne skompilowane wyrażenie, ręcznie wykonane równoważne skompilowane wyrażenie, a także skomponowane wersje. Powinny to być dokładniejsze liczby. Co ciekawe, nie widzę dużej różnicy między wersjami prostymi i skomponowanymi. Skompilowane wyrażenia są naturalnie wolniejsze, ale tylko o bardzo niewiele. Potrzebujesz wystarczająco dużej ilości danych wejściowych i liczby iteracji, aby uzyskać dobre liczby. To robi różnicę.

A jeśli chodzi o drugie pytanie, nie wiem, w jaki sposób byłbyś w stanie uzyskać z tego większą wydajność, więc nie mogę ci w tym pomóc. Wygląda tak dobrze, jak będzie.

Moją odpowiedź na trzecie pytanie znajdziesz w HandMadeLambdaExpression()metodzie. Nie jest to najłatwiejsze wyrażenie do zbudowania ze względu na metody rozszerzające, ale wykonalne.

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

A wyniki na moim komputerze:

Lambda:
  Odpowiedzi: 340971948 123230 (ms)
  Średnio: 340,971948 0,12323 (ms)
Wyrażenie lambda:
  Odpowiedzi: 357077202 129051 (ms)
  Średnio: 357,077202 0,129051 (ms)
Ręcznie robione wyrażenie lambda:
  Odpowiedzi: 345029281 124696 (ms)
  Średnio: 345,029281 0,124696 (ms)

Opanowany:
  Odpowiedzi: 340409238 123027 (ms)
  Średnia: 340,409238 0,123027 (ms)
Wyrażenie złożone:
  Odpowiedzi: 350800599 126782 (ms)
  Średnio: 350,800599 0,126782 (ms)
Ręcznie złożone wyrażenie:
  Odpowiedzi: 352811359 127509 (ms)
  Średnio: 352,811359 0,127509 (ms)

Skompilowana wydajność lambda na delegatach może być wolniejsza, ponieważ skompilowany kod w czasie wykonywania może nie być zoptymalizowany, jednak kod napisany ręcznie i skompilowany za pomocą kompilatora C # jest zoptymalizowany.

Po drugie, wiele wyrażeń lambda oznacza wiele anonimowych metod, a wywołanie każdej z nich zajmuje trochę więcej czasu niż ocena metody prostej. Na przykład dzwonienie

Console.WriteLine(x);

i

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

są różne, a przy drugiej wymagane jest trochę więcej narzutów, ponieważ z punktu widzenia kompilatora są to właściwie dwa różne wywołania. Najpierw wywołanie samego x, a następnie w ramach tej instrukcji wywołującej x.

Zatem połączona Lambda z pewnością będzie miała niewielką wydajność w porównaniu z pojedynczym wyrażeniem lambda.

Jest to niezależne od tego, co jest wykonywane w środku, ponieważ nadal oceniasz poprawną logikę, ale dodajesz dodatkowe kroki do wykonania przez kompilator.

Nawet po skompilowaniu drzewa wyrażeń nie będzie miało optymalizacji i nadal zachowa swoją małą złożoną strukturę, ocenianie i wywoływanie go może wymagać dodatkowej walidacji, sprawdzenia wartości null itp., Które mogą spowalniać wydajność skompilowanych wyrażeń lambda.