Playing with expression trees in the rain
In addition to meeting friends and family, my vacation has offered a lot of hacking opportunities, as the weather has been far from optimal. I've been looking into Expression Trees, which is what makes LINQ (a C# 3.0 feature) fly. First of all LINQ stands for Language INtegrated Query (I guess LIQ wasn't such a good name), sort-of SQL integrated into the programming language itself. You can run queries on collections, XML and databases out-of-the-box or you can write your own LINQ provider.
This is where Expression Trees comes into the picture. Expression trees is a feature most often found in compilers as a subset of AST (Abstract syntax trees). Expression trees are data structures for representing expressions. The relation between LINQ and expression trees are not the point of this blog post, lets just say that LINQ ships with an expression tree implementation which can be used for other purposes. The System.LINQ.Expressions namespace (which I think lives in the DLR project on Codeplex, which means it is Open Source under Ms-PL) contains everything you need to create your own expressions and compile them at run-time.
After reading about Expression Trees I digged up a small hack of mine called Symbols. It is a tiny library (just barely a shelf actually) for calculating the derivative of mathematical functions.
Variable x = new Variable(), y = new Variable(); RealNToReal G = x*x + x*y + y*y; RealNToReal dGdx = G.dfd(x); // dG/dx RealNToReal dGdy = G.dfd(y); // dG/dy x.Value = 45; y.Value = 30; Console.WriteLine( "G({0},{1}): {2}, dG/dx({0},{1}): {3}, dG/dy({0},{1}): {4}", x.Value, y.Value, G.Evaluate(), dGdx.Evaluate(), dGdy.Evaluate()); // Outputs G(45,30): 4275, dG/dx(45,30): 120, dG/dy(45,30): 105
Behind the scenes this code actually creates a tree of objects of different types for different purposes. Of course this is very simple since the parsing is implicitly done by the overloaded operators. For example, the object G will contain this tree:
Add Add Mult Variable (45) Variable (45) Mult Variable (45) Variable (30) Mult Variable (30) Variable (30)
But the dfd(Varible v) method explicitly manipulates this tree (actually, it creates a new one), for example dGdx becomes:
Add
Add
Add
Mult
Constant (1)
Variable (45)
Mult
Variable (45)
Constant (1)
Add
Mult
Constant (1)
Variable (30)
Mult
Variable (45)
Constant (0)
Add
Mult
Constant (0)
Variable (30)
Mult
Variable (30)
Constant (0)
As you can see there is room for optimizations (reduce multiplications of 1 and 0, anyone?). However, this is a perfect example of Expression Trees, though I didn't realize it when I wrote it. But I've now added a method that creates a System.LINQ.Expression from a RealNToReal tree. This allows the tree to be compiled to a delegate, which means much faster evaluation (execution actually) and more convinience:
var lambda = dGdx.GetExpression<Func<double, double, double>>(); var comp = (Func<double, double, double>)lambda.Compile();
I also wrote this snippet to find out the difference in execution time:
Func<double, double, double> eval = (X, Y) => { x.Value = X; y.Value = Y; return dGdx.Evaluate(); }; start = DateTime.Now; for (int i = 0; i < 1000000; i++) eval(i, 45); TimeSpan diff1 = DateTime.Now - start; start = DateTime.Now; for (int i = 0; i < 1000000; i++) comp(i, 45); TimeSpan diff2 = DateTime.Now - start; Console.WriteLine(diff1); Console.WriteLine(diff2); Console.ReadLine();
Which outputs something like
00:00:00.6084000 00:00:00.0156000
most of the time. Sometimes the difference is less though, but what varies is the evaluated tree, not the compiled method. One important thing is the cast to the delegate type (Func<double, double, double>). If this is not performed you'll have to run the method using DynamicInvoke, which is much slower! Spent some time wondering why my tree evaluation was faster than the compiled method. Lesson learned.
If anyone else is bored by crappy weather, feel free to play around with the code: Symbols.cs.
Comments
No comments so far. You leave the first:
© 2008 Markus Johnsson