Jon Skeet: Coding Blog : CSharpDevCenter

Migrating from Visual Studio 2010 beta 1 to beta 2 – solution file change required

skeet — Mon, 26 Oct 2009 10:46:36 GMT

Having installed Visual Studio 2010 beta 2 on my freshly-reinstalled netbook (now with Windows 7 and and SSD – yummy) I found that my solution file from Visual Studio 2010 beta 1 wasn’t recognised properly: double-clicking on the file didn’t do anything. Opening the solution file manually was absolutely fine, but slightly less convenient than being able to double-click.

After a bit of investigation, I’ve found the solution. Manually edit the solution file, and change the first few lines from this:

Microsoft Visual Studio Solution File, Format Version 11.00
# Visual Studio 10

to this:

Microsoft Visual Studio Solution File, Format Version 11.00
# Visual Studio 2010

It's just a case of changing "10" to "2010".

Hopefully between this and the linked SuperUser post, this should avoid others feeling the same level of bafflement :)

For vs Foreach on arrays and lists

skeet — Thu, 29 Jan 2009 23:08:02 GMT

As promised earlier in the week, here are the results of benchmarking for and foreach.

For each of int and double, I created an array and a List<T>, filled it with random data (the same for the list as the array) and ran each of the following ways of summing the collection:

A simple for loop, testing the index against the array length / list count each time
A for loop with an initial variable remembering the length of the array, then comparing the index against the variable each time
A foreach loop against the collection with the type known at compile and JIT time
A foreach loop against the collection as IEnumerable<T>
Enumerable.Sum

I won't show the complete code in this post, but it's you can download it and then build it against the benchmarking framework. Here's a taste of what it looks like - the code for a list instead of an array, and double instead of int is pretty similar:

List<int> intList = Enumerable.Range(0, Size)
                              .Select(x => rng.Next(100))
                              .ToList();
int[] intArray = intList.ToArray();

var intArraySuite = TestSuite.Create("int[]", intArray, intArray.Sum())
    .Add(input => { int sum = 0;
        for (int i = 0; i < input.Length; i++) sum += input;
        return sum;
    }, "For")
    .Add(input => { int sum = 0; int length = input.Length;
        for (int i = 0; i < length; i++) sum += input;
        return sum;
    }, "ForHoistLength")
    .Add(input => { int sum = 0;
        foreach (int d in input) sum += d;
        return sum;
    }, "ForEach")
    .Add(IEnumerableForEach)
    .Add(Enumerable.Sum, "Enumerable.Sum")
    .RunTests();

...

static int IEnumerableForEach(IEnumerable<int> input)
{
    int sum = 0;
    foreach (int d in input)
    {
        sum += d;
    }
    return sum;
}

(I don't normally format code quite like that, and wouldn't even use a lambda for that sort of code - but it shows everything quite compactly for the sake of blogging.)

Before I present the results, a little explanation:

I considered int and double entirely separately - so I'm not comparing the int[] results against the double[] results for example.
I considered array and list results together - so I am comparing iterating over an int[] with iterating over a List<int>.
The result for each test is a normalized score, where 1.0 means "the best of the int summers" or "the best of the double summers" and other scores for that type of summation show how much slower that test ran (i.e. a score of 2.0 would mean it was twice as slow - it got through half as many iterations).
I'm not currently writing out the number of iterations each one completes - that might be interesting to see how much faster it is to sum ints than doubles.

Happy with that? Here are the results...

-------------------- Doubles --------------------
============ double[] ============
For                 1.00
ForHoistLength      1.00
ForEach             1.00
IEnumerableForEach 11.47
Enumerable.Sum     11.57

============ List<double> ============
For                 1.99
ForHoistLength      1.44
ForEach             3.19
IEnumerableForEach 18.78
Enumerable.Sum     18.61

-------------------- Ints --------------------
============ int[] ============
For                 1.00
ForHoistLength      2.03
ForEach             1.36
IEnumerableForEach 15.22
Enumerable.Sum     15.73

============ List<int> ============
For                 2.82
ForHoistLength      3.49
ForEach             4.78
IEnumerableForEach 25.71
Enumerable.Sum     26.03

I found the results interesting to say the least. Observations:

When summing a double[] any of the obvious ways are good.
When summing an int[] there's a slight benefit to using a for loop, but don't try to optimise it yourself - I believe the JIT recognizes the for loop pattern and removes array bounds checking, but not when the length is hoisted. Note the lack of difference when summing doubles - I suspect that this is because the iteration part is more significant when summing ints because integer addition is blindingly fast. This is important - adding integers is about as little work as you're liikely to do in a loop; if you're doing any real work (even as trivial as adding two doubles together) the difference between for and foreach is negligible
Our IEnumerableForEach method has pretty much the same performance as Enumerable.Sum - which isn't really surprising, as it's basically the same code. (At some point I might include Marc Gravell's generic operators to see how they do.)
Using a general IEnumerable<T> instead of the specific List<T> makes a pretty huge difference to the performance - I assume this is because the JIT inlines the List<T> code, and it doesn't need to create an object because List<T>.Enumerator is a value type. (The enumerator will get boxed in the general version, I believe.)
When using a for loop over a list, hosting the length in the for loop helped in the double version, but hindered in the int version. I've no idea why this happens.

If anyone fancies running this on their own box and letting me know if they get very different results, that would be really interesting. Likewise let me know if you want me to add any more tests into the mix.

Benchmarking made easy

skeet — Mon, 26 Jan 2009 20:57:55 GMT

While I was answering a Stack Overflow question on the performance implications of using a for loop instead of a foreach loop (or vice versa) I promised to blog about the results - particularly as I was getting different results to some other posters.

On Saturday I started writing the bigger benchmark (which I will post about in the fullness of time) and used a technique that I'd used when answering a different question: have a single timing method and pass it a delegate, expected input and expected output. You can ask a delegate for the associated method and thus find out its name (for normal methods, anyway - anonymous functions won't give you anything useful, of course) so that's all the information you really need to run the test.

I've often shied away from using delegates for benchmarking on the grounds of it interfering with the results - including the code inline with the iteration and timing obviously has a bit less overhead. However, the CLR is so fast at delegate invocation these days that it's really not an issue for benchmarks where each iteration does any real work at all.

It's still a pain to have to write that testing infrastructure each time, however. A very long time ago I wrote a small attribute-based framework. It worked well enough, but I've found myself ignoring it - I've barely used it despite writing many, many benchmarks (mostly for newsgroup, blog and Stack Overflow posts) over the course of the years. I'm hoping that the new framework will prove more practical.

There are a few core concepts and (as always) a few assumptions:

