Greg Beech's Tech Blog

Function currying in C#

Greg Beech — Tue, 16 Sep 2008 07:36:50 GMT

C# does not automatically curry functions, so a function that multiplies two doubles together and returns the result must be assigned to a delegate that takes two arguments and returns a result:

Func<double, double, double> multiply = (a, b) => a * b;

This seems reasonable, but unfortunately it means that if we want to define a partial application of the function where one argument is already supplied (for example we might want to create a function that calculates the circumference of a circle from its diameter by supplying Math.PI) then we can't do it directly. Attempting to write the following statement gives the compiler error "Delegate 'Func' does not take '1' arguments":

var circumferenceFromDiameter = multiply(Math.PI);      // hopefully type Func<double, double>

What we actually want to achieve is a function that takes a double and returns a function that takes another double and returns the result of the two multiplied together. It is possible to write this in C#, but you have to change the function declaration from the intuitive 'two arguments goes to one result' syntax to somewhat harder to grasp nested lambda expression syntax. This is shown below with annotated type information so you can see what's going on (although I actually think the type information is more of a distraction than a help).

Func<double, Func<double, double>> multiply = a => b => a * b;
var circumferenceFromDiameter = multiply(Math.PI);      // type Func<double, double>
var circumference = circumferenceFromDiameter(10.0);    // type double

What would be useful are some methods for the Func<> class that could perform the currying for us, and fortunately as it's a mechanical translation these are quite easy to write. Shown below are extension methods for the 2, 3 and 4 argument versions of Func<>; there isn't one for the single argument version as this is already in curried form.

public static class Func
{
    public static Func<T1, Func<T2, TResult>> Curry<T1, T2, TResult>(
        this Func<T1, T2, TResult> func)
    {
        return arg1 => arg2 => func(arg1, arg2);
    }

    public static Func<T1, Func<T2, Func<T3, TResult>>> Curry<T1, T2, T3, TResult>(
        this Func<T1, T2, T3, TResult> func)
    {
        return arg1 => arg2 => arg3 => func(arg1, arg2, arg3);
    }

    public static Func<T1, Func<T2, Func<T3, Func<T4, TResult>>>> Curry<T1, T2, T3, T4, TResult>(
        this Func<T1, T2, T3, T4, TResult> func)
    {
        return arg1 => arg2 => arg3 => arg4 => func(arg1, arg2, arg3, arg4);
    }
}

We can now write the initial multiply expression as we'd prefer, and still be able to partially apply the function. It does take an extra line because you can't directly apply the extension method to the lambda expression without specifying that it is typed as a Func<>, and to do that in a single line results in a lot of ugly casting syntax.

Func<double, double, double> multiply = (a, b) => a * b;
var multiplyBy = multiply.Curry();                      // type Func<double, Func<double, double>>
var circumferenceFromDiameter = multiplyBy(Math.PI);    // type Func<double, double>
var circumference = circumferenceFromDiameter(10.0);    // type double

Note that this approach doesn't just facilitate writing local lambda expressions in a simpler way, it also allows you to partially apply library methods that you don't have control over the signature of by assigning them to an appropriate Func<> and then currying it. It's not ideal because you have to add syntactic noise to do the currying manually, but it's better than not being able to do it at all.

Just for fun, here's all you have to do to get the above scenario working in F#. We don't need to manually curry the methods as it is done automatically. There's also a lot less syntactic noise because F# doesn't require you to declare the concrete type of lambda expressions; it performs type checking based on what parameter type they take and what they return which makes a lot more sense than the C# approach - if you've ever come across the Predicate<T> != Func<T, bool> paradox then you'll know what I mean.

let multiply (a:double) b = a * b                   // type double -> double -> double
let circumferenceFromDiameter = multiply Math.PI    // type double -> double
let circumference = circumferenceFromDiameter 10.0

Images wrong or missing in blog posts

Greg Beech — Tue, 09 Sep 2008 00:17:48 GMT

Recently I've been using more images to illustrate blog posts, and unfortunately have run into an issue with Windows Live Writer and Community Server 2008. The full details are in that forum, including a workaround and a fix, but essentially if the image is pasted from the clipboard without saving it to disk first Writer generates file names that overlap, and Community Server uses the same folder for all images, so images from old blog posts get randomly overwritten.

Fortunately I managed to recover all of the image files from the post history so have been able to fix up all the posts on-site (I think - if you see any that are wrong please let me know) but I have a feeling that anyone subscribing to the RSS feed will still have broken or wrong image links. I've also patched my server so hopefully won't have any more problems in the future.

Sorry for any confusion or inconvenience this may have caused.

Determining the bias of a shuffle algorithm

Greg Beech — Mon, 08 Sep 2008 23:17:59 GMT

Last time I wrote Shuffle and TakeRandom extension methods for IEnumerable<T> which use the Fisher-Yates algorithm to perform an unbiased shuffle of a sequence and take a random subset from it. In order to optimise the performance of the TakeRandom method I had to reverse the documented implementation of the shuffle so it produced the results at the start of the sequence rather than the end, and thus allow it to be short-circuited once enough values had been randomised.

It all looks fine in theory, but as even simple algorithms are notoriously hard to implement correctly I wouldn't have been happy publishing it without testing to ensure that (a) the shuffle works, and (b) it really is unbiased.

One way to determine the bias is to shuffle integer sequences and then add the values at corresponding indexes, giving the total value at each index. If the shuffle is unbiased then each value should appear at each index an equal number of times, and so the total value calculated for each index should be the same. If we compute the percentage relative standard deviation (%RSD) of the totals, a value of zero indicates an unbiased algorithm and any non-zero value indicates biased one, with larger values being more biased.

Below are a couple of extension methods to compute the standard deviation and relative standard deviation for sequences of integers. It's impressive how terse the syntax is to do this with the Linq extensions; however, it is frustrating that in C# there is no way to create them as open generic methods and indicate that they apply to anything that can have mathematical operations performed on it, so if you want versions of these that work with sequences of float you have to cut-and-paste the implementations and replace the int keyword.

public static class Enumerable
{
    public static double StandardDeviation(this IEnumerable<int> values)
    {
        return StandardDeviationInternal(values, values.Average());
    }

    public static double RelativeStandardDeviation(this IEnumerable<int> values)
    {
        var average = values.Average();
        var standardDeviation = StandardDeviationInternal(values, average);
        return (standardDeviation * 100.0) / average;
    }

    private static double StandardDeviationInternal(IEnumerable<int> values, double average)
    {
        return Math.Sqrt(values.Select(value => Math.Pow(value - average, 2.0)).Average());
    }
}

To compute the %RSD we need to consider the effect that the randomness has on the distribution of the values. With a low number of sequences shuffled there may be a uneven distribution of randomness leading to invalid results, however as the number of sequences shuffled increases the randomness should be more evenly distributed and cancel itself out (assuming an unbiased random number generator). From this we can see that as the number of sequences shuffled approaches infinity, the calculated %RSD approaches the correct answer.

Unfortunately we haven't got time to shuffle an infinite number of sequences, so my test application makes do with shuffling a logarithmic range from 100 to 100,000,000 sequences of the numbers 1..10, printing the results to the console (and yes, I know I could have used a for loop):

class Program
{
    static void Main()
    {
        ShuffleTest(100);
        ShuffleTest(1000);
        ShuffleTest(10000);
        ShuffleTest(100000);
        ShuffleTest(1000000);
        ShuffleTest(10000000);
        ShuffleTest(100000000);
        Console.ReadLine();
    }

    private static void ShuffleTest(int iterations)
    {
        var totals = new int[10];
        var generator = System.Linq.Enumerable.Range(1, 10);
        for (var iteration = 0; iteration < iterations; iteration++)
        {
            var index = 0;
            foreach (var value in generator.Shuffle())
            {
                totals[index] += value;
                index++;
            }
        }

        Console.WriteLine("{0,-9} iterations => {1:0.000} %RSD", iterations, totals.RelativeStandardDeviation());
    }
}

Plotting the results in Excel shows that as the number of iterations increases the %RSD does approach zero; by one hundred million iterations the measured %RSD is only 0.005. Note that if the %RSD scale is also plotted as logarithmic the trend-line is straight, but I think most people find the non-logarithmic scale easier to understand at a glance. We can therefore say with confidence that the shuffle implementation from the previous entry is completely unbiased.

If you want to compare this against a biased algorithm then shown below is a common mistake people make when implementing the Fisher-Yates shuffle, where the random range is computed from 0 rather than n:

private static IEnumerable<T> ShuffleInternal<T>(T[] array, int count)
{
    // this algorithm has a mistake in the random.Next call: 0 should be n
    for (var n = 0; n < count; n++)
    {
        var k = random.Next(0, array.Length);
        var temp = array[n];
        array[n] = array[k];
        array[k] = temp;
    }

    return array;
}

Plotting the results on the same chart as the correctly implemented algorithm shows that this one approaches a value of approximately 3.17 %RSD and so is proven to be biased:

This isn't the only approach to prove that a shuffle algorithm implementation is unbiased, but it is quick to implement and run, and gives a high level of confidence in the results. You can, and should, test any other shuffle algorithm you implement in a similar manner.

Shuffle and TakeRandom extension methods for IEnumerable

Greg Beech — Wed, 03 Sep 2008 00:13:08 GMT

It's a fairly common practice on web sites to display sets of randomly ordered items, whether it's a selection of your friends, items related to the one you're looking at, or even something as simple as a tag cloud. Sometimes the entire set of items is randomised, and sometimes you want to take a random selection from the set and display that (the latter is typically done so you can cache a larger set of data and then take items from it without going to the database again).

The System.Linq.Enumerable class provides a lot of methods to process collections, but it appears that randomisation is beyond its remit. As such I wrote a couple of extension methods to shuffle a collection and take a random selection from it, which use the Fisher-Yates algorithm to give an unbiased shuffle in O(n) time.

public static class Enumerable
{
    private static readonly Random random = new Random();

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
    {
        // Durstenfeld implementation of the Fisher-Yates algorithm for an O(n) unbiased shuffle
        var array = source.ToArray();
        var n = array.Length;
        while (n > 1)
        {
            var k = random.Next(n);
            n--;
            var temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }

        return array;
    }

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> source, int count)
    {
        return source.Shuffle().Take(count);
    }
}

These work perfectly well, but unfortunately the TakeRandom method isn't as efficient as it could be because the Shuffle method always shuffles the entire list even though we're only interested in the first count elements. This implementation of the algorithm can't be stopped to retrieve the first elements as it constructs the result at the end of the array, and although we could use the existing Reverse extension method to work around this it would be somewhat inefficient.

Instead, we can rewrite the algorithm in reverse so that it constructs the result at the start, and then stop it after count iterations to retrieve the part-shuffled sequence. To illustrate I'll use the same stepwise walk-through as Wikipedia, but with every random 'roll' swapped (1 -> 8, 2 -> 7, 3 -> 6, etc.) because we're working from the opposite end:

Range	Roll	Result \| Scratch
		\| 1 2 3 4 5 6 7 8
1 - 8	3	3 \| 2 1 4 5 6 7 8
2 - 8	7	3 7 \| 1 4 5 6 2 8
3 - 8	3	3 7 1 \| 4 5 6 2 8
4 - 8	8	3 7 1 8 \| 5 6 2 4
5 - 8	6	3 7 1 8 6 \| 5 2 4
6 - 8	6	3 7 1 8 6 5 \| 2 4
7 - 8	8	3 7 1 8 6 5 4 \| 2

Looking at the result, if we substitute each digit using the same mechanism as for the rolls (1 -> 8, 2 -> 7, etc.) it becomes 62813457 which is the reverse of the Wikipedia example's result of 75431826, indicating that this approach produces equivalent, unbiased results. The reversed algorithm can be trivially implemented as a for loop in a private function and then consumed by both the public Shuffle and TakeRandom methods.

public static class Enumerable
{
    private static readonly Random random = new Random();

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
    {
        var array = source.ToArray();
        return ShuffleInternal(array, array.Length);
    }

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> source, int count)
    {
        var array = source.ToArray();
        return ShuffleInternal(array, Math.Min(count, array.Length)).Take(count);
    }

    private static IEnumerable<T> ShuffleInternal<T>(T[] array, int count)
    {
        // Durstenfeld implementation of the Fisher-Yates algorithm for an O(n) unbiased shuffle
        // starts from the beginning rather than the end so we can just shuffle the first count
        for (var n = 0; n < count; n++)
        {
            var k = random.Next(n, array.Length);
            var temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }

        return array;
    }
}

So there you have it - a pair of fast and unbiased methods to shuffle a sequence, or take a random subset of elements from it. You'll notice that unlike most Linq methods they do not use deferred execution; this is because methods using deferred execution should be re-entrant and due to their random nature these are not.

Finally I should point out that if you're doing anything that requires completely unpredictable shuffling (e.g. a deck of cards in a casino application) you need to replace the random number generator with a cryptographically strong one such as the .NET RandomNumberGenerator.

Optimised IP address to country code mapping

Greg Beech — Mon, 01 Sep 2008 19:52:48 GMT

One of the things that web sites tend to do frequently is look up the country a user is from based on their IP address, for example to direct them to the appropriate site for their country or to restrict content that cannot be legally shown to them. There are numerous solutions to perform this mapping such as calling third-party web services or looking up the country from a database, but as it is such a commonly used function it is worthy of being optimised into an in-memory data structure.

This is potentially tricky to build as IP addresses are organised in ranges with allocated country codes (about 92000 at the current time) but there are approximately two billion possible values for the IP address itself, so to handle the mapping with reasonable memory usage we need to be able to efficiently map an individual IP address to a range without storing all of the IP addresses in the data structure.

Initial research on the net shows that a commonly used structure for IP address routing is the Patricia trie, and I also found a number of articles about it being used for IP address to country code mapping. Unfortunately the code for the all the articles I found were either released under, or appeared to be derived from code which is released under, the dreaded GPL license which means that it's too risky to even download it to take a look. The only other implementations I could find were from academia (read: incomprehensible ANSI C) which meant I'd be writing the trie myself from scratch.

Fast-forward a day and a half, and I've got a working IP address lookup table based on a binary Patricia trie, which supports the basic functions of adding IP address ranges and finding the range that an IP address is associated with. An optimisation I added was that instead of using one trie to hold all the nodes, I used a sparse array of 256 lazily created tries with each one corresponding to the first byte of the IPv4 address; as most of the first byte values are distinct on each bit this allows a single byte comparison rather than walking eight nodes.

The performance is pretty good. On my 2.1MHz Intel Core2 Duo machine, the trie takes around 0.8 seconds to build and can perform ten million lookups in 8.2 seconds (or around 1.2 million lookups per second).

However, there is a price to pay for this. The code is complex. It's difficult to ascertain that the code is bug-free without doing an exhaustive search of all IP addresses, and it would be difficult to come back to the code and perform any maintenance work even with the large amount of commenting. Although it was fun to investigate the structure, I'd prefer to have something simpler in our production codebase even if it does sacrifice a bit of efficiency.

Enter binary search.

For any sorted list of values a binary search executes in O(lg N) time, and if it doesn't find an exact match the .NET implementation returns the bitwise complement of the next largest result. This means that if the values being searched are the start IP addresses in the range, that the index of the appropriate range can be returned by taking the value (if found) or the bitwise complement minus one (if not found) of the result for the candidate IP address. If we used a single list then we'd expect around lg 92000 = 17 comparisons per search, however if we keep the idea of using 256 lists we can bring this down to around lg (92000/256) = 9 comparisons plus one to find the correct root.

This is a much simpler data structure to build, and within about half an hour I had a working version for comparison of performance. The results were as follows, loading 92000 entries from a flat file and then performing ten million lookups of various addresses:

Yes, you are reading that right. The simple multiple sorted list structure using binary search turned out to be nearly twice as fast for lookups as the complex multiple Patricia trie one, managing around 2.1 million lookups per second. It was also faster to load, although this is slightly unfair as the data was already sorted when loaded so this result would be different if it was being loaded from unsorted data as that would affect the lists but not the tries.

Thinking about it, it isn't hard to see why this result was achieved. The nodes in the Patricia trie are necessarily implemented as classes so they can have references to each other which means that traversing the tree involves following object references around the heap, and both the building of the tree and the lookups require bit-shifting and masking operations as well as integer comparisons. By contrast the entries in the sorted lists can be structures meaning that each list is using contiguous memory, and although more comparisons are required they are simple integer ones without any bit-shifting and as such only take a single clock cycle to execute.

In terms of memory usage the binary search solution will also be better due to its entries being structures and thus having no object header, and not needing pointers to their left and right children.

Unfortunately I can't release the code for the lookup table as I wrote it during work time, but to write your own lookup table using sorted lists and binary search only takes about fifty lines and half an hour, and it will comprehensively outperform an implementation using Patricia tries which takes hundreds of lines and many hours to implement .

Disposing and finalizing partially constructed objects

Greg Beech — Wed, 27 Aug 2008 22:44:43 GMT

On MSDN forums there was a question about whether class constructors should be permitted to do a lot of work or not:

I have a dilemma and a dispute with some colleagues: should the constructor of a C# class do a lot or the minimum and latter in a method call put a lot of logic?

I am coming from a C++ background and there it is better to do just simple data initialization in the constructor, throwing an exception from a constructor is bad since the object is not fully constructed yet.

Does the same argument work in C#?

Should I do the minimum work in the constructor?

My colleagues' position is that having a minimal constructor will leave the state of the object as not fully defined and then changed by a subsequent call to another method.

The two main factors to whether a constructor should do a significant amount of work are whether it should leave the class in a state ready to be used for real work if possible, and whether it matters if the constructor throws an exception and leaves the instance in a partially constructed state. I think we can all agree that it is much more intuitive to construct an object and have it ready for use than to construct it and have to call some sort of Initialize method afterwards, so lets assume that the real issue is with resource clean-up of partially constructed objects.

Rather than offer opinion here, I wrote a simple program to demonstrate disposal and finalization of a partially constructed object.

class Program
{
    static unsafe void Main(string[] args)
    {
        Foo foo = null;
        try
        {
            foo = new Foo();
        }
        catch (Exception ex)
        {
            Console.WriteLine("{0} occurred constructing Foo", ex.GetType());
        } 
        
        try
        {
            foo.Dispose();
        }
        catch (Exception ex)
        {
            Console.WriteLine("{0} occurred disposing Foo", ex.GetType());
        } 

        GC.Collect();
        GC.WaitForPendingFinalizers();
    }
}

class Foo : IDisposable
{
    public Foo()
    {
        throw new Exception();
    }

    ~Foo()
    {
        Console.WriteLine("Foo finalizer called");
    }

    public void Dispose()
    {
        Console.WriteLine("Foo dispose called");
    }
}

The output from this program is:

System.Exception occurred constructing Foo
System.NullReferenceException occurred disposing Foo
Foo finalizer called

From this we can ascertain that if the object is not constructed correctly then the reference to the object will not be assigned, which means that no methods can be called on it, so the Dispose method cannot be used to deterministically clean up managed resources. The implication here is that if the constructor creates expensive managed resources which need to be cleaned up at the earliest opportunity then it should do so in an exception handler within the constructor as it will not get another chance.

We can also ascertain that the finalizer will be called on the object even if the constructor throws an exception. This is possible because, unlike C++, CLR objects do not start as their base type and then morph into derived types as they are constructed but start out as the type they will end up as so the garbage collector knows what type the object is and where the finalizer is in the method table. As such, the presence of a finalizer does not affect whether you should throw exceptions from a constructor because as long as you write the finalizer code defensively to only clean up unmanaged resources that have been allocated (which you should be doing anyway) then it will work fine whether the object was fully constructed or not.

And, of course, there is the final scenario in which the constructor neither allocates expensive managed resources, nor any unmanaged resources, so it doesn't matter whether you throw an exception because the partially constructed instance will just be cleaned up by the garbage collector.

In summary, do as much work as needed to get the object in a usable state in the constructor, but clean up any expensive managed resources you allocate in an exception handler if you can't complete it successfully.

Computers don't care whether your resources are directly addressable

Greg Beech — Sun, 24 Aug 2008 16:16:58 GMT

The article Roots of the REST/SOAP Debate (along with many others like it) claims that SOAP web services have a limitation in that resources they work with are not directly addressable via a URI, but that you have to connect to the SOAP endpoint and then call a method on it. The analogy used is as follows:

Let me offer an analogy. Suppose you were living temporarily in a hotel. The hotel might not have direct dial connections from the outside. In order to call a room you have to contact the operator first (this is like contacting the "SOAP endpoint") and then ask them to connect you to your room.

This is simply incorrect. Saying that you need to contact the operator first and then connect them to the room implies that to make a call to a SOAP service you have to first connect to the service endpoint itself, and then send a message to it which performs an operation. When you're writing code that uses web service proxies then it may appear this way because you first create the proxy and then call a method on it, but this doesn't reflect what actually happens on the wire.

When you create the proxy nothing at all is sent on the wire, it simply constructs a local object that knows where to send requests to (you do not need an instance of a proxy as it could also be done with static methods where you pass the service URI in each time; the proxy instance is typically used for convenience if you're making multiple method calls). When you call the method on the proxy, then a single message is sent to the service URI which interprets it using the designated method, and sends a response. From an HTTP perspective, this is exactly the same mode of operation as REST-style services.

The analogy continues:

Now imagine that there is an outside service that you would like to buy. It is a once-a-day automated wake-up call and horoscope service. You try to sign up for the service but when you are asked to enter the phone number to call back you realize that there is no single number you can provide. The service must contact the operator first and then the operator must patch them through to you. Obviously the computer on the other end is not going to be smart enough to know to go through the operator and the operator will not know to patch the call through to your room.

So lets say that the person in the analogy does provide them with a direct phone number, and the service is ready to call them back with a horoscope. Assuming both parties speak English then the service might say "Hello, your horoscope is..." or it might say "Good morning, today you will be..." and the person would understand either because we intelligently interpret the response. However computers do not do this because they are not sentient; they need a well defined response representation and will not understand the horoscope unless they already know what it is. The article does allude to this fact later...

If two HTTP services can agree on an information representation (for instance RSS (the Rich Site Summary) or SAML (Security Assertions Markup Language) then those two services can communicate about these information resources merely by passing URIs to resources.

...but it forgets to include the point that if two HTTP services have agreed on the information representation of the response, then they could also easily agree on the representation of the request. This means that as long as the service knows how to call the phone number you pass then it doesn't matter whether it needs a payload, which means it doesn't matter whether it is a directly-addressable REST-style URI or a SOAP web service URI. The problem is not the protocol itself; the problem is a lack of universal data type definitions.

I know what you're thinking at this point - that it's simpler just to use a REST-style URI than a SOAP web service for the callback as you don't need a payload. And you're right. But lets explore the last quote a little further and talk about retrieving RSS feeds. If I told you that the RSS feed for this blog was at http://gregbeech.com/blogs/tech/rss.aspx then you'd find it easy to get the latest posts, but if I told you that this URI is capable of restricting posts to date ranges then what URI would you use to only retrieve posts in the first half of 2007? And would you extend the URI in the same way on an RSS feed that wasn't generated by Community Server?

Exactly.

As soon as you want to do anything other than call a static URI on a REST-style service, you need to know how to construct and extend the URI to return the right data. And if it's a complex service you may also need to pass an XML payload containing the data (this is particularly common for PUT commands). Just because a service uses REST-style URIs does not mean that it can be easily used by any other service, irrespective of whether it understands the response format.

So if REST-style services are no different in their on-wire interaction to SOAP services, and are no more interoperable than SOAP services, where does the argument come from that they are preferable because of their directly-addressable URIs? Well, people care what the URIs are so they can type them and see where they link to before they click them, and they don't want to have to create a payload because it's inconvenient. A service client, however, does not care what the actual URIs are as long as it has been told how to build them (which means it does not care whether resource is directly-addressed using a REST-style URI or whether it is indirectly addressed using a SOAP service) and similarly has no issue with creating a payload as it has no concept of convenience.

All of which means that any preference for REST-style services over SOAP services on the basis of them being directly addressable or "more like the web" is based on a flawed anthropomorphism of a service client. So lets drop this pointless facet of the SOAP vs REST argument once and for all, OK?

Emitting primitive type conversions with Reflection.Emit

Greg Beech — Wed, 20 Aug 2008 21:34:39 GMT

Conversion between primitive types is trivial in high-level languages like C# as you can use the cast operator, optionally surrounded with checked or unchecked to force the integer overflow semantics. At CIL level the conversion is less trivial, involving the choice of no fewer than 27 different op-codes, which are required to be used in combination with each other under some circumstances.

This is yet another place where extension methods are incredibly useful, because rather than having to remember all this it is possible to capture the information about how to convert between two types in a method and expose it alongside the low-level ones on the ILGenerator class. The extension method to do this is below (note that IsUnsignedInteger is an extension method for the Type class which returns whether the type is one of byte, ushort, uint or ulong).

public static void EmitConv(this ILGenerator il, Type fromType, Type toType, bool ovf)
{
    if (fromType == toType)
    {
        // no conversion required
    }
    else if (toType == typeof(float) || toType == typeof(double))
    {
        // if converting to a floating point number then we must use a conv.* instruction as there are no ovf
        // checked operations that work with them. if the starting point is an unsigned integer then we must
        // convert it to a real first as conv.r4 and conv.r8 don't work with unsigned integers (at IL level
        // the char data type is considered to be a 2-byte unsigned integer)
        if (fromType.IsUnsignedInteger() || fromType == typeof(char))
        {
            il.Emit(OpCodes.Conv_R_Un);
        }

        EmitConv(il, toType);
    }
    else if (ovf)
    {
        // overflow checking required so use conv.ovf.* or conv.ovf.*.un depending on the source type
        if (fromType.IsUnsignedInteger() || fromType == typeof(char))
        {
            EmitConv_Ovf_Un(il, toType);
        }
        else
        {
            EmitConv_Ovf(il, toType);
        }
    }
    else
    {
        // no overflow checking so use the conv.* instruction
        EmitConv(il, toType);
    }
}

Not many of the 27 instructions present there; just one to handle the special case of converting unsigned integers to reals. The real heavy lifting is done by the three other Emit* methods, which all use dictionary lookups in the same way as my post about emitting arbitrary constants. I doubt there's any point in putting more text at the bottom of the post, so I'll say now that this code has been tested by over 350 unit tests which cover every possible type conversion, using both in-range and out-of-range values for both checked and unchecked variants.

Here are the lookup dictionaries:

private static readonly IDictionary<Type, Action<ILGenerator>> emitConvMethods = 
    new Dictionary<Type, Action<ILGenerator>>
        {
            { typeof(sbyte), il => il.Emit(OpCodes.Conv_I1) },
            { typeof(byte), il => il.Emit(OpCodes.Conv_U1) },
            { typeof(short), il => il.Emit(OpCodes.Conv_I2) },
            { typeof(ushort), il => il.Emit(OpCodes.Conv_U2) },
            { typeof(int), il => il.Emit(OpCodes.Conv_I4) },
            { typeof(uint), il => il.Emit(OpCodes.Conv_U4) },
            { typeof(long), il => il.Emit(OpCodes.Conv_I8) },
            { typeof(ulong), il => il.Emit(OpCodes.Conv_U8) },
            { typeof(float), il => il.Emit(OpCodes.Conv_R4) },
            { typeof(double), il => il.Emit(OpCodes.Conv_R8) },
            { typeof(char), il => il.Emit(OpCodes.Conv_U2) },
        };

private static readonly IDictionary<Type, Action<ILGenerator>> emitConvOvfMethods = 
    new Dictionary<Type, Action<ILGenerator>>
        {
            { typeof(sbyte), il => il.Emit(OpCodes.Conv_Ovf_I1) },
            { typeof(byte), il => il.Emit(OpCodes.Conv_Ovf_U1) },
            { typeof(short), il => il.Emit(OpCodes.Conv_Ovf_I2) },
            { typeof(ushort), il => il.Emit(OpCodes.Conv_Ovf_U2) },
            { typeof(int), il => il.Emit(OpCodes.Conv_Ovf_I4) },
            { typeof(uint), il => il.Emit(OpCodes.Conv_Ovf_U4) },
            { typeof(long), il => il.Emit(OpCodes.Conv_Ovf_I8) },
            { typeof(ulong), il => il.Emit(OpCodes.Conv_Ovf_U8) },
            { typeof(char), il => il.Emit(OpCodes.Conv_Ovf_U2) },
        };

private static readonly IDictionary<Type, Action<ILGenerator>> emitConvOvfUnMethods = 
    new Dictionary<Type, Action<ILGenerator>>
        {
            { typeof(sbyte), il => il.Emit(OpCodes.Conv_Ovf_I1_Un) },
            { typeof(byte), il => il.Emit(OpCodes.Conv_Ovf_U1_Un) },
            { typeof(short), il => il.Emit(OpCodes.Conv_Ovf_I2_Un) },
            { typeof(ushort), il => il.Emit(OpCodes.Conv_Ovf_U2_Un) },
            { typeof(int), il => il.Emit(OpCodes.Conv_Ovf_I4_Un) },
            { typeof(uint), il => il.Emit(OpCodes.Conv_Ovf_U4_Un) },
            { typeof(long), il => il.Emit(OpCodes.Conv_Ovf_I8_Un) },
            { typeof(ulong), il => il.Emit(OpCodes.Conv_Ovf_U8_Un) },
            { typeof(char), il => il.Emit(OpCodes.Conv_Ovf_U2_Un) },
        };

And here are the methods that make use of them:

private static void EmitConv(ILGenerator il, Type toType)
{
    if (emitConvMethods.ContainsKey(toType))
    {
        var emitConv = emitConvMethods[toType];
        emitConv(il);
    }
    else
    {
        throw new NotSupportedException("A conv.* op-code cannot be emitted for " + toType + ".");
    }
}

private static void EmitConv_Ovf(ILGenerator il, Type toType)
{
    if (emitConvOvfMethods.ContainsKey(toType))
    {
        var emitConvOvf = emitConvOvfMethods[toType];
        emitConvOvf(il);
    }
    else
    {
        throw new NotSupportedException("A conv.ovf.* op-code cannot be emitted for " + toType + ".");
    }
}

private static void EmitConv_Ovf_Un(ILGenerator il, Type toType)
{
    if (emitConvOvfUnMethods.ContainsKey(toType))
    {
        var emitConvOvfUn = emitConvOvfUnMethods[toType];
        emitConvOvfUn(il);
    }
    else
    {
        throw new NotSupportedException("A conv.ovf.*.un op-code cannot be emitted for " + toType + ".");
    }
}

Code without comments is code that doesn't work

Greg Beech — Mon, 04 Aug 2008 19:58:52 GMT

The other week Jeff Atwood posted a blog entry named Coding Without Comments that stated... well I'm actually not sure. It started by making the valid point that comments should indicate why your code works the way it does and shouldn't be needed to explain what it does, but then went entirely off track and ended up pretty much stating that all comments are detrimental to code quality (emphasis Jeff's):

While comments are neither inherently good or bad, they are frequently used as a crutch. You should always write your code as if comments didn't exist. This forces you to write your code in the simplest, plainest, most self-documenting way you can humanly come up with.

The example used in the blog post was refactoring some code that calculated a square root using the Newton-Raphson approximation to make it more clear how it worked. Which is all very useful. But the problem is that there are a lot of different ways to calculate a square root which make trade-offs in terms of speed, accuracy, memory usage and simplicity, and by the end of the post we still didn't know why the Newton-Raphson method was chosen in the first place because there were no comments with that information. And I really doubt this is something you want to encode in the method name:

var sqrt = NewtonRaphsonApproximationBecauseItConvergesQuicklyWithAGoodInitialGuess(n);

Clearly the claim that you should write code as if comments didn't exist is a fallacy because they are necessary to explain why you wrote it that way (or, indeed, why you didn't write it another way). But what about my claim that code without comments doesn't even work? This is down to the probability that code without any comments hasn't been used in the real world.

When you start writing code, you write it to meet a specification, using the available documentation for any APIs you're calling, and it all looks right. Everything has been code reviewed by at least one other person, you've added argument checking and assertions about your current state to every method, and run plenty of unit and system tests against it, so you know that when it goes into production everything will work perfectly.

Except it doesn't.

One example at blinkBox is the frame-grabbing code which uses DirectShow to grab a frame and then loads the resultant byte array into a Bitmap class. This worked perfectly during testing, and then suddenly in the live environment we kept getting an error with one particular file where the Bitmap constructor claimed the bytes were invalid. Just to see what the bits looked like if we could load them into the image I tried using LockBits and an unsafe memory copy into the bitmap's memory area; the result was a skewed black-and-white image. Noticing that the stride of the image was not native-pointer aligned and many APIs prefer aligned data, my colleague Jon and I set about padding the data to an aligned stride and then trying to use that as the image data. The constructor still wouldn't accept it, but using the unsafe memory copy and then trimming the width to the original size produced a perfect image. I still don't know why the data is invalid, or why this hack works, but we've found that for about 1 in 500 source files we need it.

There's simply no way that you could predict this, or even find it without huge quantities of test data, and putting that sort of hack in the exception handling block without a comment explaining the empirical reasoning behind it and the fact that it may not be perfect as we don't even know why it really works would be reproachable. I think the comment came out at around 20 lines, including ASCII art.

As our codebase matures, there are more and more parts of it that have long comments explaining why things are implemented the way they are, what alternatives were considered and discounted, what circumstances were observed in the live environment that cause this edge case or that edge case or the other edge case, and why the code looks wrong but needs to be that way. Some particularly tortuous parts have significantly more comments than code itself.

Code without this type of comment is code that has never been hardened by real-world use; code that has never hit the 0.1% edge cases; code that simply doesn't work properly. I'm sure Jeff will find this out once he's had StackOverflow up and running for a few months.

Tips & Tricks: Use DebuggerDisplayAttribute for easier debugging

Greg Beech — Mon, 28 Jul 2008 20:44:29 GMT

When debugging, it's common to hover over an object to get a quick view of what its properties are. With a single object this is fine because you can easily expand it to view its contents, but when you have a collection of objects it's painful to see the contents as you have to expand every element. The typical view in the debugger of a collection of simple movie classes is like this:

public class Movie
{
    public int Id { get; set; }
    public string Title { get; set; }
    public float Rating { get; set; }
}

This is where DebuggerDisplayAttribute comes in; by applying it to our Movie class the collection hover can be made much more informative. The format string looks similar to normal .NET format strings in that the values to replace are between curly braces, but instead of being told what to substitute the debugger treats these values as expressions and attempts to evaluate them using the current context. Here we simply list the properties of the object:

[DebuggerDisplay("Id = {Id}, Title = {Title}, Rating = {Rating}")]
public class Movie
{
    public int Id { get; set; }
    public string Title { get; set; }
    public float Rating { get; set; }
}

Where this gets really interesting, however, is that with the C# debugger you can enter much more powerful expressions to evaluate than just the property names. If we didn't want to have really long titles listed in full (because "The assassination of Jesse James by the coward Robert Ford" might scroll off all but the widest of monitors) we could truncate them to 20 characters and show an ellipsis to indicate the truncation:

[DebuggerDisplay(
    "Id = {Id}, " +
    "Title = {Title.Substring(0, System.Math.Min(Title.Length, 20)) + (Title.Length > 20 ? \"…\" : \"\")}, " +
    "Rating = {Rating}")]
public class Movie
{
    public int Id { get; set; }
    public string Title { get; set; }
    public float Rating { get; set; }
}

There is a down-side to this power though - because evaluation of the DebuggerDisplayAttribute format string is compiler-specific, the first example will work fine most other debuggers such as VB, but the second one will not evaluate due to its use of the C#-specific ternary operator. Depending on the debugger this will cause it to display either the default value of the class name, or an error indicating which part of the syntax could not be evaluated; this may be important if you work in a multi-language environment, or if you ship your classes as a library to customers.

Dynamic sorting and paging in SQL Server with the CASE expression

Greg Beech — Mon, 21 Jul 2008 22:04:21 GMT

The normal use for the CASE expression in T-SQL is to perform simple modifications to one of the columns in a SELECT statement; the type of example given in MSDN show it being used to expand state abbreviations such as 'CA' to 'California', or to categorise products into 'Cheap' and 'Expensive' depending on their price. However, the CASE expression is a lot more flexible than that, and can be used to implement dynamic sorting and paging without dynamic SQL.

Taking the classic Northwind database, here is a query that can retrieve pages of customers, sorted by either contact name, company name or country, ordered either ascending or descending:

DECLARE @SortType TINYINT, @SortAscending BIT, @FirstRow INT, @MaxRows INT;
SELECT @SortType = 1, @SortAscending = 1, @FirstRow = 10, @MaxRows = 10;

WITH FoundCustomers AS
(
    SELECT
        ROW_NUMBER() OVER
        (
            ORDER BY CASE @SortType
                WHEN 0 THEN c.ContactName
                WHEN 1 THEN c.CompanyName
                WHEN 2 THEN c.Country
            END ASC
        ) AS RowNumberAsc
        ,ROW_NUMBER() OVER
        (
            ORDER BY CASE @SortType
                WHEN 0 THEN c.ContactName
                WHEN 1 THEN c.CompanyName
                WHEN 2 THEN c.Country
            END DESC
        ) AS RowNumberDesc
        ,c.*
    FROM
        dbo.Customers c
)
SELECT
    fc.*
FROM
    FoundCustomers fc
WHERE
    CASE @SortAscending
        WHEN 1 THEN fc.RowNumberAsc
        WHEN 0 THEN fc.RowNumberDesc
    END
    BETWEEN @FirstRow AND @FirstRow + @MaxRows - 1
ORDER BY
    CASE @SortAscending 
        WHEN 1 THEN fc.RowNumberAsc 
        WHEN 0 THEN fc.RowNumberDesc 
    END;

Although this is an elegant solution, it does have some issues with performance; this particular query takes approximately twice as long as a statement hard-coded to use a given sort type and order. Looking at the execution plan shows the main cost in the query is the sorting (on my machine it is around 70% of the cost of the hard-coded query) and that even though RowNumberDesc is never used the sort orders are still computed for it, which is where the extra time is going.

In pursuit of performance, we're going to have to repeat most of the statement by breaking the query into separate ascending and descending ones. This isn't so good for maintenance, but as performance is critical in most databases the additional overhead of the combined query is the worse of two evils.

DECLARE @SortType TINYINT, @SortAscending BIT, @FirstRow INT, @MaxRows INT;
SELECT @SortType = 2, @SortAscending = 1, @FirstRow = 10, @MaxRows = 10;

IF @SortAscending = 1
BEGIN
    WITH FoundCustomers AS
    (
        SELECT
            ROW_NUMBER() OVER
            (
                ORDER BY CASE @SortType
                    WHEN 0 THEN c.ContactName
                    WHEN 1 THEN c.CompanyName
                    WHEN 2 THEN c.Country
                END ASC
            ) AS RowNumber
            ,c.*
        FROM
            dbo.Customers c
    )
    SELECT
        fc.*
    FROM
        FoundCustomers fc
    WHERE
        fc.RowNumber BETWEEN @FirstRow AND @FirstRow + @MaxRows - 1
    ORDER BY
        fc.RowNumber;
END
ELSE
BEGIN
    WITH FoundCustomers AS
    (
        SELECT
            ROW_NUMBER() OVER
            (
                ORDER BY CASE @SortType
                    WHEN 0 THEN c.ContactName
                    WHEN 1 THEN c.CompanyName
                    WHEN 2 THEN c.Country
                END DESC
            ) AS RowNumber
            ,c.*
        FROM
            dbo.Customers c
    )
    SELECT
        fc.*
    FROM
        FoundCustomers fc
    WHERE
        fc.RowNumber BETWEEN @FirstRow AND @FirstRow + @MaxRows - 1
    ORDER BY
        fc.RowNumber;
END;

Examining the execution plan for this query shows that it is almost exactly the same as the query hard-coded to a particular sort type and order, with the addition of a Compute Scalar step before the sort. This additional step takes less than 0.001% of the query time, so is a perfectly acceptable addition. We can infer from this that SQL Server can optimise a statement ordered by a CASE expression equally as well as one ordered by a hard-coded column.

The typical approach for dynamic sorting and paging that I've seen in the past has used dynamic SQL with sp_executesql to achieve the results. By using the CASE expression instead you can make your stored procedures verifiable at design time which aids database refactoring immensely, and achieve the same performance as hard-coded queries.

Update: 28 July 08

It turns out you actually don't have to split the query into two to get optimal performance; my colleague Jason was playing around with this some more and came up with a combined query using multiple searched CASE expressions rather than the a single simple CASE expression as shown above. Amazingly this is actually legal syntax, and gives the same optimal execution plan as the simple form:

DECLARE @SortType TINYINT, @SortAscending BIT, @FirstRow INT, @MaxRows INT;
SELECT @SortType = 2, @SortAscending = 0, @FirstRow = 10, @MaxRows = 10;

WITH FoundCustomers AS
(
    SELECT
        ROW_NUMBER() OVER
        (
            ORDER BY 
                CASE WHEN @SortType = 0 AND @SortAscending = 1 THEN c.ContactName END ASC
                ,CASE WHEN @SortType = 0 AND @SortAscending = 0 THEN c.ContactName END DESC
                ,CASE WHEN @SortType = 1 AND @SortAscending = 1 THEN c.CompanyName END ASC
                ,CASE WHEN @SortType = 1 AND @SortAscending = 0 THEN c.CompanyName END DESC
                ,CASE WHEN @SortType = 2 AND @SortAscending = 1 THEN c.Country END ASC
                ,CASE WHEN @SortType = 2 AND @SortAscending = 0 THEN c.Country END DESC
        ) AS RowNumber
        ,c.*
    FROM
        dbo.Customers c
)
SELECT
    fc.*
FROM
    FoundCustomers fc
WHERE
    fc.RowNumber BETWEEN @FirstRow AND @FirstRow + @MaxRows - 1
ORDER BY
    fc.RowNumber;

Emitting arbitrary constants with Reflection.Emit

Greg Beech — Sun, 20 Jul 2008 22:51:57 GMT

I've been writing a fair bit of Reflection.Emit code recently, and along the way have developed quite a number of extension methods for the ILGenerator class to handle the complex semantics of some seemingly trivial operations, and choose the most efficient op-codes (e.g. when can the short forms be used). I had already written EmitLdc methods to handle constant values for every type that can be represented as constant, but then came across the slightly odd circumstance where I had values that I knew could be emitted as constants, but they were in the form of a boxed System.Object instance so couldn't directly bind to the correct method.

The obvious solution is to add a new EmitLdc overload that takes a plain object as an argument and performs manual casting and dispatch to the correct overload at runtime. Unfortunately as C# doesn't allow types to be used in switch statements, and doesn't support pattern matching, there's no trivial way to do this except with a very large if/else statement or heavily nested ternary operators. These are both a bit inefficient and look clumsy, so a better option is with a static dictionary of EmitLdc methods keyed by type.

Fortunately C# 3.0 introduced object initializers and lamda expressions which allow this dictionary to be built in a very concise and declarative manner:

private static readonly IDictionary<Type, Action<ILGenerator, object>> emitLdcMethods = 
    new Dictionary<Type, Action<ILGenerator, object>>
        {
            { typeof(bool), (il, val) => il.EmitLdc((bool)val) },
            { typeof(sbyte), (il, val) => il.EmitLdc((sbyte)val) },
            { typeof(byte), (il, val) => il.EmitLdc((byte)val) },
            { typeof(short), (il, val) => il.EmitLdc((short)val) },
            { typeof(ushort), (il, val) => il.EmitLdc((ushort)val) },
            { typeof(int), (il, val) => il.EmitLdc((int)val) },
            { typeof(uint), (il, val) => il.EmitLdc((uint)val) },
            { typeof(long), (il, val) => il.EmitLdc((long)val) },
            { typeof(ulong), (il, val) => il.EmitLdc((ulong)val) },
            { typeof(float), (il, val) => il.EmitLdc((float)val) },
            { typeof(double), (il, val) => il.EmitLdc((double)val) },
            { typeof(char), (il, val) => il.EmitLdc((char)val) },
            { typeof(decimal), (il, val) => il.EmitLdc((decimal)val) }
        };

The method can then be written to perform a key lookup from the dictionary based on the type of the value being emitted, and fail otherwise.

public static void EmitLdc(this ILGenerator il, object value)
{
    var valueType = value.GetType();
    if (emitLdcMethods.ContainsKey(valueType))
    {
        var emitLdc = emitLdcMethods[valueType];
        emitLdc(il, value);
    }
    else if (valueType.IsEnum)
    {
        EmitLdc(il, (Enum)value);
    }
    else
    {
        throw new NotSupportedException("The value cannot be emitted as a constant.");
    }
}

The eagle-eyed will notice that there's a special case for enumerated types, because these can be emitted as constants (being based on a CLR primitive type) but retrieving the type of an Enum object will give the enumeration type, not the underlying type or System.Enum, so won't work with the dictionary approach. The EmitLdc method for enums simply uses Enum.GetUnderlyingType and then uses the same lookup dictionary with that type.

Service-orientation is inevitable for performant database applications

Greg Beech — Wed, 16 Jul 2008 22:05:31 GMT

Databases cause two performance problems for applications. Firstly they are difficult to scale out compared to other server roles which means they can easily become the scalability bottleneck, and secondly they are on a remote machine which means that each query made to them involves network latency. To reduce processing overhead and latency, a common approach is to make as few queries as possible, and to only return as much data as is strictly needed for any query, meaning that fewer joins are likely in the database and the network payload is smaller.

The object-oriented approach to reducing payload size is lazy-loading, where only the most frequently used properties of objects are retrieved in the query, and properties that are thought to be less frequently used are loaded on-demand when they are accessed. Lets take a concrete example. Say you are modelling a movie with information such as the title, thumbnail, and actors you might model this in the object-oriented world as a Movie class with Title, Thumbnail and Actors properties. If you find that most of the time you only need to display the title and thumbnail but not the actors, then you might decide to lazy-load the Actors property to remove the join in the database to the table of actors and reduce the network payload.

But what happens when you have a view of movies that needs to display the actors for each movie in the list? It's not a commonly used view so you want to keep the actors lazily loaded (as always populating them would make the general case less efficient) but it's not so infrequently used that poor performance can be ignored.

Without breaking encapsulation the only possible solution is that each movie in the list makes an independent call to the database to retrieve its actors, so you cause multiple database accesses in a relatively inefficient way (databases are optimised for processing data in sets so single rows are typically not much quicker than a small set) and add significant network latency too. To reduce the latency you could use a parallel loop, but even then you haven't alleviated any of the database overhead which is the thing we're most concerned about.

If you have collections of objects that have lazily loaded properties, you have to break encapsulation to improve performance.

We could break encapsulation only as far as the collection and say that movies have a specialised collection type and that they are aware of the collections they are contained in, so when a movie is asked to load its actors it requests the collection to load the actors for all the movies as a bulk operation. This means that the movie has to keep track of which collections it is in using callbacks from the add/insert/remove operations, and that you are restricted to specific types of collection which precludes the use of things like Linq-to-Objects. Breaking encapsulation in this way isn't an attractive option.

The next level at which we could break encapsulation is to create a static method on the Movie class that accepts a sequence of movies and populates the actors on each of them. We now aren't restricted to specific collection types, and the population of the actor properties can be done in a single efficient batch operation, but this is no longer transparent to the user as they have to call a method to have the properties populated. Moreover, because the properties exist on the class this is somewhat unintuitive as you don't expect to have to pass an object to a method to have its properties populated, so it probably makes more sense to remove the Actors property from the Movie object and have the method that does the bulk retrieval return a dictionary of actors by movie.

Unfortunately when it comes to testing this static method to retrieve the actors, we find that it isn't very test-friendly as it can't be stubbed or mocked, so there always has to be a database with suitable test data behind it. Instead of a static method, then, we'll move it off the Movie class and make it an instance method on a MovieService class which is retrieved in an indirect way (such as from a service container) to enable stubbing and/or mocking. We've now got a highly performant and testable solution, but to achieve this we had to remove any direct relationship between movies and actors.

This scenario can be applied to any lazily loaded property on any type of object which can exist in collections, which leads us to the inescapable conclusion that lazy loading simply isn't a reasonable option in most cases, thus objects must always be returned as a whole. As such, objects must not have a direct relationship with any other object that does not form part of that whole. Any properties that would have been lazily loaded are now separate objects, and retrieved in bulk by services as and when needed. The domain model has been transformed into a set of state objects with no direct relationship which are passed between services; it has been transformed into messages.

By optimising the performance of our object-oriented model, we arrived at a service-oriented message-passing architecture.

You may not like it. You may say that this isn't the easiest model to program against. You may say it reduces the discoverability of related items and functionality. And I'm not going to argue with you on any of those points. But take consolation in the fact that it was inevitable from the start.

Object-Relational Mapping frameworks won't improve your timescales

Greg Beech — Thu, 10 Jul 2008 22:52:30 GMT

On every database-backed project I've worked on, which is quite a few ranging from 4 to over 50 developers, the number of people working on the database is relatively small. Typically in a three-tier application the ratio of developers on UI:services:data is around 5:2:1 because high quality user interface development requires a lot of work, and it is far more time consuming to display data in an attractive way than it is to retrieve or save it. At blinkBox the ratio is even higher at about 8:2:1.

This means that even if you assume that the services/data teams spend all their time writing data access code, and you could improve the productivity there, you still won't save a huge amount of development time because your main overhead is in the user interface team, and the data access method doesn't affect them too much (or shouldn't if you've designed your API properly).

In reality services/data don't spend all their time writing data access code or stored procedures. I've spent all of the last year leading our services team and working closely with the data team. As a rough estimate, I reckon I spend about 5% of my time writing data access code and the rest on thinking through scenarios, designing and creating higher level APIs, tuning caching, implementing security, implementing logging, adding performance counters, and troubleshooting issues that have nothing to do with data access because we use a very thin layer on top of SqlClient which has no surprising side effects. The database guys probably spend about 20% of their time writing stored procedures, and the rest on schema refactoring (which is only possible due to the stored procedure layer), data migration, reporting, performance optimisation, and asynchronous data publishing

Which means that even if you reduce all the time spent on data access code time to zero, you could only save about (0.25 * 0.05) + (0.13 * 0.20) = 0.038 = 3.8% of your overall development time, which really isn't significant enough to worry about. You'll lose more time than that from hangovers due to office parties.

Any improvement in productivity in data access code will have a negligible effect on the timescales of a project, so don't buy into Object-Relational Mapping frameworks on the premise that they will save you time, because even if they could the time just isn't there to save.

Emitting decimal pseudo-constants with Reflection.Emit

Greg Beech — Mon, 07 Jul 2008 00:14:29 GMT

Some languages such as C# let you treat the System.Decimal type as an integral type most of the time, even having the keyword decimal, and will let you declare constant fields of the type under some circumstances. However, decimal isn't a primitive type in the same way as the other numerics, and is implemented quite differently from them. At CIL level, you can't actually declare a constant decimal in the normal way; you have to create an initonly field marked with DecimalConstantAttribute which is understood by the CLR.

The logic shown here is optimised to emit decimal constants declared within a method body, however the logic at the bottom of the method could also be used for the constructor of DecimalConstantAttribute. It's interesting to note that the C# 3.0 compiler does not special-case any of the static fields in the same way as this method does, which may be because there's such minimal performance difference that it isn't really worth the added complexity.

Other EmitLdc method calls within this are additional extension methods I implemented to cover other primitive data types, which do things such as special-casing the loading of the i4 type for the built-in constant values, and performing unchecked casting to emit unsigned values. If anyone wants me to post the code for them then I'm happy to do so, but they really are quite trivial.

public static void EmitLdc(this ILGenerator il, decimal value)
{
    const BindingFlags FieldFlags = BindingFlags.Public | BindingFlags.Static;
    if (value == decimal.Zero)
    {
        il.Emit(OpCodes.Ldsfld, typeof(decimal).GetField("Zero", FieldFlags));
    }
    else if (value == decimal.One)
    {
        il.Emit(OpCodes.Ldsfld, typeof(decimal).GetField("One", FieldFlags));
    }
    else if (value == decimal.MinusOne)
    {
        il.Emit(OpCodes.Ldsfld, typeof(decimal).GetField("MinusOne", FieldFlags));
    }
    else if (value == decimal.MinValue)
    {
        il.Emit(OpCodes.Ldsfld, typeof(decimal).GetField("MinValue", FieldFlags));
    }
    else if (value == decimal.MaxValue)
    {
        il.Emit(OpCodes.Ldsfld, typeof(decimal).GetField("MaxValue", FieldFlags));
    }
    else if (Math.Round(value) == value && value >= long.MinValue && value <= long.MaxValue)
    {
        // if the decimal is a whole number then we can optimise the construction by pushing the smallest
        // acceptable integer type value onto the stack and using the appropriate constructor
        if (value >= int.MinValue && value <= int.MaxValue)
        {
            EmitLdc(il, (int)value);
            il.Emit(OpCodes.Newobj, typeof(decimal).GetConstructor(new[] { typeof(int) }));
        }
        else
        {
            EmitLdc(il, (long)value);
            il.Emit(OpCodes.Newobj, typeof(decimal).GetConstructor(new[] { typeof(long) }));
        }
    }
    else
    {
        // the Decimal.GetBits method returns four integers, the first three of which are the lo/med/hi parts 
        // of the decimal and the fourth which is structured as follows:
        // -------------------------------------------------------------------------------------------------
        // |31|30|29|28|27|26|25|24|23|22|21|20|19|18|17|16|15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00|                     
        // |ns|      not used      |         scale         |                   not used                    |
        // -------------------------------------------------------------------------------------------------
        // where ns is the negative sign (1 indicates negative) and the scale is a value between 1 and 28

        var parts = Decimal.GetBits(value);
        Debug.Assert(parts.Length == 4, "Expected the Decimal.GetBits method to return 4 parts");
        var negative = ((parts[3] >> 31) & 1) == 1;
        var scale = (parts[3] >> 16) & 0xFF;

        EmitLdc(il, parts[0]);
        EmitLdc(il, parts[1]);
        EmitLdc(il, parts[2]);
        EmitLdc(il, negative);
        EmitLdc(il, scale);
        il.Emit(OpCodes.Newobj, typeof(decimal).GetConstructor(
            new[] { typeof(int), typeof(int), typeof(int), typeof(bool), typeof(byte) }));
    }
}

There are optimisations that could be made here to make the emit code itself faster, namely caching the decimal constructors in static fields so we don't have to use reflection to find them each time. We could also set up a Dictionary<decimal, Action> containing the Ldsfld emit functions so there is only one specific-value check needed rather than five (which is essentially what a switch statement would do, but because a decimal isn't a real constant C# won't allow a switch statement based on it). For the sake of readability though, I've shown the code in a single method.