Skip to content

Fast Late-Bound Invocation with Expression Trees

March 6, 2009

Note: After working with expression trees further, I’ve found that generating CIL by hand is dramatically faster than using expression trees. Still, this is an interesting concept, and I’ve kept this post here for posterity.

The implementation of Ninject has some solutions to interesting problems. One in particular is somewhat sticky: how do we call any method, without knowing what methods will be called, nor their signatures, until runtime? The easiest way to do this is via MethodInfo.Invoke(), but reflection-based invocation is extremely expensive in comparison to normal invocation. Fortunately, we can solve this problem through the use of anonymous delegates and runtime code generation.

In order to do this, we need some sort of late-binding system. In Ninject 1, I used DynamicMethod and System.Runtime.Emit to emit CIL at runtime. This solution worked well, but was very complex, difficult to understand, and didn’t support medium trust scenarios. Ninject 2 instead leverages expression trees to accomplish the same thing – and actually, under the hood, the solutions are identical, since expression trees are translated into CIL opcodes when you compile the Expression<TDelegate>. From a code perspective, however, using expression trees is a much cleaner solution because it offloads the heavy lifting to the types in the BCL.

Basically, what I’m talking about is taking any method and creating a delegate for it with this signature:

delegate void object LateBoundMethod(object target, object[] arguments);

This is an open delegate, meaning it can be called on any instance of the type that declares the method that the delegate is bound to. The first parameter to the delegate, target, is the instance that the method will be called on. For example, if we create a LateBoundMethod delegate for String.StartsWith(), we can pass any string in as the first parameter.

The solution is surprisingly simple using expression trees:

using System;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

namespace FastDelegates
{
  public delegate object LateBoundMethod(object target, object[] arguments);

  public static class DelegateFactory
  {
    public static LateBoundMethod Create(MethodInfo method)
    {
      ParameterExpression instanceParameter = Expression.Parameter(typeof(object), "target");
      ParameterExpression argumentsParameter = Expression.Parameter(typeof(object[]), "arguments");

      MethodCallExpression call = Expression.Call(
        Expression.Convert(instanceParameter, method.DeclaringType),
        method,
        CreateParameterExpressions(method, argumentsParameter));

      Expression<LateBoundMethod> lambda = Expression.Lambda<LateBoundMethod>(
        Expression.Convert(call, typeof(object)),
        instanceParameter,
        argumentsParameter);

      return lambda.Compile();
    }

    private static Expression[] CreateParameterExpressions(MethodInfo method, Expression argumentsParameter)
    {
      return method.GetParameters().Select((parameter, index) =>
        Expression.Convert(
          Expression.ArrayIndex(argumentsParameter, Expression.Constant(index)), parameter.ParameterType)).ToArray();
    }
  }
}

When you call the Create() method, DelegateFactory creates an anonymous delegate that accepts loosely-typed parameters, casts them, and invokes the actual method that you specified.

You can use the DelegateFactory like this:

MethodInfo method = typeof(String).GetMethod("StartsWith", new[] { typeof(string) });
LateBoundMethod callback = DelegateFactory.Create(method);

string foo = "this is a test";
bool result = (bool) callback(foo, new[] { "this" });

result.ShouldBeTrue();

Obviously this is a contrived example since we know the type at compile-time. However, if you don’t know what types or methods you’ll be using, this is a great way to avoid the expense of reflection. After you build the delegate originally, your code operates reflection-free for as many times as you want to invoke the method.

We’re using this technique in Community Server REST futures, to bind a call to a REST actions to a specific method on a controller that handles the request. Since these REST actions must support many successive calls, the use of these generated delegates dramatically increases our performance versus reflection-based invocation.

About these ads

From → miscellaneous

29 Comments
  1. I get an ArgumentException (Expression of type ‘System.Boolean’ cannot be used for return type ‘System.Object’) on the Expression.Lambda call.

  2. Interesting… I wonder if I need to figure out boxing. This was notepad code, extracted from our codebase. :)

  3. Used “Expression.Convert(call, typeof(object))” instead of just “call” as the first parameter, and all works.

  4. Ah, there we go. That’ll take care of boxing. Thanks, I updated the post.

  5. Alex Lyman permalink

    For the boxing, you just need the lambda body to be `Expression.Convert(call, typeof(object))` instead of just `call`.

  6. It appears that to make this “complete” you different Create methods for instance methods, static methods and constructors. Each follows roughly the same pattern, with minor variations. Given those three delegate factory methods, you’ve got a very nice little late-bound delegate factory. With a little creativity, it might be possible to reduce the three Create methods into a single method, but that means having to pass null for the “target” of static methods and constructors. Nice idea. Thanks for the post.

  7. This is a cool solution, but I wonder how much overhead you’re really saving here over a method.invoke() call? If you still have to look up the MethodInfo with Reflection you’re probably hitting the most expensive part of the Reflection call (Invoke) in the first place.

  8. Rick, for a single call, this would be more expensive. The use scenario for this is when you’ll be calling the method repeatedly, and in that case you cache the LateBoundMethod and pay the expense of reflection (and expression compilation) only once. Calling the LateBoundMethod should be much faster than calling MethodInfo.Invoke.

  9. Simone Busoli permalink

    Wouldn’t this be enough?

    var method = typeof(string).GetMethod(“StartsWith”, new[]{typeof(string)});
    var del = Delegate.CreateDelegate(Expression.GetFuncType(new[]{typeof(string), typeof(string), typeof(bool)}), method);
    (bool)del.DynamicInvoke(“aa”, “a”);

  10. @Simone: Yes, that would work, but DynamicInvoke() is almost as expensive as MethodInfo.Invoke(). You still need to have objects of the proper types in order to pass them to the strong-typed Invoke() method of a delegate. The expression trees allow you to interface with the delegate with only a collection of weak-typed System.Objects.

  11. Simone Busoli permalink

    Yes, that would work, but DynamicInvoke() is almost as expensive as MethodInfo.Invoke(). You still need to have objects of the proper types in order to pass them to the strong-typed Invoke() method of a delegate. The expression trees allow you to interface with the delegate with only a collection of weak-typed System.Objects.

    Nate, you’re right on the first part and wrong on the second, you don’t need to know anything more than you need to know with he expression-based solution.
    Anyway, it looks that DynamicInvoke is even slower than MethodInfo.Invoke.

  12. @Simone: I was saying, if you want to avoid DynamicInvoke() and use Invoke(), you need to know the types. That’s the difference between Delegate.CreateDelegate() and the expression tree solution.

  13. Simone Busoli permalink

    Nate, the Delegate class has no Invoke method, I’m not sure I follow you.

  14. @Simone: The Delegate and MulticastDelegate classes don’t define the Invoke() method directly, but concrete delegate types do individually. MulticastDelegate is an odd type; it’s handled specially by the CLR.

    If you do:

    Func func = x => x.ToString();

    These two lines are equivalent:

    func(42);
    func.Invoke(42);

    Point being, if you call Invoke(), you need to match your arguments to the type of the delegate. Using the expression tree pattern, you can call the delegate using weak-typed arguments, but still reap the performance benefit of avoiding DynamicInvoke() or MethodInfo.Invoke().

  15. Simone Busoli permalink

    Point being, if you call Invoke(), you need to match your arguments to the type of the delegate.

    Sure, but we’re not dealing with delegates here, just Delegates, so what’s the point?

  16. @Simone: I don’t even know what we’re debating now. My only point is that calling Delegate.CreateDelegate() is not an effective solution, because you still have to use DynamicInvoke(). The only way to get the performance gain is to be able to call Invoke() on the delegate, which you can do with the expression tree method but not with CreateDelegate().

  17. Simone Busoli permalink

    I don’t know either, you just keep saying the following


    You still need to have objects of the proper types in order to pass them to the strong-typed Invoke() method of a delegate. The expression trees allow you to interface with the delegate with only a collection of weak-typed System.Objects

    Which is wrong. What’s right, instead, is that the solution based on expressions is faster than other solutions.

  18. Here are my points:

    1. Delegate.CreateDelegate() will create a new delegate at runtime, but to invoke it you have to use DynamicInvoke(), which is slow.

    2. In order to avoid the cost of DynamicInvoke(), you have to call the Invoke() method on a delegate, which requires that you know (at compile time) the method’s signature.

    3. The expression tree technique allows you to create a weak-typed open delegate, which casts the arguments passed in to the correct types, and invokes the original method.

    4. You can call the Invoke() method of the delegate generated by the expression tree technique without knowing (at compile time) the types of arguments you’re passing in.

    I don’t understand why you think that I’m incorrect, but I’m getting the impression that you either missed the point or that you just want to be argumentative. If it’s the former, I’ll ask you to re-read the original post; if it’s the latter, I’ll ask you to go elsewhere.

  19. Simone Busoli permalink

    I won’t go over your reply. Let me just say that you look like a skilled verbalist, and your replies to my comments were mostly out of context.
    I know what you’re talking about, it’s just very badly exposed.

  20. Nate – after running some perf tests on this I’m not sure if it’s worth it to do this, unless you make a boat load of calls against your dynamic delegate (and this might make good sense in nInject).

    The compilation of the delegate is wickedly expensive – in my tests you’d have to make somewhere around 2500 Reflection calls to make up for the compilation overhead. Perf is super fast once you have the compiled delegate, but it’s heavy price to pay up front.

    Here’s what I played with:
    http://www.west-wind.com/weblog/posts/653034.aspx

  21. I remember when I coded C++ how memory management was a big issue, and I found it very exciting, and very nerdy.
    In C++ people would do big (I mean BIG) work to make automatic memory management instead of running new() and delete() all the time.
    And I remember thinking when I started coding C# that all this garbage collection was just for people who didn’t understand to code.
    However I dit grow wiser and now understand how C# raised the bar (abstraction) for me so I didn’t have to do technically challenging and nerdy stuff, but simply use the right tool (.Net) for the right job.
    I see the same thing here, what you are trying to do would be very easy and simple to do in a dynamic language like Ruby…

  22. @Klaus: That’s true, with a language that supports dynamic dispatch, this would be simpler. However, the whole concept is to *reduce* the cost of late-bound invocation. Using Ruby, you pay a much higher price on *every* invocation, since the compiler can’t determine the method bindings at compile-time.

    This isn’t to say Ruby isn’t a great language, but it’s also not the “next step” in programming — it’s just a different way of thinking that happens to have become more popular in recent years.

  23. I think you’re idea is great. I’ve faced the same problem in the past and I completely missed the possibility of using lambda expressions.

    Although I have no doubts that your solution works and is fast enough, I see some room for improvement.

    First thing, you can add the ‘params’ keyword to the LateBoundMethod delegate like that:
    public delegate object LateBoundMethod(object target, params object[] arguments);

    With this, it’s not necessary to explicitly create an array when calling the delegate. For example, you could write:
    bool result = (bool) callback(foo, “this”);
    instead of:
    bool result = (bool) callback(foo, new[] { “this” });

    My second point is more relevant. I was worried about argument validation. For example, what would happen if someone calls a LateBoundMethod passing an incorrect number of parameters? Or if arguments = null?

    Better than simply asking, I tested it. The asnwers were IndexOutOfRangeException and NullReferenceException, respectively. Both exceptions are somewhat ugly for a grownup component to throw. IMHO, the more “correct” exceptions would be TargetParameterCountException and ArgumentNullException.

    I went ahead and tried to implement this change. I think I’ve reached a reasonable solution. Of course, argument validation will slow down the execution a bit for both generation and calling. Anyway, I believe any mature code should do this.

    Nate, if you don’t mind, I’ll post my solution on my blog. Naturally, with a very big reference to the original author. In the meantime, if anyone is interested in seeing my code, send me an email (jpbochi at gmail dot com).

  24. Ameesh permalink

    Great work !

    However while I can get this to work with most method calls, it doesnt seem to work with methods that dont have a return value. (void methods).. ?

  25. Ahh! Fantastic! This was just what I was looking for. After pulling my hair for hours, your little example helped me solve my issue in about 20 minutes.

    Thanks a million!

Trackbacks & Pingbacks

  1. Weekly Web Nuggets #54 : Code Monkey Labs
  2. More on Late-Bound Invocations with Expression Trees - Jimmy Bogard -
  3. AGS SOE’s without the SOAP – v2 « MapWrecker 2.0
  4. Elegant Code » CreateDelegate<T> – An Exercise in Using Expressions

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: