A Scrum Of One

Classes and Memoization - A Neat C# Trick

2013-11-03T20:33:00.000-08:00

This post talks about a set of utilities provided in the BrightSword SwissKnife library (nuget, codeplex).

When programming in the real world (as opposed to programming for an academic exercise), we and (and should) combine concepts to synergistically improve our solution.

We have visited Memoization as a technique, and have seen the use of functional programming to provide more succinct, maintainable code in discussing the Reflection Utility.

In this post, we will combine those two concepts (and derive a programming rule-of-thumb) to provide a more efficient utility for Reflection.

You will find this utility here, and can access it as BrightSword.SwissKnife.TypeMemberDiscoverer<T>

The Simple Approach

The Reflection Utility extension method surface is simple to use and highly maintainable, because there is minimal code-duplication.

To re-cap, our extension method surface for properties looks like:

public static IEnumerable<PropertyInfo> GetAllProperties(this Type _this, BindingFlags bindingFlags = DefaultBindingFlags)
{
    return _this.GetAllMembers((_type, _bindingFlags) => _type.GetProperties(_bindingFlags), bindingFlags);
}

which allows for usage like this:

var readonlyProperties = typeof (T).GetAllProperties().Where(_ => !_.CanWrite || _.GetSetMethod() == null);

One of the immediately evident drawbacks is that each invocation of the extension method involves reflection over the type’s members, and therefore we pay a linear cost for reflection.

One approach might be to consider Memoization to store and reuse the result of the reflection utilities, and pay the price for reflection just once. This post discusses the approach SwissKnife takes in order to do this.

The real problem with simple memoization is the BindingFlags parameter, which may select different sets of members each time. In order to optimally reduce the required computation, we could restrict the BindingFlags value to some reasonable default (such as ‘all public members’) and memoize the result-set of members by Type.

This line of thought leads to something like this:

public static class TypeMemberDiscoverer
{
    private const BindingFlags DefaultBindingFlags = BindingFlags.Default | BindingFlags.Instance | BindingFlags.Public;

    public static ConcurrentDictionary<Type, IEnumerable<PropertyInfo>> _propertySetCache = 
        new ConcurrentDictionary<Type, IEnumerable<PropertyInfo>>();

    public static IEnumerable<PropertyInfo> GetAllProperties(this Type type)
    {
        return _propertySetCache.GetOrAdd(type,
                                          _ => _.GetAllMembers((_type,
                                                                _bindingFlags) => _type.GetProperties(_bindingFlags),
                                                               DefaultBindingFlags));
    }
}

This approach still provides an extension method, and now the default property set is cached and the GetAllMembers call is only performed once.

However, we can use a feature of the C# language to get a slightly more elegant solution, and simultaneously derive a programming rule-of-thumb.

Static Fields in Generic Types

Because C# generic classes are true classes, a static field defined in an open generic class will actually be defined as a separate static field in each corresponding closed generic class.

Consider the open generic type:

public class Foo<T>
{
    private static int _bar;
}

Consider now, a Foo<int> and a Foo<string>.

Both of these closed generic types will have a static field of type int called _bar.

As expected, all instances of Foo<int> will share a static _bar field, and all instances of Foo<string> will share a static _bar field.

What you might not expect, however is that Foo<int> will not be the same as Foo<string>. In fact, Resharper™ and Microsoft Code Analysis both have warnings alerting you that this behaviour might be potentially unexpected – you might expect that the field is shared across all types that close the open generic type, but it won’t be!

However, in our case, this is exactly the behaviour we want! Because static fields in generic classes are actually only shared by instances of the corresponding closed generic type, we can use a generic class itself as a kind of memoization container, where we can cache something by Type!

So the general rule-of-thumb is: If you find yourself trying to cache against a type name for whatever reason, consider using a generic class as a cache container. The static initializers of a class are guaranteed thread-safe, and you can write more readable code and let the language provide the cache!

So we can write a generic type with one type parameter, as follows:

public static class TypeMemberDiscoverer<T>
{
    private const BindingFlags DefaultBindingFlags = BindingFlags.Default | BindingFlags.Instance | BindingFlags.Public;

// ReSharper disable StaticFieldInGenericType
    private static readonly IEnumerable<PropertyInfo> _properties = 
        typeof(T).GetAllMembers((_type,
                                 _bindingFlags) => _type.GetProperties(_bindingFlags), DefaultBindingFlags);
// ReSharper restore StaticFieldInGenericType

    public static IEnumerable<PropertyInfo> GetAllProperties()
    {
        return _properties;
    }
}

The usage is:

var readonlyProperties = TypeMemberDiscoverer<int>.GetAllProperties()
                                                  .Where(_ => !_.CanWrite || _.GetSetMethod() == null);

In the class above, we pay the price to discover the properties exactly once – when the TypeMemberDiscoverer<int> type is initialized. We can use the Lazy<T> pattern to further defer the evaluation to when the GetAllProperties() call is first invoked.

public static class TypeMemberDiscoverer<T>
{
    private const BindingFlags DefaultBindingFlags = BindingFlags.Default | BindingFlags.Instance | BindingFlags.Public;

// ReSharper disable StaticFieldInGenericType
    private static readonly Lazy<IEnumerable<PropertyInfo>> _propertiesL = 
        new Lazy<IEnumerable<PropertyInfo>>(
            () => typeof(T).GetAllMembers((_type,
                                           _bindingFlags) => _type.GetProperties(_bindingFlags),
                                          DefaultBindingFlags));
// ReSharper restore StaticFieldInGenericType

    public static IEnumerable<PropertyInfo> GetAllProperties()
    {
        return _propertiesL.Value;
    }
}

This is both efficient and easier-to-read, and it doesn't need a ConcurrentDictionary to work!

Summary

We can use the functional programming principle of memoization to cache the result of an expensive operation (recursive reflection). This eliminates repeated computation at the expense of memory.
We can do this elegantly by using a feature of the C# language which allows static fields in a generic type to act as a cache keyed by the type parameters.
We can further reduce wasted effort by using the Lazy pattern provided by the runtime, and only compute (and cache) results when first used

Functions as Function Results

2013-11-03T15:00:00.001-08:00

This post talks about a set of utilities provided in the BrightSword SwissKnife library (nuget, codeplex).

Learning to write performance-sensitive code is a journey. There are many programming tools and techniques which contribute to different aspects of improving code performance.

The most elegant of these are the fundamentally timeless classics – mathematical methods and proofs that are agnostic to technologies. However, understanding these techniques generally requires a rigorous understanding and application of logic and mathematical technique.

Memoizing is a commonly used mathematical technique to improve the performance of the act of calculations – historically, great care was taken to compute, verify and publish the values resulting from the calculation of formulae – logarithms, arithmetic and trigonometric functions, for example.

You will find a general-purpose Memoize function here, but its implementation is more advanced than is discussed by this post. We will cover the advanced issues in a future post which addresses recursion.

Introduction

We’ve seen that we can abstract away boilerplate code and parameterize logic using functions as function arguments.

We also had a stab at memoizing a function parameterized only by a single generic type parameter. We’re going to spend a little more time talking about memoizing functions now.

Consider the following snippet using the Math.Sqrt function, which computes the square root of a given positive real number.


var y = Math.Sqrt (Math.Sqrt (a)) + 2 * Math.Sqrt (b) * Math.Sqrt (a);

A function, such as Math.Sqrt, which always returns the same result for the same arguments without changing any other state is called a “pure” function. Such functions have a property known as referential transparency, which means that the result value of the function can replace its invocation in an expression. Because of this property, we do not need to evaluate Math.Sqrt(a) twice in the expression above. We could simply store the result against the argument somewhere and return it whenever the function is invoked with the same argument. Such a technique is called memoization.

Memoizing

We could take several approaches to memoize a function: the most naïve approach might be to use code such as:

public static ConcurrentDictionary<double, double> GlobalCacheForSqrt = new ConcurrentDictionary<double, double>();
public static double sqrt_memoized(double x)
{
    return GlobalCacheForSqrt.GetOrAdd(x,
                                       Math.Sqrt);
}

...

var y = sqrt_memoized(sqrt_memoized(a)) + 2 * sqrt_memoized(b) * sqrt_memoized(a);

This would work, but what price have we paid to make this happen?

We have created a global value cache to store the results of the Math.Sqrt function.
We have created a wrapper function to return the cached value and only invoke the Math.Sqrt function if we haven’t done it once before.

If we wanted to memoize another function, we would have to do the same two steps all over again, which is somewhat tedious. But somewhat more seriously, we are memoizing the results in mutable global state – making the system impure.

What we really want is to localize the cache somewhere local and safe, and also remove the tedium of writing the wrapping function.

Something that looks like this:


public class MemoizedSqrt
{
    private readonly ConcurrentDictionary<double, double> _cache = new ConcurrentDictionary<double, double>();

    public double Sqrt(double x)
    {
        return _cache.GetOrAdd(x,
                               Math.Sqrt);
    }
}

...

var sqrt_memoized = Memoize<double, double>(Math.Sqrt);
var y = sqrt_memoized(sqrt_memoized(a)) + 2 * sqrt_memoized(b) * sqrt_memoized(a);

This is much nicer – it has now hidden away the cache inside of a class, but we still have to write a different class for each function we want to memoize.

So let’s look at a different way of doing this – imagine we had a magic box which took in a function like Math.Sqrt, and returned the sqrt_memoized for us, automatically encapsulating a class with the cache in it.

Imagine no further – we can build such a box. It’s simply a higher-order function which takes a function as an argument and returns another function.


public static Func<TDomain, TRange> Memoize<TDomain, TRange>(Func<TDomain, TRange> f)
{
    private class M
    {
        private readonly ConcurrentDictionary<TDomain, TRange> _cache = new ConcurrentDictionary<TDomain, TRange>();
        private readonly Func<TDomain, TRange> _f;

        public M(Func<TDomain, TRange> f)
        {
             _f = f;
        }

        public TRange MemoizedF(TDomain x)
        {
             return _cache.GetOrAdd(x,
                                    _f);
        }
    }

    return new M<TDomain, TRange>(f).MemoizedF;
}

...

var sqrt_memoized = Memoize<double, double>(Math.Sqrt);
var y = sqrt_memoized(sqrt_memoized(a)) + 2 * sqrt_memoized(b) * sqrt_memoized(a);

And there you have it – one single function to memoize any single-argument function, all neatly packaged into a static method.

All done!

What? Howls of protest? This couldn’t work?

Of course it won’t work! There’s no way to embed the class M inside the Memoize function. But we have a nice, elegant solution and we don’t want to mess it up by making the class M public…what do we do?

Getting some Closure

The trick to getting that inner embedded class inside the function is to let the compiler put it there instead of writing the class ourselves.

Remember that we are writing a higher-order function, so we could just build and return the memoizing function in place.

Consider the following code:

public static Func<TDomain, TRange> Memoize<TDomain, TRange>(Func<TDomain, TRange> f)
{
    var _cache = new ConcurrentDictionary<TDomain, TRange>();
    return _ => _cache.GetOrAdd(_, f);
}

Let’s break this down – ignoring the type arguments:

Memoize is a function which takes in a function f and returns an anonymous function.
The function has a local variable _cache to cache appropriately typed results against arguments.
The result is a function which references the cache. The salient point to notice is that the _cache variable is outside the scope of the result function. We say that the result function closes over the _cache variable.
The function returned requires a proper reference to the _cache variable even after the Memoize function exits.
In order to keep the reference alive, the compiler creates an inner, anonymous class storing the closed variable and exposing a method representing the resultant function.
The compiler then instantiates the class and returns a reference to the method, which now references the closed variable legally.

In fact the anonymous class looks and behaves almost exactly the class we tried to sneak in.

This construct is called a closure, and is an excellent way to encapsulate state without creating classes and objects.

In fact, the last code snippet is a general purpose memoizing function for functions of one argument, and you will agree is much more elegant than any of the other alternatives!

Summary

SwissKnife provides a Memoize function to elegantly provide memoized versions of pure single-argument functions.
We can use the functional programming principle of higher-order functions to memoize pure functions to leverage Referential Transparency. Memoizing functions ensure that functions are evaluated only once per argument value and the cached value of the result can be used subsequently.
We use closures to encapsulate the state associated with the cache.

Functions as Function Arguments

2013-11-02T20:15:00.001-07:00

This post talks about a set of utilities provided in the BrightSword SwissKnife library (nuget, codeplex).

Reflection is a commonly used meta-programming technique where run-time inspection of types allows for more elegant solutions in some cases. The .NET framework provides powerful primitives to use reflection, which have a nice orthogonal and consistent interface for the various type elements.

A necessary, but less desirable, consequence of an orthogonal interface is the ‘boilerplate’ nature of the code which uses different elements. There is typically a great deal of symmetry and similarity in the code, which generally leads to a cut-copy-paste kind of code-proliferation – and results in unmaintainable code.

In this post, we’ll talk about the software techniques we can use to mitigate this form of code-proliferation, and actively develop a lean and maintainable utility without sacrificing flexibility.

You will find these utilities here, where there are a set of extension methods on the Type type.

Reflection Utilities

One of the fundamental principles of functional programming is the concept of a First-Class Function.

A language with a First Class function is one that allows functions to be treated exactly the same way as other first class entities such as variables and constants. This generally means that there is the concept of being able to pass in a function as an argument to another function (just like one can pass in a string as an argument), assign a function to a variable, or return the function as the result of a function.

This is a very powerful concept, as it allows us to parameterize logic just like we traditionally parameterize values.

GetAllProperties|GetAllMethods|GetAllEvents

Consider the problem of reflecting over a type and enumerating over its properties:

A naïve implementation of a function to enumerate a type’s properties might look like this:

public static IEnumerable<PropertyInfo> GetProperties(Type t) 
{ 
    foreach (var item in t.GetProperties()) 
    { 
        yield return item; 
    } 
}

An analogous method to enumerate methods would then be:

public static IEnumerable<MethodInfo> GetMethods(Type t) 
{ 
    foreach (var item in t.GetMethods()) 
    { 
        yield return item; 
    } 
}

The reason this is a naïve implementation is that interfaces do not inherit, in the traditional sense of the term, the members of their base interfaces – rather they inherit the requirement that the base interface is implemented as well. See my earlier post for the background to this problem.

The complete solution involves recursively walk up the inheritance chain for interfaces, whilst keep track of interfaces seen before, and enumerating the members of each interface encountered.

The code to do this is somewhat more involved:

public static IEnumerable<PropertyInfo> GetInterfaceProperties(this Type type,
                                                               ISet<Type> processedInterfaces = null) 
{
    Debug.Assert(type.IsInterface); 
    
    processedInterfaces = processedInterfaces ?? new HashSet(); 
    
    if (processedInterfaces.Contains(type)) 
    { 
        yield break;
    } 
    
    foreach (var _pi in type.GetProperties())
    { 
        yield return _pi; 
    } 
    
    foreach (var _pi in type.GetInterfaces()
                            .SelectMany(_ => _.GetInterfaceProperties(processedInterfaces))) 
    { 
        yield return _pi;
    } 
    
    processedInterfaces.Add(type);
}

After taking a single glance at this code, one can imagine what the analogous code for Methods and Events might be – a lot of similar code with a few method calls and types changed.

This is an ideal situation to use the functional programming support provided by C#.

We can wrangle out the boilerplate code out of this to get:

public static IEnumerable<TMemberInfo> GetInterfaceMembers(this Type type, 
                                                           Func<Type, IEnumerable<TMemberInfo>> accessor,
                                                           ISet<Type> processedInterfaces = null)
    where TMemberInfo : MemberInfo 
{
    Debug.Assert(type.IsInterface); 
    
    processedInterfaces = processedInterfaces ?? new HashSet(); 
    
    if (processedInterfaces.Contains(type)) 
    { 
        yield break; 
    } 

    foreach (var _pi in accessor(type)) 
    { 
        yield return _pi; 
    } 

    foreach (var _pi in type.GetInterfaces()
                            .SelectMany(_ => _.GetInterfaceMembers(accessor, processedInterfaces))) 
    { 
        yield return _pi; 
    } 

    processedInterfaces.Add(type); 
}

So by introducing the <TMember> type parameter to represent a MemberInfo generically, and providing a function argument accessor which provides a collection of members of the specified type, we can abstract out the boilerplate code and parameterize the accessor logic.

SwissKnife uses this approach to provide a set of extension methods on the Type type, which simply parameterize a common function:

public static IEnumerable<PropertyInfo> GetAllProperties(this Type _this, BindingFlags bindingFlags = DefaultBindingFlags) 
{ 
    return _this.GetAllMembers((_type, _bindingFlags) => _type.GetProperties(_bindingFlags), bindingFlags); 
} 

public static IEnumerable<MethodInfo> GetAllMethods(this Type _this, BindingFlags bindingFlags = DefaultBindingFlags) 
{ 
    return _this.GetAllMembers((_type, _bindingFlags) => _type.GetMethods(_bindingFlags), bindingFlags); 
} 

public static IEnumerable<EventInfo> GetAllEvents(this Type _this, BindingFlags bindingFlags = DefaultBindingFlags) 
{ 
    return _this.GetAllMembers((_type, _bindingFlags) => _type.GetEvents(_bindingFlags), bindingFlags); 
}

which allows for usage like this:

var readonlyProperties = typeof (T).GetAllProperties()
				   .Where(_ => !_.CanWrite || _.GetSetMethod() == null);

A functional approach to coding up these functions has reduced coding noise and resulted in simpler, easier-to-use, easier-to-understand and easier-to-maintain code.

Summary

SwissKnife provides a utility mechanism to simplify reflection over a type to enumerate different types of members. This is especially useful in the case of interface hierarchies.
We can use the functional programming principle of first-class functions to extract boilerplate code and parameterize logic in addition to values. This makes code easier to maintain.

Putting the Fun in Functional Programming

2013-10-31T04:59:00.001-07:00

Introduction

Like everyone who has been programming for some time, I have a set of tools and utility functions which I have developed over time, and reuse often.

My library of utilities has been available for some time both as open-sourced code and a free-to-use NuGet package.

The purpose of this series of posts is to talk about observations in my evolution as a functional programmer, and how the implementation and approaches I tend to take these days increasingly use functional concepts.

As you browse the code, you’ll come across more utilities than the ones discussed in this blog series. This series is going to try and focus on those utilities which demonstrate some facet of functional programming.

What is Functional Programming? Why do I care?

Functional Programming is a programming paradigm that treats programs as the evaluation of mathematical functions and expressions.

One can conceive of a kind of spectrum of programming abstraction:

Assembly Language which abstracts away parameterized opcodes
FORTRAN, COBOL and BASIC introduce control flow statements and subroutines
Pascal and C which allow for rich user-defined types, abstracting data and largely obviating the GOTO construct
Modula-2 and C++ which introduce concepts of objects maintaining state, encapsulating both data and related functions
Java and C# 1.0 which introduce concepts of managed memory and a virtual runtime environment, allowing for simpler creation of objects and popularizing Exceptions
Modern C# which introduces concepts of true type parameterization, lambdas and attributes. LINQ is a very powerful programming extension which is available here.
Scala introduces type classes and F# provides full type inference. These languages also use pattern-matching and recursion constructs to obviate some familiar imperative programming patterns.
LISP, a proto-functional language, is actually a multi-paradigm language, and as such, generally provides a great introduction to programming. LISP relies heavily on recursion, obviates some of the familiar programming constructs such as for loops and variables, introduces the concept of isomorphic code and data which makes it trivial to generate and immediately execute a function, and provides powerful meta-programming support.
Haskell, which emphasizes purity to the extent of introducing the concept of IO Monads to limit the impact of side-effects on a pure functional language.

Other authors have spoken cogently about the experience of a programmer skilled in a language somewhere in the spectrum (say a Java expert) looking up towards a more abstract language and not being able to comprehend why a construct or concept from that language would be useful or even necessary.

Therefore, it isn’t unreasonable to ask why we would need a functional programming perspective when we can do almost all we need with our daily programming language. Hopefully, as we go through this blog series, we’ll get a flavour of the kinds of things that functional programming makes easier, or possible!

What’s coming down the track?

Functions as Function Arguments
Functions as Function Results
Classes and Memoization - A Neat C# Trick
Introduction to Monads
The trouble with Exceptions!
Static methods and Classes

Acknowledgements

My involvement with functional programming goes all the way back to college, where teachers like Dr. Takis Metaxis introduced me to symbolic computing with LISP.

I highly recommend reading Real-World Functional Programming: With Examples in F# and C# by Tomas Petricek and Jon Skeet.

If you get a chance to listen to the “Programming with Purity” talk by Joseph Albahari, do so – he has one of the most lucid explanations of Monads around!

I have stood on the shoulders of giants by reading their blogs: The relevant posts by Eric Lippert, Wes Dyer and Stephen Toub are especially enlightening. Mike Hadlow’s blog is also good reading.

For a truly mind-blowing experience, see the 13-part series on Functional Programming by the one and only Erik Meijer, who, of course, has the last word on monads and Category Theory!

Do stick around, and I’ll try to explain how I synthesize some of these concepts into tools that I use frequently.

It’s been a while…but a lot has happened!

2013-10-29T04:08:00.001-07:00

Can’t believe it’s been a whole year since I blogged anything!

And what a year it’s been!

This year has turned out to be one of the more interesting ones in my career – lots of very cool stuff that’s been taking up all my time…now that it’s coming to a close, I’m going to write up some blog posts to talk about what has happened!

Daily work stuff

In my day job, I work for a software development company that builds accounting software which runs in the cloud. The flagship product – the one I work on – is a .NET rewrite of a very successful C++/ISAM desktop app. The rewrite began as a desktop application replacement so it was designed as such, but with the emergence of cloud technologies, we decided to make the app a hybrid and offer a rich client interface to a cloud service.

The basic premise was a good one – the architecture was well layered so we were able to stick the internet between the server and the client and get the thing to run. However, the devil in the details was performance – the desktop application, quite reasonably, expected to have a fast, fat connection to a local database, but that changed once we separated the UI from the server.

Over the last couple of years, we tried all the quick wins and got the app out, but performance was still sub-optimal and we needed to come up with some fundamental changes to break the problem.

At the start of this year, a couple of us was given the opportunity to go in with a sledgehammer and try to break the problem out. In six weeks we had a pattern for some drastic improvements and we’ve spent the better part of this year rolling that pattern out through the most performance sensitive areas.

Big win!

I’ll blog about some of the technical approaches we have taken to get these dramatic improvements, but it’s safe to say that they are not for the faint-hearted!

We actually rounded off the last year with 3 months of really creative work building the first cut of the MYOB API. Working with @H_Desai and building stuff with ASP.NET Web API was a pretty satisfying experience!

Open Source Mania

In my copious free time (ha ha) I decided to clean up and open source a whole bunch of stuff.

Amongst the weaponry that is now public are:

BrightSword SwissKnife

A (mostly functional-programming based) set of utilities to help with everyday programming.

I’ve got a blog series on practical functional programming which centres around SwissKnife coming.

Warning: Contains Monads.

BrightSword Squid

Rhino Mocks is a nice way to create anonymous types for interfaces but it is slow as all heck and a bit unwieldy, so I decided to write a fast library to generate DTOs with behaviours for general purpose use. MVVM patterns with Property Change Notifications work straight from the tin! And it’s 3 orders of magnitude faster than Rhino!

Contains lots of nasty nasty IL and Reflection.Emit!

BrightSword Pegasus

A reference library for CQRS and (Dynamic) Queue Centric Workflows based on Windows Azure. This thing is seriously cool and makes short work of writing extensible, scalable cloud applications.

Most of the stuff is pretty well tested – and I even set up my own automated build-pipeline to monitor source control, compile, test and upload to nuget. So all these libraries can be referenced and used through nuget.

Use the Nuget Packages. Fork the repos. Submit Pull requests.

The Cloud Architecture Talk

@MaheshKrishnan and I have been doing talks together for a few years now, and we spend a fair bit of our time idly gossiping about technology and trends. We observed that the best-practice software patterns for the cloud aren’t well articulated and well understood by the community at large, so we decided to build a talk around the most common patterns.

We built a application to demonstrate the patterns as well, and drew up some diagrams. Unlike most of our other talks, we demonstrate very little code in the talk itself, but the code is all open source.

We are both humbled and pleasantly surprised by its reception!

So far, we’ve given it at:

The DDD! Melbourne Conference
MYOB technical brown bag series
Melbourne Azure Meetup & VIC.NET
Singapore .NET Dev SIG
TechEd Australia 2013

And we have been invited to give it at NDC London!

Yes. That’s right! We’re speaking at NDC London!

TechEd Australia 2013

This year’s TechEd was pretty special!

Went to the Gold Coast with @simonraikallen, @couchcoder and @shaun_a_wilde.

Hanging with @shaun_a_wilde and @couch_coder

With @MaheshKrishnan at the Microsoft stand

@MaheshKrishnan and I gave a slightly modified version of the Cloud Architecture Patterns talk focusing on the implementation aspects. It was pretty well received, and we got a fair bit of good feedback from the audience. Lively discussion and lots of questions are always a good sign that people paid attention to the material and that it was relevant.

Got to meet @linqpad – would’ve loved to have an hour pairing with him on some stuff to do with monads, but perhaps another day.

Met and hung out with the usual suspects…

Hanging with @RockyH…

… @drmcghee and @frankarr. Didn’t know at the time that this was the last TechEd Frank Arrigo was going to be at – so I’m glad we got this shot!

I won a 3D printer at the raffle, but wasn’t around to collect it so I lost it! I still get guys poking fun at me for this!

Our company had been selected as a case study for our use of Azure, and it was a pretty special privilege to represent them at the last, conference-wide Lock Note session.

It was made all the more special because the Microsoft CVP responsible for Azure – Scott Guthrie – was presenting the Lock Note, and I got a chance to get on stage with him and talk for five minutes about how we used Azure.

So the reason I wasn’t around to claim my printer was that I was hanging out with @ScottGu, rehearsing for the Lock Note, and I got to spend about half an hour just hanging with the Gu, who is, for the record, a very friendly, down-to-earth guy.

Pretty awesome, all told!

Casablanca: C++ on Azure

2012-09-27T05:09:00.001-07:00

We (John Azariah and Mahesh Krishnan) gave a talk at Tech Ed Australia this year titled Casablanca: C++ on Azure. The talk itself was slotted in at 8:15 am on the last day of Tech.Ed after a long party the night before. The crowd was small, and although we were initially disappointed by the turn out, we took heart in the fact that this was the most viewed online video at Tech.Ed this year – lots of five star ratings, Facebook likes and tweets. This post gives you an introduction to Casablanca and highlights the things we talked about in the Tech.Ed presentation.

So, what is Casablanca? Casablanca is an incubation effort from Microsoft with the aim of providing an option for people to run C++ on Windows Azure. Until now, if you were a C++ programmer, the easiest option for you to use C++ would be to create a library and then P/Invoke it from C# or VB.NET code. Casablanca gives you an option to do away with things like that.

If you are a C++ developer and want to move your code to Azure right away, all we can say is “Hold your horses!” It is, like we said, an incubation effort and not production ready, yet. But you can download it from the Devlabs site, play with it and provide valuable feedback to the product team.

You are also probably thinking, “Why use C++?” The answer to that question is really “Why not?” Microsoft has been providing developers the option to use various other languages/platforms such as java and Node.js to write for Azure, and now they are giving the same option to C++ programmers – use the language of their choice to write applications in Azure. Although there has been a bit of resurgence in C++ in the last couple of years, we are not really trying to sell C++ to you. If we are writing a Web App that talks to a database, then our first choice would probably still be ASP.NET MVC using C#, and maybe Entity Frameworks to talk to the DB. What we are trying to say is that you still need to use the right language and framework that works best for you, and if C# is the language you are comfortable with, then why change.

On the other hand if you are using C++, then you probably already know why you want to continue using it. You may be using it for cross-platform compatibility or better performance or maybe you have lots of existing legacy code that you can’t be bothered porting across. Whatever the reason, Casablanca gives you an option to bring your C++ code to Azure without having to use another language to talk to its libraries.

The Node influence

When you first start to look at Casablanca code, you will notice how some of the code has some resemblance to Node.js. A simple Hello World example in node will look like this -

var http = require('http');

http.createServer(function (request, response) {

  response.writeHead(200, 
                  {'Content-Type': 'text/plain'});
  respose.end('Hello World!');

}).listen(8080, '127.0.0.1');

The equivalent Hello World in C++ would look something like this -

using namespace http;

http_listener::create("http://127.0.0.1:8080/",
    [](http_request request)    
    {        
        return request.reply(status_codes::OK, 
                      "text/plain", "Hello World!");
    }).listen();

Notice the similarity? This isn’t by accident. The Casablanca team has been influenced a fair bit by Node and the simplicity by which you can code in node.

Other inclusions

