14 October 2014
In September, I was talking about Implementing F#-inspired "with" updates for immutable classes in C# - in which I mentioned that
The UpdateWithSignature
delegate itself is a compiled LINQ expression so, once the cost of generating it has been paid the first time that it's required, the calls to this delegate are very fast
In the past, I've made use of LINQ expressions for writing code that is generated at runtime that will be executed many times and would benefit from being as fast as code written at compile time. I'm by no means an expert, but I've put it to use a few times and feel like I'm slowly getting the hang of it. What struck me, the first few times that I tried to find out how to do things, was how sparse the information seems to be out there. There's reference material from Microsoft - which is helpful if you basically have a good grasp on what you're doing and need to look up some minutiae of the implementation. You can find quite advanced articles, but these also tend to assume deep knowledge and jump right into the deep end. Then there's beginner-oriented overview articles - these can be excellent at giving an introduction into what LINQ expressions can mean and what they can be used for, but they don't tend to go beyond fairly simple examples and don't (I found) help you get into the frame of mind that you need to build up complex expressions.
I thought it might be helpful for an "intermediary level" article to exist that takes the basic concepts and walks through creating something useful with it.
Now, I should maybe preface this with an admission that in a subsequent post to the one I quoted above (see "A follow-up to "Implementing F#-inspired 'with' updates in C#"), I said that I probably wouldn't end up using this dynamic run-time-compiled code in real world projects - but it still seems like a good sized example of something real-world-ish. So I'm going to walk through recreating it. If you haven't read that post, no worries, I'm going to act like you haven't and explain everything as I go (and after you're finished, if you haven't read that post, you can go do so :)
Here's the setup, which corresponds roughly to what I was trying to do last month. I've got a class RoleDetails -
public class RoleDetails
{
public RoleDetails(string title, DateTime startDate, DateTime? endDateIfAny)
{
Title = title;
StartDate = startDate;
EndDateIfAny = endDateIfAny;
}
public string Title { get; private set; }
public DateTime StartDate { get; private set; }
public DateTime? EndDateIfAny { get; private set; }
}
I wanted to generate a method at runtime which I could pass the arguments "title", "startDate" and "endDateIfAny" to and have it return a new instance of the class, using those values to define the new instance. The equivalent of
public static RoleDetails UpdateWith(
RoleDetails source,
Optional<string> title,
Optional<DateTime> startDate,
Optional<DateTime?> endDateIfAny)
{
if (source == null)
return new ArgumentNullException("source");
if (!title.IndicatesChangeFromValue(source.Title)
&& !startDate.IndicatesChangeFromValue(source.StartDate)
&& !endDateIfAny.IndicatesChangeFromValue(source.EndDateIfAny))
return this;
return new RoleDetails(
title.GetValue(source.Title),
startDate.GetValue(source.StartDate),
endDateIfAny.GetValue(source.EndDateIfAny)
);
}
where the Optional type is a struct
public struct Optional<T>
{
private T _valueIfSet;
private bool _valueHasBeenSet;
public T GetValue(T valueIfNoneSet)
{
return _valueHasBeenSet ? _valueIfSet : valueIfNoneSet;
}
public bool IndicatesChangeFromValue(T value)
{
if (!_valueHasBeenSet)
return false;
if ((value == null) && (_valueIfSet == null))
return false;
else if ((value == null) || (_valueIfSet == null))
return true;
return !value.Equals(_valueIfSet);
}
public static implicit operator Optional<T>(T value)
{
return new Optional<T>
{
_valueIfSet = value,
_valueHasBeenSet = true
};
}
The structure we need to form is a "body expression" that performs the method's internals, and for this to be packaged up with method arguments into a compiled lambda expression.
Before going too wild, a simple example to illustrate this is a good start:
private Func<RoleDetails, string> GetRoleTitleRetriever()
{
var sourceParameter = Expression.Parameter(typeof(RoleDetails), "source");
var titlePropertyRetriever = Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("Title")
);
return
Expression.Lambda<Func<RoleDetails, string>>(
titlePropertyRetriever,
sourceParameter
).Compile();
}
The "titlePropertyRetriever" is an expression that will return the value of the "Title" property from a RoleDetails instance that is represented by an expression passed into it. In this case, that expression is the "sourceParameter" which will be combined with the "titlePropertyRetriever" (which, here, represents the entirety of the "body" expression) to create a lambda expression. The "sourceParameter" is the single argument for this particular lambda.
A lamba expression can be used in conjunction with other expressions if you need to form a complicated construct. Here we have a very simple action and so we call the "Compile" method and return the result. The static method "Expression.Lambda" returns an Expression<Func<RoleDetails, string>>. Calling "Compile" on it returns a Func<RoleDetails, string>. This is a delegate that we can call directly in our code.
This code could be used thusly -
var role1 = new RoleDetails("Head Honcho", DateTime.Now, null);
var role2 = new RoleDetails("Dogsbody", DateTime.Now, null);
var titleRetriever = GetRoleTitleRetriever();
var title1 = titleRetriever(role1); // This equals "Head Honcho"
var title2 = titleRetriever(role2); // This equals "Dogsbody"
While obviously very simplistic, this gives us some sense of the structure we want. Note that there is no explicit representation of "return" in there - the body expression is expected to return a value and the result of the last expression is taken as the return value.
What I'm trying to get towards, though, is something that produces a new instance of the same type - not just a property retrieved from it. So instead of a Func<RoleDetails, string>, we want a Func<RoleDetails, RoleDetails> which does some sort of work.
The next (small) step is to illustrate calling a constructor. The following will return a new instance of RoleDetails using all the same property values.
private Func<RoleDetails, RoleDetails> GetCloner()
{
var sourceParameter = Expression.Parameter(typeof(RoleDetails), "source");
var constructor = typeof(RoleDetails).GetConstructor(new[] {
typeof(string),
typeof(DateTime),
typeof(DateTime?)
});
return
Expression.Lambda<Func<RoleDetails, RoleDetails>>(
Expression.New(
constructor,
Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("Title")
),
Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("StartDate")
),
Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("EndDateIfAny")
)
),
sourceParameter
).Compile();
}
Reflection is used to get a reference to the constructor that takes arguments with types string, DateTime and DateTime?. The body expression consists of the result of "Expression.New", which takes a constructor and expressions for the values and returns an expression for the new instance.
I'm not going to go into too much detail about using reflection to look up constructors, properties, methods, etc.. since it's easy to good find resources that cover this topic at all levels. In my original post, I was talking about code that would analyse the target type and match the best constructor to available properties (for cases where there might be multiple constructors) - here, I'm going to leave all that out and "hard code" the mappings. It shouldn't be a big deal to take what I'm (hopefully!) going to explain here and then complicate it by bolting on some reflection-based type analysis.
It's worth noting here, that the code above has hard-coded strings for property names and relies upon a particular constructor signature being available. As soon as you introduce reflection like this, you give up much of what the compiler can offer you and if the target types get refactored in a manner that changes the facts relied on then you won't find out until runtime that you've got a problem. But that's the cost of runtime craziness like this. I think it's a fair assumption going in that you're well aware of all this! Often this sort of code gymnastics is not appropriate, but other times runtime convenience is very useful - I tend to use AutoMapper as the canonical example since people seem to find it very easy to grasp the pros and cons of it but it's an prime example of something that you mightn't find issues with until runtime (as opposed to less "dynamic" code that issues can be identified with at compile time, through static analysis in the IDE).
The next step in our example code is the introduction of additional arguments. To stick to baby steps, all we'll do is define a delegate the takes a source reference and returns a new instance by overriding a single property - specifically the "Title":
private Func<RoleDetails, string, RoleDetails> GetTitleUpdater()
{
var sourceParameter = Expression.Parameter(typeof(RoleDetails), "source");
var titleParameter = Expression.Parameter(typeof(string), "title");
var constructor = typeof(RoleDetails).GetConstructor(new[] {
typeof(string),
typeof(DateTime),
typeof(DateTime?)
});
return
Expression.Lambda<Func<RoleDetails, string, RoleDetails>>(
Expression.New(
constructor,
titleParameter,
Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("StartDate")
),
Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("EndDateIfAny")
)
),
sourceParameter,
titleParameter
).Compile();
}
Here, it's clear how to affect the Func signature - by changing the type param for "Expression.Lambda" and by specifying the corresponding number of parameters. Instead of the body expression and a single argument, we now specify two arguments. The types of the arguments in the Func are consistent with the types of the "sourceParameter" and "titleParameter". The third Func type param is also RoleDetails since that is what is returned by the RoleDetails constructor that "Expression.New" is using.
It's also clear how expressions can be interchanged - before the "Expression.New" call was taking a constructor reference and then expressions for the constructor arguments that all consisted of type MemberExpression (since this the return type of "Expression.Property"). Now we've switched the first MemberExpression out for a ParameterExpression. "Expression.New" doesn't care if the constructor argument expressions are property retrievals, method arguments, constant values - they can be anything, so long as they can be described by a type of Expression.
Let's address two issue now. Firstly, there should be three arguments passed in - for each of the three constructor arguments - instead of one. And these arguments should be of type Optional<T>, so that they can effectively have "no value" and default to the value they have on the "source" reference.
private delegate RoleDetails RoleDetailsUpdater(
RoleDetails source,
Optional<string> title,
Optional<DateTime> startDate,
Optional<DateTime?> endDateIfAny
);
private RoleDetailsUpdater GetSimpleUpdater()
{
var sourceParameter = Expression.Parameter(typeof(RoleDetails), "source");
var titleParameter = Expression.Parameter(typeof(Optional<string>), "title");
var startDateParameter = Expression.Parameter(typeof(Optional<DateTime>), "startDate");
var endDateIfAnyParameter = Expression.Parameter(typeof(Optional<DateTime?>), "endDateIfAny");
var constructor = typeof(RoleDetails).GetConstructor(new[] {
typeof(string),
typeof(DateTime),
typeof(DateTime?)
});
return
Expression.Lambda<RoleDetailsUpdater>(
Expression.New(
constructor,
Expression.Call(
titleParameter,
typeof(Optional<string>).GetMethod("GetValue"),
Expression.Property(sourceParameter, "Title")
),
Expression.Call(
startDateParameter,
typeof(Optional<DateTime>).GetMethod("GetValue"),
Expression.Property(sourceParameter, "StartDate")
),
Expression.Call(
endDateIfAnyParameter,
typeof(Optional<DateTime?>).GetMethod("GetValue"),
Expression.Property(sourceParameter, "EndDateIfAny")
)
),
sourceParameter,
titleParameter,
startDateParameter,
endDateIfAnyParameter
).Compile();
}
Now we're using the return values of "GetValue" method calls for all of the constructor arguments. Each method call is taking a property value extracted from the "source" reference as an argument (since "GetValue" takes a single argument - as per the definition of Optional earlier). I've also snuck in another change. I found that it was getting unwieldy specifying a Func with five arguments (RoleDetails, string, DateTime and DateTime? as inputs and another RoleDetails as the output) and so defined a delegate to instead. This delegate can be used with "Expression.Lambda" just as well as any Func can.
There are two concepts missing still, though, that are key to the original intention. We need to throw an exception if the "source" reference is null. And we need to return the source reference straight back out if none of the arguments represent a change; if the "title", "startDate" and "endDateIfAny" values all match those on the source reference then we may as well return that source reference straight back, rather than creating a new instance that we don't need - this only makes sense because RoleDetails is an immutable type (but since it is, it does make sense).
To deal with branching, there is a method "Expression.IfThenElse" which takes an expression for the condition (this expression must represent a boolean-returning operation) and then expressions for if-true and if-false. There is something to be aware of here, though - in C# (and in LINQ expressions) an "If" (or "If..Else") statement is not an "expression" where "expression" means "something that returns a value". It branches execution but, unlike with the property accessor or methods calls we've seen so far, it doesn't return a value. To make it work as required here, at the end of each branch we need to return via a "label" that marks the end of the block and has a type corresponding to the block's return type.
A label indicates an exit point in a block. If the block has a return type, then the label must have a compatible return value (if the block's return type is void then the label needn't specify a return value since the block will not be returning any value). The label's return value may be null, but if a type other than System.Object is being returned then that null constant must be described with the actual return type.
Once this label is defined, "Expression.Return" can be used to terminate the branches on an if-then-else construct. This is all illustrated in the next example.
The source-argument-null-check is easier; we'll combine "Expression.IfThen" (rather than "IfThenElse") with "Expression.Throw". There is no return label nonsense to worry about since, once an exception has been thrown, there's no return value involved! "Expression.Throw" takes a single argument, which is the exception that it should throw.
private RoleDetailsUpdater GetUpdater()
{
// These are the parameters for the RoleDetailsUpdater delegate that will be generated
var sourceParameter = Expression.Parameter(typeof(RoleDetails), "source");
var titleParameter = Expression.Parameter(typeof(Optional<string>), "title");
var startDateParameter = Expression.Parameter(typeof(Optional<DateTime>), "startDate");
var endDateIfAnyParameter = Expression.Parameter(
typeof(Optional<DateTime?>),
"endDateIfAny"
);
// When evaluated, these expressions will extract the property values from the "source" reference
var sourceTitleRetriever = Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("Title")
);
var sourceStartDateRetriever = Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("StartDate")
);
var sourceEndDateIfAnyRetriever = Expression.Property(
sourceParameter,
typeof(RoleDetails).GetProperty("EndDateIfAny")
);
// When evaluated, these will determine whether any of the argument values differ from the
// property values on the "source" reference
var isTitleValueNew = Expression.Call(
titleParameter,
typeof(Optional<string>).GetMethod("IndicatesChangeFromValue"),
sourceTitleRetriever
);
var isStartDateValueNew = Expression.Call(
startDateParameter,
typeof(Optional<DateTime>).GetMethod("IndicatesChangeFromValue"),
sourceStartDateRetriever
);
var isEndDateIfAnyValueNew = Expression.Call(
endDateIfAnyParameter,
typeof(Optional<DateTime?>).GetMethod("IndicatesChangeFromValue"),
sourceEndDateIfAnyRetriever
);
var areAnyValuesNew = Expression.OrElse(
isTitleValueNew,
Expression.OrElse(isStartDateValueNew, isEndDateIfAnyValueNew)
);
// This is the where the real work takes place: If "source" is null then throw an exception.
// If any of the arguments require that a new instance being created, then construct that
// instance with the new data and return it. Otherwise just return the source reference.
var returnTarget = Expression.Label(typeof(RoleDetails));
return
Expression.Lambda<RoleDetailsUpdater>(
Expression.Block(
Expression.IfThen(
Expression.Equal(sourceParameter, Expression.Constant(null)),
Expression.Throw(Expression.Constant(new ArgumentNullException("source")))
),
Expression.IfThenElse(
areAnyValuesNew,
Expression.Return(
returnTarget,
Expression.New(
typeof(RoleDetails).GetConstructor(new[] {
typeof(string),
typeof(DateTime),
typeof(DateTime?)
},
Expression.Call(
titleParameter,
typeof(Optional<string>).GetMethod("GetValue"),
sourceTitleRetriever
),
Expression.Call(
startDateParameter,
typeof(Optional<DateTime>).GetMethod("GetValue"),
sourceStartDateRetriever
),
Expression.Call(
endDateIfAnyParameter,
typeof(Optional<DateTime?>).GetMethod("GetValue"),
sourceEndDateIfAnyRetriever
)
)
),
Expression.Return(
returnTarget,
sourceParameter
)
),
Expression.Label(returnTarget, Expression.Constant(null, typeof(RoleDetails)))
),
sourceParameter,
titleParameter,
startDateParameter,
endDateIfAnyParameter
).Compile();
}
Note the use of "Expression.OrElse" above. We use this since we're dealing with boolean logic (eg. is the start-date-value new or is the end-date-value new). There is an "Expression.Or" method, but that is for numeric operations (eg. 1 & 4).
At this point, we've achieved what I laid out as the original intention.
I'm not going to pretend that it's particularly beautiful or succinct - especially compared to the code that you would write by hand. But then, if you had a scenario where you could write this by hand then you probably would, rather than having to resort to writing code that generates more code! And when I think about how LINQ expressions compare to the "old school" alternative of directly generating IL then it's a lot more read-and-write-able. Perhaps "maintainable" is a better word for it :)
IL generation, unfortunately, still has its place - it's been a while since I looked into this, but I think that if you wanted to generate an entire class, rather than a delegate, then you have to resort to emitting IL.
Debugging compiled expressions can be a mixed bag. If you make mistakes that compile but cause errors at runtime then you may get a helpful error or you may get something fairly cryptic.
The safest approach, I've found, is to construct the code in the smallest functional units you can and to then test it with code that exercises every path in the generated expression. In the example above, this was done by starting with code that simply extracted a single property value from the source argument. Then multiple property values were extracted and passed into a constructor method. Then the delegate signature was changed to take multiple arguments and to use these with the constructor. Then these arguments were changed to the use Optional type and use its "GetValue" method to fall back to the source properties if required. Finally a guard clause was added for a null source reference and a condition added to return the source reference straight back if none of the arguments indicate that a new instance is required. If any of these steps introduced a new error, it should have been relatively easy to work out what went wrong.
To illustrate, if you were adding the code that will "exit early" if no new instance is required, and you forgot to specify a type for the null constant - ie. instead of
Expression.Label(returnTarget, Expression.Constant(null, typeof(RoleDetails)))
you wrote
Expression.Label(returnTarget, Expression.Constant(null))
then you would get an error (if you called the code with arguments that executed the no-new-instance-required code path):
Expression of type 'System.Object' cannot be used for label of type 'Tester.RoleDetails'
I would say that this could be considered half way between helpful and cryptic.. if you realise what it means then it's perfectly sensible, but if you can't see what it's referring to (and it's not like you will get the line number of the incorrect Expression call to help you - you'll just get an exception when "Expression.Block" is executed) then it can appear somewhat incomprehensible.
As I said before, an expression block must have a consistent return type, and the block in the code above should return a RoleDetails instance - but "Expression.Constant(null)" defaults to type System.Object since it is not instructed otherwise. If the code is built and tested step-by-step, then it should be fairly simple to trace the error back to its source.
Another approach for examining the behaviour of expressions is to look at the "Body" property of the lambda expression. This must be done on the return value of "Expression.Lambda", before "Compile" is called. It also requires that the expression be valid. So this will not apply to the above example, where the label is of an incorrect type, since that will result in an exception being thrown when "Expression.Block" is called (since that method does work to ensure that the content described obeys its rules for consistency).
It may be useful, though, in a case where you have an expression that is valid but that does not behave as you expect. If you take the code above and tweaked it a bit by changing
return
Expression.Lambda<RoleDetailsUpdater>(
// .. the rest of the expression generation code still goes here
).Compile();
into
var lambda = Expression.Lambda<RoleDetailsUpdater>(
// .. the rest of the expression generation code still goes here
);
return lambda.Compile();
then you could insert a break point before the return statement and look at the "Body" property of the "lambda" reference. It would have the following value:
.Block() {
.If ($source == null) {
.Throw .Constant<System.ArgumentNullException>(
System.ArgumentNullException: Value cannot be null.Parameter name: source
)
} .Else {
.Default(System.Void)
};
.If (
.Call $title.IndicatesChangeFromValue($source.Title)
|| .Call $startDate.IndicatesChangeFromValue($source.StartDate)
|| .Call $endDateIfAny.IndicatesChangeFromValue($source.EndDateIfAny)
) {
.Return #Label1 { .New Tester.RoleDetails(
.Call $title.GetValue($source.Title),
.Call $startDate.GetValue($source.StartDate),
.Call $endDateIfAny.GetValue($source.EndDateIfAny)) }
} .Else {
.Return #Label1 { $source }
};
.Label
null
.LabelTarget #Label1:
}
This isn't exactly C# but it does illustrate the code paths in a way that is fairly comprehensible and may highlight any logic errors you've made.
At this point, I'd say we've covered a lot of the basic and - hopefully - you're set up to break into the reference material (such as the MSDN docs). Most of the static "Expression" methods are sensibly named and so usually fairly easy to find information for with a little searching (or just relying on intellisense).
If, for example, you had an Expression whose type was an array and you wanted an element from that array, you would use "Expression.ArrayAccess" (whose first parameter is the target Expression and the next is a set of index expression - the number of required index expressions will depend upon the number of dimensions the array has).
Something I particularly remember finding difficult to track an example for was code where you needed local variables within a block. There are examples for accessing arguments and setting lambda return values and altering the values of the arguments, but setting a local variable within a block scope.. not as easy to find.
I may well have been having a bad day when I was struggling with it - once you see how it's implemented, it looks easy! But I thought I'd use it as an excuse for another example. Because I'm still not an expert in writing this sort of code, I prepared this example in Visual Studio in the manner in which I explained above; bit-by-bit, starting with an implementation that returned a constant, then one that returned the hash code of a single property, then extended it to cover all of the variables and then deal with the special cases like a null "source" reference and then ValueType properties and then static properties.
The example I had in mind was a way to generate a method that would calculate a hash code for a given type. As it stands, in isolation, it's not quite a real-world requirement - but hopefully you can conceive of how something not completely dissimilar could be useful. Plus it's a nice size in that it's not quite trivial but not enormous - and it reiterates some of the same techniques seen above.
So.. if this was to be written using just reflection, it could be something like this:
public Func<T, int> GetHashCodeGenerator<T>()
{
// ToArray is called against these properties since the set is going to be enumerated every time
// the returned hash code generator is executed - so it makes sense to do the work to retrieve
// this data only once and then stash it away
var properties = typeof(T).GetProperties()
.Where(p => p.CanRead)
.OrderBy(p => p.Name)
.ToArray();
var firstIndexedProperty = properties.FirstOrDefault(p => p.GetIndexParameters().Any());
if (firstIndexedProperty != null)
{
throw new ArgumentException(string.Format(
"Indexed property encountered, this is not supported: {0}",
firstIndexedProperty.Name
));
}
return source =>
{
if (source == null)
throw new ArgumentNullException("source");
var hashCode = 0;
foreach (var property in properties)
{
// Even if it's a static property, there is no problem executing property.GetValue(source),
// it will return the same value for any instance, but it won't throw an exception
var propertyValue = property.GetValue(source);
var propertyValueHashCode = (propertyValue == null) ? 0 : propertyValue.GetHashCode();
hashCode = 3 * (hashCode ^ propertyValueHashCode);
}
return hashCode;
};
}
This is called (using our faithful RoleDetails example class) in the manner:
// Retrieve a delegate that takes a RoleDetails instance and returns a hash code
var roleDetailsHashCodeGenerator = GetHashCodeGenerator<RoleDetails>();
// Use this delegate to generate some hash codes
var role1HashCode = roleDetailsHashCodeGenerator(role1);
var role2HashCode = roleDetailsHashCodeGenerator(role2);
Note: If you look carefully you'll see something odd - when I call "GetProperties" I use "OrderBy" on the results. This is because I included the code above (which relies on reflection for every call) and the code that I'll get to below (which uses reflection to generate a compiled expression to perform the same work) in the same test program and wanted them to return the same hash code for any given reference. Which doesn't seems unreasonable. But the algorithm requires that the properties be reported in a consistent order if the two implementations of that algorithm are to return matching hash codes. However, the MSDN article for "Type.GetProperties" states that
Your code must not depend on the order in which properties are returned, because that order varies.
So if I was just writing a single version of this method then I probably wouldn't bother with the OrderBy call, but since I wanted to write a LINQ-expressions-based version and a non-expressions-based version and I wanted the two versions to return identical results then I do need to be explicit about the property ordering.
If you're happy with everything covered so far, then the code coming up won't pose any problem.
There are some new Expression methods calls - "Expression.MultiplyAssign" corresponds to the C# statement "x *= y" or "x = x * y" and "Expression.ExclusiveOrAssign" corresponds to "x ^= y" or "x = x ^ y" (the XOR operation).
It's worth being aware that LINQ expressions can be used to define looping constructs - such as a for, foreach or do-while loop - using "Expression.Loop" but you'll have to implement some of the logic of yourself. For a "for" loop, for example, you'll need to declare a local variable that is altered each iteration and then checked against a particular condition each time to determine whether the loop should be exited. For a "foreach" loop, you'll need to call the "GetEnumerator" method on the loop target and use the methods on that to proceed through or exit the loop.
Here, though, I don't need any loops within the expressions. Since I know what properties must be considered when generating the expressions, I'm uneffectively unrolling the loop to generate a set of statements that retrieve a hash code for each property value and then combine them with an accumulator to come up with the final value.
public Func<T, int> GetCompiledHashCodeGenerator<T>()
{
var properties = typeof(T).GetProperties().Where(p => p.CanRead).OrderBy(p => p.Name);
var firstIndexedProperty = properties.FirstOrDefault(p => p.GetIndexParameters().Any());
if (firstIndexedProperty != null)
{
throw new ArgumentException(string.Format(
"Indexed property encountered, this is not supported: {0}",
firstIndexedProperty.Name
));
}
var sourceParameter = Expression.Parameter(typeof(T), "source");
var accumulatorVariable = Expression.Variable(typeof(int), "accumulator");
var blockExpressions = new List<Expression>();
// Check for a null "source" reference (can be skipped entirely if T is a ValueType)
if (!typeof(T).IsValueType)
{
blockExpressions.Add(
Expression.IfThen(
Expression.Equal(sourceParameter, Expression.Constant(null)),
Expression.Throw(Expression.Constant(new ArgumentNullException("source")))
)
);
}
// Calculate a combined hash by starting with zero and then enumerating the properties -
// performing an XOR between the accumulator and the current property value and then
// multiplying before continuing
blockExpressions.Add(
Expression.Assign(accumulatorVariable, Expression.Constant(0))
);
var getHashCodeMethod = typeof(object).GetMethod("GetHashCode");
foreach (var property in properties)
{
// Static properties must specify a null target, otherwise there will be an exception
// thrown at runtime: "Static property requires null instance, non-static property
// requires non-null instance."
var isStaticProperty = property.GetGetMethod().IsStatic;
var propertyValue = Expression.Property(isStaticProperty ? null : sourceParameter, property);
if (property.PropertyType.IsValueType)
{
// If the property is a ValueType then we don't have to worry about calling GetHashCode
// on a null reference..
blockExpressions.Add(
Expression.ExclusiveOrAssign(
accumulatorVariable,
Expression.Call(propertyValue, getHashCodeMethod)
)
);
}
else
{
// .. otherwise we need to check for null and default to a zero hash code if this is the
// case (I picked zero since it's what Nullable<T> returns from its GetHashCode method
// if that Nullable<T> is wrapping a null value).
//
// Proof-reading update: I've just realised that an XOR-assign operation with zero is
// equivalent to no-operation and so we could do nothing if the property value is null.
// But by this point, I've already completed the first draft of the post and done some
// performance comparisons and I'm too lazy to do that all again! Maybe no-one will pick
// up on the algorithm mistake and then also not read this comment. If you *are* reading
// it.. well, hi! :)
blockExpressions.Add(
Expression.IfThenElse(
Expression.Equal(propertyValue, Expression.Constant(null)),
Expression.ExclusiveOrAssign(accumulatorVariable, Expression.Constant(0)),
Expression.ExclusiveOrAssign(
accumulatorVariable,
Expression.Call(propertyValue, getHashCodeMethod)
)
)
);
}
blockExpressions.Add(
Expression.MultiplyAssign(accumulatorVariable, Expression.Constant(3))
);
}
// The last expression in the block indicates the return value, so make it the
// "accumulatorVariable" reference
blockExpressions.Add(accumulatorVariable);
// This Expression.Block method signature takes a set of local variable expressions (in this
// case there's only one; the accumulatorVariable) followed by the expressions that form the
// body of the block
return
Expression.Lambda<Func<T, int>>(
Expression.Block(
new[] { accumulatorVariable },
blockExpressions
),
sourceParameter
).Compile();
}
I wrote this in the way I recommended earlier; in bite-size chunks. Maybe one day I'll be able to just sit down and reel out complex trees of expressions in one fell swoop and instinctively know where any errors I introduce originate.. actually, if I've got a fictional "one day" then I might as well fantasise that I won't make any mistakes that need tracking down in the first place - which will be even better! However, today, I need to break it down and confirm each step.
The first step was to take a source argument, call GetHashCode on it and return that directly - using the builtin "GetHashCode" method on System.Object, rather than implementing the logic myself. The next step was to loop through each property and generate expressions that would retrieve that property's value from the source reference and combine it with a local accumulator variable, returning this accumulator variable's final value at the end of the block. Then I added null checks to the property retrievals, defaulting to a hash code of zero to prevent trying to call GetHashCode on a null reference (zero is consistent with the hash code returned from Nullable<T> when it wraps a null value). Then I realised that this check could be skipped entirely if the property's PropertyType was a value-type, since that could never be null! The logic that dealt with static properties was added next. Finally, an if-null guard clause was added so that an ArgumentNullException would be raised if the source reference is null. Again, I realised that if the source type was a value-type then this was unnecessary - there's no need to check something for null if you know that it never can be null.
Each step was small enough that any problems could easily be traced to their source but each one contributed real functionality.
It was interesting that the expression-generating code lent itself to these "short cuts" in the final code (the don't-check-for-null-if-the-type-is-such-that-it-never-can-be-null short cuts). In the reflection version, we could write something like
if (!typeof(T).IsValueType && (source == null))
throw new ArgumentNullException("source");
but there's no advantage to that over
if (source == null)
throw new ArgumentNullException("source");
In the LINQ expression version, the advantage is that if "T" is a value type then the hash code generation will not include the if-null clause at all!
This is a micro-optimisation, perhaps, especially when we're hoping for much greater saves overall due to avoiding reflection each time our version of GetHashCode is called. And, in a way, it probably is a micro-optimisation, but I would also argue that it's correct and it makes sense to do it regardless of any performance improvement, since it matches the object graph more closely and shows that you've thought about what you're actually doing.
Talking of performance.. the point of this article was to talk about how to write LINQ expressions, it wasn't about when they should be used. But since we now have two implementations of a generic GetHashCode method - one requiring reflection for each call and one using a compiled expression - surely it would be silly not to take it as anecdotal evidence of the potential performance improvements??
Here's the meat of a console app that should illustrate it. To be as accurate as possible, it needs to be built in release configuration and then run several times. Run at the command line (rather than through Visual Studio) to hook in as little debugging jiggery pokery as possible -
var role1 = new RoleDetails("Penguin Cuddler", DateTime.Now, null);
var reflectionBasedHashCodeGenerator = GetHashCodeGenerator<RoleDetails>();
var compiledHashCodeGenerator = GetCompiledHashCodeGenerator<RoleDetails>();
var timerReflection = new Stopwatch();
var timerCompiled = new Stopwatch();
for (var outerLoop = 0; outerLoop < 100; outerLoop++)
{
timerReflection.Start();
for (var innerLoop = 0; innerLoop < 10000; innerLoop++)
reflectionBasedHashCodeGenerator(role1);
timerReflection.Stop();
timerCompiled.Start();
for (var innerLoop = 0; innerLoop < 10000; innerLoop++)
compiledHashCodeGenerator(role1);
timerCompiled.Stop();
}
Console.WriteLine("Total Reflection: " + timerReflection.ElapsedMilliseconds + "ms");
Console.WriteLine("Total Compiled: " + timerCompiled.ElapsedMilliseconds + "ms");
Console.WriteLine(
"Improvement: {0}x",
((double)timerReflection.ElapsedMilliseconds / timerCompiled.ElapsedMilliseconds).ToString("0.00")
);
I ran this three times and got an average 3000ms for the reflection-only approach and 186ms for the compiled-expression version. That's a 16.1x improvement - not bad!
Now, there is a cost to building and compiling these expressions. I would say that if you're not expecting to execute them hundreds of thousands of times, then what's the point of going through the pain of writing the expression-generating code - it would be much easier to just write the reflection-based version. And if you're running it (at least) hundreds of thousands of times, then the overhead of compiling the expressions will be negligible.
But maybe that rationalisation would be a cop-out.
So I changed the above code to consider the time taken to call GetHashCodeGenerator and GetCompiledHashCodeGenerator, such that it contributed to the timerReflection and timerCompiled totals.
With this change, the averages over three runs were now 3008ms and 204ms, giving an average performance multiplier of 14.8 times (where each run performed a million calls per implementation). Still a very respectable performance bump for somewhere that you know it will make a difference (again, why bother with all this hard work if you don't already know that it's worth it - or, rather, if a profiler hasn't shown you that it will be).
A couple of years ago, I wrote a library that basically aimed to be "like AutoMapper but supporting instantiate-by-constructor" (actually, I started it with the intention of it being an extension to AutoMapper to support instantiate-by-constructor - which it can still be used as - but then it took on a bit of a life of its own and became happy to stand on its own two feet). Earlier this year, I updated it to support optional constructor arguments and thought I'd look at how the performance of the library compared to AutoMapper. My library has less functionality than AutoMapper (though it does, of course, have the automated instantiate-by-constructor feature, which AutoMapper does not - the reason I wrote the library!) but by doing less and using compiled expressions for the entire translation, it tackled the example I was using (which was not chosen to try to game the system in any way, incidentally) 100x faster for each translation. Which just goes to show that if you avoid work you don't need to do (like the micro-optimisations above) and speed up the big slow bits (replacing repeated reflection with compiled expressions) you can get serious gains! You can read about it in Reflection and C# optional constructor arguments.. just in case you want to pick holes in my reasoning :)
Posted at 23:07
2 October 2014
A couple of weeks ago, I was talking about a way to structure an "UpdateWith" method that immutable classes in C# could have so that callers can change one or more properties in a single call, resulting in a new instance of the class. Presuming, of course, that the new property values varied from the old values - otherwise the original instance should be returned (there's no point creating a new instance to represent the exact same data when the containing type is an immutable "value"). Feel free to go read Implementing F#-inspired "with" updates for immutable classes in C# if you didn't already!
The really simple way to do something like this is to actually not have an "UpdateWith" method at all and for the calling code to call the constructor directly, but means that there will potentially be a lot places that need fixing if the constructor arguments are changed or re-ordered at any time. Another simple approach is for there to be multiple "Update" methods, one for each property (so you might have an "UpdateName" method, an "UpdateStartDate"; a distinct "Update{whatever}" for each individual property).
I was feeling oh so proud of myself for thinking to combine a multiple-parameter "Update" method with an "Optional" struct so that the best of every world could be had - a single call could update one or more properties without having to specify values for properties that are not to be updated. Unlike with the "Update{whatever}" methods, if two properties need to be updated, only a single new instance will be required - there will not be new instances for each separate property update - so there would be no added GC pressure from unnecessary "intermediate" instances.
To illustrate -
public class RoleDetails
{
public RoleDetails(string title, DateTime startDate, DateTime? endDateIfAny)
{
Title = title;
StartDate = startDate;
EndDateIfAny = endDateIfAny;
}
public string Title { get; private set; }
public DateTime StartDate { get; private set; }
public DateTime? EndDateIfAny { get; private set; }
public RoleDetails UpdateWith(
Optional<string> title = new Optional<string>(),
Optional<DateTime> startDate = new Optional<DateTime>(),
Optional<DateTime?> endDateIfAny = new Optional<DateTime?>())
{
if (!title.IndicatesChangeFromValue(Title)
&& !startDate.IndicatesChangeFromValue(StartDate)
&& !endDateIfAny.IndicatesChangeFromValue(EndDateIfAny))
return this;
return new RoleDetails(
title.GetValue(Title),
startDate.GetValue(StartDate),
endDateIfAny.GetValue(EndDateIfAny)
);
}
}
The Optional struct looked like this:
public struct Optional<T>
{
private T _valueIfSet;
private bool _valueHasBeenSet;
public T GetValue(T valueIfNoneSet)
{
return _valueHasBeenSet ? _valueIfSet : valueIfNoneSet;
}
public bool IndicatesChangeFromValue(T value)
{
if (!_valueHasBeenSet)
return false;
if ((value == null) && (_valueIfSet == null))
return false;
else if ((value == null) || (_valueIfSet == null))
return true;
return !value.Equals(_valueIfSet);
}
public static implicit operator Optional<T>(T value)
{
return new Optional<T>
{
_valueIfSet = value,
_valueHasBeenSet = true
};
}
}
I then went on a bit of a wild tangent and thought "if pretty much all of these UpdateWith methods are going to look the same and be boring to write, could I have some magic code generate it for me on the fly?" - this led me to write a small library that allows the following:
public RoleDetails UpdateWith(
Optional<string> title = new Optional<string>(),
Optional<DateTime> startDate = new Optional<DateTime>(),
Optional<DateTime?> endDateIfAny = new Optional<DateTime?>())
{
return DefaultUpdateWithHelper.GetGenerator<RoleDetails>()(this, title, startDate);
}
I got a variety of feedback on the post. One of the really interesting things to find was that the main idea itself was already in real-world use, in Microsoft's Roslyn .net compiler, for example. The file ProjectInfo.cs has a "With" method that follows a very similar structure with a corresponding Optional.cs struct that is also very similar to what I'd written. I found this very encouraging.. even if it did steal the thunder from "my" idea!
More of the feedback related to performance concerns regarding the "DefaultUpdateWithHelper.GetGenerator" method. It returns a delegate to create a new instance, based upon the provided arguments. This delegate is a compiled LINQ Expression, cached against the target type and the provided argument structure. The problem was that some reflection was required in order to determine whether there was a compiled expression in the cache that could be re-used, so each call to "GetGenerator" carried that reflection overhead. The question was just how much..
But before I go into that, one of the constructive comments was that I wasn't generating a hash code on my cache key type correctly. The cache key contained the information about the target type, along with the number of arguments and their types. The function to produce a combined hash for this information was
public int GetHashCode(CacheKeyData obj)
{
if (obj == null)
throw new ArgumentNullException("obj");
var hash = obj.DeclaringType.GetHashCode() ^ obj.TargetType.GetHashCode();
for (var index = 0; index < obj.NumberOfUpdateParameters; index++)
hash = hash ^ obj.GetUpdateParameter(index).GetHashCode();
return hash;
}
This goes through each aspect of the cache key data and performs XOR operations to get a combined result. It was pointed out by Strilanc on Reddit that it's better practice to multiple by a prime number after every XOR. This way, if there are two references that report the same hash code then they won't cancel each other out.
The reason that I'd used XOR without thinking about it too much was that I knew that XOR on two ints could never cause an overflow and so seemed like a safe easy option. But, in C#, this isn't something we normally have to worry about - for example
// Trying to set "var i0 = int.MaxValue + 1;" will result in a compile error
// "The operation overflows at compile time in checked mode"
// but performing in two steps will not
var i0 = int.MaxValue;
var i1 = i0 + 1;
does not result in an overflow exception. Instead, it wraps around (so i1 will be equal to int.MinValue). In order to "opt in" to overflow exceptions being raised for theses sorts of operations, the "checked" keyword needs to be used (or there's a "checked" compiler option that does the same).
So we can safely change the implementation to
public int GetHashCode(CacheKeyData obj)
{
if (obj == null)
throw new ArgumentNullException("obj");
var hash = obj.DeclaringType.GetHashCode() ^ obj.TargetType.GetHashCode();
for (var index = 0; index < obj.NumberOfUpdateParameters; index++)
hash = (3 * hash) ^ obj.GetUpdateParameter(index).GetHashCode();
return hash;
}
There was also a comment left on my blog
.. your usage of the object.Equals() method also creates garbage..
which I had to think about to understand what was meant. When I realised, I kicked myself that I'd missed it! In the Optional struct there's the method
public bool IndicatesChangeFromValue(T value)
{
if (!_valueHasBeenSet)
return false;
if ((value == null) && (_valueIfSet == null))
return false;
else if ((value == null) || (_valueIfSet == null))
return true;
return !value.Equals(_valueIfSet);
}
That final call has to resort to
public virtual bool Equals(object obj);
on the base Object type since the compiler has no other choice that could apply to any "T". But if "T" is not a reference type then it has to be boxed in order to access it as an Object (which is necessary to access this lowest-common-denominator "Equals" method).
A better solution is to check whether "obj" implements IEquatable<T>. Microsoft recommends that structs implement this interface (see the article Struct Design on MSDN) and the primitive types such System.Int32 (aka int) all follow this suggestion.
So the boxing can be avoided in most cases by changing the method to
public bool IndicatesChangeFromValue(T value)
{
if (!_valueHasBeenSet)
return false;
if ((value != null) && (value is IEquatable<T>))
return !((IEquatable<T>)value).Equals(value);
if ((value == null) && (_valueIfSet == null))
return false;
else if ((value == null) || (_valueIfSet == null))
return true;
return !value.Equals(_valueIfSet);
}
I'm chalking up these two recommendations as even more evidence that code reviewing can be helpful.. :)
Having addressed the above improvements, the question about how the code actually performs still remains.
There are three candidates to consider when weighing up the automagical DefaultUpdateWithHelper. The first two appear above. One is the hand-written version shown in the RoleDetails class right at the top of the post. The other is the one-liner "GetGenerator" call. There is a third option, however, that allows multiple calls to avoid the cache-check and so avoid reflection entirely on all but the first request; that is to call "GetGenerator" once and record it in a static reference -
private static UpdateWithSignature<RoleDetails> updater
= DefaultUpdateWithHelper.GetGenerator<RoleDetails>(typeof(RoleDetails).GetMethod("UpdateWith"));
public RoleDetails UpdateWith(
Optional<string> title = new Optional<string>(),
Optional<DateTime> startDate = new Optional<DateTime>(),
Optional<DateTime?> endDateIfAny = new Optional<DateTime?>())
{
return updater(this, title, startDate);
}
To get an idea of the raw performance of these methods, I wrote a console app that would repeatedly call a variation of an "UpdateWith" method. I've named the three varieties that I'm interested in: "ManualWith" (the hand-written version), "SimpleWith" (the one-liner) and "StaticWith" (shown above; the one-liner where the result is stored in a static reference to avoid multiple calls to "GetGenerator").
Having a console app meant that the process would be started fresh and then torn down for each run, hopefully ensuring an even playing field. This is particularly in relation to GC, which can introduce variance into longer-running processes. In this case, I'm interested in the direct execution performance of the various methods and I'm not trying to compare GC overhead (which is something that can be investigated, but which can be very complicated to do correctly).
The source code for this app can be found at gist.github.com/anonymous/31b752d24212ad43836e. It's as simple as possible and must be run in Release configuration in order to provide the most realistic results. I ran it multiple times for each of the variations, running a complete set of each before repeating (just to try to give everything the best odds of averaging out as possible).
For "ManualWith", the loop count had to be ten million to get any sensible measurements. The average time per execution was 1.0 ticks (an average of 3538ms for 10,000,000 calls).
For "SimpleWith", the loop count had to be 100,000. The average per execution was 81.7 ticks (averaging 2997ms for 100,00 calls).
"StaticWith" needed the loop count bumping back up to ten million again - averaging 2.1 ticks per execution (7874ms average for 10,000,000 calls).
Now, actually, I don't think that's too bad (the "StaticWith" result, I mean). If something's a real convenience and the only overhead it introduces is that object instantiation is twice as slow, I think that in most cases it could be considered a win - the reality is that instantiating objects is not likely to be a bottleneck where performance becomes a concern*. The reason for the performance difference between "ManualWith" and "StaticWith" is going to be from the boxing of the Optional values when they are passed to the delegate, combined with the fact that the arguments are passed to the "updater" as a params array; ie. an object[] - which must be instantiated. My original post talked about more tweaks that the library allowed to specify the number of arguments and so not require the object array, but it would still have to box the Optional values.
* (Insert comment here about profiling before assigning blame for performance and another about how exchanging convenience for performance only works if any performance cost is offset by having said convenience).
So.. all things considered, do I genuinely expect to use one of the "magic" approaches in my code going forward? Well, no. I will be using the format of the "UpdateWith" method and utilising the Optional struct in the method signature, but I probably won't bother with the DefaultUpdateWithHelper and the library I wrote. It was fun to write and I learnt a lot doing it and through the feedback on it, but I still have a niggly feeling about the worry that changes to the constructor (in a refactor, or whatever) will not cause compile-time errors in the "UpdateWith" method if I forget to update that as well. I won't find out until runtime that there's a problem (or until the unit tests, that I suggested last time as one of the trade-offs for the convenience, are executed). And I'm a big fan of helping the compiler to help me.
Plus there's the fact that the difference in code size between the "StaticWith" code and the "ManualWith" isn't really that large. Even as more properties are added, it's still very scannable and doesn't bloat up too much even though you have to write the code for each property's "IndicatesChangeFromValue" check and manually pass the "GetValue" result for each constructor argument. Looking at that Roslyn code doesn't make me think that the methods (written in the "ManualWith" manner) are too big, and some of them have a lot of constructor arguments.
If only there was some way to get the best of both worlds; brevity in type definitions but all the benefits of static analysis..
This was another thing that came from the comments on my blog (thanks Ian Yates! :), a library of templates that take a simple definition such as
class Fruit
{
string color;
int skinThickness;
}
and transforms it into a fully-fledged immutable class with a "With" method (which is exactly like the "UpdateWith" method I've been talking about). It has its own Optional struct, the same as in Roslyn's source. The generated types even have a nested Builder type which has mutable properties and a "ToImmutable" method which returns an immutable type with the described data - for times when it's just easier to prepare a reference in a few steps before "freezing" it (or for "efficient multi-step mutation", according to the README). It's little indications of attention to detail such as this that I liked when I looked into the project: github.com/AArnott/ImmutableObjectGraph.
The idea of constructing T4 templates like this is one that I've kicked around before but never gotten round to actually implementing, so finding this was a nice surprise!
Now, there are a few flies in the ointment. The library relies on a pre-release version of Microsoft's Immutable Collections, and references to the binary's location are hard-coded into the template files. Also, the template files currently need to be copied into every project that you want to use them with. There's no NuGet package to make it easy to pull into a project - and if you try to pull down the code from GitHub using "Download Zip" then it refuses to compile (though cloning it in GitHub for Windows works fine). It assumes that all generated types should support a "DefaultInstance" (which I disagree with since it's basically too close to another version of null - an instance that has not been given any information to represent real information.. for a list type, this may make sense - the empty list - but not for types such as the RoleDetails I've been using as an example so far).
But hopefully this is where the wonders of open source will come to the fore! I've submitted a pull request to try to encourage the templates into a NuGet package (putting the impetus on the consumer to include a version of the Immutable Collections, if required). You can find it at Generate a NuGet package (and prevent the templates being copied into each consuming project). However, there is another pull request that has been open for some time (since April) which I think has merit and which I have tested myself, that has been acknowledged by the author but not merged: Fixing compiler warnings with collections and inheritance. I don't know why it hasn't been merged. Considering that one of the decisions in my request may be contentious (pulling "CollectionHelper" methods into the generated types that require them, in order to prevent the imported binary requiring an Immutable Collection reference), I'm not sure how confident I am at the moment that it will be accepted.
Further changes to address my other concerns could be made as well - such as an attribute that could be added to indicate that a default instance should not be defined. Depending upon how the pull request is received, I might submit more or I might go rogue and maintain my own fork. As I understand the "MS-PL" license, I'm fairly sure this is allowed (though I'd be much happier to end up with everything merged into one beautiful definitive version).
The really big question that I want to answer, though, is whether the use of the templates will mesh well with code contracts. The generated types do specify "partial class" and so can be extended - they could implement an interface, for example, which has contracts specified on it. And the classes call an optional "Validate" method, which could be used to verify the constructor arguments. I'm not sure yet if this will all be capable of what I have in mind, I've only had a very preliminary look into it.. but I think it has promise!
Just imagine: the brevity of the type declarations above, the guarantees of contracts (though this will necessarily affect the succinctness of the code - even if a separate "contract interface" is implemented, the contract for that interface must still be written somewhere), the static analysis benefits for the generated types.. all this goodness in one solution! So maybe I don't actually have all the pieces together just yet.. but I'm certainly going to be trying to get them over the next few weeks and carrying it all onward to programming nirvana!
Posted at 21:49
Dan is a big geek who likes making stuff with computers! He can be quite outspoken so clearly needs a blog :)
In the last few minutes he seems to have taken to referring to himself in the third person. He's quite enjoying it.