A benchmark test is a function which takes a single value and returns a single value. This is expressed generically, of course, so you can make the input and output whatever type you like. A test also has a descriptive name, although this can often be inferred as the name of the function itself. The function will be called many times, the exact number being automatically determined.
A test suite is a collection of benchmark tests and another descriptive name, as well as the input to supply to each test and the expected output.
A benchmark result has a duration and an iteration count, as well as the descriptive name of the test which was run to produce the result. Results can be scaled so that either the duration or the iteration count matches another result. Likewise a result has a score, which is simply the duration (in ticks, but it's pretty arbitrary) divided by the iteration count. Again, the score can be retrieved in a scaled fashion, using a specified result as a "standard" with a scaled score of 1.0. Lower is always better.
A result suite is simply the result of running a test suite. A result suite can be scaled, which is equivalent to building a new result suite with scaled copies of each original result. The result suite contains the smarts to display the results.
Running a test consists of two phases. First, we guess roughly how fast the function is. We run 1 iteration, then 2, then 4, then 8 etc - until it takes at least 3 seconds. At that point we scale up the number of iterations so that the real test will last around 30 seconds. This is the one we record. The final iteration of each set is tested for correctness based on the expected output. Currently the 3 and 30 second targets are hard-coded; I could perhaps make them parameters somewhere, but I don't want to overcomplicate things.

Now for the interesting bit (from my point of view, anyway): I decided that this would be a perfect situation to try playing with a functional style. As a result, everything in the framework is immutable. When you "add" a test to a test suite, it returns a new test suite with the extra test. Running the test suite returns the result suite; scaling the result suite returns a new result suite; scaling a result returns a new result etc.

The one downside of this (beyond a bit of inefficiency in list copying) is that C# collection initializers only work with mutable collections. They also only work with direct constructor calls, whereas generic type inference doesn't apply to constructors. In the end, the "static generic factory method" combined with simple Add method calls yields quite nice results, even though I can't use a collection initializer:

double[] array = ...; // Code to generate random array of doubles

var results = TestSuite.Create("Array", array, array.Sum())
                       .Add(ArrayFor)
                       .Add(ArrayForEach)
                       .Add(Enumerable.Sum, "LINQ Enumerable.Sum")
                       .RunTests()
                       .ScaleByBest(ScalingMode.VaryDuration);

results.Display(ResultColumns.NameAndDuration);

This is a pretty small amount of extra code to write, beyond the code we actually want to benchmark (the ArrayFor and ArrayForEach methods in particular). No looping by iteration count, no guessing at the number of iterations and rerunning it until it lasts a reasonable amount of time, etc.

My only regret is that I haven't written this in a test-driven way. There are currently no unit tests at all. Such is the way of projects that start off as "let's just knock something together" and end up being rather bigger than originally intended.

At some point I'll make it all downloadable from my main C# page, in normal source form, binary form, and also a "single source file" form so you can compile your benchmark with just csc /o+ /debug- Bench*.cs to avoid checking the assembly filename each time you use it. For the moment, here's a zip of the source code and a short sample program, should you find them useful. Obviously it's early days - there's a lot more that I could add. Feedback would help!

Next time (hopefully fairly soon) I'll post the for/foreach benchmark and results.

Designing LINQ operators

skeet — Fri, 23 Jan 2009 23:40:39 GMT

I've started a small project (I'll post a link when I've actually got something worthwhile to show) with some extra LINQ operators in - things which I think are missing from LINQ to Objects, basically. (I hope to include many of the ideas from an earlier blog post.) That, and a few Stack Overflow questions where I've effectively written extra LINQ operators and compared them with other solutions, have made me think about the desirable properties of a LINQ operator - or at least the things you should think about when implementing one. My thoughts so far:

Lazy/eager execution

If you're returning a sequence (i.e. another IEnumerable<T> or similar) the execution should almost certainly be lazy, but the parameter checking should be eager. Unfortunately with the limitations of the (otherwise wonderful) C# iterator blocks, this usually means breaking the method into two, like this:

public static IEnumerable<T> Where(this IEnumerable<T> source,
                                   Func<T, bool> predicate)
{
    // Eagerly executed
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    return WhereImpl(source, predicate);
}

private static IEnumerable<T> WhereImpl(IEnumerable<T> source,
                                        Func<T, bool> predicate)
{
    // Lazily executed
    foreach (T element in source)
    {
        if (predicate(element))
        {
            yield return element;
        }
    }
}

Obviously aggregates and conversions (Max, ToList etc) are generally eager anyway, within normal LINQ to Objects. (Just about everything in Push LINQ is lazy. They say pets look like their owners...)

Streaming/buffering

One of my favourite features of LINQ to Objects (and one which doesn't get nearly the publicity of deferred execution) is that many of the operators stream the data. In other words, they only consume data when they absolutely have to, and they yield data as soon as they can. This means you can process vast amounts of data with very little memory usage, so long as you use the right operators. Of course, not every operator can stream (reversing requires buffering, for example) but where it's possible, it's really handy.

Unfortunately, the streaming/buffering nature of operators isn't well documented in MSDN - and sometimes it's completely wrong. As I've noted before, the docs for Enumerable.Intersect claim that it reads the whole of both sequences (first then second) before yielding any data. In fact it reads and buffers the whole of second, then streams first, yielding intersecting elements as it goes. I strongly encourage new LINQ operators to document their streaming/buffering behaviour (accurately!). This will limit future changes in the implementation admittedly (Intersect can be implemented in a manner where both inputs are streamed, for example) but in this case I think the extra guarantees provided by the documentation make up for that restriction.

Once-only evaluation

When I said that reversing requires buffering earlier on, I was sort of lying. Here's an implementation of Reverse which doesn't buffer any data anywhere:

public static IEnumerable<T> StreamingReverse<T>(this IEnumerable<T> source)
{
    // Error checking omitted for brevity
    int count = source.Count();
    for (int i = count-1; i >= 0; i--)
    {
        yield return source.ElementAt(i);
    }
}

If we assume we can read the sequence as often as we like, then we never need to buffer anything - just treat it as a random-access list. I hope I don't have to tell you that's a really, really bad idea. Leaving aside the blatant inefficiency even for sequences like lists which are cheap to iterate over, some sequences are inherently once-only (think about reading from a network stream) and some are inherently costly to iterate over (think about lines in a big log file - or the result of an ordering).

I suspect that developers using LINQ operators assume that they'll only read the input data once. That's a good assumption - wherever possible, we ought to make sure that it's correct, and if we absolutely can't help evaluating a sequence twice (and I can't remember any times when I've really wanted to do that) we should document it in large, friendly letters.

Mind your complexity

In some ways, this falls out of "try to stream, and try to only read once" - if you're not storing any data and you're only reading each item once, it's quite hard to come up with an operator which isn't just O(n) for a single sequence. It is worth thinking about though - particularly as most of the LINQ operators can work with large amounts of data. For example, to find the smallest element in a sequence you can either sort the whole sequence and take the first element of the result or you can keep track of a "current minimum" and iterate through the whole sequence. Clearly the latter saves a lot of complexity (and doesn't require buffering) - so don't just take the first idea that comes into your head. (Or at least, start with that and then think how you could improve it.)

Again, documenting the complexity of the operator is a good idea, and call particular attention to anything which is unintuitively expensive.

Conclusion

Okay, so there's nothing earth-shattering here. But the more I use LINQ to answer Stack Overflow questions, and the more I invent new operators in the spirit of the existing ones, the more powerful I think it is. It's amazing how powerful it can be, and how ridiculously simple the code (sometimes) looks afterwards. It's not like the operator implementation is usually hard, either - it's just a matter of thinking of the right concepts. I'm going to try to follow these principles when I implement my extra operator library, and I hope you'll bear them in mind too, should you ever feel that LINQ to Objects doesn't have quite the extension method you need...

You don't have to use query expressions to use LINQ

skeet — Wed, 07 Jan 2009 17:32:24 GMT

LINQ is clearly gaining a fair amount of traction, given the number of posts I see about it on Stack Overflow. However, I've noticed an interesting piece of coding style: a lot of developers are using query expressions for every bit of LINQ they write, however trivial.

Now, don't get the wrong idea - I love query expressions as a helpful piece of syntactic sugar. For instance, I'd always pick the query expression form over the "dot notation" form for something like this:

var query = from file in Directory.GetFiles(logDirectory, "*.log")
            from line in new LineReader(file)
            let entry = new LogEntry(line)
            where entry.Severity == Severity.Error
            select file + ": " + entry.Message;

(Yes, it's yet another log entry example - it's one of my favourite demos of LINQ, and particularly Push LINQ.) The equivalent code using just the extension methods would be pretty ugly, especially given the various range variables and transparent identifiers involved.

However, look at these two queries instead:

var query = from person in people
where person.Salary > 10000m
select person;

var dotNotation = people.Where(person => person.Salary > 10000m);

In this case, we're just making a single method call. Why bother with three lines of query expression? If the query becomes more complicated later, it can easily be converted into a query expression at that point. The two queries are exactly the same, even though the syntax is different.

My guess is that there's a "black magic" fear of LINQ - many developers know how to write query expressions, but aren't confident about what they're converted into (or even the basics of what the translation process is like in the first place). Most of the C# 3.0 and LINQ books that I've read do cover query expression translation to a greater or lesser extent, but it's rarely given much prominence.

I suspect the black magic element is reinforced by the inherent "will it work?" factor of LINQ to SQL - you get to write the query in your favourite language, but you may well not be confident in it working until you've tried it; there will always be plenty of little gotchas which can't be picked up at compile time. With LINQ to Objects, there's a lot more certainty (at least in my experience). However, the query expression translation shouldn't be part of what developers are wary of. It's clearly defined in the spec (not that I'm suggesting that all developers should learn it via the spec) and benefits from being relatively dumb and therefore easy to predict.

So next time you're writing a query expression, take a look at it afterwards - if it's simple, try writing it without the extra syntactic sugar. It may just be sweet enough on its own.

Value types and parameterless constructors

skeet — Wed, 10 Dec 2008 17:55:40 GMT

There have been a couple of questions on StackOverflow about value types and parameterless constructors:

I learned quite a bit when answering both of these. When a further question about the default value of a type (particularly with respect to generics) came up, I thought it would be worth delving into a bit more depth. Very little of this is actually relevant most of the time, but it's interesting nonetheless.

I won't go over most of the details I discovered in my answer to the first question, but if you're interested in the IL generated by the statement "x = new Guid();" then have a look there for more details.

Let's start off with the first and most important thing I've learned about value types recently:

Yes, you can write a parameterless constructor for a value type in .NET

I very carefully wrote "in .NET" there - "in C#" would have been incorrect. I had always believed that the CLI spec prohibited value types from having parameterless constructors. (The C# spec used the terminology in a slightly different way - it treats all value types as having a parameterless constructor. This makes the language more consistent for the most part, but it does give rise to some interesting behaviour which we'll see later on.)

It turns out that if you write your value type in IL, you can provide your own parameterless constructor with custom code without ilasm complaining at all. It's possible that other languages targeting the CLI allow you to do this as well, but as I don't know any, I'll stick to IL. Unfortunately I don't know IL terribly well, so I thought I'd just start off with some C# and go from there:

public struct Oddity
{
    public Oddity(int removeMe)
    {
        System.Console.WriteLine("Oddity constructor called");
    }
}

I compiled that into its own class library, and then disassembled it with ildasm /out:Oddity.il Oddity.dll. After changing the constructor to be parameterless, removing a few comments, and removing some compiler-generated assembly attributes) I ended up with this IL:

.assembly extern mscorlib
{
  .publickeytoken = (B7 7A 5C 56 19 34 E0 89 )  
  .ver 2:0:0:0
}
.assembly Oddity
{
  .hash algorithm 0x00008004
  .ver 0:0:0:0
}
.module Oddity.dll
.imagebase 0x00400000
.file alignment 0x00000200
.stackreserve 0x00100000
.subsystem 0x0003
.corflags 0x00000001

.class public sequential ansi sealed beforefieldinit Oddity
       extends [mscorlib]System.ValueType
{
  .pack 0
  .size 1
  .method public hidebysig specialname rtspecialname 
          instance void  .ctor() cil managed
  {
    .maxstack  8
    IL_0000:  nop
    IL_0001:  ldstr      "Oddity constructor called"
    IL_0006:  call       void [mscorlib]System.Console::WriteLine(string)
    IL_000b:  nop
    IL_000c:  ret
  }
}

I reassembled this with ilasm /dll /out:Oddity.dll Oddity.il. So far, so good. We have a value type with a custom constructor in a class library. It doesn't do anything particularly clever - it just logs that it's been called. That's enough for our test program.

When does the parameterless constructor get called?

There are various things one could investigate about parameterless constructors, but I'm mostly interested in when they get called. The test application is reasonably simple, but contains lots of cases - each writes to the console what it's about to do, then does something which might call the constructor. Without further ado:

using System;
using System.Runtime.CompilerServices;

class Test
{
    static Oddity staticField;
    Oddity instanceField;

    static void Main()
    {
        Report("Declaring local variable");
        Oddity localDeclarationOnly;
        // No variables within the value, so we can use it
        // without inializing anything
        Report("Boxing");
        object o = localDeclarationOnly;
        // Just make sure it's really done it
        Report(o.ToString());
        Report("new Oddity() - set local variable");
        Oddity local = new Oddity();
        Report("Create instance of Test - contains instance variable");
        Test t = new Test();
        Report("new Oddity() - set instance field");
        t.instanceField = new Oddity();
        Report("new Oddity() - set static field");
        staticField = new Oddity();
        Report("new Oddity[10]");
        o = new Oddity[10];
        Report("Passing argument to method");
        MethodWithParameter(local);
        GenericMethod<Oddity>();
        GenericMethod2<Oddity>();
        Report("Activator.CreateInstance(typeof(Oddity))");
        Activator.CreateInstance(typeof(Oddity));
        Report("Activator.CreateInstance<Oddity>()");
        Activator.CreateInstance<Oddity>();
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    static void MethodWithParameter(Oddity oddity)
    {
        // No need to do anything
    }

    static void GenericMethod<T>() where T : new()
    {
        Report("default(T) in generic method with new() constraint");
        T t = default(T);
        Report("new T() in generic method with new() constraint");
        t = new T();
    }

    static void GenericMethod2<T>() where T : struct
    {
        Report("default(T) in generic method with struct constraint");
        T t = default(T);
        Report("new T() in generic method with struct constraint");
        t = new T();
    }

    static void Report(string text)
    {
        Console.WriteLine(text);
    }
}

And here are the results:

Declaring local variable
Boxing
Oddity
new Oddity() - set local variable
Oddity constructor called
Create instance of Test - contains instance variable
new Oddity() - set instance field
Oddity constructor called
new Oddity() - set static field
Oddity constructor called
new Oddity[10]
Passing argument to method
default(T) in generic method with new() constraint
new T() in generic method with new() constraint
default(T) in generic method with struct constraint
new T() in generic method with struct constraint
Activator.CreateInstance(typeof(Oddity))
Oddity constructor called
Activator.CreateInstance<Oddity>()
Oddity constructor called

So, to split these out:

Operations which do call the constructor

new Oddity() - whatever we're storing the result in. This isn't much of a surprise. What may surprise you is that it gets called even if you compile Test.cs against the original Oddity.dll (without the custom parameterless constructor) and then just rebuild Oddity.dll.
Activator.CreateInstance<T>() and Activator.CreateInstance(Type). I wouldn't be particular surprised by this either way.

Operations which don't call the constructor

Just declaring a variable, whether local, static or instance
Boxing
Creating an array - good job, as this could be a real performance killer
Using default(T) in a generic method - this one didn't surprise me
Using new T() in a generic method - this one really did surprise me. Not only is it counterintuitive, but in IL it just calls Activator.CreateInstance<T>(). What's the difference between this and calling Activator.CreateInstance<Oddity>()? I really don't understand.

Conclusions

Well, I'm still glad that C# doesn't let us define our own parameterless constructors for value types, given the behaviour. The main reason for using it - as far as I've seen - it to make sure that the "default value" for a type is sensible. Given that it's possible to get a usable value of the type without the constructor being called, this wouldn't work anyway. Writing such a constructor would be like making a value type mutable - almost always a bad idea.

However, it's nice to know it's possible, just on the grounds that learning new things is always a good thing. And at least next time someone asks a similar question, I'll have somewhere to point them...

Redesigning System.Object/java.lang.Object

skeet — Fri, 05 Dec 2008 17:52:44 GMT

I've had quite a few discussions with a colleague about some failures of Java and .NET. The issue we keep coming back to is the root of the inheritance tree. There's no doubt in my mind that having a tree with a single top-level class is a good thing, but it's grown a bit too big for its boots.

Pretty much everything in this post applies to both .NET and Java, sometimes with a few small changes. Where it might be unclear, I'll point out the changes explicitly - otherwise I'll just use the .NET terminology.

What's in System.Object?

Before we work out what we might be able to change, let's look at what we've got. I'm only talking about instance methods. At the moment:

Life-cycle and type identity

There are three members which I believe really need to be left alone.

We need a parameterless constructor because (at least with the current system of chaining constructors to each other) we have to have some constructor, and I can't imagine what parameter we might want to give it. I certainly find it hard to believe there's a particular piece of state which really deserves to be a part of every object but which we're currently missing.

I really don't care that much about finalizers. Should the finalizer be part of Object itself, or should it just get handled automatically by the CLR if and only if it's defined somewhere in the inheritance chain? Frankly, who cares. No doubt it makes a big difference to the implementation somewhere, but that's not my problem. All I care about when it comes to finalizers is that when I have to write them it's as easy as possible to do it properly, and that I don't have to write them very often in the first place. (With SafeHandle, it should be a pretty rare occurrence in .NET, even when you're dealing directly with unmanaged resources.)

GetType() or (getClass() in Java) is pretty important. I can't see any particular alternative to having this within Object, unless you make it a static method somewhere else with an Object parameter. In fact, that would have the advantage of freeing up the name for use within your own classes. The functionality is sufficiently important (and really does apply to every object) that I think it's worth keeping.

Comparison methods

Okay, time to get controversial. I don't think every object should have to be able to compare itself with another object. Of course, most types don't really support this anyway - we just end up with reference equality by default.

The trouble with comparisons is that everyone's got a different idea of what makes something equal. There are some types where it really is obvious - there's only one natural comparison. Integers spring to mind. There are other types which have multiple natural equality comparisons - floating point numbers (exact, within an absolute epsilon, and within a relative epsilon) and strings (ordinal, culture sensitive and/or case sensitive) are examples of this. Then there are composite types where you may or may not care about certain aspects - when comparing URLs, do I care about case? Do I care about fragments? For http, if the port number is explicitly specified as 80, is that different to a URL which is still http but leaves the port number implicit?

.NET represents these reasonably well already, with the IEquatable<T> interface saying "I know how to compare myself with an instance of type T, and how to produce a hashcode for myself" and IEqualityComparer<T> interface saying "I know how to compare two instances of T, and how to produce a hashcode for one instance of T." Now suppose we didn't have the (nongeneric!) Equals() method and GetHashCode() in System.Object. Any type which had a natural equality comparison would still let you compare it for equality by implementing IEquatable<T>.Equals - but anything else would either force you to use reference equality or an implementation of IEqualityComparer<T>.

Some of the principle consumers of equality comparisons are collections - particularly dictionaries (which is why it's so important that the interfaces should include hashcode generation). With the current way that .NET generics work, it would be tricky to have a constraint on a constructor such that if you only specified the types, it would only work if the key type implemented IEquatable<T>, but it's easy enough to do with static methods (on a non-generic type). Alternatively you could specify any type and an appropriate IEqualityComparer<T> to use for the keys. We'd need an IdentityComparer<T> to work just with references (and provide the equivalent functionaliy to Object.GetHashCode) but that's not hard - and it would be absolutely obvious what the comparison was when you built the dictionary.

Monitors and threading

This is possibly my biggest gripe. The fact that every object has a monitor associated with it was a mistake in Java, and was unfortunately copied in .NET. This promotes the bad practice of locking on "this" and on types - both of which are typically publicly accessible references. I believe that unless a reference is exposed explicitly for the purpose of locking (like ICollection.SyncRoot) then you should avoid locking on any reference which other code knows about. I typically have a private read-only variable for locking purposes. If you're following these guidelines, it makes no sense to be able to lock on absolutely any reference - it would be better to make the Monitor class instantiable, and make Wait/Pulse/PulseAll instance members. (In Java this would mean creating a new class and moving Object.wait/notify/notifyAll members to that class.)

This would lead to cleaner, more readable code in my view. I'd also do away with the "lock" statement in C#, making Monitor.Enter return a token implementing IDisposable - so "using" statements would replace locks, freeing up a keyword and giving the flexibility of having multiple overloads of Monitor.Enter. Arguably if one were redesigning all of this anyway, it would be worth looking at whether or not monitors should really be reentrant. Any time you use lock reentrancy, you're probably not thinking hard enough about the design. Now there's a nice overgeneralisation with which to end this section...

String representations

This is an interesting one. I'm genuinely on the fence here. I find ToString() (and the fact that it's called implicitly in many circumstances) hugely useful, but it feels like it's attempting to satisfy three different goals:

Giving a developer-readable representation when logging and debugging
Giving a user-readable representation as part of a formatted message in a UI
Giving a machine-readable format (although this is relatively rare for anything other than numeric types)

It's interesting to note that Java and .NET differ as to which of these to use for numbers - Java plumps for "machine-readable" and .NET goes for "human-readable in the current thread's culture". Of course it's clearer to explicitly specify the culture on both platforms.

The trouble is that very often, it's not immediately clear which of these has been implemented. This leads to guidelines such as "don't use ToString() other than for logging" on the grounds that at least if it's implemented inappropriately, it'll only be a log file which ends up with difficult-to-understand data.

Should this usage be explicitly stated - perhaps even codified in the name: "ToDebugString" or something similar? I will leave this for smarter minds to think about, but I think there's enough value in the method to make it worth keeping.

MemberwiseClone

Again, I'm not sure on this one. It would perhaps be better as a static (generic!) method somewhere in a class whose name indicated "this is for sneaky runtime stuff". After all, it constructs a new object without calling a constructor, and other funkiness. I'm less bothered by this than the other items though.

Conclusion

To summarise, in an ideal world:

Equals and GetHashCode would disappear from Object. Types would have to explicitly say that they could be compared
Wait/Pulse/PulseAll would become instance methods in Monitor, which would be instantiated every time you want a lock.
ToString might be renamed to give clearer usage guidance.
MemberwiseClone might be moved to a different class.

Obviously it's far too late for either Java or .NET to make these changes, but it's always interesting to dream. Any more changes you'd like to see? Or violent disagreements with any of the above?

The Snippy Reflector add-in

skeet — Sun, 23 Nov 2008 10:25:53 GMT

Those of you who've read C# in Depth will know about Snippy - a little tool which makes it easy to build complete programs from small snippets of code.

I'm delighted to say that reader Jason Haley has taken the source code for Snippy and built an add-in for Reflector. This will make it much simpler to answer questions like this one about struct initialization, where you really want to the IL generated for a snippet. Here's a screenshot to show what it does:

This is really cool - if you want to dabble to see what the C# compiler does in particular situations, check it out. It comes as just the DLL, or a zipped version. Thanks for putting in all this work, Jason :)

Update: Jason now has his own (more detailed) blog entry too.

Copenhagen C# talk videos now up

skeet — Wed, 19 Nov 2008 07:17:31 GMT

The videos from my one day talk about C# in Copenhagen are now on the MSDN community site. There are eight sessions, varying between about 25 minutes and 50 minutes in length. I haven't had time to watch them yet, but when I do I'll submit brief summaries so you can quickly get to the bits you're most interested in. (As far as I'm aware, they're only available via Silverlight, which I realise isn't going to be convenient for everyone.)

Feedback is very welcome.

.NET 4.0's game-changing feature? Maybe contracts...

skeet — Thu, 06 Nov 2008 01:38:00 GMT

Update: As Chris Nahr pointed out, there's a blog post by Melitta Andersen of the BCL team explaining this in more detail.

Obviously I've been looking at the proposed C# 4.0 features pretty carefully, and I promise I'll blog more about them at some later date - but yesterday I watched a PDC video which blew me away.

As ever, a new version of .NET means more than just language changes - Justin van Patten has written an excellent blog post about what to expect in the core of thee framework. There are nice things in there - tuples and BigInteger, for example - but it was code contracts that really caught my eye.

Remember Spec#? Well, as far as I can tell the team behind it realised that people don't really want to have to learn a new language - but if the goodness of Design By Contract can be put into a library, then everyone can use it. Enter CodeContracts...

Actual examples are relatively few and far between at the moment, but the basic idea is that you write your contracts at the start of methods - not in attributes, presumably because that's too limiting in terms of what you can express - and then a post-build tool will "understand" those contracts, find potential issues, and do a bit of code-rewriting where appropriate (e.g. to move the post-condition testing to the end points of the method). Object invariants can also be expressed as separate methods.

Rather than guess at the syntax in this blog post I highly recommend you watch the PDC 2008 video on both this and Pex (an intelligent code explorer and test generator). The teams have clearly thought through a lot of significant issues:

Contracts can be enforced at runtime, or stripped out for release builds. (I'll be interested to see whether I can keep the pre-condition checks in the release build, just removing invariants and post-conditions etc.)
If you're stripping out the contracts, you can still have them in a separate assembly - so if you supply a library to someone, they can still have all the Design by Contract goodness available, and see where they're potentially violating your preconditions
Contracts will be automatically documented in the generated XML documentation file (although this has yet to be implemented, I believe)
Interfaces can be associated with contract classes where the contracts are expressed. (They couldn't be in the interface, as they require method bodies.)
Pex will be able to generate tests in MS Test, NUnit and MbUnit. (Hooray! This got a massive cheer at PDC.)

Now I should point out that I haven't tried any of this - I've just watched a video which was very slick and obviously used a well-tested scenario. If this genuinely works, however, I think it could change the way mainstream developers approach coding just as LINQ is changing the way we see data. (Obviously there's nothing fundamentally new about DbC - but there's a difference between it existing and it being mainstream.)

I'm really, really excited about this :) Definitely time to boot up the VPC image when I get a moment...

C# 4.0: dynamic ?

skeet — Thu, 30 Oct 2008 22:04:10 GMT

I've not played with the VS2010 CTP much yet, and I've only looked briefly at the documentation and blogs about the new C# 4.0 dynamic type, but a thought occurred to me: why not have the option of making it generic as a way of saying "I will dynamically support this set of operations"?

As an example of what I mean, suppose you have an interface IMessageRouter like this:

public interface IMessageRouter
{
void Send(string message, string destination);
}

(This is an arbitrary example, by the way. The idea isn't specifically more suitable for message routing than anything else.)

I may have various implementations, written in various languages (or COM) which support the Send method with those parameters. Some of those implementations actually implement IMessageRouter but some don't. I'd like to be able to do the following:

dynamic<IMessageRouter> router = GetRouter();

// This is fine (but still invoked dynamically)
router.Send("message", "skeet@pobox.com");
// Compilation error: no such overload
router.Send("message", "skeet@pobox.com", 20);

Intellisense would work, and we'd still have some of the benefits of static typing but without the implementations having to know about your interface. Of course, it would be quite easy to create an implementation of the interface which did exactly this - but now imagine that instead of IMessageRouter we had MessageRouter - a concrete class. In this case the compiler would still restrict the caller to the public API of the class, but it wouldn't have to be the real class. No checking would be performed by the compiler that your dynamic type actually supported the operations - given that we're talking about dynamic invocation, that would be impossible to do. It would instead be an "opt-in" restriction the client places on themselves. It could also potentially help with performance - if the binding involved realised that the actual type of the dynamic object natively implemented the interface or was/derived from the class, then no real dynamic calls need be made; just route all directly.

This may all sound a bit fuzzy - I'm extremely sleepy, to be honest - but I think it's a potentially interesting idea. Thoughts?

Update

Apparently this post wasn't as clear as it might be. I'm quite happy to keep the currently proposed dynamic type idea as well - I'd like this as an additional way of using dynamic objects.

DeveloperDeveloperDeveloper: Registration now open (hurry!)

skeet — Wed, 22 Oct 2008 09:53:34 GMT

The registration page for DeveloperDeveloperDeveloper Day 2008 (Reading, November 22nd) is now open. In the past this has been heavily oversubscribed, so if you want to come you'll need to register quickly.

I've got a speaking slot in the afternoon: implementing LINQ to Objects in 60 minutes. As always, I'm very much looking forward to it.

Mapping from a type to an instance of that type

skeet — Wed, 08 Oct 2008 20:24:09 GMT

A question came up on Stack Overflow yesterday which I've had to deal with myself before now. There are times when it's helpful to have one value per type, and that value should be an instance of that type. To express it in pseudo-code, you want an IDictionary<typeof(T), T> except with T varying across all possible types. Indeed, this came up in Protocol Buffers at least once, I believe.

.NET generics don't have any way of expressing this, and you end up with boxing and a cast. I decided to encapsulate this (in MiscUtil of course, although it's not in a released version yet) so that I could have all the nastiness in a single place, leaving the client code relatively clean. The client code makes calls to generic methods which either take an instance of the type argument or return one. It's a really simple class, but a potentially useful one:

/// <summary>
/// Map from types to instances of those types, e.g. int to 10 and
/// string to "hi" within the same dictionary. This cannot be done
/// without casting (and boxing for value types) as .NET cannot
/// represent this relationship with generics in their current form.
/// This class encapsulates the nastiness in a single place.
/// </summary>
public class DictionaryByType
{
    private readonly IDictionary<Type, object> dictionary = new Dictionary<Type, object>();

    /// <summary>
    /// Maps the specified type argument to the given value. If
    /// the type argument already has a value within the dictionary,
    /// ArgumentException is thrown.
    /// </summary>
    public void Add<T>(T value)
    {
        dictionary.Add(typeof(T), value);
    }

    /// <summary>
    /// Maps the specified type argument to the given value. If
    /// the type argument already has a value within the dictionary, it
    /// is overwritten.
    /// </summary>
    public void Put<T>(T value)
    {
        dictionary[typeof(T)] = value;
    }

    /// <summary>
    /// Attempts to fetch a value from the dictionary, throwing a
    /// KeyNotFoundException if the specified type argument has no
    /// entry in the dictionary.
    /// </summary>
    public T Get<T>()
    {
        return (T) dictionary[typeof(T)];
    }

    /// <summary>
    /// Attempts to fetch a value from the dictionary, returning false and
    /// setting the output parameter to the default value for T if it
    /// fails, or returning true and setting the output parameter to the
    /// fetched value if it succeeds.
    /// </summary>
    public bool TryGet<T>(out T value)
    {
        object tmp;
        if (dictionary.TryGetValue(typeof(T), out tmp))
        {
            value = (T) tmp;
            return true;
        }
        value = default(T);
        return false;
    }
}

It doesn't implement any of the common collection interfaces, because it would have to do so in a way which exposed the nastiness. I'm tempted to make it implement IEnumerable<KeyValuePair<Type, object>> but even that's somewhat unpleasant and unlikely to be useful. Easy to add at a later date if necessary.

(I know the XML documentation leaves something to be desired. One day I'll learn how to really do it properly - currently I fumble around if I'm trying to refer to other types etc within the docs.)

Why boxing doesn't keep me awake at nights

skeet — Wed, 08 Oct 2008 19:42:02 GMT

I'm currently reading the (generally excellent) CLR via C#, and I've recently hit the section on boxing. Why is it that authors feel they have to scaremonger about the effects boxing can have on performance?

Here's a piece of code from the book:

using System;

public sealed class Program {
   public static void Main() {
      Int32 v = 5;   // Create an unboxed value type variable.

#if INEFFICIENT
      // When compiling the following line, v is boxed
      // three times, wasting time and memory
      Console.WriteLine("{0}, {1}, {2}", v, v, v);
#else
      // The lines below have the same result, execute
      // much faster, and use less memory
      Object o = v;

      // No boxing occurs to compile the following line.
      Console.WriteLine("{0}, {1}, {2}", o, o, o);
#endif
   }
}

In the text afterwards, he reiterates the point:

This second version executes much faster and allocates less memory from the heap.

This seemed like an overstatement to me, so I thought I'd try it out. Here's my test application:

using System;
using System.Diagnostics;

public class Test
{
    const int Iterations = 10000000;

    public static void Main()
    {
        Stopwatch sw = Stopwatch.StartNew();
        for (int i=0; i < Iterations; i++)
        {
#if CONSOLE_WITH_BOXING
            Console.WriteLine("{0} {1} {2}", i, i, i);
#elif CONSOLE_NO_BOXING
            object o = i;
            Console.WriteLine("{0} {1} {2}", o, o, o);
#elif CONSOLE_STRINGS
            string s = i.ToString();
            Console.WriteLine("{0} {1} {2}", s, s, s);
#elif FORMAT_WITH_BOXING
            string.Format("{0} {1} {2}", i, i, i);
#elif FORMAT_NO_BOXING
            object o = i;
            string.Format("{0} {1} {2}", o, o, o);
#elif FORMAT_STRINGS
            string s = i.ToString();
            string.Format("{0} {1} {2}", s, s, s);
#elif CONCAT_WITH_BOXING
            string.Concat(i, " ", i, " ", i);
#elif CONCAT_NO_BOXING
            object o = i;
            string.Concat(o, " ", o, " ", o);
#elif CONCAT_STRINGS
            string s = i.ToString();
            string.Concat(s, " ", s, " ", s);
#endif
        }
        sw.Stop();
        Console.Error.WriteLine("{0}ms", sw.ElapsedMilliseconds);
    }
}

I compiled the code with one symbol defined each time, with optimisations and without debug information, and ran it from a command line, writing to nul (i.e. no disk or actual console activity). Here are the results:

Symbol	Results (ms)	Average (ms)
CONSOLE_WITH_BOXING	33054	33444
	33898
	33381
CONSOLE_NO_BOXING	34638	33451
	32423
	33294
CONSOLE_STRINGS	29259	28337
	29071
	26683
FORMAT_WITH_BOXING	17143	17210
	18100
	16389
FORMAT_NO_BOXING	15814	15657
	15936
	15222
FORMAT_STRINGS	9178	8999
	9077
	8742
CONCAT_WITH_BOXING	12056	12563
	14304
	11329
CONCAT_NO_BOXING	11949	12240
	13145
	11628
CONCAT_STRINGS	5833	5936
	6263
	5713

So, what do we learn from this? Well, a number of things:

As ever, microbenchmarks like this are pretty variable. I tried to do this on a "quiet" machine, but as you can see the results varied quite a lot. (Over two seconds between best and worst for a particular configuration at times!)
The difference due to boxing with the original code in the book is basically inside the "noise"
The dominant factor of the statement is writing to the console, even when it's not actually writing to anything real
The next most important factor is whether we convert to string once or three times
The next most important factor is whether we use String.Format or Concat
The least important factor is boxing

Now I don't want anyone to misunderstand me - I agree that boxing is less efficient than not boxing, where there's a choice. Sometimes (as here, in my view) the "more efficient" code is slightly less readable - and the efficiency benefit is often negligible compared with other factors. Exactly the same thing happened in Accelerated C# 2008, where a call to Math.Pow(x, 2) was the dominant factor in a program again designed to show the efficiency of avoiding boxing.

The performance scare of boxing is akin to that of exceptions, although I suppose it's more likely that boxing could cause a real performance concern in an otherwise-well-designed program. It used to be a much more common issue, of course, before generics gave us collections which don't require boxing/unboxing to add/fetch data.

In short: yes, boxing has a cost. But please look at it in context, and if you're going to start making claims about how much faster code will run when it avoids boxing, at least provide an example where it actually contributes significantly to the overall execution cost.

Non-nullable reference types

skeet — Mon, 06 Oct 2008 20:51:08 GMT

I suspect this has been done several times before, but on my way home this evening I considered what would be needed for the reverse of nullable value types - non-nullable reference types. I've had a play with an initial implementation in MiscUtil (not in the currently released version) and it basically boils down (after removing comments, equality etc) to this:

public struct NonNullable<T> where T : class
{
    private readonly T value;

    public NonNullable(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException("value");
        }
        this.value = value;
    }

    public T Value
    {
        get
        {
            if (value == null)
            {
                throw new NullReferenceException();
            }
            return value;
        }
    }

    public static implicit operator NonNullable<T>(T value)
    {
        return new NonNullable<T>(value);
    }

    public static implicit operator T(NonNullable<T> wrapper)
    {
        return wrapper.Value;
    }
}

Currently I've got both conversion operators as implicit, which isn't quite as safe/obvious as it is with nullable value types, but it does make life simpler. Obviously this is experimental code more than anything else, so I may change my mind later.

The simple use case is something like this (along with testing error cases):

[Test]
public void Demo()
{
    SampleMethod("hello"); // No problems
    try
    {
        SampleMethod(null);
        Assert.Fail("Expected exception");
    }
    catch (ArgumentNullException)
    {
        // Expected
    }
    try
    {
        SampleMethod(new NonNullable<string>());
        Assert.Fail("Expected exception");
    }
    catch (NullReferenceException)
    {
        // Expected
    }
}

private static void SampleMethod(NonNullable<string> text)
{
    // Shouldn't get here with usual conversions, but could do
    // through default construction. The conversion to string
    // will throw an exception anyway, so we're guaranteed
    // that foo is non-null afterwards.
    string foo = text;
    Assert.IsNotNull(foo);
}

I don't intend to use this within MiscUtil at the moment. Note that it's a struct, which has a few implications:

It has the same memory footprint as the normal reference type. No GC pressure and no extra dereferencing. This is basically the main reason for making it a struct.
It ends up being boxed to a new object. Boo hiss - ideally the boxing conversion would box it to the wrapped reference, and you could "unbox" (not really unboxing, of course) from a non-null reference to an instance of the struct.
It's possible to create instances wrapping null references, by calling the parameterless constructor or using the default value of fields etc. This is very annoying.

The good news is that it's self-documenting and easy to use - the conversions will happen where required, doing appropriate checking (reasonably cheaply). The bad news is the lack of support from either the CLR (boxing behaviour above) or language (I'd love to specify string! text as the parameter in the sample method above.) I suspect that if Microsoft were to do this properly, they'd want to avoid all of the problems above - but I'm not sure how...

Anyway, just a little experiment, but an interesting one - any thoughts?

Formatting strings

skeet — Mon, 06 Oct 2008 10:45:00 GMT

A while ago I wrote an article about StringBuilder and a reader mailed me to ask about the efficiency of using String.Format instead. This reminded me of a bone I have to pick with the BCL.

Whenever we make a call to String.Format, it has to parse the format string. That doesn't sound too bad, but string formatting can be used a heck of a lot - and the format is almost always hard-coded in some way. It may be loaded from a resource file instead of being embedded directly in the source code, but it's not going to change after the application has started.

I put together a very crude benchmark which joins two strings together, separating them with just a space. The test uses String.Format first, and then concatenation. (I've tried it both ways round, however, and the results are the same.)

using System;
using System.Diagnostics;

public static class Test
{
    const int Iterations=10000000;
    const int PieceSize=10;

    static void Main()
    {
        string first = GenerateRandomString();
        string second = GenerateRandomString();
        int total=0;

        Stopwatch sw = Stopwatch.StartNew();
        for (int i=0; i < Iterations; i++)
        {
            string x = String.Format("{0} {1}", first, second);
            total += x.Length;
        }
        sw.Stop();
        Console.WriteLine("Format: {0}", sw.ElapsedMilliseconds);
        GC.Collect();

        sw = Stopwatch.StartNew();
        for (int i=0; i < Iterations; i++)
        {
            // Equivalent to first + " " + second
            string x = String.Concat(first, " ", second);
            total += x.Length;
        }
        sw.Stop();
        Console.WriteLine("Concat: {0}", sw.ElapsedMilliseconds);
        if (total != Iterations * 2 * (PieceSize*2 + 1))
        {
            Console.WriteLine("Incorrect total: {0}", total);
        }
    }

    private static readonly Random rng = new Random();
    private static string GenerateRandomString()
    {
        char[] ret = new char[PieceSize];
        for (int j=0; j < ret.Length; j++)
        {
            ret[j] = (char) ('A' + rng.Next(26));
        }
        return new string(ret);
    }
}

And the results (on my very slow Eee)...

Format: 14807
Concat: 3567

As you can see, Format takes significantly longer than Concat. I strongly suspect that this is largely due to having to parse the format string on each iteration. That won't be the whole of the cost - String needs to examine the format specifier for each string as well, in case there's padding, etc - but again that could potentially be optimised.

I propose a FormatString class with a pair of Format methods, one of which takes a culture and one of which doesn't. We could then hoist our format strings out of the code itself and make them static readonly variables referring to format strings. I'm not saying it would do a huge amount to aid performance, but it could shave off a little time here and there, as well as making it even more obvious what the format string is used for.

Lessons learned from Protocol Buffers, part 4: static interfaces

skeet — Fri, 29 Aug 2008 18:50:32 GMT

Warning: During this entire post, I will use the word static to mean "relating to a type instead of an instance". This isn't a strictly accurate use but I believe it's what most developers actually think of when they hear the word.

A few members of the interfaces in Protocol Buffers have no logical reason to act on instances of their types. The message interface has members to return the message's type descriptor (the PB equivalent of System.Type), the default instance for the message type, and a builder for the message type. The builder interface copies the first two of these, and also has a method to create a builder for a particular field. None of these touch any instance data.

In most cases this doesn't actually cause any difficulties - we usually have an instance available when we're in the PB library code, and the generated types have static properties for the default instance and the type descriptor anyway. Even so, it feels messy to have interface members which rely only on the type of the implementation and not on any of the actual data of the instance.

I've wondered before now about the possibility of having static members in interfaces - usually when thinking about plug-in architectures - but there's always been the problem of working out how to specify the type on which to call the members. Variables and other expressions usually refer to values rather than types, and System.Type doesn't help as it provides no compile-time knowledge of the type being referred to.

There's one big exception to this, however: generic type parameters. I don't know why it had never occurred to me before, but this is a great fit for the ability to safely call static methods on types which are unknown at compile-time. Furthermore, it could provide a great way of enforcing the presence of constructors with appropriate signatures, and even operators. Before I get too far ahead of myself, let's tie the simple case to a concrete example.

Creating builders from nothing

In my previous post I gave an example of a method which ideally wanted to return a new message given a CodedInputStream and an ExtensionRegistry (both types within Protocol Buffers, the details of which are unimportant to this example). The current code looks like this:

private static TMessage BuildImpl<TMessage2, TBuilder> (Func<TBuilder> builderBuilder,
                                                        CodedInputStream input,
                                                        ExtensionRegistry registry)
    where TBuilder : IBuilder<TMessage2, TBuilder>
    where TMessage2 : TMessage, IMessage<TMessage2, TBuilder>
{
    TBuilder builder = builderBuilder();
    input.ReadMessage(builder, registry);
    return builder.Build();
}

For the purposes of this discussion I'll simplify it a little, making it a generic method in a non-generic type.

private static TMessage BuildImpl<TMessage, TBuilder> (Func<TBuilder> builderBuilder,
                                                       CodedInputStream input,
                                                       ExtensionRegistry registry)
    where TBuilder : IBuilder<TMessage, TBuilder>
    where TMessage : IMessage<TMessage, TBuilder>
{
    TBuilder builder = builderBuilder();
    input.ReadMessage(builder, registry);
    return builder.Build();
}

The first parameter is a function which will return us a builder. We can't simply add a new() constraint to TBuilder as not all geenrated builders will have a public constructor. However, we do know that the TMessage type has a CreateBuilder() method because it implements IMessage<TMessage, TBuilder>. Unfortunately we don't have an instance of TMessage to call CreateBuilder() on! Really, we'd like to be able to change the code to this:

private static TMessage BuildImpl<TMessage, TBuilder> (CodedInputStream input, ExtensionRegistry registry)
    where TBuilder : IBuilder<TMessage, TBuilder>
    where TMessage : IMessage<TMessage, TBuilder>
{
    TBuilder builder = TMessage.CreateBuilder();
    input.ReadMessage(builder, registry);
    return builder.Build();
}

That's currently impossible, but only because we can't specify static methods in interfaces. Suppose we could write:

public interface IMessage<TMessage, TBuilder>
    where TMessage : IMessage<TMessage, TBuilder>
    where TBuilder : IBuilder<TMessage, TBuilder>
{
    static TBuilder CreateBuilder();

    // Other methods as before
}

Wouldn't that be useful? The value would almost entirely be for generic types or methods where the type parameter is constrained to specify the relevant interface, but that could arguably still be very handy.

Operators and constructors

At this point hopefully the idea I mentioned earlier of being able to specify operators and constructors is quite obvious. For instance, we could make all the existing numeric types implement IArithmetic<T> (where T was the same type, e.g. int : IArithmetic<int>):

public interface IArithmetic<T>
{
    static T operator +(T left, T right);
    static T operator -(T left, T right);
    static T operator /(T left, T right);
    static T operator *(T left, T right);
}

// Used in LINQ to Objects, for example:
public static T Sum<T>(this IEnumerable<T> source) where T : IArithmetic<T>
{
    T total = default(T);
    foreach (T element in source)
    {
        total += element; // Interface says we can do total + element
    }
    return total;
}

Plug-ins for a particular program could implement IPlugin:

public interface IPlugin
{
    static new (PluginHost host);

    // Normal plug-in members here
    string Title { get; }
}

// Used within a PluginHost like this...
public T CreatePlugin<T>() where T : IPlugin
{
    T plugin = new T(this);
    log.Info("Loaded plugin {0}", plugin.Title);
    return plugin;
}

In fact, I'd imagine it would make sense to define a whole family of IConstructable interfaces, along the same lines as the Func and Action delegate families:

public interface IConstructable
{
    static new();
}

public interface IConstructable<T>
{
    static new(T arg)
}

public interface IConstructable<T1, T2>
{
    static new(T1 arg1, T2 arg2);
}

// etc

Inheritance raises its ugly head

There's a fly in the ointment here. Normally, if a base type implements an interface, that means a type derived from it will effectively implement the interface too. That ceases to hold in all cases. You can get away with it for straightforward static methods/properties, in the same way that people often write code such as UTF8Encoding.UTF8 when they really just mean Encoding.UTF8. However, it doesn't work for constructors - they aren't inherited, so you can't guarantee that Banana has a parameterless constructor just because Fruit does.

This is not only a problem for one concrete class deriving from another, but also for abstract implementations of interfaces. This happens a lot in Protocol Buffers; often the interface is partially implemented by the abstract class, with the final "leaf" classes in the inheritance tree implementing outstanding members and occasionally overriding earlier implementations for the sake of efficiency. Should we be able to specify an abstract static method in the abstract class, making sure that there's an appropriate implementation by the time we hit a concrete class? As it happens that would be useful elsewhere in the Protocol Buffer library, but I'll admit it's slightly messy. I suspect there are ways round all of these issues, even if they might sometimes involve restricting the feature to particular, common use cases. However, every niggle would add its own piece of complexity.

There may well be other issues which would prove challenging - and other interesting aspects such as what explicit interface implementation would mean, if anything, in the context of static members. Language experts may well be able to reel off great lists of problems - I'd be very interested to here the ensuing discussions.

Conclusion

I believe that static interface members could prove very useful in generic algorithms, particularly if operators and constructors were allowed as well as the existing member types available in interfaces. There are significant sticking points to be carefully considered, and I wouldn't like to prejudge the outcome of such deliberations in terms of whether the feature would be useful enough to merit the additional language complexity involved. It feels odd to implement an interface member which is effectively only of use when the implementing type is being used as the type argument for a generic type or method, but as developers learn to think more generically that may be less of a restriction than it currently seems.

This post is the last in my current batch talking about Protocol Buffers. There may well be more, but it's unlikely now that the Protocol Buffer port is almost entirely complete. Most of these posts have involved generics, and the current limitations of what C# allows us to express in them. I do not intend to give the impression that I'm dissatisfied with C# - I've just found it interesting to take a look at what lies beyond the current boundaries of the language. The one aspect of these posts which I would definitely like to see addresses is that of covariant return types - the Java implementation of Protocol Buffers is significantly simpler in many ways purely due to this one point.

Lessons learned from Protocol Buffers, part 3: generic type relationships

skeet — Fri, 29 Aug 2008 18:48:48 GMT

In part 2 of this series we saw how the message and builder interfaces were self-referential in order to allow the implementation types to be part of the API. That's one sort of relationship, but in this post we'll see how the two interfaces relate to each other. If you remember from part 1 every generated message type has a corresponding builder type. As it happens, this is implemented with a nested type, so if you had a Person message, the generated types would be Person and Person.Builder (in a specified namespace, of course).

Without any interfaces involved, this would be very simple. The types would just look like this (with more members, of course):

public class Person
{
    public static Builder CreateBuilder() { ... }

    public Builder CreateBuilderForType() { ... }

    public class Builder
    {
        public Builder() { ... }

        public Person Build() { ... }
    }
}

You may well be wondering why there are two methods for creating a builder. The static method is convenient for code which knows it's dealing with the Person message. The instance method ends up being part of the message interface, which makes it useful for code which can work with any message. In addition, the constructor for Person.Builder is accessible in the C# version. In the original Java code the only way of creating a builder is via the methods in the message class; I decided to remove this restriction for the sake of making the oh-so-readable object initializer syntax available in C# 3.

Redesigning the interfaces to refer to each other

In part 2 we created self-referential interfaces for the message and builder interfaces which looked like this:

public interface IMessage<TMessage> where TMessage : IMessage<TMessage>
{
...
}

public interface IBuilder<TBuilder> where TBuilder : IBuilder<TBuilder>
{
...
}

The constraints on the type parameters allow us to make the API very specific, and we can use the same trick again when we relate the builder and message types together. The step where we introduce a new type parameter to each of them is straightforward:

public interface IMessage<TMessage, TBuilder> where TMessage : IMessage<TMessage, TBuilder>
{
...
}

public interface IBuilder<TMessage, TBuilder> where TBuilder : IBuilder<TMessage, TBuilder>
{
...
}

Unfortunately without any restrictions on the "foreign" type parameter in each interface, we don't get enough information to make everything work. We need to tie the two types together more tightly, like this:

public interface IMessage<TMessage, TBuilder>
    where TMessage : IMessage<TMessage, TBuilder>
    where TBuilder : IBuilder<TMessage, TBuilder>
{
    ...
}

public interface IBuilder<TMessage, TBuilder>
    where TMessage : IMessage<TMessage, TBuilder>
    where TBuilder : IBuilder<TMessage, TBuilder>
{
    ...
}

To make this concrete for Person and Person.Builder we end up with implementations like this:

public class Person : IMessage<Person, Builder>
{
    public static Builder CreateBuilder() { ... }

    public Builder CreateBuilderForType() { ... }

    public class Builder : IBuilder<Person, Builder>
    {
        public Builder() { ... }

        public Person Build() { ... }
    }
}

This works, but it's really ugly. Any generic methods wanting to take a TMessage type parameter implementing IMessage<TMessage, TBuilder> have to also have a TBuilder type parameter, and the two constraints need to be expressed each time. It's a real pain. In fact, I've got an IMessage<TMessage> interface which contains almost nothing in it (and which the more generic interface extends). This allows me to get hold of the message type (and use it in the API), inferring the builder type by reflection. That's a pain too, frankly. It's a particular nuisance because when I do infer the builder type, I haven't actually got any compile-time constraint the lets any other code know that it's the right builder type for the message type. In one specific case it's led to this horrific method (in a type generic in TMessage:

Fortunately this is hidden from public view - and the only reason to do it at all is to enable a pleasant API of MessageStreamIterator<TMessage> : IEnumerable<TMessage> where TMessage : IMessage<TMessage>. The result of the evil method above is exactly what the caller is likely to want, otherwise I wouldn't put up with it. However, that sort of excuse has been coming up far too much in the PB implementation, so I've had a quick think about what could be done about it.

Contemplating a more expressive language

I should really prefix this section by saying that I'm not actually suggesting this as a way forward for C# or .NET. (I suspect it would take more work in the CLR as well as just in the language; I don't know enough about CLR generics to say for sure, but I'd be surprised if this were feasible.) I haven't encountered many situations where I've wanted anything like this, and the extra complexity in the language would be quite high, I suspect. Suppose an interface could contain extra type parameters, including constraints, in the body of the interface:

// Purely imaginary syntax!
public interface IMessage<TMessage> where TMessage : IMessage<TMessage>
{
    <TBuilder> where TBuilder : IBuilder<TBuilder>, TBuilder.TMessage : TMessage

    // Normal methods, which could use TBuilder
}

public interface IBuilder<TBuilder> where TBuilder : IBuilder<TBuilder>
{
    <TMessage> where TMessage : IMessage<TMessage>, TMessage.TBuilder : TBuilder

    // Normal methods, which could use TMessage
}

There are various ways in which the interface implementation could indicate the type of TBuilder. The syntax itself isn't particularly interesting - it's the extra information which is conveyed which is the important bit. I've dithered between this being a step forward and it not. At first glance it looks no better than having both type parameters in the interface declaration, but I believe it would genuinely make a difference. For instance, the above evil method could be written as:

private static TMessage BuildImpl(Func<TMessage.TBuilder> builderBuilder,
                                  CodedInputStream input,
                                  ExtensionRegistry registry)
{
    TMessage.TBuilder builder = builderBuilder();
    input.ReadMessage(builder, registry);
    return builder.Build();
}

This time there's no need for the method to be generic, because the type is already generic in the message type. Furthermore, we can call this method with no reflection. All other APIs which have previously had to be specify two type parameters can now just specify the one. Apart from anything else, this leaves more scope for type inference in generic methods - passing either a message or a builder to a generic method happens occasionally, but it's very rare to pass in both.

We've essentially expressed the relationship between the message type and the builder type a little more explicitly, so that we can guarantee it exists (and use it) at compile time. That's at the heart of the problem to start with - without a second type parameter in the initial interface declaration, in the current language there's no way of expressing a close relationship with another type.

Conclusion

I don't think it would be fair to say that C# really lets us down here - it happens not to support a pretty rare scenario, and that's fair enough. I'd be interested to know whether any other languages allow the same sort of concepts to be expressed more pleasantly. The ugly solution I've presented here does at least work, and it's nearly invisible to most users, who are likely to just reference the concrete generated types. I'm not happy with the verbosity which has become necessary in many places, but it's in a good cause. It's interesting to note that the Java API doesn't use this sort of doubly-generic relationship: again, covariant return types allow the concrete message and builder types to express their APIs directly and still implement a more general interface at the same time.

In the next part I'll look at another possibility which would make interfaces and generics a more powerful combination: static interface methods.

Lessons learned from Protocol Buffers, part 2: self-referential generic types

skeet — Wed, 20 Aug 2008 20:37:27 GMT

In the first part of this series we saw that a message type and its builder are closely related. The tricky bit comes when we want to define an interface describing messages and builders. Although some members clearly depend on the data being built (the first and last name in the person example above, for instance) others apply to all messages or all builders. For instance, a message can always provide you with a suitable builder, and a builder always allows you to build it to create the actual message. Likewise the message and builder types also have methods which return other instances of themselves - you can ask any message for the default message of the same type, or clone a builder. Many common builder methods effectively return this (i.e. the same builder) - but the declared return type needs to be the concrete type involved, not just the interface, otherwise you couldn't then use the returned builder to set properties without casting.

(Aside: some of the members of the common interface would be more pleasant if they could be declared statically. We'll look at that later in the series.)

We have two slightly different issues here: defining the interface to allow members to return the concrete types, and tying builders and messages together. This post will just talk about the first of these issues. Enjoy the luxury of only having to think about one type parameter at a time - it won't last long.

First encounters of the self-referential kind

I first came across a generic constraint which referred to itself back in the early days of Java 5. Here's the declaration for java.lang.Enum:

public abstract class Enum<E extends Enum<E>>

Assuming you're more comfortable in C#, I'll translate that into C# syntax:

public abstract class Enum<T> where T : Enum<T>

The constraint is easier read than understood. Any concrete, constructed class deriving from this will be an "enum of something" where something itself an "enum of something".

Now, Java puts additional restrictions on the Enum class (it's like System.Delegate in C# - you can't explicitly derive from it yourself; you have to let the compiler do it for you). However, the syntax is perfectly valid in "normal" code. Typically when you encounter this kind of type constraint, you satisfy it in new classes by using the same class as the type argument for T. So, in the Enum example we might have:

public sealed class Currency : Enum<Currency>
{
// Code
}

public sealed class Status : Enum<Status>
{
// Code
}

There's nothing to actually stop you from declaring class Status : Enum<Currency> - it's not just not normally useful. Likewise you can leave the derived type as a generic one, but again that's atypical. I don't know any way to enforce the usual implementation - short of building into the language, as Java did - but it's generally not a problem.

Back to Protocol Buffers

So why is this useful? Well, moving on from enums let's look at the builder interface in Protocol Buffers. Here's part of it - somewhat simplified, admittedly:

public interface IBuilder<TBuilder> where TBuilder : IBuilder<TBuilder>
{
    TBuilder Clear();
    TBuilder Clone();
    TBuilder ClearField(FieldDescriptor field);
    TBuilder AddRepeatedField(FieldDescriptor field, object value);
    TBuilder SetUnknownFields(UnknownFieldSet unknownFields);
    TBuilder MergeUnknownFields(UnknownFieldSet unknownFields);
    TBuilder MergeFrom(ByteString data);
    TBuilder MergeFrom(CodedInputStream input);
    TBuilder MergeFrom(CodedInputStream input, ExtensionRegistry registry);
}

None of those methods mention the actual message directly - for that we need another type parameter, as we'll see in the next post - but all of them return a TBuilder. As it happens, the interface documentation requires that all the methods return the same reference back, just as StringBuilder methods do, but you could equally create an interface around immutable types, expecting each operation to return a new value. For instance, you could create an IArithmetic<T> interface such that int could implement IArithmetic<int>, double could implement IArithmetic<double> etc. You can then chain multiple operations together, e.g. 5.Add(10).Multiply(2) and know that you're always within the world of integers.

It's important to note that the return type of each of the methods in our builder interface is TBuilder, not IBuilder<TBuilder>. I point this out mostly because the latter is what I originally had. After all, it's often best to expose fairly general return types. That works fine while you're only using operations within the interface, but often clients know more detail about the concrete type and want to use that information. For instance, you might want to be able to write:

Person.Builder builder = ...; // Get a builder from somewhere
builder = builder.Clear()
                 .SetFirstName("Fred")
                 .SetLastName("Jones")
                 .Clone();

Here SetFirstName() and SetLastName() aren't members of the interface, but Clear() and Clone() are. We can mix and match like this (and finally reassign the builder variable) because the interface is as strongly typed as it is. Code which only knows about the interface can still do whatever it likes, because it knows that TBuilder implements IBuilder<TBuilder>. In particular, that means it's fine for some of the interface to be implemented by an abstract class - in Protocol Buffers there can be quite a deep inheritance tree for messages and builders, and a lot of the methods (particularly the merging ones) can be written in terms of the others. (Yes, that suggests that an extension method might be appropriate - but leaving it in the interface allows for particular implementations to override the general one, which can be important for optimisation. There's also the matter of making the whole thing play nicely for people who are still stuck with .NET 2.0 and Visual Studio 2005.)

A small diversion via Java

It's interesting to note that while my C# port is larely a port of the Java code, there are significant differences around how generics are used. This is understandable given how different generics are in .NET and Java. (My preference being heavily towards the .NET side - but there are moments when Java has its advantages.) However, one aspect of Java which is used to great effect is covariant return types. In the Java protocol buffers, the Message and Builder interfaces aren't generic at all. For instance, the equivalent of the earlier part of the builder interface is just this:

public interface Builder
{
    Builder clear();
    Builder clone();
    Builder clearField(FieldDescriptor field);
    Builder addRepeatedField(FieldDescriptor field, object value);
    Builder setUnknownFields(UnknownFieldSet unknownFields);
    Builder mergeUnknownFields(UnknownFieldSet unknownFields);
    Builder mergeFrom(ByteString data);
    Builder mergeFrom(CodedInputStream input);
    Builder mergeFrom(CodedInputStream input, ExtensionRegistry registry);
}

Does that mean we can't chain operations together any more, mixing and matching "concrete-type-specific" methods (such as the setters for first name and last name) with the interface methods? Not at all - because where Person.Builder implements (say) clear() it can do it like this:

Person.Builder clear()
{
// Implementation
return this;
}

At that point, everything which knows at compile-time that it's calling Person.Builder.clear() knows that it returns a Person.Builder - whereas code which only knows that it's calling the interface method only knows that it will return some implementation of the interface. (Apologies for the naming here - it's unfortunate from a clarity standpoint that both the interface and the implementation is called Builder, but I thought it would be worth being faithful to the real code on this point.)

It's just about possible to do this in C# as well, with explicit interface implementation. Again, I went that way to start with - and it was a disaster. In the intermediate abstract classes I was having to cast to the interface sometimes, not cast at other times, declare new abstract protected methods of ClearImpl etc. It was simply awful. I've gone back to my school of thought which is that explicit interface implementation is handy when it's absolutely required (or where you deliberately want to make it hard to call certain members), but should be largely avoided.

In fact, I do have a non-generic interface for both messages and builders, but where types would be involved I've renamed the methods to things like WeakClear and WeakBuild. These Weak* methods are only defined in terms of the non-generic interfaces, and are mostly used in cases where we really don't know at compile time what kind of message we're dealing with, even in a generic sense. Life would, however, be much simpler if only we had covariant return types in C#.

Conclusion

Self-referential generic types shouldn't be used more widely than they really need to be - they can be tough to get your head round. However, they can be useful when you want to maintain a strongly typed API which needs to talk in terms of itself. One redeeming feature of the complexity in Protocol Buffers is that most of it is in the implementation: users of Person and Person.Builder really don't need to know or care about the interfaces for most of the time. So long as they use a strongly typed expression to start with, they'll keep that strong typing and be presented with appropriate members to call as if the interfaces and intermediate abstract classes didn't even exist. It's an API which gets out of your way when you're not interested in it, which is always a nice sign.

While trying a number of schemes I've learned that there can often be a lot of subtly different options available, and their benefits and drawbacks aren't always obvious until you try them. Oh, and covariant return types would be very welcome, and explicit interface implementation should generally be avoided where possible :)

Next time I'll reveal a bit more about the real interfaces in my PB port. Bear in mind that messages need to know about their builders, and vice versa...

Lessons learned from Protocol Buffers, part 1: messages, builders and immutability

skeet — Wed, 20 Aug 2008 16:31:00 GMT

My port of the Protocol Buffers project has proved pretty interesting. I thought I'd share some of the lessons I've learned along the way, as well as some of the frustrations at concepts I still can't express in C#.

This was originally all going to be in one post, but I'm becoming acutely aware of how long some posts can grow. I don't know about you, but I find very long blog posts quite intimidating, so I've decided to split them up into individual topics. You'll still probably need to read the posts in order to understand them though - and this introductory post is the most important one in that respect.

Messages and Builders

The Protocol Buffers project (or PB for short) is basically another serialization technology, putting emphasis on efficiency, platform neutrality, and backward/forward compatibility. The normal set of steps in using PB is something like this:

Write a .proto file describing your data in terms of messages.
Run protoc to generate C# (and Java/C++ if you so wish).
In your application, use the builder associated with the message type to create an instance of a message.
Serialize the data to a stream.
At some other point in the application (or a different app) deserialize the data.

The idea is that builders are mutable, while the messages they build are immutable. You can use builders either with Set* methods which return the same builder again, or properties which can be used within object initializers. For example:

// Syntax available in C# 2
Person john = new Person.Builder()
    .SetFirstName("John")
    .SetLastName("Doe")
    .Build();

// Using an object initializer
Person jane = new Person.Builder
    { FirstName="Jane", LastName="Doe" }
    .Build();

Of course, you don't have to do all the building in one expression, it's just a handy option in many cases.

As you can see, the builder is generated as a nested type of the message. That's handy, as it means the builder has access to the private members of the message. To avoid lots of data copying we employ popsicle immutability - the builder directly manipulates the message until it's built, at which point it makes sure that nothing will change it afterwards. If that makes you uncomfortable in terms of it not being "true" immutability, I sympathise - but I also give String as a counterexample; StringBuilder works in exactly this way, modifying a string directly until it exposes it to the outside world.

Other than the copying - and the fact that all the code exists explicitly, and the caller has to know about the builder - this is quite similar to the suggestion I made about C# immutability a while ago. One point which makes it all simpler is that every data type in Protocol Buffers is itself immutable - so we don't need to worry about deep copies and the like.

Unfortunately the current implementation doesn't support collection initializers - if you have a repeated field in your message, you have to call Add* to populate it. The Add* methods return the builder just like the Set* methods, so you can still do it all in one expression, but it's not terribly neat. Using a collection initializer compiles, but fails at execution time because the properties for repeated fields always return immutable lists. This is by design, to stop callers from creating a builder, fetching the list property, calling Build and then adding to the list. A better solution (and one which I plan to implement soon) is to have a PopsicleList<T> which is initially mutable but which will become immutable at the appropriate time (i.e. when Build() is called). At that point we'll be able to write:

Person jane = new Person.Builder
    { FirstName="Jane", LastName="Doe",
      Friends = { "Tom", "", "Harry" } }
    .Build();

There's quite a lot more to messages and builders than this - things like the reflection-like API to query properties of the message based on fields in the the message descriptor - but what I've described so far ought to be enough for most of what I want to talk about, most of which relates to generics. In the next part, I'll talk about self-referential generic types.