The proliferation of HTML, Web servers, web pages and the various languages to write web applications based on HTML happened in the 90s. C++ may have been around a lot longer than that, but surprisingly, it didn’t ride the HTML wave. Web servers were probably written in C++, but the applications themselves were written using much simpler languages like PHP. Of course, we did have CGI, which you could write using C++, and there were scores of web applications written in C++ but somehow, it really wasn’t the language of choice for writing them. (It didn’t help that scores of C++ developers moved on to things like Java, C#, and Ruby). What C++ needed was a good library or SDK to work with HTTP requests, and process them.

In addition to this, RESTful applications are becoming common place, and is increasingly becoming the preferred way to write services. So, the ability to easily process GET, PUT, POST and DELETE requests in C++ was also needed.

When we talk about RESTful apps, we also need to talk about the format in which the data is sent to/from the server. JSON seems to be the format of choice these days due to the ease with which it works with Javascript.

The Casablanca team took these things into consideration and added classes into Casablanca to work with the HTTP protocol, easily create RESTful apps and work with JSON.

To process the different HTTP actions and write a simple REST application to do CRUD operations, the code will look something like this:

auto listener = http_listener::create(L"http://localhost:8082/books/");

listener.support(http::methods::GET, [=](http_request request)
{
    //Read records from DB and send data back
});

listener.support(http::methods::POST, [=](http_request request)
{
    //Create record from data sent in Request body
});

listener.support(http::methods::PUT, [=](http_request request)
{
    //Update record based on data sent in Request body
});

listener.support(http::methods::DEL, [=](http_request request)
{
    //Delete
});

/* Prevent Listen() from returning until user hits 'Enter' */ 
listener.listen([]() { fgetc(stdin); }).wait();

Notice how easy it is to process the individual HTTP actions? So, how does conversion from and to Json objects work? To convert a C++ object to a Json object and send it back as a response, the code will look something like this:

using namespace http::json;
...

value jsonObj = value::object();
jsonObj[L"Isbn"] = value::string(isbn);
jsonObj[L"Title"] = value::string(title);
...

request.reply(http::status_codes::OK, jsonObj);

To read json data from the request, the code will look something like this:

using namespace http::json;

...

value jsonValue = request.extract_json().get();

isbn = jsonValue[L"Isbn"].as_string();

You have a collection? no problem, the following code snippet shows how you can create a Json array

...
auto elements = http::json::value::element_vector();
for (auto i = mymap.begin(); i != mymap.end(); ++i) 
{
    T t = *i;

    auto jsonOfT = ...; // Convert t to http::json::value
    elements.insert(elements.end(), jsonOfT);
}
return http::json::value::array(elements);

Azure Storage

If you are running your application in Windows Azure, then chances are you may also want to use Azure storage. Casablanca provides you with the libraries to be able to do this. The usage, again is quite simple, to create the various clients for blobs, queues and tables the usage is as follow:

storage_credentials creds(storageName, storageKey);

cloud_table_client table_client(tableUrl, creds);
cloud_blob_client blob_client(blobUrl, creds);
cloud_queue_client queue_client(queueUrl, creds);

Notice the consistent way of creating the various client objects. Once you have initialized them, then their usage is quite simple too. The following code snippet shows you how to read data from Table storage:

cloud_table table(table_client, tableName);
query_params params;
	...
auto results = table.query_entities(params)
                      .get().results();

for (auto i =  results.begin(); 
          i != result_vector.end(); ++i) 
{
    cloud_table_entity entity = *i;
    entity.match_property(L"ISBN", isbn);
    ...
}

Writing to Table storage is not difficult either, as seen in this code snippet:

cloud_table table(table_client, table_name);
cloud_table_entity entity(partitionKey, rowKey);

entity.set(L"ISBN", isbn, cloud_table_entity::String);
	...

cloud_table.insert_or_replace_entity(entity);

Writing to blobs, and queues follow a similar pattern of usage.

Async…

nother one of the main inclusions in Casablanca is the ability to do things in an asynchronous fashion. If you’ve looked at the way things are done on Windows Store applications or used Parallel Patterns Library (PPL), then you would already be familiar with the “promise” syntax. In the previous code snippets, we resisted the urge to use it, as we hadn’t introduced it yet.

… and Client-Side Libraries

Also, we have been talking mainly about the server side use of Casablanca, but another thing to highlight is the fact that it can also be used to do client side programming. The following code shows the client side use of Casablanca and how promises can be used:

http::client::http_client client(L"http://someurl/");
client.request(methods::GET, L"/foo.html")
.then(
      [=](pplx::task task)
      {
         http_response response = task.get();
         //Do something with response
         ...
      });

If you need to find out more about ppl and promises, then you should read the article “Asynchronous Programming in C++” written by Artur Laksberg in the MSDN magazine.

Wait, there is more…but first lets get started

Casablanca has also been influenced by Erlang, and the concept of Actors, but let’s talk about it another post. To get started with Casablanca, download it from the DevLabs site. It is available for both VS 2010 and 2012.

I’m back!

2012-09-25T16:37:00.001-07:00

It’s been a crazy year since TechEd Australia 2011, and I’ve been strangely quiet…

But I’m back now…

Migrating a Web Application to Azure: Step 4

2011-08-27T10:38:00.001-07:00

Moving the application to Windows Azure

A New Project

The first step is to add a new cloud project to the solution.

Ensure that you do not add any web or worker roles.

We will convert the existing web application within the solution to a Web Role in the Azure Project.

Right Click on the ‘Roles’ folder in the Azure Project, select ‘Add’ and then ‘Web Role Project in solution…’.

Select the web application – in this case ‘SharPix_Step2’

After adding the project as a Web Role, it should look like this:

Right-Click on the ‘SharPix_Step2’ role and select ‘Properties’

In this dialog, under normal circumstances, you should set Instance count to at least 2 to enable fail-over and scaling, and you would pick an appropriate VM size.

Also, we will start by using the Compute and Storage Emulators, so specify ‘UseDevelopmentStorage=true’ as the Diagnostics storage account.

Running In Emulator…

Visual Studio comes with a tiny taste of the cloud built-in, in the form of the Storage and Compute Emulators.

Simply running our new Azure Project gives us:

Note the URL and the port number. This is no longer the Visual Studio Development Web Server, but the Compute Emulator in action. Examining the Windows Tray shows us that the emulators are running….

To the cloud!

In order to push the Azure Project to our cloud environment, we need to configure Visual Studio and set up our credentials to ensure that we carefully control access to our Azure environment.

Right-Click on the Azure Project and select ‘Publish’. We could use previously issued certificates here, or issue a new one for this project by selecting ‘Add’.

Create a New Certificate, and fill in the details required.

Visual Studio creates a new certificate and stores it in a temporary, obscure, folder. Copy the path from this dialog onto your clipboard and head over to the Windows Azure Management portal.

Click on ‘Management Certificates’, select the Azure Subscription you want to deploy to, and select ‘Add Certificate’ from the right-click context menu.

Once the certificate is uploaded, select and copy the Subscription ID from the portal and fill it into (3) of the Windows Azure Project Management Authentication dialog shown above. Give the Project some reasonable name and click ‘OK’

After dispatching all the other dialogs, you will be left with the first ‘Publish Windows Azure Application’ dialog. Ensure you have selected a Production Environment, and specify the storage account to use.

Hurry Up and Wait

Clicking ‘Publish’ on the dialog above begins the deployment process, which can easily take 15 minutes or more. During this time, some information is relayed through to Visual Studio about the actions being taken and their various statuses.

When the deployment is complete, click on the ‘Website URL’ link, or view the deployment in the Server Explorer and select ‘View in Browser’ from the right-click context menu.

The application finally appears. Note the URL is now that of an Azure cloud application.

In the Management Portal, expanding the Azure Subscription will show the Deployment node and all the compute instances fired up in the production environment. In our case, we have just one instance, but we could add more.

And there it is. A fully local web application that is now running in the cloud and using cloud-based blob and database storage.

Next we’ll talk about federating authentication to this application.

Migrating a Web Application to Azure: Step 3

2011-08-27T08:32:00.001-07:00

Getting rid of file access

One issue to watch out for with an application in the cloud is file access.

File-Access in a highly-elastic environment such as Azure is generally a bad idea because it reduces the ability for a request to be correctly handled by multiple server instances. To combat this, generally, all access to the file system should be changed to access Azure storage, which does scale across multiple server instances.

In our example, we have contrived to have a picture stored in the database, but cached on the file-system on its first use, and subsequent access is to the cached file.

Local Application, Images from Server Files

We have code that looks like this in the original code:

public ServerPath EnsureImage(Picture picture)
{
    // ensure the directory exists
    var directoryPath = EnsureDirectory(RelativePathToImagesDirectory);

    // now ensure the file exists
    var filePath = EnsureFile(
        directoryPath,
        picture.OriginalFilename,
        _path =>
        {
            using (var stream = new FileStream(
                _path.Absolute,
                FileMode.OpenOrCreate,
                FileSystemRights.TakeOwnership | FileSystemRights.Write,
                FileShare.None,
                1024,
                FileOptions.None))
            {
                stream.Write(picture.Image.ToArray(), 0, picture.Image.Length);
            }
        });

    return filePath;
}

internal ServerPath EnsureFile(ServerPath root,
                               string filename,
                               Action<ServerPath> fileCreateFunc)
{
    var path = new ServerPath(Path.Combine(root.Relative, filename), Server.MapPath);

    if (!(File.Exists(path.Absolute)))
    {
        fileCreateFunc(path);
    }

    return path;
}

which results in

Note that the web application is still running locally, and the images refer to files located at relative paths within the server.

To remove the dependency on the file-system, we can use Azure Blob Storage to store the cached files.

The Rise Of The Blob…

Blob storage Azure is very cool. It presents a REST-based API to upload, tag, list and retrieve unstructured binary data like images, documents and videos.

So we can switch the application to interact with the Azure Blob store, referring to the images from the storage in the cloud.

To do this, we use the Azure storage account we created earlier.

The important pieces of information to capture are the Access Key (you get this when you click on the button with the orange outline), and the Azure storage account name which is highlighted.

We then initialize access to the blob storage account and container from within the application:

public void Initialize()
{
    if (CloudStorageAccount == null)
    {
        CloudStorageAccount = CloudStorageAccount.Parse("AccountName=cos204;AccountKey=<put_your_key_here>;DefaultEndpointsProtocol=http");
    }

    if (CloudBlobClient == null)
    {
        CloudBlobClient = new CloudBlobClient(CloudStorageAccount.BlobEndpoint, CloudStorageAccount.Credentials);
    }

    if (ThumbnailsContainer == null)
    {
        ThumbnailsContainer = CloudBlobClient.GetContainerReference("thumbnails");
    }

    ThumbnailsContainer.CreateIfNotExist();

    if (ThumbnailsContainer.GetPermissions().PublicAccess != BlobContainerPublicAccessType.Container)
    {
        ThumbnailsContainer.SetPermissions(new BlobContainerPermissions
                                               {PublicAccess = BlobContainerPublicAccessType.Container});
    }

    if (ImagesContainer == null)
    {
        ImagesContainer = CloudBlobClient.GetContainerReference("images");
    }

    ImagesContainer.CreateIfNotExist();

    if (ImagesContainer.GetPermissions().PublicAccess != BlobContainerPublicAccessType.Container)
    {
        ImagesContainer.SetPermissions(new BlobContainerPermissions { PublicAccess = BlobContainerPublicAccessType.Container });
    }
}

What we are doing here is initializing the Blob Storage infrastructures and creating containers for Thumbnails and Images.

It’s important to note that the demo code shows a hardcoded Azure Connection String just to simplify the code snippet for reference. Normally this would be hidden away in a configuration file.

Local Application, Remote Images

We can now replace the file-access code shown above with its Azure Blob equivalent.

public ServerPath EnsureImage(Picture picture)
{
    var filePath = EnsureBlob(
        ImagesContainer,
        picture.OriginalFilename,
        _blob =>
            {
                var blobStream = _blob.OpenWrite();
                try
                {
                    blobStream.Write(picture.Image.ToArray(), 0, picture.Image.Length);
                }
                finally
                {
                    blobStream.Flush();
                    blobStream.Close();
                }
            });

    return filePath;
}

internal ServerPath EnsureBlob(CloudBlobContainer blobContainer,
                               string filename,
                               Action<CloudBlob> blobCreateFunc)
{
    var blob = blobContainer.GetBlobReference(filename);

    if (blobContainer.ListBlobs().FirstOrDefault(_blob => _blob.Uri.AbsoluteUri == blob.Uri.AbsoluteUri) == null)
    {
        blobCreateFunc(blob);
    }

    return new ServerPath(filename, blob.Uri.AbsoluteUri);
}

With this implementation of EnsureImage(), we get:

Pretty cool.

We now have a web application running on the local server, with data in the cloud, caching files and referencing Azure Blob storage also in the cloud!

Inspecting Blob Storage

While developing and debugging this stage of the migration, it’s useful to see exactly what is being stored in the Azure Blob storage.

The Windows Azure Management Portal does not have a handy tool to inspect the structure and contents of the Azure Storage account, so we turn to some other tools to do that.

The pack of Windows Azure Tools for Visual Studio 2010 v1.4 enables a storage account browser, which can be configured with the storage account and the key as before, allowing for full access to the storage account.

We can use this to ensure that the blob storage account is structured as we expect, and filled with the contents we expect.

Next, we’ll move the application itself to Azure.

Migrating a Web Application to Azure: Step 2

2011-08-26T20:33:00.001-07:00

Migrating the database to SQL Azure

Now that we have a local web-application with a database, and a SQL Azure instance up and running, we can start the application migration by moving the database to SQL Azure.

SQL Azure is a modified version of SQL Server 2008 R2, and there are some small, but significant limitations on the SQL DDL commands that can be run on Azure. See here and here for more information.

The upshot is, if you already have a local SQL Server database, then you’re really much better off using some specialized migration tools to move it to Azure. The tool of choice for us is the SQL Azure Migration Wizard off codeplex.

Download and install the latest version of this tool on your development box. You’ll thank the tool-developer later!

Fire up the tool, and select “SQL Database” under “Analyze / Migrate”

Select the local database server which hosts the instance you want to migrate

Select the database(s) to migrate in turn.

In our case, we will have to migrate both the ASPNETDB and PICTURES databases.

Click through the dialogs, and migrate database object present in the database.

The Migration Wizard has created the script to use for the migration, and will now require your credentials to migrate to. This is where you fill in the details from the SQL Azure instance screen in the previous step.

Let’s let the migrator create a PICTURES database on the Azure Server

…and begin the migration work

…and we are done!

The Azure portal shows the two databases created and ready for use.

Now, let’s hook up the application we wrote to use these databases in the cloud. To do this, we point the connection strings in the Web.Config of the web application to the databases in the cloud.

Thusly:

And that’s it. Here’s the application running locally but with the data in the cloud.

I’ve created a new album called “Clouds” now, and uploaded three new pictures. If we look at the Azure database instance and look at the data in the PICTURES instance, we see the data there:

Next, we’ll talk about setting up the Azure workspace so we can move our application there…

Migrating a Web Application to Azure: Step 1

2011-08-26T19:34:00.001-07:00

Setting up your Azure workspace

So we have a working web-application which we want to move to Azure.

The first thing to do is to get a Windows Live ID and line up one Windows Azure subscription and one SQL Azure subscription.

Sign into windows.azure.com with your Live ID

Click on the “Hosted Services, Storage Accounts and CDN” button on the bottom left panel, then on “Hosted Services” on the top left panel.

Right-Click on your Azure Subscription in the main panel and select “New Hosted Service”

Choose not to deploy at this stage!

Similarly create a Storage Account on the same subscription.

Now create a database server on the SQL Azure Subscription.

Ensure you set the firewall rules to include both your machine’s IP address and other Azure services. Your SQL Azure instance will need to be accessed from the Windows Azure instance,

Once you create the database server, you should make a note of the following pieces of information:

The subscription id
Your administrator login and password
The instance name, and the fully-qualified database server DNS name

Now we have Windows Azure and SQL Azure instances set up for use.

Next we’ll migrate our database to SQL Azure.

Migrating a Web Application to Azure: Step 0

2011-08-25T10:53:00.001-07:00

Creating a traditional, locally run web application

Let’s start with a simple, traditional web application.

This is a contrived application, built specifically for demonstrating the issues we want to address in the process of migrating to Azure.

Please do not consider this application as indicative of following best-practices for web application development!

Also, the purpose of this web application is not to wow anyone with a slick user interface! :)

Let’s imagine a site where someone logs on, creates a photo album or two, and uploads a few images to each album.

Prerequisites

You will need the following applications and tools to follow along the process of migrating an application to Azure

Visual Studio 2010 (SP1 strongly recommended)
SQL Server 2008 R2; you’ll be using SQL Server Management Studio
Windows Azure SDK 1.4

We’ll introduce a few more tools along the way, but we can get started with this.

Steps

Let’s create this application the simplest way possible:

First, create the ASPNETDB Application Services database on the SQL Server 2008 instance. You may need to run aspnet_regsql.exe from the .NET framework directory.

Then create a basic web application in Visual Studio:

Modify the Web.Config on the web application to point the Application Services Providers to our database.

Pressing F5 to run/debug the web application should fire up the default application, and allow you to create an account to authenticate against in future. The default home page after logging in should look like this:

To create the picture album site, we create a new database with this simple schema:

Note that for this demonstration, we will store the uploaded picture in an image column on the Picture table, in the database.

We’ll use Linq 2 SQL to create a data-model for our application.

When we’re done with adding the Linq2Sql classes, the connectionStrings collection in our Web.Config looks like:

Now we’ll actually develop the application, and let’s say we finally land up with:

Let’s also assume that the application contains, for the sake of this demonstration, the following code to extract the binary data from the database and cache the file on the file system, so that the images on the rendered page refer to the cached file:

var relativePathToDirectory = "~/.cache";

// ensure the directory exists
var absolutePathToDirectory = Server.MapPath(relativePathToDirectory);
if (!Directory.Exists(absolutePathToDirectory))
{
    Directory.CreateDirectory(absolutePathToDirectory);
}

// now ensure the file exists
var relativePathToFile = Path.Combine(relativePathToDirectory, picture.OriginalFilename);
var absolutePathToFile = Server.MapPath(relativePathToFile);

if (File.Exists(absolutePathToFile)) return absolutePathToFile;

using (var stream = new FileStream(
        absolutePathToFile,
        FileMode.OpenOrCreate,
        FileSystemRights.TakeOwnership | FileSystemRights.Write,
        FileShare.None,
        1024,
        FileOptions.None))
{
    stream.Write(picture.Image.ToArray(), 0, picture.Image.Length);
}

Conclusion

We have a rudimentary, but fully functional web application that runs on our local web server in the traditional manner.

We will need to consider the specific changes to make when we want to migrate this application to the cloud.

PS:

We’ll put the source code on github and stick the link in here just after the talk.

Migrating a Web Application to Azure: Introduction

2011-08-25T08:59:00.001-07:00

This is a series of posts relating to the details of the talk Mahesh Krishnan and I will be giving at TechEd Australia 2011. You can follow along in this series of posts for more details and gotchas that we can’t cover in the 60 minute talk at TechEd!

Here are the details of the talk:

We’ll be taking a contrived, but simple, traditional data-driven web application, and outlining the issues to consider, and steps to take, to move the application to Windows Azure/Sql Azure.

We’ll show you how to set up your Azure subscription, migrate your database to Sql Azure, manage session state with Azure’s Session State Manager, move file-system based actions to Windows Azure blob storage, and secure your application with Azure’s ACS 2.0 Federated Authentication.

We’ll show you what tools you need and how to use Visual Studio 2010 SP1 to simplify the process of migrating.

There’s some code, but mostly we’re going to be discussing issues, tips and tricks.

See you there!

Functional Object Manipulation

2011-07-10T21:30:00.001-07:00

In the last couple of posts, we’ve looked at ways to copy scalar properties from one object to another, with the high performance of explicit assignments and the low maintenance of reflection.

The approach of creating a lambda to operate on the object instance as a whole shows a lot of promise. For example, we may want to compare two object instances property-by-property, and the code for that would look quite similar.

public static class Comparer
{
    public static bool Compare<T>(this T source, T destination) { return CompareClosure<T>.Compare(source, destination); }

    private static class CompareClosure<T>
    {
        private static Func<T, T, bool> BuildComparerLambda(Func<PropertyInfo, bool> propertyFilter = null)
        {
            propertyFilter = propertyFilter ?? (_ => true);

            var sourceParameterExpression = Expression.Parameter(typeof(T), "_left");
            var destinationParameterExpression = Expression.Parameter(typeof(T), "_right");

            var properties = typeof(T).GetProperties().Where(propertyFilter);
            var expressions = properties.Select(_pi => Expression.Equal(Expression.Property(destinationParameterExpression, _pi), Expression.Property(sourceParameterExpression, _pi)));
            var conjoinedExpression = expressions.Aggregate<Expression, Expression>(Expression.Constant(true), Expression.AndAlso);

            var lambdaExpression = Expression.Lambda<Func<T, T, bool>>(conjoinedExpression, sourceParameterExpression, destinationParameterExpression);
            return lambdaExpression.Compile();
        }

        private static readonly Func<T, T, bool> _compare = BuildComparerLambda();
        public static bool Compare(T source, T destination) { return _compare(source, destination); }
    }
}

which gives us:

What are are doing in the code is mapping each property to a boolean value indicating whether the two instances have the same value for the property, and then folding that set of boolean values to a single boolean value by aggregating it with the && operator (and a seed value of ‘true’).

We can readily see a pattern emerging here:

There are two types of operations possible for a given arity. In the case of Compare and Copy where the operation arity is 2, we can create either an Action<T, T> or a Func<T, T, TResult>.

The Action<> case is a lambda that performs an operation on each property with reference to the given argument instances.

We can create a general operation builder by lifting a parameter which specifies the desired operation on a property, with reference to the lambda arguments.

public static Action<T, T> BuildOperationAction<T>(
    Func<PropertyInfo, ParameterExpression, ParameterExpression, Expression> operationExpressionFactory)
{
    var leftParameterExpression = Expression.Parameter(typeof (T), "_left");
    var rightParameterExpression = Expression.Parameter(typeof (T), "_right");

    var properties = typeof (T).GetProperties();
    var expressions = properties.Select(_ => operationExpressionFactory(_, leftParameterExpression, rightParameterExpression));

    var blockExpression = Expression.Block(expressions);
    var lambdaExpression = Expression.Lambda<Action<T, T>>(blockExpression, leftParameterExpression, rightParameterExpression);

    return lambdaExpression.Compile();
}

The Func<> case is a lambda that maps the set of properties to a set of values with reference to the argument instances, and then aggregates this set of values to a single value using an aggregator.

We can create a general operation builder by lifting:

a parameter which specifies the desired operation on a property, with reference to the lambda arguments
a parameter which specifies the aggregate operation to fold the set of computed values to a single value, and
a parameter specifying the initial value for the aggregator.

Thusly:

public static Func<T, T, TResult> BuildOperationFunc<T, TResult>(
    Func<PropertyInfo, ParameterExpression, ParameterExpression, Expression> operationExpressionFactory,
    Func<Expression, Expression, Expression> conjunction, Expression seed)
{
    var leftParameterExpression = Expression.Parameter(typeof (T), "_left");
    var rightParameterExpression = Expression.Parameter(typeof (T), "_right");

    var properties = typeof (T).GetProperties();
    var expressions = properties.Select(_ => operationExpressionFactory(_, leftParameterExpression, rightParameterExpression));

    var joinedExpression = expressions.Aggregate(seed, conjunction);
    var lambdaExpression = Expression.Lambda<Func<T, T, TResult>>(joinedExpression, leftParameterExpression, rightParameterExpression);

    return lambdaExpression.Compile();
}

This allows us to implement Copy() and Compare() as follows:

public static bool CompareWith<T>(this T source, T destination) { return CompareClosure<T>.Compare(source, destination); }
private static class CompareClosure<T>
{
    private static readonly Func<T, T, bool> _compare =
        BuildOperationFunc<T, bool>(
            (_pi, _src, _dest) => Expression.Assign(Expression.Property(_dest, _pi), Expression.Property(_src, _pi)),
            Expression.AndAlso,
            Expression.Constant(true));

    public static bool Compare(T source, T destination) { return _compare(source, destination); }
}

public static void CopyTo<T>(this T source, T destination) { CopyClosure<T>.Copy(source, destination); }
private static class CopyClosure<T>
{
    private static readonly Action<T, T> _copy =
        BuildOperationAction<T>(
            (_pi, _src, _dest) => Expression.Assign(Expression.Property(_dest, _pi), Expression.Property(_src, _pi)));

    public static void Copy(T source, T destination) { _copy(source, destination); }
}

Very neat.

We could develop more operations than Copy and Compare, building fast, automatically maintained mappers for data access (think ORMs) and UI field access, by simply specifying the equivalent expression. The development effort is simply in the development of the expression.

For example, here is a mapper which maps properties defined on type T, from a dynamic source object to backing fields on a target object of type T:

private static readonly Action<T, T> _copyDynamicToStaticBackingFields = 
	BuildOperationAction<T>(
	    (_pi, _src, _dest) =>
	    {
	        var sourceBinder = RuntimeBinder.GetMember(CSharpBinderFlags.InvokeSpecialName, _pi.Name, typeof (T), new [ ] { ThisArgument });
	        var sourceGetExpression = Expression.Convert(Expression.Dynamic(sourceBinder, typeof (object), _src), _pi.PropertyType);

	        var fieldName = String.Format("_{0}{1}", _pi.Name.Substring(0, 1).ToLower(), _pi.Name.Substring(1));

	        var fieldInfo = typeof (T).GetField(fieldName, BindingFlags.Instance | BindingFlags.NonPublic);
	        if (fieldInfo == null) return Expression.Default(typeof (void));

	        var destinationAccessExpression = Expression.Field(_dest, fieldInfo);
	        return Expression.Assign(destinationAccessExpression, sourceGetExpression);
	    });

We could further develop this approach by developing the BuildOperationXXX functions for Action<>s and Func<>s of arity 1, which would allow us to quickly develop fast, low-maintenance object printers and serializers.

I believe that this set of generating functions is likely to be more generally useful, so I’ve created a CodePlex project for this. Please visit it and let me know how you used it!

The Object Copier, revisited.

2011-07-10T17:48:00.001-07:00

We saw in the previous post how we could improve the maintainability of reflection-based code by building lambdas using reflection, and then gain the performance benefits by applying the lambdas at execution time.

Taking the idea a step further, we can easily see that what we are really doing is generating a function to do the copy operation on the entire object and applying the copy function.

(T _source, T _destination) =>
    {
        _destination.Id = _source.Id;
        _destination.Name = _source.Name;
        ...
    }

Based on the approach we took last time, this is easily achievable by wrapping the individual assignments into a block statement, wiring through the parameter expressions from the block into the individual lambdas, and then compiling out a full copy. Thusly:

public static class Copier
{
    public static void CopyTo<T>(this T source, T destination) { CopyClosure<T>.Copy(source, destination); }

    private static class CopyClosure<T>
    {
        private static Action<T, T> BuildCopierLambda()
        {
            var sourceParameterExpression = Expression.Parameter(typeof(T), "_source");
            var destinationParameterExpression = Expression.Parameter(typeof(T), "_destination");

            var properties = typeof(T).GetProperties();
            var expressions = properties.Select(_pi => Expression.Assign(Expression.Property(destinationParameterExpression, _pi), Expression.Property(sourceParameterExpression, _pi)));

            var blockExpression = Expression.Block(expressions);
            var lambdaExpression = Expression.Lambda<Action<T, T>>(blockExpression, sourceParameterExpression, destinationParameterExpression);

            return lambdaExpression.Compile();
        }

        private static readonly Action<T, T> _copy = BuildCopierLambda();
        public static void Copy(T source, T destination) { _copy(source, destination); }
    }
}

There are a few things to note about the code:

The outer, public, static Copier class is non-generic to allow the CopyTo operation to be defined as an extension property on generic type T.

The compiler will create a special, unique CopyClosure class for each type T. This ensures that the _copy Action is unique for each type T. Also, the _copy Action is initialized in a thread-safe manner, because the compiler guarantees thread-safety on field initializers.

This approach actually improves performance, because there is no run-time iteration!

Stay tuned for more improvements…

A (Fast) Object Copier

2011-06-27T14:54:00.001-07:00

A colleague of mine asked me today to help with the onerous task of “twisting-off” the data in an entity into a DTO. Something about serialization, he said…

He said that he didn’t mind if the copying was slow – just that he didn’t want to put in hundreds of lines of code each saying

destination.Id = source.Id;
destination.Name = source.Name;
destination.DateAndTimeOfBirth = source.DateAndTimeOfBirth;
destination.BirthWeightInKilograms = source.BirthWeightInKilograms;
destination.IsMultipleBirth = source.IsMultipleBirth;
destination.BirthOrder = source.BirthOrder;
...

So I sat down and knocked off the traditional reflection-based code:

internal static T Map<T>(T source, T destination) where T : class
{
    foreach (var pi in typeof (T).GetProperties())
    {
        pi.SetValue(destination,
                    pi.GetValue(source, BindingFlags.GetProperty | BindingFlags.Instance, null, null, null),
                    BindingFlags.SetProperty | BindingFlags.Instance,
                    null,
                    null,
                    null);
    }
    return destination;
}

(I’ve removed the error checking just to keep things simple for this post)

Neat and all, and does the job.

But I couldn’t help wondering if I could do better – specially since I knew that the performance would potentially be too terrible to bear…

Express(ion) yourself!

It would be nice to use the tricks we learned with expressions to create, for a given type, a set of assignment expressions for each of the properties, and then simply apply all expressions one by one to the source and destination, and that way the cost of reflection is borne only once.

Fair enough. I got home, and after dinner, knocked off this piece of code:

public static class FastCopier
{
    public static T Copy<T>(T source, T destination) where T : class
    {
        return FastCopierInternal<T>.Copy(source, destination);
    }

    private static class FastCopierInternal<T>
    {
        private static readonly IDictionary<PropertyInfo, Action<T, T>> _copyFunctions = typeof (T).GetProperties().ToDictionary(_pi => _pi, GetCopyFunc);
    
        private static Action<T, T> GetCopyFunc(PropertyInfo propertyInfo)
        {
            Trace.WriteLine(String.Format("Creating mapping func for {0}.{1}", propertyInfo.DeclaringType.Name, propertyInfo.Name));
            var sourceParameterExpression = Expression.Parameter(typeof (T), "_source");
            var destinationParameterExpression = Expression.Parameter(typeof (T), "_destination");
    
            var sourceAccessExpression = Expression.Property(sourceParameterExpression, propertyInfo);
            var destinationAccessExpression = Expression.Property(destinationParameterExpression, propertyInfo);
    
            var sourceAssignmentExpression = Expression.Assign(destinationAccessExpression, sourceAccessExpression);
    
            var lambdaExpression = Expression.Lambda<Action<T, T>>(sourceAssignmentExpression,
                                                                   sourceParameterExpression,
                                                                   destinationParameterExpression);
    
            return lambdaExpression.Compile();
        }
    
        public static T Copy(T source, T destination)
        {
            foreach (var func in _copyFunctions.Values)
            {
                func(source, destination);
            }
    
            return destination;
        }
    }
}

Here we have a static class with a single public method to do the Copy for a given type T.

Internally, we have a static generic copier class which only gets instantiated once for each type T, and which builds up an associative array of the properties of the type and the function required to copy each property from source to destination.

Here’s what the lambda expression looks like as it is built:

When the public Copy method on the outer class is called, it calls the Copy method on the (implicitly initalized) inner static class, which applies each of the copy functions in turn to copy the source to the destination one property at a time.

Pretty cool. So how much faster are we?

Explicit copy of object 1000000 times took 204 ms
Fast copy of object 1000000 times took 790 ms
Slow copy of object 1000000 times took 23801 ms

Running over a million objects, the fastest, as expected, is when we explicitly code the DTO initialization, and let the compiler optimize.

The lambda version is around 3.5x slower, but still pretty darn fast compared with the basic, slow, all-reflection version – which is two orders of magnitude slower!

Not a bad option to have, when the development and maintenance cost of creating the DTOs and keeping them up to date is factored in!

Memoization Is Your Friend

2011-06-05T19:26:00.001-07:00

I just came across some gems regarding memoization here, here, here and here. As a side note, I’d like to go on record and say that Wes Dyer’s derivation of fixed-point combinators is second to none! Even I could understand what he was saying! :) Another great discussion of fixed-point combinators is here. For more theoretical underpinnings, this paper discusses memoization of fixed-point functions.

We’re being plagued by performance issues in the project I’m currently working on, and it would be really nice to have a quick way to to automatically memoize some functions to gain the benefits of laziness and good book-keeping.

So, here is my implementation of a Memoize() function, which uses the fixed-point combinator concepts explained in Wes’ blog.

public static Func<TArgument, TResult> MemoizeFix<TArgument, TResult>(Func<Func<TArgument, TResult>, Func<TArgument, TResult>> func)
{
    // ReSharper disable AccessToModifiedClosure
    Func<TArgument, TResult> funcMemoized = null;

    funcMemoized = func(_ => funcMemoized(_));
    funcMemoized = funcMemoized.Memoize();

    return funcMemoized;
    // ReSharper restore AccessToModifiedClosure
}

private static Func<TArgument, TResult> Memoize<TArgument, TResult>(this Func<TArgument, TResult> func)
{
    var _map = new ConcurrentDictionary<TArgument, TResult>();
    return _ => _map.GetOrAdd(_, func);
}

In MemoizeFix(), we create the funcMemoized variable as null so that we get around the definite assignment problem. Because we defer the assignment to after the application of the memoization, we actually want to have access to the modified closure.

The other nice thing with .NET 4.0 is the ability to use the ConcurrentDictionary as a thread-safe result cache, with the added bonus of a very terse invocation to GetOrAdd().

We can use the memoization routines this way:

private static readonly Func<int, long> FastFibonacci = Functional.MemoizeFix<int, long>(
    fib => n => (n <= 0 ? 0 : (n <= 2 ? 1 : fib(n - 1) + fib(n - 2)))
);

private static readonly Func<int, long> FastLucas = Functional.MemoizeFix<int, long>(
    luc => (n => FastFibonacci(n) + FastFibonacci(n + 2))
);

private static readonly Func<int, double> FastFactorial = Functional.MemoizeFix<int, double>(
    fact => n => n < 2 ? 1.0d : n*fact(n - 1)
);

For functions with more than one argument, I’d create a Tuple<> with all the arguments as the cache key as the simplest extension. Thusly:

private static Func<TArg1, TArg2, TResult> Memoize<TArg1, TArg2, TResult>(this Func<TArg1, TArg2, TResult> func)
{
    var _map = new ConcurrentDictionary<Tuple<TArg1, TArg2>, TResult>();
    return (_a1, _a2) => _map.GetOrAdd(new Tuple<TArg1, TArg2>(_a1, _a2), _ => func(_.Item1, _.Item2));
}

public static Func<TArg1, TArg2, TResult> MemoizeFix<TArg1, TArg2, TResult>(Func<Func<TArg1, TArg2, TResult>, Func<TArg1, TArg2, TResult>> func)
{
    // ReSharper disable AccessToModifiedClosure
    Func<TArg1, TArg2, TResult> funcMemoized = null;

    funcMemoized = func((_a1, _a2) => funcMemoized(_a1, _a2));
    funcMemoized = funcMemoized.Memoize();

    return funcMemoized;
    // ReSharper restore AccessToModifiedClosure
}

Pretty slick :)

C# Abuse

2011-04-20T21:43:00.001-07:00

So I just watched this video presentation by Jon Skeet about some of the edges of our understanding of the C# language.

In this blog post, he threw open the challenge to define three static methods such that the following code compiles:

static void Main() 
{ 
    Foo<int>(); 
    Foo<string>(); 
    Foo<int?>(); 
}

While watching the video and playing around on my own, I came up with:

class Program
{
    static void Foo<T>() { Console.WriteLine(typeof(T).Name); }

    class Inner : Program
    {
        struct R<T> where T : class { }

        static void Foo<T>(params R<T>?[] _) where T : class { Console.WriteLine(typeof(T).Name); }
        static void Foo<T>(params T?[] _) where T : struct { Console.WriteLine(typeof(T).Name); }

        static void Main()
        {
            Foo<int>();
            Foo<string>();
            Foo<int?>();
        }
    }
}

which prints out the correct result. The analysis of how this works is given brilliantly over at Jon’s blog!

The key is the inner class, which forces the compiler to first check signature suitability for the two methods defined therein, before allowing the base class to catch-all with the most generalized signature.

The same caveat that Jon specified in his blog applies – such code should *never* be written!

Lambda Wrangling For Fun : Part 4 – Sorting Multiple Columns

2011-04-17T03:11:00.001-07:00

We can approach the problem of sorting a dataset by multiple properties using the same techniques as for the filter case.

A single-property sorting lambda looks like:

….OrderBy(_ => _.property) or ….OrderByDescending(_ => _.property)

If we wanted to sort by more than one property, we would do something like:

….OrderBy(_ => _.property1).OrderByDescending(_ => _.property2)

It’s important to notice two points:

The lambdas for each sort clause are self-contained – unlike the composite filter lambda where the same parameter is threaded through each predicate.
The direction of the sort is specified by the use of either the OrderBy or OrderByDescending extension method. This means that the composite sort criteria will be represented by a chain of OrderBy and/or OrderByDescending methods.

Bearing these points in mind, we can develop a general Sort action specification:

public interface ISort<TSource>
{
    string PropertyName { get; }
    SortDirection SortDirection { get; }

    Expression<Func<TSource, object>> GetSelectorLambda();
}

The properties are as we expected, and we have encountered a variant GetSelectorLambda before.

Applying a composite sort on an enumerable can be achieved by:

public static IOrderedEnumerable<T> Sort<T>(this IEnumerable<T> _this, IEnumerable<ISort<T>> sortOperations)
{
    var parameterExpression = Expression.Parameter(typeof (IEnumerable<T>), "_");

    Expression items = parameterExpression;
    foreach (var sortOperation in sortOperations)
    {
        // selector :  __ => __.{sortOperation.PropertyName}
        var selector = sortOperation.GetSelectorLambda();

        // items.OrderBy<T, object>(__ => __.Property) 
        //   is actually
        // Enumerable.OrderBy<T, object>(items, __ => __.Property)
        items = Expression.Call(typeof (Enumerable),
                                sortOperation.SortDirection == SortDirection.Ascending ? "OrderBy" : "OrderByDescending",
                                new [ ] { typeof (T), typeof (object) },
                                items,
                                selector);
    }

    // _ => _.OrderBy[Descending](__ => __.Property1)...OrderBy[Descending](__ => __.PropertyN)
    var lambda = Expression.Lambda<Func<IEnumerable<T>, IOrderedEnumerable<T>>>(items, parameterExpression);

    // compile the lambda...
    var func = lambda.Compile();

    // ...call the chain of extension methods on (_this)
    return func(_this);
}

The function generates calls to either the ‘OrderyBy’ or the ‘OrderByDescending’ method on the Enumerable type, using the previous result as the first argument, thus generating the chain.

It finally compiles and executes the chain of methods on the actual enumerable instance passed in.

Here is a typical use:

var sorts = new List<ISort<IPerson>> {
                                        new Sort<IPerson>("Timestamp", SortDirection.Descending),
                                        new Sort<IPerson>("Name", SortDirection.Ascending),
                                     };

var sortedPersons = persons.Sort(sorts);

Lambda Wrangling For Fun : Part 3 – Filtering Multiple Columns

2011-04-16T01:32:00.001-07:00

We now know how to generate a dynamic predicate to filter a collection of items by a single property value.

It is often useful to be able to apply multiple filters to a collection to support more sophisticated searching and filtering operations.

Let’s define a general-purpose filter interface to encapsulate the property, the target value and the comparison function.

public interface IFilter
{
    string PropertyName { get; }
    dynamic TargetValue { get; }
    Expression<Func<dynamic, dynamic, bool>> Comparison { get; }
    Expression<Func<TSource, bool>> GetPredicateLambda<TSource>();
    Expression BuildComparisonExpression<TSource>(Expression parameterExpression = null);
}

The three properties are what we expect to see, and we’ve already seen a variant of the GetPredicateLambda function before.

Before we see what the other method is needed for, let’s analyse what it means to filter multiple columns first:

One Fish, Two Fish…

A filter with a single predicate comparing against a value looks thus:

….Where(_ => predicate0(_.property0, value0))

and if we had to filter by more than one predicate would look like:

….Where(_ => predicate0(_.property0, value0) 
          && predicate1(_.property1, value1))

Notice that what we need to do is to create just the comparison part part of the lambda for each filter, with the same parameter injected into each predicate call.

This is exactly what the BuildComparisonExpression function does. Here is the implementation:

public virtual Expression BuildComparisonExpression<TSource>(Expression parameterExpression = null)
{
    // This gives us * _ *
    parameterExpression = parameterExpression ?? Expression.Parameter(typeof (TSource), "_");

    var propertyInfo = typeof (TSource).GetProperty(PropertyName, true);
    if (propertyInfo == null)
    {
        throw new MemberAccessException(String.Format("No such property exists: {0}", PropertyName));
    }

    // This gives us * _.property *
    var accessorExpression = Expression.Property(parameterExpression, propertyInfo);
    
    // This gives us * value *
    var valueExpression = Expression.Constant(TargetValue);

    // This gives us * comparison(_property, value) *
    return Expression.Invoke(Comparison, accessorExpression, valueExpression);
}

The key to this method is the last line. Expression.Invoke generates an expression which invokes the Comparison expression with the accessorExpression and valueExpression as its arguments.

Also, we do not generate the Lambda with this expression, as we may have more than one Comparison to chain together.

We do that as follows:

public static Expression<Func<TSource, bool>> GetFilterExpression<TSource>(this IEnumerable<IFilter> filterCollection)
{
    if (filterCollection == null) return _ => true;

    var parameterExpression = Expression.Parameter(typeof (TSource), "_");

    var aggregateFilterExpression = filterCollection.Aggregate(
           (Expression) Expression.Constant(true),
           (current, filter) => Expression.AndAlso(current, 
                     filter.BuildComparisonExpression<TSource>(parameterExpression)));

    return Expression.Lambda<Func<TSource, bool>>(aggregateFilterExpression, parameterExpression);
}

This function aggregates all the filter expressions, threading through the same parameterExpression, and builds the lambda function to call.

This is what a complex filter expression looks like:

Clean and straightforward lambdas.

We can now extend this approach to use conjunctions other than AndAlso, and perhaps special-case some comparison operations.

Lambda Wrangling For Fun : Part 2 – Filtering Single Columns

2011-04-12T23:31:00.001-07:00

In the previous post, we developed a way of dynamically generating a lambda based on a property name to pass through to the OrderBy or OrderByDescending LINQ function in order to sort a collection of items by the specified property.

We can do the same thing to dynamically generate a filter predicate to use in several LINQ extension methods that accept predicates.

Anatomy of a Filter

A filter predicate has three parts:

A constant value or expression to compare against
A comparison operator
A target property on the object which should be compared with the constant value

We already know how to express property selectors – we used them here.

Let’s approach the rest of the problem in stages:

Ceteris paribus…

Let’s fix the comparison operator to be the equality operator - “ == “.

Then we can write a naive lambda generator thus:

public static Func<TSource, bool> GetPropertyFilterLambda<TSource>(this TSource _this, string propertyName, object filterValue)
{
    // Given that propertyName = "Foo" and filterValue = blah
    //  we want the lambda expression * _ => _.Foo == blah *

    // This gives us the * _ => * part
    var parameterExpression = Expression.Parameter(typeof (TSource), "_");

    // This gives us the * .Foo * part - see the interfaces and inheritance blog post
    var propertyInfo = typeof(TSource).GetProperty(propertyName, true);

    // This gives us the * _.Foo * part
    var accessorExpression = Expression.Property(parameterExpression, propertyInfo);

    // This gives us the * blah * part
    var valueExpression = Expression.Convert(Expression.Constant(filterValue), propertyInfo.PropertyType);

    // This gives us the * _.Foo == blah * part
    var equalityComparisionExpression = Expression.Equal(accessorExpression, valueExpression);

    // This gives us the * _ => _.Foo == blah * part
    return Expression.Lambda<Func<TSource, bool>>(equalityComparisionExpression, parameterExpression).Compile();
}

We need to incorporate the type conversion into the constant expression because it’s very likely that the constant value is a string (passed in from an ASP.NET MVC Controller, for example) while the property is an integer property.

You’re not my Type!

By happy coincidence, the C# language does the right thing for the equality operator on strings and compares values even though strings are a reference type. But other reference types will pose a problem since the equality operator only compares references.

So let’s strongly type the constant value:

public static Func<TSource, bool> GetPropertyFilterLambda<TSource, TValue>(this TSource _this, string propertyName, TValue filterValue)
{
    // Given that propertyName = "Foo" and filterValue = blah
    //  we want the lambda expression * _ => _.Foo == blah *

    // This gives us the * _ => * part
    var parameterExpression = Expression.Parameter(typeof (TSource), "_");

    // This gives us the * .Foo * part - see the interfaces and inheritance blog post
    var propertyInfo = typeof (TSource).GetProperty(propertyName, true);

    // ensure the property is of the same type as the value
    if (!propertyInfo.PropertyType.IsAssignableFrom(typeof (TValue)))
    {
        throw new MemberAccessException(String.Format("Property {0}.{1} is not of type {2}",
                                                      typeof (TSource).Name,
                                                      propertyInfo.Name,
                                                      typeof (TValue).Name));
    }

    // This gives us the * _.Foo * part
    var accessorExpression = Expression.Property(parameterExpression, propertyInfo);

    // This gives us the * blah * part
    var valueExpression = Expression.Convert(Expression.Constant(filterValue), propertyInfo.PropertyType);

    // This gives us the * _.Foo == blah * part
    var equalityComparisionExpression = Expression.Equal(accessorExpression, valueExpression);

    // This gives us the * _ => _.Foo == blah * part
    return Expression.Lambda<Func<TSource, bool>>(equalityComparisionExpression, parameterExpression).Compile();
}

So far so good.

sed ceteris non paribus…

But there’s no way to specify a different operation than simple equality comparison with this. There is not even a way to do a deep equality comparison on non-string reference objects.

What we really need is a way to provide our own comparison functions, which will give us the flexibility to compare two objects and decide if they satisfy the predicate.

Here is such a function:

public static Expression<Func<TSource, bool>> GetPropertyFilterLambda<TSource, TValue>(this TSource _this,
                                                                                       string propertyName,
                                                                                       TValue filterValue,
                                                                                       Func<TValue, TValue, bool> compareFunc)
{
    // Given that propertyName = "Foo" and filterValue = blah
    //  we want the lambda expression * _ => compareFunc(_.Foo, blah) *

    // This gives us the * _ => * part
    var parameterExpression = Expression.Parameter(typeof (TSource), "_");

    // This gives us the * .Foo * part - see the interfaces and inheritance blog post
    var propertyInfo = typeof (TSource).GetProperty(propertyName, true);

    // ensure the property is of the same type as the value
    if (!propertyInfo.PropertyType.IsAssignableFrom(typeof (TValue)))
    {
        throw new MemberAccessException(String.Format("Property {0}.{1} is not of type {2}",
                                                      typeof (TSource).Name,
                                                      propertyInfo.Name,
                                                      typeof (TValue).Name));
    }

    // This gives us the * _.Foo * part
    var accessorExpression = Expression.Property(parameterExpression, propertyInfo);

    // This gives us the * blah * part
    var valueExpression = Expression.Convert(Expression.Constant(filterValue), propertyInfo.PropertyType);

    // This gives us the * compareFunc(_.Foo, blah) * part
    var compareExpression = Expression.Call(null, compareFunc.Method, accessorExpression, valueExpression);

    // This gives us the * _ => compareFunc(_.Foo, blah) * part
    return Expression.Lambda<Func<TSource, bool>>(compareExpression, parameterExpression);
}

which can be invoked thus:

<…>.Where(default(IIngredient)
    .GetPropertyFilterLambda(
        "Name", 
        "Cheese", 
        (_l, _r) => _l.Contains(_r)));

so we aren’t constrained to an equality operation any more!

We raise the stakes one more level and curry the constant into the comparison lambda thus:

public static Expression<Func<TSource, bool>> GetPropertyFilterLambda<TSource, TValue>(this TSource _this,
                                                                                       string propertyName,
                                                                                       Func<TValue, bool> predicate)
{
    // Given that propertyName = "Foo"
    //  we want the lambda expression * _ => predicate(_.Foo) *

    // This gives us the * _ => * part
    var parameterExpression = Expression.Parameter(typeof(TSource), "_");

    // This gives us the * .Foo * part - see the interfaces and inheritance blog post
    var propertyInfo = typeof(TSource).GetProperty(propertyName, true);

    // ensure the property is of the same type as the value
    if (!propertyInfo.PropertyType.IsAssignableFrom(typeof(TValue)))
    {
        throw new MemberAccessException(String.Format("Property {0}.{1} is not of type {2}",
                                                      typeof(TSource).Name,
                                                      propertyInfo.Name,
                                                      typeof(TValue).Name));
    }

    // This gives us the * _.Foo * part
    var accessorExpression = Expression.Property(parameterExpression, propertyInfo);

    // This gives us the * predicate(_.Foo) * part
    var compareExpression = Expression.Call(null, predicate.Method, accessorExpression);

    // This gives us the * _ => predicate(_.Foo) * part
    return Expression.Lambda<Func<TSource, bool>>(compareExpression, parameterExpression);
}

which can be invoked like this:

<…>.Where(default(IIngredient)
    .GetPropertyFilterLambda(
        "Name", 
        (string _l) => _l.Contains("Cheese"));

Neat-o!

Lambda Wrangling For Fun : Part 1 – Sorting Single Columns

2011-04-10T17:51:00.000-07:00

No doubt that a lot of us remember the good old days when we wrote web applications with grids that had sortable columns. For those crazy old timers like myself who were writing this sort of thing before the naff ASP.NET grids came out, we remember the process to go something along these lines:

Obtain the name of the column to sort the data set on.
Obtain the direction of the sort
Construct the ORDER BY clause in the SELECT query to be executed to return the data sorted in the correct way.
Execute said query and render the data set appropriately

Setting aside all the discussion about the crudeness of the solution, one thing can be said in favour of this approach – it was simple.

With a more formal service-oriented approach, one constructs a method on the service for each column to be sorted on and implements the appropriate LINQ query statically.

(Yes, I’m aware of Dynamic LINQ, but pretend it doesn’t exist for now.)

The object of this post is to discuss an approach with the flexibility of run-time column selection and the type-safety and inherent power of LINQ.

Dissecting a Lambda

System.Linq.Enumerable has a few extension methods which provide ordering semantics. Let’s consider the most commonly used one – ‘OrderBy’. In its simplest form, it looks like this:

public static System.Linq.IOrderedEnumerable OrderBy(this System.Collections.Generic.IEnumerable source, 
                                                     System.Func keySelector)

    Member of System.Linq.Enumerable

Summary:
Sorts the elements of a sequence in ascending order according to a key.

Type Parameters:
TSource: The type of the elements of source.
TKey: The type of the key returned by keySelector.

Parameters:
source: A sequence of values to order.
keySelector: A function to extract a key from an element.

Returns:
An System.Linq.IOrderedEnumerable whose elements are sorted according to a key.

So this OrderBy function takes a collection of items to be sorted, and a lambda which selects a property on each item on which to sort by.

The lambda itself specifies the type of the item (which is known because we have a strongly typed collection) and the type of the sorting property. This can be inferred if the lambda is present at compile time.

Creating a Lambda on the fly

Given a property name string, we want to somehow concoct a lambda which can be given to the OrderBy function.

Here is a function which does that – analysis to follow:

public static Func<TSource, object> GetPropertySelectorLambda<TSource>(this TSource _this, string propertyName)
{
    // Given that propertyName = "Foo", we want the lambda expression * _ => _.Foo *

    // This gives us the * _ => * part
    var parameterExpression = Expression.Parameter(typeof(TSource), "_");

    // This gives us the * .Foo * part - see the interfaces and inheritance blog post
    var propertyInfo = typeof(TSource).GetProperty(propertyName, true);

    // This gives us the * _.Foo * part
    var unboxedAccessorExpression = Expression.Property(parameterExpression, propertyInfo);

    // Guid, int and other value types can't strictly be return types in expressions
    // Why? Because 'object' is a reference type
    // So we convert value types to Object
    var accessorExpression = (unboxedAccessorExpression.Type.IsValueType
                                  ? (Expression)Expression.Convert(unboxedAccessorExpression, typeof(object))
                                  : unboxedAccessorExpression);

    // Build the lambda to the strong Func type and compile it down to a Func
    return Expression.Lambda<Func<TSource, object>>(accessorExpression, parameterExpression).Compile();
}

The Expression wrangling above is typical of functions which generate lambdas on the fly – it’s not as elegant as a truly functional language, but it works even though it’s a bit unwieldy.

The NullReferenceException that wasn’t!

The eagle-eyed reader will notice that the only use of ‘_this’ is to make the function an extension method – so that it becomes accessible in a reasonably fluent manner.

What we’re really interested is in the type of ‘_this’. The value of ‘_this’ is never used. This means that ‘_this’ can be null – or even more mysteriously, it can refer to something that can never exist!

So typically, as in an MVC controller, this method may be used thus:

// GET: /T/
public virtual ActionResult Index(string sort_column = "Timestamp")
{
    var orders = Service.Get(null, default(TOrder).GetPropertySelectorLambda(sort_column));
    return View(orders);
}

TOrder could be an interface, so we use default(TOrder) instead of new(TOrder) as the anchor for the extension method. Now, since TOrder is defined as a reference type, default(TOrder) can never be anything but null, but the extension method still works very nicely!

Cool!

Interfaces and inheritance

2011-04-09T16:43:00.000-07:00

Quite often, we would like to reflectively use properties defined on types.

Basic Reflection

The Type class has a GetProperties() method which returns all the properties on it.

var properties = typeof(Foo).GetProperties()

Consider the following inheritance hierarchy:

internal class Base
{
    public string BaseProperty { get; set; }
}

internal class Derived : Base
{
    public string DerivedProperty { get; set; }
}

var properties = typeof(Derived).GetProperties();

We expect the properties collection to have two items corresponding with BaseProperty and DerivedProperty respectively.

The Trouble with Interfaces

Now consider the following inheritance hierarchy:

internal interface IBase
{
    string BaseProperty { get; set; }
}

internal interface IDerived : IBase
{
    string DerivedProperty { get; set; }
}

var properties = typeof(IDerived).GetProperties();

Do we expect anything different? Running this gives us:

Now, there is only one property: the DerivedProperty on the IDerived interface – why?

Legalese…

It turns out that this behaviour is by design, and it hinges on the way in which inheritance is interpreted by the language designers.

This is made clear in section 8.10 of the ECMA CLI specifications where it says (emphasis mine):

8.10 Member inheritance Only object types can inherit implementations, hence only object types can inherit members (see §8.9.8). While interface types can be derived from other interface types, they only “inherit” the requirement to implement method contracts, never fields or method implementations.

Reading through the legalese, what this means is that derived interfaces do not contain their base interface properties like derived classes do – they only specify the requirement that any implementer of the interface must implement both derived and base properties.

It’s a very fine line, but I’m not immediately aware of why such a line exists!

The way out

We can quite easily write a little extension function to iterate over all the properties of a class, recursively including any base classes and interfaces.

There are a few key points to notice which will be pointed out, but first, the code:

public static IEnumerable<PropertyInfo> GetAllProperties(this Type _this,
                                                         IList<Type> processedInterfaces = null,
                                                         BindingFlags flags =
                                                             BindingFlags.Instance | BindingFlags.Public | BindingFlags.DeclaredOnly)
{
    processedInterfaces = processedInterfaces ?? new List<Type>();

    if (!processedInterfaces.Contains(_this))
    {
        foreach (var _pi in _this.GetProperties(flags))
        {
            yield return _pi;
        }

        if (_this.BaseType != null)
        {
            foreach (var _pi in _this.BaseType.GetAllProperties(processedInterfaces, flags))
            {
                yield return _pi;
            }
        }

        if (_this.IsInterface)
        {
            foreach (var _pi in _this.GetInterfaces().SelectMany(_ => _.GetAllProperties(processedInterfaces, flags)))
            {
                yield return _pi;
            }
        }

        processedInterfaces.Add(_this);
    }

    yield break;
}

The first thing to note is that we treat a single class atomically. That is to say, we consider a class to potentially have a base class and some interfaces. We recursively treat the base class the same way.

However, to prevent double-counting of the base class properties, we limit the properties considered for each class to be just those specified in the class itself.

Furthermore, multiple classes and interfaces can implement the same interface, so we keep a list of interface types that we have processed, and only process them once. This allows for complex interface hierarchies to be expressed in their simplest form. We use a default argument for this to keep the function signature as minimal as possible without sacrificing functionality.

The last bit of elegance is to use the yield operator to only process the enumeration at iteration time. As a bonus, this keeps the code very readable!

Enjoy!

Never leave well enough alone…until you understand what’s going on!

2011-03-10T21:53:00.001-08:00

We now have built a fast generator for predictably unique but ordered Guids.

Before the profiler indicated that DateTime.Now.Ticks was quite an expensive call, I suspected the process of reversing the bytes in a 64-bit integer was too unwieldy.

Having addressed the Ticks counter issue, I decided to investigate the byte-reversing operation anyway. They don’t call me a geek for nuthin’!

This is the code I had my suspicions about:

public static byte[] GetReversedBytesSlow(this Int64 value)
{
    var rgb = BitConverter.GetBytes(value);
    Array.Reverse(rgb);

    return rgb;
}

You can tell that I was looking back fondly to my C/C++ days, where we could cast the integer to an array of 8 bytes and do some pointer math!

Entering ‘unsafe’ territory…

I created a new Class Library project, and marked it as containing unsafe code.

Then I went at the unsafe code leaving caution to the winds:

public static unsafe class Convert
{
    private static byte[] GetReversedBytesFor64BitValue(byte * rgb)
    {
        return new[]
               {
                   rgb[7], rgb[6], rgb[5], rgb[4], rgb[3], rgb[2], rgb[1], rgb[0]
               };

    }

    public static byte[] GetReversedBytes(this UInt64 _this)
    {
        return GetReversedBytesFor64BitValue((byte*)&_this);
    }

    public static byte[] GetReversedBytes(this Int64 _this)
    {
        return GetReversedBytesFor64BitValue((byte*)&_this);
    }
}

Now, that felt really good to do

By hand-unrolling the pointer arithmetic, I was sure that I would definitely be faster than the general reversal algorithm that Array.Reverse would use.

The proof of the pudding…

First, we need to make sure we’re doing the right thing in our unsafe speed-demon.

We write a test:

private static void EnsureArraysAreIdentical(byte[] expected, byte[] actual)
{
    Assert.AreEqual(expected.Length, actual.Length);

    for (var i=0;i<expected.Length; i++)
    {
        Assert.AreEqual(expected[i], actual[i]);
    }
}

private const long TEST_MIN = -10000000L;
private const long TEST_MAX = 10000000L;

[TestMethod]
public void TestReverseBytes64Bit()
{
    for(var l = TEST_MIN; l < TEST_MAX; l++)
    {
        EnsureArraysAreIdentical(GetReversedBytesSlow(l), l.GetReversedBytes());
    }
}

which tests both reversal methods for identical results from –10 million to +10 million, zero inclusive.

The results speak for themselves:

Now to see if we’ve actually made any difference in the performance!

Nice!

We’ve improved the performance almost 3x – it’s just that the results only become noticeable after 20 million integer reversals!

Now that’s what I call a productive afternoon!

Making it fast!

2011-03-10T19:46:00.001-08:00

In the last post, I outlined a strategy to generate Guids in a strictly increasing order to address the issues outlined here.

While Guid.NewGuid() natively takes quite a bit of time to create a random Guid, it would be interesting to see if our implementation is slower, or faster – and to investigate ways to speed it up.

Our first run

Hmm.. that seems to be pretty good – but inspecting the code should point a steady finger at the Thread.Sleep(1) call. So how does one make the sequence increase, without the Sleep() call.

Enter Interlocked.Increment()

A strategy to ensure monotonically increasing numbers would be to initialize a counter with DateTime.Now.Ticks, and then in the generation method, to increment it in a thread-safe manner – thus:

private static long _counter;

public static Guid NewSequentialGuid()
{
    lock (LockObject)
    {
        Interlocked.CompareExchange(ref _counter, DateTime.Now.Ticks, 0);
        Interlocked.Increment(ref _counter);

        var rgb = BitConverter.GetBytes(_counter);
        Array.Reverse(rgb);

        return new Guid(_a, _b, _c, rgb);
    }
}

The tests continue to pass, assuring us that the Guids are still unique. Measuring the performance, we get:

Much better – we’ve made things around twice as fast. I would leave things as they are now – except I’m quite curious to see if I can extract some more performance out of it.

The importance of profiling

We have only five lines of code there – where do we start speeding things up?

The best way to find out would be to fire up the profiler in Visual Studio 2010 and run the program in there. That points us to:

Hmm… looks like we’re spending most of our time getting the Ticks count, even if we never use it more than once – definitely wasteful.

Why don’t we cache the Ticks count once, and just use the Interlocked.Increment call to make it unique?

private static long _counter = DateTime.Now.Ticks;

public static Guid NewSequentialGuid()
{
    lock (LockObject)
    {
        Interlocked.Increment(ref _counter);

        var rgb = BitConverter.GetBytes(_counter);
        Array.Reverse(rgb);

        return new Guid(_a, _b, _c, rgb);
    }
}

That results in

Pretty good. So let’s look at a sequence of Guids created 50ms apart.

The implication of this is that every time the OrderedGuid class is initialized, the _counter would get set, and thereafter it would be a simple incremented sequence – even though there was a time delay of 50ms between each Guid being created.

If we wanted the creation of the Guid to be more ‘random’ and be more closely tied to the Ticks count, we could keep the _counter refreshed every so often with a Timer.

private static readonly Timer Timer = new Timer(ResetCounter, null, 0, 100);

private static void ResetCounter(object arg = null)
{
    lock (LockObject)
    {
        _counter = DateTime.Now.Ticks;
    }
}

static OrderedGuid()
{
    lock (LockObject)
    {
        ResetCounter();
    }
}

This would keep the _counter up to date reasonably frequently.

As you can see, we have a good somewhat random distribution between Guids created 50ms apart.

We’ve done this without appreciably slowing things down – given the coarse granularity of the tick-counting approach to timing, all we can say is that we haven’t made things very much different by introducing the timer.

And now we have a viable, fast way of generating predictably-unique, ordered Guids.