.NET Stateful delegates and memoization


I’ve been planning to write about stateful anonymous delegates for quite some time now so here I go :-)

The common perception of anonymous delegates is that they are stateless functions used for filtering and transformations and similar things.

What is less known is that anonymous delegates can hold state by binding to local variables.
If you create an anonymous delegate inside a factory method, you can infact give the delegate it’s own state.

Example:

static Func<int> CreateCounter() 
{
     int i = 0; //bind delegate to a local mutable variable 
     return () => i++; 

     //"i" doesn't really go out of scope here 
     // because it is bound to our delegate 
}

By using this method we can now create a stateful delegate:

var myCounter = CreateCounter(); 
Console.WriteLine( myCounter() ); //prints : 0 
Console.WriteLine( myCounter() ); //prints : 1 
Console.WriteLine( myCounter() ); //prints : 2

The above code will print 1, 2, 3 in the console window, simply because the delegate is increasing the value of the bound variable inside it’s body.

So where does anonymous delegates store it’s state?
The state is stored as fields inside a class that is auto generated by the C# compiler.
This class will contain the state for all bound variables / arguments that are used inside anonymous delegates defined inside the same method.

And when is this useful?
To be honest, almost never ;-)
But there are cases where it is actually quite nice.

Here is a sample that I came up with after reading Ayendes blog ( http://www.ayende.com/Blog/archive/2008/06/04/Review-Umbrella-project.aspx )
He wrote about “memoization” and I thought that would make a great example of stateful delegates.

We can create memoizations in C# by exploiting the fact that anonymous delegates bind to local variables.

Example:

static Func<T1, T2, TResult> CreateMemo
    <T1, T2, TResult>(Func<T1, T2, TResult> source)
{
    var cache = new Dictionary<string, TResult>();
    return (arg1, arg2) =>
           {
               string key = string.Format("{0}|{1}", arg1, arg2);
               if (!cache.ContainsKey(key))
               {
                   var value = source(arg1, arg2);
                   Console.WriteLine
                       ("Returning {0} and adding it to cache", value);
                   cache.Add(key, value);
                   return value;
               }
               else
               {
                   var value = cache[key];
                   Console.WriteLine
                       ("Returning {0} from cache", value);
                   return value;
               }
           };            
}

This code will create a memoization for any delegate of the type Func<T1, T2, TResult>.
You simply pass a delegate to it, and you will get a memoized delegate back.

The code creates a dictionary that will act as our cache.
And then returns a new delegate that are bound to this dictionary.
The returned delegate will transform it’s arguments into a key and then check if the key is present in the cache.
If the key is present, it will return the cached value.
And if not, it will call the wrapped delegate and then store the result in the cache.

You can even pass normal methods as argument to the memoizer and get a delegate that acts as a cache around your method.

Well that’s it :-)
Now go and abuse the mutable variable bindings in your delegates.

Enjoy.

//Roger

Linq to objects for .NET 2 available


Patrik Löwendahl blogged about using C#3 features in .NET 2 via VS.NET 2008 a few days ago:
http://www.lowendahl.net/showShout.aspx?id=191

There are quite a few of the new features that works straight out of the box.
However, Linq does not, alot of the code that Linq uses is simply not present in the .NET 2 BCL.

So, inspired by Patriks post I opened up an old custom Linq engine that I wrote a while back and spiced it up and adapted it for .NET 2.
I also added a few of the standard list extensions such as “Take” “Skip” etc.

The code can be found here:
www.puzzleframework.com/Roger/LinqForNet2.zip

And before you get all excited, this is only Linq to objects, NOT Linq to SQL….

The code supports the following Linq constructs, features and list extensions:

  • from (ok ok, I didn’t have to code anything for that)
  • where
  • join
  • groupby
  • orderby
  • select
  • Take
  • Skip
  • TakeWhile
  • SkipWhile
  • Distinct
  • Deferred execution

Enjoy : – )

 //Roger

Linq Expressions – Creating objects


This post shows how you can use Linq expression trees to replace Activator.CreateInstance.

but first, please note that this is a followup on Oren’s post so read it before you read mine:
http://www.ayende.com/Blog/archive/2008/02/27/Creating-objects–Perf-implications.aspx

