Enhanced Weak Events Part One - DynamicMethod vs. Expression Tree Compilation

Introduction / Background

In my last post some months ago I showed a use case for weak events*. Since then, I've ran into some other interesting event problems, and that gave me time to make some improvements over Daniel's code.
* If you're not familiar with the concept of weak events, I believe the best introduction you can find is Daniel Grunwald's article.

Weak Events Enhancements Part One: Faster Forwarder Delegates / DynamicMethod vs. Lambda Expression Compilation

The first improvement that I made is, in fact, the last that I've implemented. In Daniel's final solution (FastSmartWeakEvent), a forwarder method is compiled using System.Reflection.Emit.DynamicMethod. Although this is a very light way to generate code dynamically, it's very low level. Usually, the generating code is quite unreadable and very hard to debug, to modify or to extend. Daniel's first version, for example, had a type safety issue. I imagine that it was hard to find, and the solution is not obvious to understand (at least it wasn't obvious for me).

For some time I was wondering if there was any higher level alternative to a raw DynamicMethod. The usual way to hide low level code is by encapsulating it inside a higher level framework. I don't remember how the idea came to me at the time, but I realized that .NET Framework 3.5 already contains what I was looking for: Expression Trees.

Expressions trees can be composed dynamically, and compiled to a delegate whenever they are ready. I tried it out, and developed a new WeakEventForwarderProvider class. The implementation details have several interesting catches. In fact, I think there are enough of them that I'll cover them in another post. Until then, feel free to check out the code. For now, I'll share the results that I've found.

Maintainability: Readability is a key feature of a maintainable code, but opinions might always diverge about it. It depends on coding style, and my style is somewhat unusual. Even though I admit the new code is not easy to read, I feel that it has improved a bit from the original; and there is still room for improvement. Debugging, on the other hand, has certainly been improved. The main reason for this is that the debugger is able to show any intermediate expression as nice programmer-readable strings. They can also be converted to string. So, it's much easier to know what is being generated.

Correctness: Using DynamicMethod, it's possible to generate any sequence of IL commands. One obvious advantage of this is a very high flexibility. The trade-off is that it's too easy to generate broken code. Expression trees work as middle ground solution. Its major restriction is that statements are not allowed inside expressions. Fortunately, that can be worked around, specially when generating small pieces of code (I promise to explain how in a future post). A great advantage expressions do provide is a very good validation at dynamic-code-generation-time. The type safety bug that leaked from Daniel's first version of WeakEvents was found and fixed very easily using expressions.

Compiling Performance: I knew that expression compilation uses DynamicMethod internally, so I took for granted that it would be slower to compile. Surprisingly enough, the results that I've measured were close to a tie. Sometimes it appeared that lambda compilation was faster. This is still puzzling to me. While I don't find a good explanation, I'll let the topic open for discussion. My best guess is that the overhead that expression trees add is so much smaller than the overhead of emitting the code that, proportionately, the first can be disregarded.

Executing Performance: Code execution performance is a tricky subject. You can always try to tweak assembly code to make it faster. You can do it at IL level with DynamicMethod too. But that generally is a bad idea. To quote Donald Knuth, premature optimization is the root of all evil. I've found out that the expression tree compiler is quite good. My tests have shown that my expression-generated delegates were about 15% faster to execute than the ones that Daniel has got. That's better than I've expected.

Performance-wise, I came to a conclusion that simply reinforces one of my software beliefs. A well-built framework will not make user code slower. Actually, some remarkable cases are capable to make user code even faster. In my opinion, instead of optimizing your code, find a good library or framework to do the job for you. If you can't find it, do not optimize. At least not now. Considering all aspects, my expression tree solution was very satisfactory. And it was fun to code too.

Following Posts

These are the next posts that I'm planning to write on Weak Events:
- Events Part Two: Immutable event entry list;
- Events Part Three: Synchronized Events
- Events Part Four: Custom Events and unsolved problems
- Dynamic Code Generation With Lambda Expressions

Source Code

Download Custom Events source code here (v1.1 @ 2008.07.31). It contains stuff that I've not discussed yet. If you're eager to see it, feel free to delve into the code. See you soon (I hope :)).

Updated at 2009.08.03: Source code link updated.

Dynamic Lambda Expressions Using An Isolated AppDomain

Background

In August, I submitted a post about Lambda Expressions and Differentiation. There, I told shortly about a dynamic compiler for lambda expressions using CodeDom. I've enhanced the compiler so that it now deserves a post of its own.

Introduction

I'll start with the original problem that I needed to solve. I wanted to make a console application that would accept lambda expressions wrote by the user, transform it in another lambda expression and show it. After some research, let me list some of the stuff that can or can't be done with .NET:

1. One can write a lambda expressions to a easily readable string (that is similar to C# code, but it's not compilable);
2. One can dynamically create lambda expressions using static functions of the Expression class;
3. One cannot create (at least not directly) lambda expressions from a string containing valid C# code;
4. One can dynamically compile code using CodeDOM.

Due to feature #1, it's effortless to show the transformed lambda expressions to the user. Feature #2 is essential to the transformations that I intended to do, which was finding derivatives (please, read the original post if you're interested).

A major problem came along when I realized the fact #3. So, the source lambda expressions in the first versions of my little application were hard coded. After I finished the derivation part, I began searching for options to generate lambda expressions from user inputted strings.

One alternative was to make a parser (or find on the web) that put together an expression using feature #2. The other alternative is to let the framework do it by dynamically compiling the code (feature #4). Since the second is promptly available and is much more reliable than any parser I could code, that's what I chose to use.

Dynamic Compilation

Before I continue, let me state that I'll not get into the details about using CodeDOM. Here is a much more detailed explanation. Also, although you can compile VB.NET too, I'll talk only about C# here, sorry.

Basically, it works like this. You need the full text of one or more source code files (including usings, namespaces, classes, and so forth). Then, through a CodeDomProvider, you can compile your code to an Assembly. The assembly can exist only in memory or it could be generated directly to a file. You can access and execute what is in the assembly by reflection.

For my particular case, where I wanted to generate lambda expressions from a string, CodeDOM is too generic. So, I made a wrapper around it that compiles a lambda expression code string by filling the template below. Then, using reflection I executed DynamicFunc and forwarded the returned LambdaExpression.

using $Using0$;
using $Using1$;
//...
using $UsingN$;
namespace JpLabs.DynamicCode.DynamicAssembly
{
    public static class DynamicClass
    {
        public static LambdaExpression DynamicFunc() {
            return (Expression<$DelegateType$>)( $LambdaExpresion$ );
        }
    }
}

This solution solved my problem, but it has some issues. First, it's slow. Actually, it is not nearly as fast as it could be. One could say that I'm using an elephant gun to kill a fox. It's possible to modify it to compile several expressions at once, but that was not the case. I needed to compiled expressions one by one as the user inputs it.

The bigger issue is that, each time an expression is compiled, an assembly is generated. Unlike object instances, the memory of loaded types and assemblies can't be release. In fact, there's one way to do that, it's by unloading the entire application domain.

Cross AppDomain Dynamic Compilation

One application might use multiple domains for several reasons. But I believe nearly that all of them have to deal with one typical problem. Code in one domain cannot access data in other domain. So, they have to communicate in alternative ways. The two ways that are most straightforward are serialization and remoting.

The data I wanted to cross between domains are lambda expresssions. Unfortunately, a LambdaExpression is not Serializable. And remoting is not an option too. I need to be able to unload the compiler domain, and by doing this, all remoting objects would be released and the proxies would cease to work.

I thought I had hit a impassable wall. But I found this article with a solution. It also uses multiple domains to dynamically compile code. If you read to this point, you will probably like to take a look there too.

The idea somewhat crazy. .NET reflection allows you to access the IL of a method. One can pack it into a Serializable class and send it to another domain. There, the method would be reconstructed using the IL. This can be accomplished with the semi-magic DynamicMethod class. To let you understand its wonderful features, I'll quote MSDN remarks about it:
You can use the DynamicMethod class to generate and execute a method at run time, without having to generate a dynamic assembly and a dynamic type to contain the method. The executable code created by the just-in-time (JIT) compiler is reclaimed when the DynamicMethod object is reclaimed. Dynamic methods are the most efficient way to generate and execute small amounts of code.

The input for a DynamicMethod is exactly what we have: the IL that came from the compiled code on the other domain. The output is a delegate to a newly created (and releasable) function. Since the function returns our so desired lambda expression, we just need to call it.

Now, let me summarize the steps involved in this lambda expression compiler:

1. Create an AppDomain;
2. Instantiate a compiler (actually, a wrapper around CodeDOM) on the new AppDomain;
3. Compile the input string into an in-memory assembly using the template I've shown above;
4. Unload the compiler domain (or keep it for reuse and unload it later);
5. Extract the IL of the DynamicFunc method (please, refer to the template), and send it to the original domain;
6. Employ a DynamicMethod to get a delegate from the compiled IL;
7. Call the delegate and it shall return a LambdaExpression.

Conclusion

Here's an reliable way to dynamically compile code without requiring always more memory. To be honest, I did some improvements that I didn't mention above. To mention, I tried to make the compiler generic enough so that it could compile other stuff than lambda expression. I think you can simply extend the compiler to achieve that. Please, tell me if anyone of you get to the point of doing that. I'll even let you in a short future-possible-enhancements-list:

• Extend compiler to compile other stuff than lambda expressions;
• Improve the compiler so that it can compile a batch of code strips.

And, finally, the source code download link: here. Of course, this source includes a test project for the compiler. And, of course, the test project is my Differentiator.

Thanks!

Lambda Expressions and Differentiation (continued)

Today, I made a presentation about the first article that I've posted on this blog. Since then I did some improvements on the code.

The one extra feature that I implemented was a parser for lambda expressions. One of the first things that I did when I started fiddling with lambda expression was trying to generate one from a string. To my disappointment, there's not such a feature included in the .NET Framework. So, I coded a humble one using CodeDom.

I'm sharing the last source code that I have. You're free to play with it with one condition. You have to share enhancements with me. :P

Also, I would like to let a challenge here. If you want to learn Lambda Expressions and don't have an idea to implement, try making code to simplify a polynomial function.

Finally, as always, please, let your comment here.

Lambda Expressions and Higher-Order Functions

[This article has a continuation here]

First, I need to ask you not to be scare of the title I've chosen. Less than two months ago, I barely knew what the first name was and have never heard of the latter.

As you might know, the brand-new C# 3.0 has support to lambda expressions. You can imagine it as a less wordy way to describe anonymous delegates. A major difference between them is that a lambda expression doesn't necessarily needs to be compiled. In fact, it's just a representation of a function. In addition to being compiled, they can be serialized (if you want to pass it on), analyzed and even dynamically created at run-time. I'll be using the last two here.

Now, let me introduce the computational (as well as mathematical) concept of a higher-order funcion (aka operators in math). It's nothing more than a function that receives another function as a parameter and/or returns a function.

Why would a function receive another function as a parameter? If you can't imagine a good answer or are just not convinced there's one, I suggest that you read this very didactic article (this is also good). Anyway, you can implement such functions in c# 2.0 without problems. What I want to examine are functions that returns another functions. If you are not using c# 3.0 (or a functional language), you might find some difficulties. Basically, you would be limited to returning one of a set of pre-declared functions. You could try using closures or dynamic code generation to add some versatility, but it probably would be rather cumbersome.

You may be asking why would anyone need such higher-order function. I will let this question open and focus on how to implement it. I was searching for a good example and can't imagine a better one than the differentiation, i.e., the mathematical process of obtaining the derivative of a function.

So, I'll build a functional that receives a f(x) and return a f'(x). The declaration of this in c# would be like that:

static public Expression<Func<double,double>> Differentiate(this Expression<Func<double,double>> f)
{
//I will find the derivative of f with respect to the variable x (it's the 1st and sole parameter)
ParameterExpression x = f.Parameters[0];

//Diff is the function that actually does the differentiation
Expression derivative = Diff(f.Body, x);

//Build a new lambda expression with the derivative expression body
return Expression.Lambda<Func<double,double>>(derivative, f.Parameters);
}

*Func<double,double> is a delegate type for functions that receives a single double parameter and returns a double. Expression<Func<double,double>> is the type of a lambda expression that represents a Func<double,double> function.

As you can see I used a Diff function that actually calculates the derivative. How does it work? It needs to analyze the original expression and create a new expression that represents its derivative. Luckily enough, this calculation can be done recursively using a set a rules. Let's start with the sum rule: namely, derivatives of sums are equal to the sum of derivatives. Coding that in c# 3.0 is easier than you one might thought. Look:

static Expression Diff(Expression exp, ParameterExpression dx)
{
switch (exp.NodeType) {
case ExpressionType.Add: {
BinaryExpression f = (BinaryExpression)exp;
//Sum rule: [g(x) + h(x)]' == g'(x) + h'(x).
return Expression.Add( //Create an add expression
   Diff(f.Left, dx),  //g'(x) +
   Diff(f.Right, dx)  //h'(x)
);
}
/* other cases omitted ... */
}
}

In similar ways, we can implement the other recursive rules (such as the product rule, the quotient rule, the power rule, etc). However, any recursion need a stop condition. We'll have two stop conditions: for constants, which derivative is zero; and for the variable x, which derivative is one. The code looks like this:

case ExpressionType.Parameter: {
//be aware that f(x) = y is a constant with respect to x
return (exp == dx) ? Expression.Constant(1d) : Expression.Constant(0d);
}
case ExpressionType.Constant: {
return Expression.Constant(0d);
}

There's also the chain rule, that is quite trickier to implement. I did it with very little code, though. As you're not faint of heart, take a look at my full source.

And that's all for the day, folks. Please, comment.