In C#3 we can use Linq expression trees to solve this problem to.
I’m not saying that it is a better or faster solution than Oren’s IL emit version.
The IL emit is completely optimized for what it is supposed to do, so its hard to beat.
This is just an alternative if you are a bit affraid of IL emit ;-), Linq expressions are just easier to understand for most people. 

So how is it done?
First we need a delegate declaration:

delegate T ObjectActivator<T>(params object[] args);

We will use this delegate in order to create our instances.
We also need a generator that can compile our delegates from expression trees:

public static ObjectActivator<T> GetActivator<T>
    (ConstructorInfo ctor)
{
    Type type = ctor.DeclaringType;
    ParameterInfo[] paramsInfo = ctor.GetParameters();                  

    //create a single param of type object[]
    ParameterExpression param =
        Expression.Parameter(typeof(object[]), "args");
 
    Expression[] argsExp =
        new Expression[paramsInfo.Length];            

    //pick each arg from the params array 
    //and create a typed expression of them
    for (int i = 0; i < paramsInfo.Length; i++)
    {
        Expression index = Expression.Constant(i);
        Type paramType = paramsInfo[i].ParameterType;              

        Expression paramAccessorExp =
            Expression.ArrayIndex(param, index);              

        Expression paramCastExp =
            Expression.Convert (paramAccessorExp, paramType);              

        argsExp[i] = paramCastExp;
    }                  

    //make a NewExpression that calls the
    //ctor with the args we just created
    NewExpression newExp = Expression.New(ctor,argsExp);                  

    //create a lambda with the New
    //Expression as body and our param object[] as arg
    LambdaExpression lambda =
        Expression.Lambda(typeof(ObjectActivator<T>), newExp, param);              

    //compile it
    ObjectActivator<T> compiled = (ObjectActivator<T>)lambda.Compile();
    return compiled;
}

It’s a bit bloated but keep in mind that this version is completely dynamic and you can pass any constructor with any arguments to it.

Once we have the generator and the delegate in place, we can start creating instances with it:

ConstructorInfo ctor = typeof(Created).GetConstructors().First();
ObjectActivator<Created> createdActivator = GetActivator<Created>(ctor);
...
//create an instance:
Created instance = createdActivator (123, "Roger");

 And that’s it.
I haven’t done any benchmarking to compare it to Oren’s IL emit version, but I would guess that it is almost but not quite as fast.

Benchmark – Creating 1000 000 instances:

Activator.CreateInstance: 8.74 sec
Linq Expressions:         0.104 sec

My benchmarks is w/o the .ToString() stuff that is included in Oren’s post.. so don’t compare my numbers to his.. it’s done on a different machine too.

//Roger

Linq Expressions – Calculating with generics


You can find the full code for this post here:
http://www.puzzleframework.com/Roger/GenericMath.cs.txt 

The .NET framework lacks support for calculating with generic types.
There is no way to ensure that a generic type supports operations like Add, Sub, Div and Mul etc.

More about the problem can be found here:
http://www.thescripts.com/forum/thread278230.html

“They are not. There have been a few threads on this subject before,
and the conclusion was that it is impossible to perform any of the
built-in mathematical operations on generic types.”

Many have tried to come up with solutions for calculating with generic types, most of them based on provider solutions where you have to provide a “Calculator” class for each type that you want your generic class to support.
Quirky to say the least..

One such solution exists here: http://www.codeproject.com/KB/cs/genericnumerics.aspx

And don’t get me wrong, I’m NOT saying that those are bad implementations, it was just not possible to solve this in any clean way before.

But now when we have Linq Expression Trees we can solve this. and do it quite nicely.

We can produce delegates that performs the math operations for us.
Like this:

private static Func<T, T, T> CompileDelegate 
 (Func<Expression,Expression,Expression> operation) 
{ 
    //create two inprameters 
    ParameterExpression leftExp = 
 Expression.Parameter(typeof(T), "left");                   

    ParameterExpression rightExp = 
 Expression.Parameter(typeof(T), "right");                   

    //create the body from the delegate that we passed in 
    Expression body = operation (leftExp,rightExp);              

    //create a lambda that takes two args of T and returns T 
    LambdaExpression lambda = 
Expression.Lambda(typeof(Func<T, T, T>), body, leftExp, rightExp);              

     //compile the lambda to a delegate 
    // that takes two args of T and returns T 
    Func<T, T, T> compiled = (Func<T, T, T>)lambda.Compile(); 
    return compiled; 
}

 We can now call this method and get our typed delegates for math operations:

private static readonly Func<T, T, T> Add = 
    CompileDelegate(Expression.Add);

And this is pretty much all the magic we need to solve the problem with generics and math operations.
I have created a generic class that support all the standard operators based on this approach.

You can find the full code here:
http://www.puzzleframework.com/Roger/GenericMath.cs.txt

This makes it possible to use code like this:

private static T DoStuff<T>(T arg1, T arg2, T arg3) 
{ 
    if (!Number<T>.IsNumeric) 
        throw new Exception("The type is not numeric");       

    Number<T> v1 = arg1; 
    Number<T> v2 = arg2; 
    Number<T> v3 = arg3; 
         
    return v1 * v2 - v3; //not possible with normal generics 
}

OK that was a very naive example, but atleast you can see that it is possible to perform calcualtions on the generic type.
So no more provider based calculator classes, just fast typed delegates :-)

Enjoy

[Edit]
For those who are interested in this kind of stuff, there is a project called MiscUtil that can be found here:
http://www.yoda.arachsys.com/csharp/miscutil/

They do the same stuff as in this article, but much more complete and polished code than my sample.

//Roger

Linq Expressions – Access private fields


In this post I will show how you can use Linq Expressions to access private(or public) class fields instead of using Reflection.FieldInfo.

Normally when you want to access a field by its name on a type you have to resort to reflection.
You will end up with something like this:

FieldInfo field = MyType.GetField("someField",BindingFlags.NonPublic | .... ); 
object res = field.GetValue (MyObj);

This suffers from allot of drawbacks, it’s ugly, it’s untyped and its horribly slow to access data via FieldInfo.

Instead of playing around with FieldInfo, you can now use Linq Expressions to build a typed delegate that does this for you.

Here is how you do it:

public static Func<T,R> GetFieldAccessor<T,R>(string fieldName) 
{ 
  ParameterExpression param = 
  Expression.Parameter (typeof(T),"arg");  

  MemberExpression member = 
  Expression.Field(param, fieldName);   

  LambdaExpression lambda = 
  Expression.Lambda(typeof(Func<T,R>), member, param);   

  Func<T,R> compiled = (Func<T,R>)lambda.Compile(); 
  return compiled; 
}

So what does this method do?
The first line in it will create a parameter expression, that is an argument that will be passed into our delegate eventually.

The next line creates a member expression, that is the code that access the field we want to use.
If you look at the code, you will see that we create an expression that access fields (Expression.Field) and that the first arg is the parameter we created before and the 2nd arg is the name of the field we want to access.
So what it does is that it will access the named field on the object that we pass as an argument to our delegate.

The 3rd line is where we create our lambda expression.
The lambda expression is the template for our delegate, we describe what we want to pass into it and what we want to get out of it.

The last part of the code will compile our lambda into a typed delegate: Func<T,R>, where T is the type of the argument we want to pass it and R is the type of the result we want to get out of it.

Here is an example on how to use this code:

Person person = new Person(); 
person.FirstName = "Roger"; 
var getFirstName = GetFieldAccessor<Person,string> ("firstName"); 
... 
//typed access via delegate 
string result = getFirstName(person);

Also do note that the “firstName” arg is the name of the field we want to access, not the property that I access in the sample.

This approach is also much faster than Reflection.FieldInfo.
I made a little benchmark where I accessed the same field a million times.

The Reflection.FieldInfo approach took 6.2 seconds to complete.
The Compiled lambda approach took 0.013 seconds to complete.
That’s quit a big difference.

So with this approach you can optimize your old reflection code and get some serious performance gains..

Well, that’s all for now.

Enjoy.

//Roger

kick it on DotNetKicks.com

See also: