Jon Skeet: Coding Blog

The perils of conditional mutability

skeet — Sun, 06 May 2012 13:58:45 GMT

This morning I was wrestling with trying to make some Noda Time unit tests faster. For some reason, the continuous integration host we're using is really slow at loading resources under .NET 4. The unit tests which run in 10 seconds on my home laptop take over three hours on the continuous integration system. Taking stack traces at regular intervals showed the problem was with the NodaFormatInfo constructor, which reads some resources.

I may look into streamlining the resource access later, but before we get to that point, I wanted to try to reduce the number of times we call that constructor in the first place. NodaFormatInfo is meant to be cached, so I wouldn't have expected thousands of instances to be created - but it's only cached when the System.Globalization.CultureInfo it's based on is read-only. This is where the problems start...

CultureInfo is conditionally mutable (not an official term, just one I've coined for the purposes of this post). You can ask whether or not it's read-only with the IsReadOnly property, and obviously if it's read-only you can't change it. Additionally, CultureInfo is composed of other conditionally mutable objects - DateTimeFormatInfo, NumberFormatInfo etc. There's a static ReadOnly method on CultureInfo to create a read-only wrapper around a mutable CultureInfo. It's not clearly documented whether that's expected to take a deep copy (so that callers can really rely on it not changing) or whether it's expected to reflect any further changes made to the culture info it's based on. To go in the other direction, you can call Clone on a CultureInfo to create a mutable copy of any existing culture.

Further complications are introduced by the properties on the composite objects - we have properties such as DateTimeFormatInfo.MonthNames which returns a string array. Remember, arrays are always mutable. So it's really important to know whether the array reference returned from the property refers to a copy of the underlying data, or whether it refers to the array that's used internally by the type. Obviously for read-only DateTimeFormatInfo objects, I'd expect a copy to be returned - but for a mutable DateTimeFormatInfo, it would potentially make sense to return the underlying array reference. Unfortunately, the documentation doesn't make this clear - but in practice, it always returns a copy. If you need to change the month names, you need to clone the array, mutate the clone, and then set the MonthNames property.

All of this makes CultureInfo hard to work with. The caching decision earlier on only really works if a "read-only" culture genuinely won't change behind the scenes. The type system gives you no help to catch subtle bugs at compile-time. Making any of this robust but efficient (in terms of taking minimal copies) is tricky to say the least.

Not only does it make it hard to work with from a client's point of view, but apparently it's hard to implement correctly too...

First bug: Mono's invariant culture isn't terribly invariant...

(Broken in 2.10.8; apparently fixed later.)

I discovered this while getting Noda Time's unit tests to pass on Mono. Unfortunately there are some I've had to effectively disable at the moment, due to deficiencies in Mono (some of which are being fixed, of course).

Here's a program which builds a clone of the invariant culture, changes the clone's genitive month names, and then prints out the first non-genitive name from the plain invariant culture:

using System;
using System.Globalization;

class Test
{
    static void Main()
    {
        CultureInfo clone = (CultureInfo) CultureInfo.InvariantCulture.Clone();
        // Note: not even deliberately changing MonthNames for this culture!
        clone.DateTimeFormat.MonthGenitiveNames[0] = "Changed";

        // Prints Changed
        Console.WriteLine(CultureInfo.InvariantCulture.DateTimeFormat.MonthNames[0]);
    }
}

I believe this bug is really due to the lack of support for genitive month names in Mono at the moment - the MonthGenitiveNames property always just returns a reference to the month names for the invariant culture - without taking a copy first. (It always returns the invariant culture's month names, even if you're using a different culture entirely.) The code above shows an "innocent" attempt to change a mutable clone - but in reality we could have used any culture (including an immutable one) to make the change.

Note that in the .NET implementation, the change would only have been to a copy of the underlying data, so even the clone wouldn't have reflected change anywhere.

Second bug: ReadOnly losing changes

The second bug is the one I found this morning. It looks like it's fixed in .NET 4, but it's present in .NET 3.5, which is where it bit me this morning. When you try to make a read-only wrapper around a mutated culture, some of the properties are preserved... but some aren't:

using System;
using System.Globalization;

class Test
{
    static void Main()
    {
        CultureInfo clone = (CultureInfo) CultureInfo.InvariantCulture.Clone();
        clone.DateTimeFormat.AMDesignator = "ChangedAm";

        // The array is recreated on each call to MonthNames, so changing the
        // value within the array itself doesn't work :(
        string[] months = (string[]) clone.DateTimeFormat.MonthNames;
        months[0] = "ChangedMonth";
        clone.DateTimeFormat.MonthNames = months;

        CultureInfo readOnlyCopy = CultureInfo.ReadOnly(clone);
        Console.WriteLine(clone.DateTimeFormat.AMDesignator); // ChangedAm
        Console.WriteLine(clone.DateTimeFormat.MonthNames[0]); // ChangedMonth

        Console.WriteLine(readOnlyCopy.DateTimeFormat.AMDesignator); // ChangedAm
        Console.WriteLine(readOnlyCopy.DateTimeFormat.MonthNames[0]); // January (!)
    }
}

I don't know what's going on here. In the end I just left the test code using the mutable clone, having added a comment explaining why it wasn't created a read-only wrapper.

I've experimented with a few different options here, including setting the MonthNames property on the clone after creating the wrapper. No joy - I simply can't make the new month names stick in the read-only copy. <sigh>

Conclusion

I've been frustrated by the approach we've taken to cultures in Noda Time for a while. I haven't worked out exactly what we should do about it yet, so it's likely to stay somewhat annoying for v1, but I may well revisit it significantly for v2. Unfortunately, there's nothing I can do about CultureInfo itself.

What I would have preferred in all of this is the builder pattern: make CultureInfo, DateTimeFormatInfo etc all immutable, but give each of them mutable builder types, with the ability to create a mutable builder based on an existing immutable instance, and obviously to create a new immutable instance from a builder. That would make all kinds of things simpler - including caching.

For the moment though, I hope we can all learn lessons from this - or have old lessons reinforced, at least:

Making a single type behave in different ways based on different "modes" makes it hard to use correctly. (Yes, this is the same first conclusion as with DateTime in the previous post. Funny, that.)
Immutability has to be deep to be meaningful: it's not much use having a supposedly read-only object which composes a StringBuilder...
Arrays should be considered somewhat harmful. If you're going to return an array from a method, make sure you document whether this is a copy of the underlying data, or a "live" reference. (The latter should be very rare, particularly for a public API.) The exception here is if you return an empty array - that's effectively immutable, so you can always return it with no problems.
The builder pattern rocks - use it!

In my next post I'll try to get back to the TimeZoneInfo oddities I mentioned last time.

More fun with DateTime

skeet — Wed, 02 May 2012 20:12:43 GMT

(Note that this is deliberately not posted in the Noda Time blog. I reckon it's of wider interest from a design perspective, and I won't be posting any of the equivalent Noda Time code. I'll just say now that we don't have this sort of craziness in Noda Time, and leave it at that...)

A few weeks ago, I was answering a Stack Overflow question when I noticed an operation around dates and times which should have been losing information apparently not doing so. I investigated further, and discovered some "interesting" aspects of both DateTime and TimeZoneInfo. In an effort to keep this post down to a readable length (at least for most readers; certain WebDriver developers who shall remain nameless have probably given up by now already) I'll save the TimeZoneInfo bits for another post.

Background: daylight saving transitions and ambiguous times

There's one piece of inherent date/time complexity you'll need to understand for this post to make sense: sometimes, a local date/time occurs twice. For the purposes of this post, I'm going to assume you're in the UK time zone. On October 28th 2012, at 2am local time (1am UTC), UK clocks will go back to 1am local time. So 1:20am local time occurs twice - once at 12:20am UTC (in daylight saving time, BST), and once at 1:20am UTC (in standard time, GMT).

If you want to run any of the code in this post and you're not in the UK, please adjust the dates and times used to a similar ambiguity for when your clocks go back. If you happen to be in a time zone which doesn't observe daylight savings, I'm afraid you'll have to adjust your system time zone in order to see the effect for yourself.

DateTime.Kind and conversions

As you may already know, as of .NET 2.0, DateTime has a Kind property, of type DateTimeKind - an enum with the following values:

Local: The DateTime is considered to be in the system time zone. Not an arbitrary "local time in some time zone", but in the specific current system time zone.
Utc: The DateTime is considered to be in UTC (corollary: it always unambiguously represents an instant in time)
Unspecified: This means different things in different contexts, but it's a sort of "don't know" kind; this is closer to "local time in some time zone" which is represented as LocalDateTime in Noda Time.

DateTime provides three methods to convert between the kinds:

ToUniversalTime: if the original kind is Local or Unspecified, convert it from local time to universal time in the system time zone. If the original kind is Utc, this is a no-op.
ToLocalTime: if the original kind is Utc or Unspecified, convert it from UTC to local time. If the original kind is Local, this is a no-op.
SpecifyKind: keep the existing date/time, but just change the kind. (So 7am stays as 7am, but it changes the meaning of that 7am effectively.)

(Prior to .NET 2.0, ToUniversalTime and ToLocalTime were already present, but always assumed the original value needed conversion - so if you called x.ToLocalTime().ToLocalTime().ToLocalTime() the result would probably end up with the appropriate offset from UTC being applied three times!)

Of course, none of these methods change the existing value - DateTime is immutable, and a value type - instead, they return a new value.

DateTime's Deep Dark Secret

(The code in this section is presented in several chunks, but it forms a single complete piece of code - later chunks refer to variables in earlier chunks. Put it all together in a Main method to run it.)

Armed with the information in the previous sections, we should be able to make DateTime lose data. If we start with 12:20am UTC and 1:20am UTC on October 28th as DateTimes with a kind of Utc, when we convert them to local time (on a system in the UK time zone) we should get 1:20am in both cases due to the daylight saving transition. Indeed, that works:

// Start with different UTC values around a DST transition
var original1 = new DateTime(2012, 10, 28, 0, 20, 0, DateTimeKind.Utc);
var original2 = new DateTime(2012, 10, 28, 1, 20, 0, DateTimeKind.Utc);

// Convert to local time
var local1 = original1.ToLocalTime();
var local2 = original2.ToLocalTime();

// Result is the same for both values. Information loss?
var expected = new DateTime(2012, 10, 28, 1, 20, 0, DateTimeKind.Local);
Console.WriteLine(local1 == expected); // True
Console.WriteLine(local2 == expected); // True
Console.WriteLine(local1 == local2); // True

If we've started with two different values, applied the same operation to both, and ended up with equal values, then we must have lost information, right? That doesn't mean that operation is "bad" any more than "dividing by 2" is bad. You ought to be aware of that information loss, that's all.

So, we ought to be able to demonstrate that information loss further by converting back from local time to universal time. Here we have the opposite problem: from our local time of 1:20am, we have two valid universal times we could convert to - either 12:20am UTC or 1:20am UTC. Both answers would be correct - they are universal times at which the local time would be 1:20am. So which one will get picked? Well... here's the surprising bit:

// Convert back to UTC
var roundTrip1 = local1.ToUniversalTime();
var roundTrip2 = local2.ToUniversalTime();

// Values round-trip correctly! Information has been recovered...
Console.WriteLine(roundTrip1 == original1); // True
Console.WriteLine(roundTrip2 == original2); // True
Console.WriteLine(roundTrip1 == roundTrip2); // False

Somehow, each of the local values knows which universal value it came from. The The information has been recovered, so the reverse conversion round-trips each value back to its original one. How is that possible?

It turns out that DateTime actually has four potential kinds: Local, Utc, Unspecified, and "local but treat it as the earlier option when resolving ambiguity". A DateTime is really just a 64-bit number of ticks, but because the range of DateTime is only January 1st 0001 to December 31st 9999. That range can be represented in 62 bits, leaving 2 bits "spare" to represent the kind. 2 bits gives 4 possible values... the three documented ones and the shadowy extra one.

Through experimentation, I've discovered that the kind is preserved if you perform arithmetic on the value, too... so if you go to another "fall back" DST transition such as October 30th 2011, the ambiguity resolution works the same way as before:

var local3 = local1.AddYears(-1).AddDays(2);
var local4 = local2.AddYears(-1).AddDays(2);
Console.WriteLine(local3.ToUniversalTime().Hour); // 0
Console.WriteLine(local4.ToUniversalTime().Hour); // 1

If you use DateTime.SpecifyKind with DateTimeKind.Local, however, it goes back to the "normal" kind, even though it looks like it should be a no-op:

// Should be a no-op?
var local5 = DateTime.SpecifyKind(local1, local1.Kind);
Console.WriteLine(local5.ToUniversalTime().Hour); // 1

Is this correct behaviour? Or should it be a no-op, just like calling ToLocalTime on a "local" DateTime is? (Yes, I've checked - that doesn't lose the information.) It's hard to say, really, as this whole business appears to be undocumented... at least, I haven't seen anything in MSDN about it. (Please add a link in the comments if you find something. The behaviour actually goes against what's documented, as far as I can tell.)

I haven't looked into whether various forms of serialization preserve values like this faithfully, by the way - but you'd have to work hard to reproduce it in non-framework code. You can't explicitly construct a DateTime with the "extra" kind; the only ways I know of to create such a value are via a conversion to local time or through arithmetic on a value which already has the kind. (Admittedly if you're serializing a DateTime with a Kind of Local, you're already on potentially shaky ground, given that you could be deserializing it on a machine with a different system time zone.)

Unkind comparisons

I've misled you a little, I have to admit. In the code above, when I compared the "expected" value with the results of the first conversions, I deliberately specified DateTimeKind.Local in the constructor call. After all, that's the kind we do expect. Well, yes - but I then printed the result of comparing this value with local1 and local2... and those comparisons would have been the same regardless of the kind I'd specified in the constructor.

All comparisons between DateTimes ignore the Kind property. It's not just restricted to equality. So for example, consider this comparison:

// In June: Local time is UTC+1, so 8am UTC is 9am local
var dt1 = new DateTime(2012, 6, 1, 8, 0, 0, DateTimeKind.Utc);
var dt2 = new DateTime(2012, 6, 1, 8, 30, 0, DateTimeKind.Local);
Console.WriteLine(dt1 < dt2); // True

When viewed in terms of "what instants in time do these both represent?" the answer here is wrong - when you convert both values into the same time zone (in either direction), dt1 occurs after dt2. But a simple look at the properties tells a different story. In practice, I suspect that most comparisons between DateTime values of different kinds involve code which is at best sloppy and is quite possibly broken in a meaningful way.

Of course, if you bring Kind=Unspecified into the picture, it becomes impossible to compare meaningfully in a kind-sensitive way. Is 12am UTC before or after 1am Unspecified? It depends what time zone you later use.

To be clear, it is a hard-to-resolve issue, and one that we don't do terribly well at in Noda Time at the moment for ZonedDateTime. (And even with just LocalDateTime you've got issues between calendars.) This is a situation where providing separate Comparer<T> implementations works nicely - so you can explicitly say what kind of comparison you want.

Conclusions

There's more fun to be had with a similar situation when we look at TimeZoneInfo, but for now, a few lessons:

Giving a type different "modes" which make it mean fairly significantly different things is likely to cause headaches
Keeping one of those modes secret (and preventing users from even constructing a value in that mode directly) leads to even more fun and games
If two instances of your type are considered "equal" but behave differently, you should at least consider whether there's something smelly going on
There's always more fun to be had with DateTime...

Type initializer circular dependencies

skeet — Sat, 07 Apr 2012 09:35:45 GMT

To some readers, the title of this post may induce nightmarish recollections of late-night debugging sessions. To others it may be simply the epitome of jargon. Just to break the jargon down a bit:

Type initializer: the code executed to initialize the static variables of a class, and the static constructor
Circular dependency: two bits of code which depend on each other - in this case, two classes whose type initializers each require that the other class is initialized

A quick example of the kind of problem I'm talking about would be helpful here. What would you expect this code to print?

using System;

class Test
{
    static void Main()
    {
        Console.WriteLine(First.Beta);
    }
}

class First
{
    public static readonly int Alpha = 5;
    public static readonly int Beta = Second.Gamma;
}

class Second
{
    public static readonly int Gamma = First.Alpha;
}

Of course, without even glancing at the specification, any expectations are pretty irrelevant. Here's what the spec (section 10.5.5.1 of the C# 4 version):

The static field variable initializers of a class correspond to a sequence of assignments that are executed in the textual order in which they appear in the class declaration. If a static constructor (§10.12) exists in the class, execution of the static field initializers occurs immediately prior to executing that static constructor. Otherwise, the static field initializers are executed at an implementation-dependent time prior to the first use of a static field of that class.

In addition to the language specification, the CLI specification gives more details about type initialization in the face of circular dependencies and multiple threads. I won't post the details here, but the gist of it is:

Type initialization acts like a lock, to prevent more than one thread from initializing a type
If the CLI notices that type A needs to be initialized in order to make progress, but it's already in the process of initializing type A in the same thread, it continues as if the type were already initialized.

So here's what you might expect to happen:

Initialize Test: no further action required
Start running Main
Start initializing First (as we need First.Beta)
Set First.Alpha to 5
Start initializing Second (as we need Second.Gamma)
Set Second.Gamma to First.Alpha (5)
End initializing Second
Set First.Beta to Second.Gamma (5)
End initializing First
Print 5

Here's what actually happens - on my box, running .NET 4.5 beta. (I know that type initialization changed for .NET 4, for example. I don't know of any changes for .NET 4.5, but I'm not going to claim it's impossible.)

Initialize Test: no further action required
Start running Main
Start initializing First (as we need First.Beta)
Start initializing Second (we will need Second.Gamma)
Set Second.Gamma to First.Alpha (0)
End initializing Second
Set First.Alpha to 5
Set First.Beta to Second.Gamma (0)
End initializing First
Print 0

Step 5 is the interesting one here. We know that we need First to be initialized, in order to get First.Alpha, but this thread is already initializing First (we started in step 3) so we just access First.Alpha and hope that it's got the right value. As it happens, that variable initializer hasn't been executed yet. Oops.

(One subtlety here is that I could have declared all these variables as constants instead using "const" which would have avoided all these problems.)

Back in the real world...

Hopefully that example makes it clear why circular dependencies in type initializers are nasty. They're hard to spot, hard to debug, and hard to test. Pretty much your classic Heisenbug, really. It's important to note that if the program above had happened to initialize Second first (to access a different variable, for example) we could have ended up with a different result. In particular, it's easy to get into a situation where running all your unit tests can cause a failure - but if you run just the failing test, it passes.

One way of avoiding all of this is never to use any type initializers for anything, of course. In many cases that's exactly the right solution - but often there are natural uses, particularly for well-known values such as Encoding.Utf8, TimeZoneInfo.Utc and the like. Note that in both of those cases they are static properties, but I would expect them to be backed by static fields. I'm somewhat ambivalent between using public static readonly fields and public static get-only properties - but as we'll see later, there's a definite advantage to using properties.

Noda Time has quite a few values like this - partly because so many of its types are immutable. It makes sense to create a single UTC time zone, a single ISO calendar system, a single "pattern" (text formatter/parser) for each of a variety of common cases. In addition to the publicly visible values, there are various static variables used internally, mostly for caching purposes. All of this definitely adds complexity - and makes it harder to test - but the performance benefits can be significant.

Unfortunately, a lot of these values end up with fairly natural circular dependencies - as I discovered just recently, where adding a new static field caused all kinds of breakage. I was able to fix the immediate cause, but it left me concerned about the integrity of the code. I'd fixed the one failure I knew about - but what about any others?

Testing type initialization

One of the biggest issues with type initialization is the order-sensitivity - combined with the way that once a type has been initialized once, that's it for that AppDomain. As I showed earlier, it's possible that initializing types in one particular order causes a problem, but a different order won't.

I've decided that for Noda Time at least, I want to be reasonably sure that type initialization circularity isn't going to bite me. So I want to validate that no type initializers form cycles, whatever order the types are initialized in. Logically if we can detect a cycle starting with one type, we ought to be able to detect it starting with any of the other types in that cycle - but I'm sufficiently concerned about weird corner cases that I'd rather just take a brute force approach.

So, as a rough plan:

Start with an empty set of dependencies
For each type in the target assembly:
- Create a new AppDomain
- Load the target assembly into it
- Force the type to be initialized
- Take a stack trace at the start of each type initializer and record any dependencies
Look for cycles in the complete set of dependencies

Note that we'll never spot a cycle within any single AppDomain, due to the way that type initialization works. We have to put together the results for multiple initialization sequences to try to find a cycle.

A description of the code would probably be harder to follow than the code itself, but the code is relatively long - I've included it at the end of this post to avoid intefering with the narrative flow. For more up-to-date versions in the future, look at the Noda Time repository.

This isn't a terribly nice solution, for various reasons:

Creating a new AppDomain and loading assemblies into it from a unit test runner isn't as simple as it might be. My code doesn't currently work with NCrunch; I don't know how it finds its assemblies yet. When I've fixed that, I'm sure other test runners would still be broken. Likewise I've had to explicitly filter types to get TeamCity (the continuous integration system Noda Time uses) to work properly. Currently, you'd need to edit the test code to change the filters. (It's possible that there are better ways of filtering, of course.)
It relies on each type within the production code which has an "interesting" type initializer to have a line like this:
private static readonly int TypeInitializationChecking = NodaTime.Utility.TypeInitializationChecker.RecordInitializationStart();
Not only does the previous line need to be added to the production code - it clearly gets executed each time, and takes up heap space per type. It's only 4 bytes for each type involved, and it does no real work when we're not testing, but it's a nuisance anyway. I could use preprocessor directives to remove the code from non-debug or non-test-targeted builds, but that would look even messier.
It only picks up cycles which occur when running the version of .NET the tests happen to execute on. Given that there are ordering changes for different versions, I wouldn't like to claim this is 100% bullet-proof. Likewise if there are only cycles when you're running in some specific cultures (or other environmental features), it won't necessarily pick those up.
I've deliberately not tried to make the testing code thread-safe. That's fine in Noda Time - I don't have any asynchronous operations or new threads in Noda Time at all - but other code may need to make this more robust.

So with all these caveats, is it still worth it? Absolutely: it's already found bugs which have now been fixed.

In fact, the test didn't get as far as reporting cycles to start with - it turned out that if you initialized one particular type first, the type initializer would fail with a NullReferenceException. Ouch! Once I'd fixed that, there were still quite a few problems to fix. Somewhat coincidentally, fixing them improved the design too - although the user-visible API didn't change at all.

Fixing type initializer cycles

In the past, I've occasionally "fixed" type initialization ordering problems by simply moving fields around. The cycles still existed, but I figured out how to make them harmless. I can say now that this approach does not scale, and is more effort than it's worth. The code ends up being brittle, hard to think about, and once you've got more than a couple of types involved it's really error-prone, at least for my brain. It's much better to break the cycle completely. To this end, I've ended up using a fairly simple technique to defer initialization of static variables. It's a poor-man's Lazy<T>, to some extent - but I'd rather not have to write Lazy<T> myself, and we're currently targeting .NET 3.5...

Basically, instead of exposing a public static readonly field which creates the cycle, you expose a public static readonly property - which returns an internal static readonly field in a nested, private static class. We still get the nice thread-safe once-only initialization of a type initializer, but the nested type won't be initialized until it needs to be. (In theory it could be initialized earlier, but a static constructor would ensure it isn't.) So long as nothing within the rest of the type initializer for the containing class uses that property, we avoid the cycle.

So instead of this:

// Requires Bar to be initialized - if Bar also requires Foo to be
// initialized, we have a problem...
public static readonly Foo SimpleFoo = new Foo(Bar.Zero);

We might have:

public static readonly Foo SimpleFoo { get { return Constants.SimpleFoo; } }

private static class Constants
{
    private static readonly int TypeInitializationChecking = NodaTime.Utility.TypeInitializationChecker.RecordInitializationStart();

    // This requires both Foo and Bar to be initialized, but that's okay
    // so long as neither of them require Foo.Constants to be initialized.
    // (The unit test would spot that.)
    internal static readonly Foo SimpleFoo = new Foo(Bar.Zero);
}

I'm currently undecided about whether to include static constructors in these classes to ensure lazy initialization. If the type initializer for Foo triggered the initializer of Foo.Constants, we'd be back to square one... but adding static constructors into each of these nested classes sounds like a bit of a pain. The nested classes should call into the type initialization checking as well, to validate they don't cause any problems themselves.

Conclusion

I have to say, part of me really doesn't like either the testing code or the workaround. Both smack of being clever, which is never a good thing. It's definitely worth considering whether you could actually just get rid of the type initializer (or part of it) entirely, avoiding maintaining so much static state. It would be nice to be able to detect these type initializer cycles without running anything, simply using static analysis - I'm going to see whether NDepend could do that when I get a chance. The workaround doesn't feel as neat as Lazy<T>, which is really what's called for here - but I don't trust myself to implement it correctly and efficiently myself.

So while both are somewhat hacky, they're better than the alternative: buggy code. That's what I'm ashamed to say I had in Noda Time, and I don't think I'd ever have spotted all the cycles by inspection. It's worth a try on your own code - see whether you've got problems lurking...

Appendix: Testing code

As promised earlier, here's the code for the production and test classes.

TypeInitializationChecker

This is in NodaTime.dll itself.

internal sealed class TypeInitializationChecker : MarshalByRefObject
{
    private static List<Dependency> dependencies = null;

    private static readonly MethodInfo EntryMethod = typeof(TypeInitializationChecker).GetMethod("FindDependencies");

    internal static int RecordInitializationStart()
    {
        if (dependencies == null)
        {
            return 0;
        }
        Type previousType = null;
        foreach (var frame in new StackTrace().GetFrames())
        {
            var method = frame.GetMethod();
            if (method == EntryMethod)
            {
                break;
            }
            var declaringType = method.DeclaringType;
            if (method == declaringType.TypeInitializer)
            {
                if (previousType != null)
                {
                    dependencies.Add(new Dependency(declaringType, previousType));
                }
                previousType = declaringType;
            }
        }
        return 0;
    }

    /// <summary>
    /// Invoked from the unit tests, this finds the dependency chain for a single type
    /// by invoking its type initializer.
    /// </summary>
    public Dependency[] FindDependencies(string name)
    {
        dependencies = new List<Dependency>();
        Type type = typeof(TypeInitializationChecker).Assembly.GetType(name, true);
        RuntimeHelpers.RunClassConstructor(type.TypeHandle);
        return dependencies.ToArray();
    }

    /// <summary>
    /// A simple from/to tuple, which can be marshaled across AppDomains.
    /// </summary>
    internal sealed class Dependency : MarshalByRefObject
    {
        public string From { get; private set; }
        public string To { get; private set; }
        internal Dependency(Type from, Type to)
        {
            From = from.FullName;
            To = to.FullName;
        }
    }
}

TypeInitializationTest

This is within NodaTime.Test:

[TestFixture]
public class TypeInitializationTest
{
    [Test]
    public void BuildInitializerLoops()
    {
        Assembly assembly = typeof(TypeInitializationChecker).Assembly;
        var dependencies = new List<TypeInitializationChecker.Dependency>();
        // Test each type in a new AppDomain - we want to see what happens where each type is initialized first.
        // Note: Namespace prefix check is present to get this to survive in test runners which
        // inject extra types. (Seen with JetBrains.Profiler.Core.Instrumentation.DataOnStack.)
        foreach (var type in assembly.GetTypes().Where(t => t.FullName.StartsWith("NodaTime")))
        {
            // Note: this won't be enough to load the assembly in all test runners. In particular, it fails in
            // NCrunch at the moment.
            AppDomainSetup setup = new AppDomainSetup { ApplicationBase = AppDomain.CurrentDomain.BaseDirectory };
            AppDomain domain = AppDomain.CreateDomain("InitializationTest" + type.Name, AppDomain.CurrentDomain.Evidence, setup);
            var helper = (TypeInitializationChecker)domain.CreateInstanceAndUnwrap(assembly.FullName,
                typeof(TypeInitializationChecker).FullName);
            dependencies.AddRange(helper.FindDependencies(type.FullName));
        }
        var lookup = dependencies.ToLookup(d => d.From, d => d.To);
        // This is less efficient than it might be, but I'm aiming for simplicity: starting at each type
        // which has a dependency, can we make a cycle?
        // See Tarjan's Algorithm in Wikipedia for ways this could be made more efficient.
        // http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
        foreach (var group in lookup)
        {
            Stack<string> path = new Stack<string>();
            CheckForCycles(group.Key, path, lookup);
        }
    }

    private static void CheckForCycles(string next, Stack<string> path, ILookup<string, string> dependencyLookup)
    {
        if (path.Contains(next))
        {
            Assert.Fail("Type initializer cycle: {0}-{1}", string.Join("-", path.Reverse().ToArray()), next);
        }
        path.Push(next);
        foreach (var candidate in dependencyLookup[next].Distinct())
        {
            CheckForCycles(candidate, path, dependencyLookup);
        }
        path.Pop();
    }
}

Diagnosing weird problems - a Stack Overflow case study

skeet — Fri, 16 Mar 2012 06:31:00 GMT

Earlier, I came across this Stack Overflow question. I solved it, tweeted it, but then thought it would serve as a useful case study into the mental processes I go through when trying to solve a problem - whether that's on Stack Overflow, at work, or at home.

It's definitely worth reading the original question, but the executive summary is:

When I compute the checksum/hash of c:\Windows\System32\Calc.exe using various tools and algorithms, those tools all give the same answer for each algorithm. When I try doing the same thing in Java, I get different results. What's going on?

Now to start with, I'd like to shower a bit of praise on the author:

The post came with a short but utterly complete program to demonstrate the problem
The comments in the program showed the expected values and the actual values
The code was mostly pretty clean (clean enough for an SO post anyway)

In short, it had pretty much everything I ask for in a question. Yay! Additionally, the result seemed to be strange. The chances of any one of Java's hashing algorithms being broken seem pretty slim, but four of them? Okay, now you've got me interested.

Reproducing the problem

Unless I can spot the error immediately, I usually try to reproduce the problem in a Stack Overflow post with a short but complete program. In this case, the program was already provided, so it was just a matter of copy/paste/compile/run. This one had the additional tweak that it was comparing the results of Java with the results of other tools, so I had to get hold of an MD5 sum tool first. (I chose to start with MD5 for no particular reason.) I happened to pick this one, but it didn't really seem it would make much difference. (As it happens, that was an incorrect assumption, but hey...)

I ran md5sums on c:\Windows\System32\calc.exe, and got the same result as the poster. Handy.

I then ran the Java code, and again got the same result as the poster: step complete, we have a discrepancy between at least one tool (and MD5 isn't that hard to get right) and Java.

Looking for obvious problems

The code has four main areas:

Reading a file
Updating digests
Converting bytes to hex
Storing and displaying results

Of these, all of the first three have common and fairly simple error modes. For example:

Failure to use the return value from InputStream.read()
Failure to update the digests using only the relevant portion of the data buffer
Failure to cope with Java's signed bytes

The code for storing and displaying results seemed solid enough to ignore to start with, and brief inspection suggested that the first two failure modes had been avoided. While the hex code didn't have any obvious problems either, it made sense to check it. I simply printed the result of hard-coding the "known good" CRC-32 value:

System.out.println(toHex(new byte[] {
(byte) 0x8D, (byte) 0x8F, (byte) 0x5F, (byte) 0x8E
}));

That produced the right result, so I ruled out that part of the code too. Even if it had errors in some cases, we know it's capable of producing the right string for one of the values we know we should be returning, so it can't be getting that value.

Initial checks around the file

I'm always suspicious of stream-handling code - or rather, I know how easily it can hide subtle bugs. Even though it looked okay, I thought I'd check - so I added a simple total to the code so I could see how many bytes had been hashed. I also removed all the hash algorithms other than MD5, just for simplicity:

MessageDigest md5 = MessageDigest.getInstance("MD5");

FileInputStream fis = new FileInputStream(file);
byte data[] = new byte[size];
int len = 0;
int total = 0;
while ((len = fis.read(data)) != -1) {
md5.update(data, 0, len);
total += len;
}
fis.close();
System.out.println("Total bytes read: " + total);

results.put(md5.getAlgorithm(), toHex(md5.digest()));

It's worth noting that I haven't tried to fix up bits of the code which I know I would change if I were actually doing a code review:

The stream isn't being closed in a finally block, so we'll have a dangling resource (until GC) if an IOException is thrown
The initial value of len is never read, and can be removed

Neither of these matters in terms of the problem at hand, and closing the file "properly" would make the sample code more complicated. (For the sake of just a short sample program, I'd be tempted to remove it entirely.)

The result showed the number of bytes being read as the command prompt did when I ran "dir c:\Windows\System32\Calc.exe" - so again, everything looks like it's okay.

Desperate times call for stupid measures

Just on a whim, I decided to copy Calc.exe to a local folder (the current directory) and retry. After all, accessing a file in a system folder might have some odd notions applied to it. It's hard to work out what, but... there's nothing to lose just by trying a simple test. If it can rule anything out, and you've got no better ideas, you might as well try even the daftest idea.

I modified the source code to use the freshly-copied file, and it gave the same result. Hmm.

I then reran md5sums on the copied file... and it gave the same result as Java. In other words, running "md5sums c:\Windows\System32\Calc.exe" gave one result, but "md5sums CopyOfCalc.exe" gave a different result. At this point we've moved from Java looking like it's behaving weirdly to md5sums looking suspicious.

Proving the root cause

At this point we're sort of done - we've basically proved that the Java code produces the right hash for whatever data it's given, but we're left with the question of what's happening on the file system. I had a hunch that it might be something to do with x86 vs x64 code (all of this was running on a 64-bit version of Windows 7) - so how do we test that assumption?

I don't know if there's a simple way of running an x86 version of the JVM, but I do know how to switch .NET code between x86 and x64 - you can do that for an assembly at build time. C# also makes the hashing and hex conversion simple, so I was able to knock up a very small app to show the problem:

using System;
using System.IO;
using System.Security.Cryptography;

class Test
{
    static void Main()
    {
        using (var md5 = MD5.Create())
        {
            string path = "c:/Windows/System32/Calc.exe";
            var bytes = md5.ComputeHash(File.ReadAllBytes(path));
            Console.WriteLine(BitConverter.ToString(bytes));
        }
    }
}

(For a larger file I'd have used File.OpenRead instead, but then I'd have wanted to close the stream afterwards. Somehow it wasn't worth correcting the existing possible handle leak in the Java code, but I didn't want to write leaky code myself. So instead I've got code which reads the whole file into memory unnecessarily... <sigh>)

You can choose the architecture to build against (usually AnyCPU, x86 or x64 - though it's interesting to see that "arm" is also an option under .NET 4.5, for obvious reasons) either from Visual Studio or using the "/platform" command line option. This doesn't change the IL emitted (as far as I'm aware) but it's used for interop with native code - and in the case of executables, it also determines the version of the CLR which is used.

Building and running in x86 mode gave the same answer as the original "assumed to be good" tools; building and running in x64 mode gave the same answer as Java.

Explaining the root cause

At this point we've proved that the file system gives different results depending on whether you access it from a 64-bit process or a 32-bit process. The final piece of the puzzle was to find some something to explain why that happens. With all the evidence about what's happening, it was now easy to search for more information, and I found this article giving satisfactory details. Basically, there are two different copies of the system executables on a 64 bit system: x86 ones which run under the 32-bit emulator, and x64 ones. They're actually in different directories, but when a process opens a file in \Windows\System32, the copy which matches the architecture of the process is used. It's almost as if the \Windows\System32 directory is a symlink which changes target depending on the current process.

A Stack Overflow comment on my answer gave a final nugget that this is called the "File System Redirector".

Conclusion

Debugging sessions often feel a bit like this - particularly if you're like me, and only resort to real debugging after unit testing has failed. It's a matter of looking under all kinds of rocks, trying anything and everything, but keeping track of everything you try. At the end of process you should be able to explain every result you've seen, in an ideal world. (You may not be able to give evidence of the actual chain of events, but you should be able to construct a plausible chain of events which concurs with your theory.)

Be aware of areas which can often lead to problems, and check those first, gradually reducing the scope of "stuff you don't understand" to a manageable level, until it disappears completely.

Eduasync 20: Changes between the VS11 Preview and the Visual Studio 11 Beta

skeet — Tue, 06 Mar 2012 19:54:54 GMT

A while I ago I blogged about what had changed under the hood of async between the CTP and the VS11 Preview. Well, now that the VS11 Beta is out, it's time to do it all again...

Note that the code in this post is in the Eduasync codebase, under a different solution (Eduasync VS11.sln). Many of the old existing projects won't compile with VS11 beta, but I'd rather leave them as they are for posterity, showing the evolution of the feature.

Stephen Toub has an excellent blog post covering some of this, so while I'll mention things he's covered, I won't go into much detail about them. Let's start off there though...

(EDIT: Stephen has also mailed me with some corrections, which I've edited in - mostly without indication, as the post has been up for less than seven hours, and it'll make for a better reading experience.)

Awaiter pattern changes

The awaiter pattern is now not just a pattern. The IsCompleted property and GetResult method are still "loose" but OnCompleted is now part of an interface: INotifyCompletion. Awaiters have to implement INotifyCompleted, but may also implement ICriticalNotifyCompletion and its UnsafeOnCompleted method.

The OnCompleted method is just as it was before, and needs to flow the execuction context; the UnsafeOnCompleted method is simpler, as it doesn't need to flow the execution context. All of this only matters if you're implementing your own awaiters, of course. (More details in Stephen's blog post. I've found this area somewhat confusing, so please do read his post carefully!)

Skeleton method changes

Just as I have previously, I'm using the (entirely unofficial) term "skeleton method" to mean the very short method created by the compiler with the same signature as an async method: this is the entry point to the async method, effectively, which creates and starts the state machine containing all the real logic.

There are two changes I've noticed in the skeleton method. Firstly, for some reason the state machine state numbers have changed. Whereas previously a state number of 0 meant "initial or running", positive values meant "between calls, or navigating back to the await expression" and -1 meant "finished", now -1 means "initial or running", non-negative means "between calls, or navigating back to await expression" and -2 means "finished". It's not clear why this change has been made, given that it requires an extra assignment at the start of every skeleton method (to set the state to -1).

More importantly, the skeleton method no longer calls MoveNext directly on the state machine that it's built. Instead, it calls Start<TStateMachine> on the AsyncTaskMethodBuilder<T> (or whichever method builder it's using). It passes the state machine by reference (presumably for efficiency), and TStateMachine is constrained to implement the now-public-and-in-mscorlib IAsyncStateMachine interface. I'll come back to the relationship between the state machine and the builder later on.

Task caching

(Code is in project 30: TaskCaching)

It's possible for an async method to complete entirely synchronously. In this situation, the result is known before the method returns, and the task returned by the method is already in the RanToCompletionState. If two tasks have already run to completion with the same value, they can be (apparently) regarded as equivalent... so the beta now caches a task in this situation, for some types and values. (Apparently the preview cached too, but I hadn't noticed, and the beta caches more.) According to my experiments and some comments:

For int, tasks with values -1 to 8 inclusive are cached
For bool, both values (true and false)
For char, byte, sbyte, short, ushort, uint, long, ulong, IntPtr and UIntPtr tasks with value 0 (or '\0') are cached
For reference types, null is cached
For other types, no tasks are cached

EDIT: After they've completed, tasks are normally immutable except for disposal - the cached tasks are tweaked slightly to make disposal a no-op.

State machine interface changes

In the VS11 preview release, each state machine implemented an interface, but that interface was internal to the generated assembly, and contained a single method (SetMoveNextDelegate). It's now a public interface with two methods:

Personally I'm not keen on the naming of "MoveNext" - I can't help but feel that if we didn't have the "naming baggage" of IEnumerator and the fact that at least early on, the code generator was very similar to that used for iterator blocks, we'd have something different. (It is moving to the next state of the state machine, but it still doesn't quite feel right.) I'd favour something like "ContinueExecution". However, it doesn't matter - it obviously does what you'd expect, and you're not going to be calling this yourself.

SetStateMachine is a stranger beast. The documentation states:

Configures the state machine with a heap-allocated replica.

... which says almost nothing, really. The implementation is always simple, just like SetMoveNextDelegate was, although this time it delegates to the builder for the real work (a common theme, as we'll see):

void IAsyncStateMachine.SetStateMachine(IAsyncStateMachine param0)
{
this.<>t__builder.SetStateMachine(param0);
}

Now AsyncTaskMethodBuilder.SetStateMachine is also documented pretty sparsely:

Associates the builder with the specified state machine.

Again, no real help. However, we'll see that it's the builder which is responsible for calling OnContinue now, and as it can call MoveNext on an IStateMachine, it makes sense to tell it which state machine it's associated with... but can't it do that directly?

Well, not quite. The problem (as I understand it) is around when boxing occurs. We initially create the state machine on the stack, and it contains the builder. (Both are structs.) That's fine until we need a continuation, but then we've got to be able to get back to the current state later, after the current stack frame has been blown away. So we need to box the state machine. That will create a copy of the current builder (within the box). We need the builder within the boxed state machine to contain a reference to the same box. So the order has to be:

Box the state machine
Tell the state machine about the boxed reference
The state machine tells its nested builder about the boxed reference

Back when the state machine was in charge of the boxing, this went via the delegate: the act of creating the box was implicit when creating the delegate, and then casting the delegate target to the interface type allowed a reference to the newly-created delegate to be set within the copy. This is similar, but using the builder instead. It's hard to follow, but of course it's not going to matter.

State machine field changes

There are various kinds of fields in the state machine:

Those corresponding with local variables and parameters in the async method
The state
The field(s) associated with awaiters
(In the preview/beta) The field associated with the "current execution stack" at the point of an await expression
(In the CTP) An unused "disposing" field

Of these, I believe only the awaiters have actually changed, but before we talk about that, let's revisit local variables.

Local variable hoisting

I've just noticed that the local variables are only hoisted to fields when its scope contains an await expressions, but in that case all local variables of that scope are hoisted, whether or not they're used "across" awaits. It would be possible to hoist only those which need to be maintained between executions, but then you wouldn't be able to see the others when debugging, which would be somewhat confusing. Likewise local variables of the same type which are never propagated across the same await could be aliased. For example, consider this async method:

static async Task<int> M(Random rng)
{
    int x = rng.Next(1000);
    int y = x + rng.Next(1000);

    await Task.Yield();

    int z = y + rng.Next(1000);

    await Task.Yield();
    return z;
}

If the compiler could be confident you didn't need to debug through this code, it could make do with one field of type "Random" and one field of type "int" - x can be a completely local variable in MoveNext (it's not used between two awaits) and y and z can be aliased (we never need the value of y after we've first written to z).

Local variable aliasing probably isn't particularly useful for "normal" methods as the JIT may be able to do it (so long as you don't have a debugger attached, potentially) but in this case we expect the state machine to be boxed at some point, so potentially does make a difference (while the stack is typically reasonably small, you could have a lot of outstanding async methods in some scenarios). Maybe in a future release, the C# compiler could have an aggressive optimization mode around this, to be turned on explicitly. (I don't think it should be a particularly high priority, mind you.)

Awaiter fields

(Code is in project 31, AwaiterFields.)

Awaiter fields have changed a bit over the course of async's history.

In the CTPs (all of them, I believe) each await expression had its own awaiter field in the state machine, with a type corresponding to the declared awaiter type from the awaitable. (Remember that the awaitable is the thing you await, such as a task, and the awaiter is what you get back from calling GetAwaiter on the awaitable).

In the VS11 Preview, there was always a single awaiter field of type object. From what I saw, it was usually populated with a single-element array containing an awaiter. For value type awaiters (i.e. where the awaiter is a struct) this is somewhat similar to boxing, but maintaining strong typing, so calls to IsCompleted etc can still be made. It's possible that reference type awaiters were stored without the array creation, as it would serve no purpose. (I don't have any machines with just the preview installed to verify this.)

In the Beta, we have a mixture. If there are any reference type awaiters, they all end up being stored in a single field of type object, which is then cast back to the actual type when required. (Don't forget that only one awaiter can be "active" at a time, which makes this possible.) This includes awaiters of an interface type - it's only the compile-time type declared as the return type of the GetAwaiter method of the awaitable which is important.

If any of the awaiter types are value types, each of these types gets its own field. So there might be a TaskAwaiter<int> field and a TaskAwaiter<string> field, for example. However, there can still be "sharing" going on: if there are multiple await expressions all of the same value type awaiter, they will all share a single field. (This all feels a little like the JITting of generics, but it's somewhat coincidental.)

MoveNext method changes

(Code is in project 32, BetaStateMachine)

As I've mentioned earlier, the builder is now responsible for a lot more of the work than it was in earlier versions. The majority of the code remains the same as far as I can tell, in terms of handling branching, evaluating expressions with multiple await expressions and so on. The code in the source repository shows what the complete state machine looks like, but for the sake of clarity, I'll just focus on a single snippet. If we have an await expression like this:

await x;

then the state machine code in the VS11 Preview would look something like this:

localTaskAwaiter = x.GetAwaiter();
if (localTaskAwaiter.IsCompleted)
{
    goto AwaitCompleted;
}
this.state = 1;
TaskAwaiter[] awaiterArray = { localTaskAwaiter };
this.awaiter = awaiterArray;
Action continuation = this.MoveNextDelegate;
if (continuation == null)
{
    Task<int> task = this.builder.Task;
    continuation = MoveNext;
    ((IStateMachine) continuation.Target).SetMoveNextDelegate(continuation);
}
awaiterArray[0].OnCompleted(continuation);
...
return;

(That's just setting up the await, of course - there's then the bit where the result is fetched, but that's less interesting. There's also the matter of doFinallyBodies.)

In the VS11 Beta, it's something this instead (for an awaiter type "AwaiterType" which implements ICriticalNotifyCompletion, in a state machine of type ThisStateMachine).

localAwaiter = x.GetAwaiter();
if (!localAwaiter.IsCompleted)
{
    state = 0;
    awaiterField = localAwaiter;
    builder.AwaitUnsafeOnCompleted<AwaiterType, ThisStateMachine>(ref localAwaiter, ref this);
    doFinallyBodies = false;
    return;
}

If the awaiter type only implements INotifyCompletion, it calls AwaitOnCompleted instead. Note how the calls are generic (but both type variables are constrained to implement appropriate interfaces) which avoids boxing.

The call to the builder will call back to the state machine's SetStateMachine method if this is the first awaiter that hasn't already completed within this execution of the async method. So that handles the section which checked for the continuation being null in the first block of code. Most of the rest of the change is explained by the difference in awaiter types, and obviously AwaitOnCompleted/AwaitUnsafeOnCompleted also ends up calling into OnCompleted on the awaiter itself.

Mutable value type awaiters

(Code is in project 32, MutableAwaiters)

One subtle difference which really shouldn't hurt people but is fun to explore is what happens if you have an awaiter which is a mutable value type. Due to the way awaiters were carefully handled pre-beta, mutations which were conducted as part of OnCompleted would still be visible in GetResult. That's not the case in the beta (as Stephen mentions in his blog post). Mind you, it doesn't mean that all mutations will be ignored... just ones in OnCompleted. A mutation from IsCompleted is still visible, as shown here:

public struct MutableAwaiter : INotifyCompletion
{
     private string message;

     public MutableAwaiter(string message)
     {
         this.message = message;
     }

     public bool IsCompleted
     {
         get
         {
             message = "Set in IsCompleted";
             return false;
         }
     }

     public void OnCompleted(Action action)
     {
         message = "Set in OnCompleted";
         // Ick! Completes inline. Never mind, it's only a demo...
         action();
     }

     public string GetResult()
     {
         return message;
     }
}

What would you expect to be returned from this awaiter? You can verify that all three members are called... but "Set in IsCompleted" is returned. That's because IsCompleted is called before the awaiter value is copied into a field within the state machine. Even though the state machine passes the awaiter by reference, it's passing the local variable, which is of course a separate variable from the field.

I'm absolutely not suggesting that you should rely on any of this behaviour. If you really need to be able to mutate your awaiter, make it a reference type.

Conclusion

The main changes in the Beta are around the interactions between the AsyncTaskMethodBuilder (et al) and the state machine, including the new interfaces for awaiters. There's been quite a bit of optimization, although I still see room for a bit more:

When there's only a single kind of reference type awaiter, the field for storing it could be of that type rather than of type object, removing the need for an execution-time cast
The "stack" variable could be removed in some cases, and made into a specific type in many others
With appropriate optimization flags, local variables which aren't used await expressions could stay local to the state machine instead of being hoisted, and hoisted variables could be aliased in some cases.

One thing which concerns me slightly is how the C# language specification is going to change - the addition of the new interfaces is definitely going to mean more complexity from this previously "tidy" feature. I'm sure it's worth it for the sake of efficiency and the like, but part of me sighs at every added tweak.

So, is this now close to the finished version of async? Only time will tell. I haven't checked whether dynamic awaitables have finally been introduced... if they have, I'll put that in the next post.

Subtleties in API design - member placement

skeet — Wed, 29 Feb 2012 17:27:25 GMT

Noda Time is nearing v1.0, which means I'm spending more time writing documentation than code. It also means reviewing the APIs we've got with a critical eye - whether that's removing extraneous members, adding useful ones, or moving things around. (In particular, writing documentation often suggests where a change would make calling code read more naturally.)

This post is about one particular section of the API, and the choices available. Although I do go into some detail around the specific calls involved, that's just for context... the underlying choices are ones which could be faced when designing any API. I've rarely spent as much time thinking about API decisions as I have with Noda Time, so hopefully this will prove interesting to you even if you really don't care about Noda Time itself as a project.

Introduction: time zones, local date/times and zoned date/times - oh my!

(Okay, so that's not quite as snappy as the Judy Garland version, but hey...)

The area of API we're going to focus on is time zones, and converting between "local" date/time values and "zoned" ones. The three types involved are:

LocalDateTime: a "local" date and time, with no specific time zone. So, something like "7:30 in the evening on February 27th 2012". This means different instants in time in different time zones, of course: if you're arranging a meeting, it's good enough when the attendees are in the same time zone, but not good enough if you're meeting with someone on the other side of the world. (A LocalDateTime also has an associated calendar system, but I'm not going to talk about that much in this post.)
DateTimeZone: a time zone. At its core, this maps any "instant" in time to an offset - the difference between UTC and local time in that time zone. The offset changes over time, typically (but not always) due to daylight saving changes.
ZonedDateTime: a date and time in a particular time zone, with an offset from UTC to avoid ambiguity in some cases (and for efficiency). This identifies a specific instant in time (simply by subtracting the offset from the local date/time). Conceptually this is equivalent to just maintaining the "instant" value, the time zone, and the calendar system - but it's generally cleaner to think of it as a "local" value with an offset from UTC.

If those brief descriptions don't make sense for you at the moment (this sort of thing is quite hard to describe concisely and precisely) you may want to see whether the Noda Time user guide "concepts" page helps.

The API task: mapping from { LocalDateTime, DateTimeZone } to ZonedDateTime

It's easy to get from a ZonedDateTime to a LocalDateTime - you can just use the LocalDateTime property. The difficult bit is the other way round. We obviously want to be able to create a ZonedDateTime from the combination of a LocalDateTime and a DateTimeZone, but the question is where to put this functionality. Three options suggest themselves:

A static method (or constructor) in ZonedDateTime which takes both the time zone and the local date/time as arguments
An instance method on LocalDateTime which just takes the time zone as an argument
An instance method on DateTimeZone which just takes the local date/time as an argument

It gets more complicated though - we're not really talking about one operation here, but potentially several. Although the mapping from instant to offset is unambiguous in DateTimeZone, the mapping from LocalDateTime to offset is not straightforward. There can be 0, 1 or 2 possible results. For example, in the America/Los_Angeles time zone the clocks go forward from 2am to 3am on Sunday March 11th 2012, and go back from 2am to 1am on Sunday 4th November 2012. That means:

The mapping from local date/time to offset at 7.30pm on February 27th 2012 is unambiguous: it's definitely -8 hours (L.A. is 8 hours behind UTC).
The mapping at 2.30am on March 11th 2012 is impossible: at 2am the clocks were put forward to 3am, so 2.30am simply never occurs.
The mapping at 2.30am on November 4th 2012 is ambiguous: it happens once before the clocks go back at 3am, and once afterwards. The offset is either -7 or -8 hours, depending on which occurrence you mean.

When mapping a local time to "global" time, this is something you should really think about. Most APIs obscure the issue, but one of the purposes of Noda Time is to force developers to think about issues which they should be aware of. This one is particularly insidious in that it's the kind of problem which is much more likely to arise when you're asleep than during daylight hours - so it's unlikely to be found during manual testing. (Ditto the day of week - most time zones have daylight saving transitions early on a Sunday morning.)

So, Noda Time exposes four ways of mapping a LocalDateTime and DateTimeZone to a ZonedDateTime:

Exact: if there's a single mapping, return it. Otherwise, throw an exception.
Earlier: if there's a single mapping, return it. If there's more than one, return the earlier one. If the time is skipped, throw an exception.
Later: if there's a single mapping, return it. If there's more than one, return the later one. If the time is skipped, throw an exception.
All information: find out all the information relevant to mapping the given local value - how many matches there are, what they would be, what the time zone information is for each mapping, etc. The caller can then do what they want.

Options available

The question is how we expose these operations. Let's look at some options, then discuss the pros and cons.

Option 1: methods on LocalDateTime

A lot of Noda Time is designed to be "fluent" so it makes a certain amount of sense to be able to take a LocalDateTime, perform some arithmetic on it, then convert it to a ZonedDateTime, then (say) format it. So we could have something like:

var zoned = local.InZone(zone); // implicitly exact
var zoned = local.InZoneOrEarlier(zone);
var zoned = local.InZoneOrLater(zone);
var mapping = local.MapToZone(zone);

Option 2: methods on DateTimeZone

All the calculations involved are really about the time zone - the local date/time value is just a simple value as far as most of this is concerned. So we can put the methods on DateTimeZone instead:

var zoned = zone.AtExactly(local);
var zoned = zone.AtEarlier(local);
var zoned = zone.AtLater(local);
var mapping = zone.MapLocalDateTime(local);

Option 3: methods (or constructors) on ZonedDateTime

Maybe we consider the two inputs to be fairly equal, but the result type is more important:

var zoned = ZonedDateTime.FromLocal(zone, local);
var zoned = ZonedDateTime.FromLocalOrEarlier(zone, local);
var zoned = ZonedDateTime.FromLocalOrLater(zone, local);
var mapping = ZoneLocalMapping.FromLocal(local)

(I'm not terribly happy about the names here; there could be better ones of course.)

Variation a: any of the above options, but with an enum for ambiguity resolution

We don't really need four methods on any of these APIs; the first three only differ by how they handle ambiguity (the situation where a particular local date/time occurs twice). We could use an enum to represent that choice instead:

var zoned = local.InZone(zone, ZoneAmbiguityResolver.Error);
var zoned = local.InZone(zone, ZoneAmbiguityResolver.Earlier);
var zoned = local.InZone(zone, ZoneAmbiguityResolver.Later);

(Or a "smart enum" with behaviour, if we wanted. A normal class type with methods etc, but only a restricted set of valid values.)

Variation b: always go via the mapping result

Given that we already have the idea of getting the full mapping results, we can reduce the API to just one method to return the mapping information, and then put extra methods on that:

var zoned = local.MapInZone(zone).SingleMatch;
var zoned = local.MapInZone(zone).SingleOrEarlier;
var zoned = local.MapInZone(zone).SingleOrLater;

(Again, the names aren't fixed in stone, and the second part could be methods instead of properties if we wanted.)

Variation c: return a sequence of results

If we return a sequence with 0, 1 or 2 ZonedDateTime values, the user can just use LINQ to get the one they want. Again, this can apply wherever we decide to put the method:

var zoned = zone.At(local).Single();
var zoned = zone.At(local).First();
var zoned = zone.At(local).Last();

So, it looks like we effectively have two mostly-orthogonal decisions here:

Where to "start" the conversion - the target type for the method call
How to represent the multiple options

We'll consider them separately.

Regarding the "source" type

To start with, I'll reveal my bias: the existing implementation is option 2 (four methods on DateTimeZone). This was after a small amount of debate on the Noda Time mailing list, and this was the most relevant bit of the discussion:

Me (before going with the current implementation):

It feels a little odd to me to use the zone as the principal class here - just in terms of usability. It makes total sense in terms of the logic, but I tend to think of having a LocalDateTime first, and then converting that to use a particular zone - it's not an operation which feels like it acts on the zone itself.

David N:

I actually feel the opposite: asking a DateTimeZone how a particular LocalDateTime would be represented in that zone feels natural, while asking the LocalDateTime how it would be represented in a zone feels odd. The zone is a first-class entity, with identity and behavior; the LocalDateTime is just a set of values. Why would the LocalDateTime be expected to know how it is represented in a particular zone?

Even though I replied to that in a "maybe" kind of tone, the argument basically convinced me. The trouble is, a colleague was then surprised when he read the documentation around calendar arithmetic and conversions. Surprising users is pretty much a cardinal sin when it comes to API design - and although in this case it was the relatively harmless sort of surprise ("I can't find the member I want in A; oh, it turns out it's in B") rather than a behavioural surprise ("I thought it would do X, but instead it does Y") it's still bad news. I should reveal my colleague's bias too - he has experience of Joda Time, where the relevant call is LocalDateTime.toDateTime(DateTimeZone). (There are calls in DateTimeZone itself, but they're lower-level.)

We've discussed this a fair amount (leading to this blog post) and so far we've concluded that it really depends on how you think about time zones. As a Noda Time user, would you consider them to be rich objects with complex behaviour, or would you think of them as mere "tokens" to be passed around and used without much direct interaction? The two ways of viewing the type aren't necessarily in conflict - I've deliberately designed CalendarSystem to hide its (fairly ugly) innards. There are a few public instance members, but most are internal. But what about time zones?

There's an argument to be made for educating Noda Time users to think about time zones as more complex beasts than just tokens, and I'm happy to do that in other areas (such as choosing which type to use in the first place) but here it feels like it's one step too far. On the other hand, I don't want to stifle users who are thinking of DateTimeZone in that way. In the mailing list thread, David also expressed a dislike for the approach of including functionality in multiple places - and to a certain extent I agree (one of the things I dislike about its API is that it lets you do just about anything with anything)... but in this case it feels like it's justified.

Regardless of how you're thinking about DateTimeZone, it's more likely that you're going to want to use a LocalDateTime value which is the result of some other expression, and then apply some "constant" zone to it, then potentially keep going. If you think about a LINQ-style pipeline of operations, the part that varies in the conversion is much more likely to be the LocalDateTime than the time zone. As such, a method on LocalDateTime allows for a more fluent calling style:

var zoned = parseResult.Value
.PlusMonths(1)
.InZone(LondonTimeZone);

versus:

var zoned = LondonTimeZone.AtExactly(parseResult.Value.PlusMonths(1));

Or to keep the code order the same as the execution order:

var local = parseResult.Value.PlusMonths(1);
var zoned = LondonTimeZone.AtExactly(local);

Obviously the effects become more noticeable the more operations you perform. Personally I'm happy with either the first or third approach - although it's worth being aware that either of the first two have the advantage of being one expression, and therefore easy to use when assigning a static readonly field or something similar.

I'm reasonably happy with having one method on each type, or possibly two (MapLocalDateTime and At*) on DateTimeZone and one (just InZone) on LocalDateTime. I really don't like the idea of having four methods on DateTimeZone and three methods on LocalDateTime. So, let's consider the different variations which cut down the number of methods required.

Expressing "exactly," "earlier," and "later" in one method

This is essentially a discussion of the "variations" above. Just to recap, the possibilities we've come up with are:

Add another parameter to the method to indicate how to handle ambiguities (or impossibilities) - just return a ZonedDateTime
Return a value of a different type (e.g. ZoneLocalMapping) which can be used to get at all the information you could want
Return a sequence of possible ZonedDateTime values, expecting the caller to probably use LINQ's First/Last/Single/FirstOrDefault etc to get at the value they want

The last of these is the only one which gives an easy way of handling the extreme corner case of a local time occurring more than twice - for example, a time zone which goes back one hour at 2am (to 1am) and then goes back another two hours at 3am. I think it's reasonable to dismiss this corner case; however mad time zones can be, I haven't seen anything quite that crazy yet.

At the time of the original discussion, Noda Time was targeting .NET 2.0, which was one reason for not going with the final option here - we couldn't guarantee that LINQ would be available. Now, Noda Time is targeting .NET 3.5 in order to use TimeZoneInfo, but it still doesn't feel like an ideal fit:

Returning a sequence doesn't give information about (say) the two zone intervals "surrounding" a gap
A sequence may be surprising to users who expect just a single value
The exceptions thrown by First, Single etc when their expectations aren't met are very domain-neutral; we can give more information
FirstOrDefault will return the default value for ZonedDateTime in the case of ambiguity. That would be unfortunate, as ZonedDateTime is a value type, and its default value is actually somewhat unhelpful. (It has a null calendar system, effectively. There's not a lot we can do about this, but that's a post for another day.) We could make it a sequence of Nullable<ZonedDateTime> and guarantee that any values in it are actually non-null, but that's really straining things.

Putting these together, there are enough negative points to this idea that I'm happy to rule it out. But what about the first two?

The first has the advantage that the caller only needs to make a single method call, effectively passing in a "magic token" (the ambiguity resolver) which they don't really need to understand. On the other hand, if they want more information, they'll have to call a different method - and I'm not really sure we want to encourage too much of this "magic token" behaviour.

The second has three disadvantages, all fairly slight:

The user may initially expect the result of a method mapping a LocalDateTime to a ZonedDateTime to be a ZonedDateTime... what's this extra intermediate result doing? This is "only" a matter of user education, and it's pretty discoverable. It's an extra concept the user needs to understand, but it's a good concept to understand.
Calling two methods or a method and a property (e.g. zone.MapLocalDateTime(localDateTime).Earlier) may end up being slightly more long-winded than a single method call. I can't get excited about this.
We have to allocate an extra object for the mapping, even when we know it's unique. Usually, this object will become eligible for garbage collection immediately. We could make it a struct, but I don't think it's a natural value type - I'd rather trust that allocating objects in gen0 is pretty cheap.

With the second method, we can replace all the existing methods in DateTimeZone with a single one (or rather, just remove the AtXyz methods, leaving MapLocalDateTime). We can then create pleasantly-named methods on ZoneLocalMapping (which isn't quite right for this purpose at the moment).

Conclusion

This has been an interesting thought experiment for me, and it's suggested some changes I will be applying before v1. We'll see how they pan out. If you want to follow them, look for relevant source code changes.

The important points I've been thinking about are:

What would a new user expect to be available? If they haven't read any documentation, what are they likely to try?
What should the user know about? Where there are important decisions to make, how can we provide guidance?
What would an experienced user (who is already thinking about the Noda Time concepts in the way that we want to encourage) expect to be available?
Where does the balance lie between providing a "too crowded" API (with lots of different ways of achieving the same thing) and a "sparse" API (where there's always one way of achieving a goal, but it may not be the most convenient one for your situation)
How does our choice fit in with other technologies? For example, the final "variation" seems like it plays nicely with LINQ at first - but a few subtleties make it a worse fit than it might seem.
How does this affect performance? (Performance is important in Noda Time - but there would have to be a significant performance problem for me to deviate from an elegant solution.)

So, any other thoughts? Did we miss some options? What other factors should we have taken into consideration?

Currying vs partial function application

skeet — Mon, 30 Jan 2012 18:32:06 GMT

This is a slightly odd post, and before you read it you should probably put yourself into one of three buckets:

Someone who doesn't care too much about functional programming, and finds higher order functions tricky: feel free to skip this post entirely.
Someone who knows all about functional programming, and already knows the difference between currying and partial function application: please read this post carefully and post comments about any inaccuracies you find. (Yes, the CAPTCHA is broken on Chrome; sorry.)
Someone who doesn't know much about functional programming yet, but is interested to learn more: please take this post with a pinch of salt, and read the comments carefully. Read other articles by more experienced developers for more information.

Basically, I've been aware for a while that some people use the terms currying and partial function application somewhat interchangably, when they shouldn't. It's one of those topics (like monads) which I feel I understand to some extent, and I've decided that the best way of making sure I understand it is to try to write about it. If it helps the topic become more accessible to other developers, so much the better.

This post contains no Haskell

Almost every explanation I've ever seen of either topic has given examples in a "proper" functional language, typically Haskell. I have absolutely nothing against Haskell, but I typically find it easier to understand examples in a programming language I understand. I also find it much easier to write examples in a program language I understand, so all the examples in this post are going to be in C#. In fact, it's all available in a single file - that includes all of the examples, admittedly with a few variables renamed. Just compile and run.

C# isn't really a functional language - I know just about enough to understand that delegates aren't really a proper substitute for first class functions. However, they're good enough to demonstrate the principles involved.

While it's possible to demonstrate currying and partial function application using a function (method) taking a very small number of parameters, I've chosen to use 3 for clarity. Although my methods to perform the currying and partial function application will be generic (so all the types of parameters and return value are arbitrary) I'm using a simple function for demonstration purposes:

static string SampleFunction(int a, int b, int c)
{
return string.Format("a={0}; b={1}; c={2}", a, b, c);
}

So far, so simple. There's nothing tricky about that method, so don't look for anything surprising.

What's it all about?

Both currying and partial function application are about converting one sort of function to another. We'll use delegates as an approximation to functions, so if we want to treat the method SampleFunction as a value, we can write:

Func<int, int, int, string> function = SampleFunction;

This single line is useful for two reasons:

Assigning the value to a variable hammers home the point that it really is a value. A delegate instance is an object much like any other, and the value of the function variable is a reference just like any other.
Method group conversions (using just the name of the method as a way of creating a delegate) doesn't work terribly nicely with type inference when calling a generic method.

We can already call the function using three arguments with no further work:

string result = function(1, 2, 3);

Or equivalently:

string result = function.Invoke(1, 2, 3);

(The C# compiler just converts the shorthand of the first form to the second. The IL emitted will be the same.)

That's fine if we've got all the arguments available at the same time, but what if we haven't? To give a concrete (if somewhat contrived) example, suppose we have a logging function with three parameters (source, severity, message) and within a single class (which I'll call BusinessLogic for the moment) we always want to use the same value for the "source" parameter, and we'd like to be able to log easily everywhere in the class specifying just the severity and message. We have a few options:

Create an adapter class which takes the log function (or more generally a logging object) and the "source" value in its constructor, stashes both in instance variables, and exposes a method with two parameters. That method just delegates to the stashed logger, using the source it's remembered to supply the first argument to the three-parameter method. In BusinessLogic we create an instance of the adapter class, and stash a reference in an instance variable - then just call the two-parameter method everywhere we need to. This is probably overkill if we only need the adapter from BusinessLogic, but it's reusable... so long as we're trying to adapt the same logging function.
Store the original logger in our BusinessLogic class, but create a helper method with two parameters. This can hard-code the value used for the "source" parameter in one place (the helper method). If we need to do this in several places, it gets annoying.
Use a more general functional programming approach - probably partial function application in this case.

I'm deliberately ignoring the discrepancy between holding a reference to "the logger" and holding a reference to "the logging function". Obviously there's a significant difference if we need to use more than one function from the logging class, but for the purposes of thinking about currying and partial function application, we'll just think of "a logger" as "a function taking three parameters" (like our sample function).

Now that I've given the slightly-real-world concrete example for a bit of motivation, I'm going to ignore it for the rest of the post, and just talk about our sample function. I don't want to write a whole BusinessLogic class which pretends to do something useful; I'm sure you can perform the appropriate mental conversion from "the sample function" to "something I might actually want to do".

Partial Function Application

The purpose of partial function application is to take a function with N parameters and a value for one of those parameters, and return a function with N-1 parameters, such that calling the result will assemble all the required values appropriately (the 1 argument given to the partial application operation itself, and the N-1 arguments given to the returned function). So in code form, these two calls should be equivalent for our 3-parameter method:

// Normal call
string result1 = function(1, 2, 3);

// Call via partial application
Func<int, int, string> partialFunction = ApplyPartial(function, 1);
string result2 = partialFunction(2, 3);

In this case I've implemented partial application with a single parameter, and chosen the first one - you could write an ApplyPartial method which took more arguments to apply, or which used them somewhere else in the final function execution. I believe that picking off parameters one at a time, from the start, is the most conventional approach.

Thanks to anonymous functions (a lambda expression in this case, but an anonymous method wouldn't be much more verbose), the implementation of ApplyPartial is simple:

static Func<T2, T3, TResult> ApplyPartial<T1, T2, T3, TResult>
(Func<T1, T2, T3, TResult> function, T1 arg1)
{
return (b, c) => function(arg1, b, c);
}

The generics make the method look more complicated than it really is. Note that the lack of higher order types in C# means that you'd need a method like this for every delegate you wanted to use - if you wanted a version for a function which started with four parameters, you'd need an ApplyPartial<T1, T2, T3, T4, TResult> method etc. You'd probably also want a parallel set of methods for the Action delegate family.

The final thing to note is that assuming we had all of these methods, we could perform partial function application again - even potentially down to a parameterless function if we wanted, like this:

Func<int, int, string> partial1 = ApplyPartial(function, 1);
Func<int, string> partial2 = ApplyPartial(partial1, 2);
Func<string> partial3 = ApplyPartial(partial2, 3);
string result = partial3();

Again, only the final line would actually invoke the original function.

Okay, so that's partial function application. That's relatively straightforward. Currying is slightly harder to get your head round, in my view.

Currying

Whereas partial function application converts a function with N parameters into a function with N-1 parameters by applying one argument, currying effectively decomposes the function into functions taking a single parameter. We don't pass any arguments into the Curry method itself:

Curry(f) returns a function f1 such that...
f1(a) returns a function f2 such that...
f2(b) returns a function f3 such that...
f3(c) invokes f(a, b, c)

(Again, note that this is specific to our three-parameter function - but hopefully it's obvious how it would extend to other signatures.)

To give our "equivalence" example again, we can write:

// Normal call
string result1 = function(1, 2, 3);

// Call via currying
Func<int, Func<int, Func<int, string>>> f1 = Curry(function);
Func<int, Func<int, string>> f2 = f1(1);
Func<int, string> f3 = f2(2);
string result2 = f3(3);

// Or to do make all the calls together...
var curried = Curry(function);
string result3 = curried(1)(2)(3);

The difference between the latter examples shows one reason why functional languages often have good type inference and compact representations of function types: that declaration of f1 is pretty fearsome.

Now that we know what the Curry method is meant to do, it's actually surprisingly simple to implement. Indeed, all we need to do is translate the bullet points above into lambda expressions. It's a thing of beauty:

static Func<T1, Func<T2, Func<T3, TResult>>> Curry<T1, T2, T3, TResult>
(Func<T1, T2, T3, TResult> function)
{
return a => b => c => function(a, b, c);
}

If you want to add some brackets to make it clearer for you, feel free - personally I think it just adds clutter. Either way, we get what we want. (It's worth thinking about how annoying it would be to write that without lambda expressions or anonymous methods. Not hard, just annoying.)

So that's currying. I think. Maybe.

Conclusion

I can't say I've ever knowingly used currying, whereas I suspect some bits of Noda Time's text parsing effectively use partial functional application. (If anyone really wants me to dig in and check, I'll do so.)

I really hope I've got the difference between them right here - it feels right, in that the two are clearly related, but also quite distinct. Now that we've reached the end, think about how that difference manifests itself when there are only two parameters, and hopefully you'll see why I chose to use three :)

My gut feeling is that currying is a more useful concept in an academic context, whereas partial functional application is more useful in practice. However, that's the gut feeling of someone who hasn't really used a functional language in anger. If I ever really get round to using F#, maybe I'll do a follow-up post. For now, I'm hoping that my trusty smart readers can provide useful thoughts for others.

Eduasync part 19: ordering by completion, ahead of time...

skeet — Mon, 16 Jan 2012 22:22:43 GMT

Today's post involves the MagicOrdering project in source control (project 28).

When I wrote part 16 of Eduasync, showing composition in the form of majority voting, one reader mailed me a really interesting suggestion. We don't really need to wait for any of the tasks to complete on each iteration of the loop - we only need to wait for the next task to complete. Now that sounds impossible - sure, it's great if we know the completion order of the tasks, but half the point of asynchrony is that many things can be happening at once, and we don't know when they'll complete. However, it's not as silly as it sounds.

If you give me a collection of tasks, I'll give you back another collection of tasks which will return the same results - but I'll order them so that the first returned task will have the same result as whichever of your original tasks completes first, and the second returned task will have the same result as whichever of your original tasks completes second, and so on. They won't be the same tasks as you gave me, reordered - but they'll be tasks with the same results. I'll propagate cancellation, exceptions and so on.

It still sounds impossible... until you realize that I don't have to associate one of my returned tasks with one of your original tasks until it has completed. Before anything has completed, all the tasks look the same. The trick is that as soon as I see one of your tasks complete, I can fetch the result and propagate it to the first of the tasks I've returned to you, using TaskCompletionSource<T>. When the second of your tasks completes, I propagate the result to the second of the returned tasks, etc. This is all quite easy using Task<T>.ContinueWith - barring a few caveats I'll mention later on.

Once we've built a method to do this, we can then really easily build a method which is the async equivalent of Parallel.ForEach (and indeed you could write multiple methods for the various overloads). This will execute a specific action on each task in turn, as it completes... it's like repeatedly calling Task.WhenAny, but we only actually need to wait for one task at a time, because we know that the first task in our "completion ordered" collection will be the first one to complete (duh).

Show me the code!

Enough description - let's look at how we'll demonstrate both methods, and then how we implement them.

private static async Task PrintDelayedRandomTasksAsync()
{
    Random rng = new Random();
    var values = Enumerable.Range(0, 10).Select(_ => rng.Next(3000)).ToList();
    Console.WriteLine("Initial order: {0}", string.Join(" ", values));

    var tasks = values.Select(DelayAsync);

    var ordered = OrderByCompletion(tasks);

    Console.WriteLine("In order of completion:");
    await ForEach(ordered, Console.WriteLine);
}

/// <summary>
/// Returns a task which delays (asynchronously) by the given number of milliseconds,
/// then return that same number back.
/// </summary>
private static async Task<int> DelayAsync(int delayMillis)
{
    await TaskEx.Delay(delayMillis);
    return delayMillis;
}

The idea is that we're going to create 10 tasks which each just wait for some random period of time, and return the same time period back. We'll create them in any old order - but obviously they should complete in (at least roughly) the same order as the returned numbers.

Once we've created the collection of tasks, we'll call OrderByCompletion to create a second collection of tasks, returning the same results but this time in completion order - so ordered.ElementAt(0) will be the first task to complete, for example.

Finally, we call ForEach and pass in the ordered task collection, along with Console.WriteLine as the action to take with each value. We await the resulting Task to mimic blocking until the foreach loop has finished. Note that we could make this a non-async method and just return the task returned by ForEach, given that that's our only await expression and it's right at the end of the method. This would be marginally faster, too - there's no need to build an extra state machine. See Stephen Toub's article about async performance for more information.

ForEach

I'd like to get ForEach out of the way first, as it's so simple: it's literally just iterating over the tasks, awaiting them and propagating the result to the action. We get the "return a task which will wait until we've finished" for free by virtue of making it an async method.

/// <summary>
/// Executes the given action on each of the tasks in turn, in the order of
/// the sequence. The action is passed the result of each task.
/// </summary>
private static async Task ForEach<T>(IEnumerable<Task<T>> tasks, Action<T> action)
{
    foreach (var task in tasks)
    {
        T value = await task;
        action(value);
    }
}

Simple, right? Let's get onto the meat...

OrderByCompletion

This is the tricky bit, and I've actually split it into two methods to make it slightly easier to comprehend. The PropagateResult method feels like it could be useful in other composition methods, too.

The basic plan is:

Copy the input tasks to a list: we need to work out how many there are and iterate over them, so let's make sure we only iterate once
Create a collection of TaskCompletionSource<T> references, one for each input task. Note that we're not associating any particular input task with any particular completion source - we just need the same number of them
Declare an integer to keep track of "the next available completion source"
Attach a continuation to each input task which will be increment the counter we've just declared, and propagate the just-completed task's status
Return a view onto the collection of TaskCompletionSource<T> values, projecting each one to its Task property

Once you're happy with the idea, the implementation isn't too surprising (although it is quite long):

/// <summary>
/// Returns a sequence of tasks which will be observed to complete with the same set
/// of results as the given input tasks, but in the order in which the original tasks complete.
/// </summary>
private static IEnumerable<Task<T>> OrderByCompletion<T>(IEnumerable<Task<T>> inputTasks)
{
    // Copy the input so we know it'll be stable, and we don't evaluate it twice
    var inputTaskList = inputTasks.ToList();

    // Could use Enumerable.Range here, if we wanted...
    var completionSourceList = new List<TaskCompletionSource<T>>(inputTaskList.Count);
    for (int i = 0; i < inputTaskList.Count; i++)
    {
        completionSourceList.Add(new TaskCompletionSource<T>());
    }

    // At any one time, this is "the index of the box we've just filled".
    // It would be nice to make it nextIndex and start with 0, but Interlocked.Increment
    // returns the incremented value...
    int prevIndex = -1;

    // We don't have to create this outside the loop, but it makes it clearer
    // that the continuation is the same for all tasks.
    Action<Task<T>> continuation = completedTask =>
    {
        int index = Interlocked.Increment(ref prevIndex);
        var source = completionSourceList[index];
        PropagateResult(completedTask, source);
    };

    foreach (var inputTask in inputTaskList)
    {
        // TODO: Work out whether TaskScheduler.Default is really the right one to use.
        inputTask.ContinueWith(continuation,
                               CancellationToken.None,
                               TaskContinuationOptions.ExecuteSynchronously,
                               TaskScheduler.Default);
    }

    return completionSourceList.Select(source => source.Task);
}

/// <summary>
/// Propagates the status of the given task (which must be completed) to a task completion source
/// (which should not be).
/// </summary>
private static void PropagateResult<T>(Task<T> completedTask,
    TaskCompletionSource<T> completionSource)
{
    switch (completedTask.Status)
    {
        case TaskStatus.Canceled:
            completionSource.TrySetCanceled();
            break;
        case TaskStatus.Faulted:
            completionSource.TrySetException(completedTask.Exception.InnerExceptions);
            break;
        case TaskStatus.RanToCompletion:
            completionSource.TrySetResult(completedTask.Result);
            break;
        default:
            // TODO: Work out whether this is really appropriate. Could set
            // an exception in the completion source, of course...
            throw new ArgumentException("Task was not completed");
    }
}

You'll notice there are a couple of TODO comments there. The exception in PropagateResult really shouldn't happen - the continuation shouldn't be called when the task hasn't completed. I still need to think carefully about how tasks should propagate exceptions though.

The arguments to ContinueWith are more tricky: working through my TimeMachine class and some unit tests with Bill Wagner last week showed just how little I know about how SynchronizationContext, the task awaiters, task schedulers, and TaskContinuationOptions.ExecuteSynchronously all interact. I would definitely need to look into that more deeply before TimeMachine was really ready for heavy use... which means you should probably be looking at the TPL in more depth too.

Conclusion

Sure enough, when you run the code, the results appear in order, as the tasks complete. Here's one sample of the output:

Initial order: 335 468 1842 1991 2512 2603 270 2854 1972 1327
In order of completion:
270
335
468
1327
1842
1972
1991
2512
2603
2854

TODOs aside, the code in this post is remarkable (which I can say with modesty, as I've only refactored it from the code sent to me by another reader and Stephen Toub). It makes me smile every time I think about the seemingly-impossible job it accomplishes. I suspect this approach could be useful in any number of composition blocks - it's definitely one to remember.

Coding in the style of Glee

skeet — Sun, 15 Jan 2012 20:07:55 GMT

As previously mentioned, at CodeMash 2012 I gave a very silly Pecha Kucha talk entitled "Coding in the style of Glee". The video is on YouTube, or can be seen embedded below:

(There's also another YouTube video from a different angle.)

This post gives the 20 slides (which were just text; no fancy pictures unlike my competitors) and what I meant to say about them. (Edited very slightly to remove a couple of CodeMash-specific in-jokes.) Don't forget that each slide was only up for 20 seconds.

Coding in the style of Glee

As you may know, I’m from the UK, and it’s wonderful to be here. This is my first US conference, so it’s great to be in the country which has shared with the world its most marvellous cultural output: the Fox show, Glee.

At first I watched it just for surface story – but now I know better – I know that really, the songs are all about the culture and practice of coding.

(It isn't easy) Bein' Green

When I started coding, it was on a ZX Spectrum, in Basic. It was hard, but the computer came with a great manual. I later learned C from a ringbinder of some course or other – and entirely failed to understand half the language. Of course, this was before Stack Overflow, when it was really hard being a newbie – where could you turn for information?

Getting to know you

Over time I became semi-competent in C, with the help of friends. But learning is a constant process, of course – getting to know new languages and platforms is just part of a good dev's life every day.

Learning itself is a skill – how similar it is to getting to know small children, I leave to your imagination.

Man in the Mirror

Glee doesn’t just talk about the coding experience, of course – it talks about specific technologies. This Michael Jackson song is talking about reflection, of course. Although the idea wasn’t new in Java, it was new to me – and now it would be almost unthinkable to come up with a new platform which didn’t let you find out about what was in the code.

Bridge over Troubled Water

Another technology covered beautifully by Glee is the interop. We’re in a big world, and we always need to talk to other systems. Whether it’s over JNI (heaven help you), P/Invoke, SOAP, REST – whatever, I hope next time you connect to another system, you’ll hear this haunting Simon and Garfunkel melody in the background.

I will survive

And who could forget persistence frameworks. I’m not sure whether Gloria Gaynor had Hibernate and the Entity Framework in mind when she sang this, but I’m utterly convinced that the Glee writers did. When you submit your data, it’s just got to survive – what else would you want?

You can't always get what you want

We’d all like perfect specifications, reliable libraries, ideal languages, etc – but that’s just not going to happen. It’s possible that of course you won’t get what you need – even if you try real hard. But hey, you might just.

Lean on me (or Agile on me)

(I didn't actually have notes written for this one. Copied from the video.)

Glee sympathizes with you - but it also have a bit of an answer: lean on me. Lean and agile development, so we can adapt to constantly changing specifications, and eventually we will have something that is useful. Maybe nothing like what we initially envisaged, but it will be something useful.

Losing my Religion

Of course, we don’t always stay in love with a platform. I’d like to dedicate this slight to Enterprise Java. Fortunately I never had to deal with Enterprise Java Beans, but I “enjoyed” enough other J2EE APIs to make me yearn for a world without BeanProcessorFactoryFactories.

Anything Goes

Now I’m pretty conservative – only in terms of coding, mind you. I’m a statically typed language guy. But Glee celebrates dynamic languages too – languages where really, anything goes until you try to execute it. Even though I haven’t gone down the dynamic route myself much, it’s important that we all welcome the diversity of languages and platforms we have.

Get Happy

Along with the rise of dynamic languages, we seem to have seen a rise of happy developers. We’ve always had enthusiastic developers, but there’s a certain air about your typical Ruby on Rails developer which feels new to me. Again, I’m not a Ruby fan myself – but it’s always nice to see other happy people, and maybe one day I’ll see the light.

Bust your Windows

I don’t know what I can say about this song. Do the Glee writers have it in for Microsoft? I don’t remember “Bust your OSX” or “Bust your Linux” for example. Only Windows is targeted here.

The Safety Dance

One big change for me since joining Google is increased awareness of the need for redundancy – the intricate dance we need to perform to create a service which will stay up no matter what. Where redundancy is a dirty word in most of industry, as developers we celebrate it – and will do anything we can to avoid…

The Only Exception

… a single point of failure.

(Yes, that really is all I'd prepared for that slide. Hence the need for improvisation.)

Telephone

(From video.) Glee celebrates the rise of phone apps. Who these days could be unaware of the importance of the development of mobile applications? And obviously, we can credit the iPhone for that, but since the iPhone, and just smart phone apps, we've also started...

U Can't Touch This

(From video.) Tablets! And touch screen devices of all kinds. So Windows 8 - very touch-based, and sooner or later we're all going to have to get with it. I don't do UIs, I've never done a touch UI in my life, I have no idea how it works. But clearly it's one of the ways forward.

Forget You

As smart phones and tablets become more ubiquitous and more bound to us as people, privacy has become more important. Glee gave us a timely reminder of the reverse of the persistence early on: we need to be able to forget about users, as well as remember them.

(A)waiting for a girl like you

(From video.) I'd like to leave on an up-note, so: I'm clearly very, very excited (really, really excited) about C# 5 and its await keyword so I ask you - I beg you - be excited about development. And always bear in mind your users.

My life would suck without you

Users rule our world. Can’t live without them, can’t shoot ‘em.

Celebrate – we do stuff to make users really happy! This is awesome! We should be thrilled!

(Even for enterprise apps, we’re doing useful stuff. Honest.)

Don't stop believing

(From video.) So to sum up: have fun, keep learning, really, really enjoy what you're doing, and... don't stop!

CodeMash 2012 report

skeet — Sun, 15 Jan 2012 19:38:42 GMT

I'm nearly home - on a bus back from Heathrow airport to Reading - returning from CodeMash 2012. This was my first US conference, and I had a wonderful time. It was pretty densely packed in terms of presenting / recording for me:

I presented two back-to-back sessions jointly with Bill Wagner, on async. These went down really well (particularly Bill's genius idea of using the Doctor Who quote about time being a "big ball of wibbly-wobbly, timey-wimey stuff") and were great fun to give. Bill's a class act, and I think we got the balance between use and underpinnings about right.
I recorded a podcast with Scott Hanselman (we were going to record two, but the first one ended up being longer than expected)
I presented a talk on "C#'s Greatest Mistakes" which ended up being somewhere between a discussion on language design, and a demonstration of surprising "features" of C#. It overran by 15 minutes without me coming close to running out of things to say, but hopefully it was useful. It was a somewhat rambly session, but at least I warned folks of that up-front. It would be nice to be able to present the same sort of material in a really "tight" way, but I'm just not sure how to.
I gave a 20x20 "Pecha Kucha" talk called "Coding in the style of Glee" as the silliest topic I could come up with on short notice. This was absolutely terrifying and extremely silly. I only came third in the contest (and the winner, Leon, was simply phenomenal) but I was happy that I'd only embarrassed myself about as much as I'd expected to. The YouTube video of this is already up, and I'll write a blog post with the slide titles and what I was trying to say in them :)

Unfortunately due to last minute async prep and desperately trying to cobble together slides for the Glee talk, I didn't have time to actually attend as many talks as I'd have liked. Even though I was present for the whole of the Scala Koans session in the PreCompilr on Wednesday, I found myself next to Bruce Eckel, and ended up chatting with him for most of the time. It would have been a bit of a waste not to, really. (And at least some of that talking was Scala-related...) I also watched the whole of the SignalR presentation by Brady Gaster - where I was apparently the only person in the room with an aversion to "dynamic" in C# 4. That made me the butt of a few jokes, but not too many for comfort.

In terms of C#-related talks, I went to the first half of Dustin Campbell's Roslyn session, but was somewhat distracted by putting together Glee slides and had to leave half way through to hand them in. My final session of the conference was Bill Wagner's "Stunt coding in C# - I dare you to try this at home" which was excellent, and a very fitting end to the conference for me.

Highlights of the conference for me:

Messing with Bill Wagner's code at the end of not just our joint async talk but also his Stunt Coding talk. I've never before asked a presented whether they mind me just stealing the keyboard, but I was confident that Bill (and the attendees) would get a kick out of it - and the code was nicer afterwards :)
Meeting so many people... some that I've met before (I hadn't seen Ted Neward since I gate-crashed a party at his house after the MVP 2005 Summit), some I'd met virtually but not physically before (like Bill) and there loads of other folks I'd never known at all before - including Cori Drew. Cori simply seemed to pop up everywhere - I swear she had about 20 clones at CodeMash. (She also recorded the video of the Glee talk, and it's her laughter you can hear - thanks very much, Cori!) Everyone at the conference was incredibly friendly, and I was really touched by how many people said on the last day that they'd appreciated me making the long trip.
Confounding Dustin Campbell and Kevin Pilch-Bisson with my evil generic overloading puzzle. Just to be clear, these are two seriously smart guys and this was a friendly over-lunch challenge. It's always a privilege to meet more of the team responsible for C# and Visual Studio.
The number of families who came - this is something I've never seen at other conferences, and it really made a difference in terms of the atmosphere of the non-dev bits. It was fabulous to see the kids in the water park, for example. Even out of just attendees, there was a greater proportion of women at CodeMash than at other conferences I've been to - obviously still vastly outnumbered by the men, but it was nice to see some improvement on that front.

This will probably be my only international conference for 2012, so it's a good job that it was so wonderfully organized. I really hope I have the chance to attend next year too. Many thanks to everyone who helped make it such a special conference.

Eduasync part 18: Changes between the Async CTP and the Visual Studio 11 Preview

skeet — Thu, 12 Jan 2012 01:34:31 GMT

In preparation for CodeMash, I've been writing some more async code and decompiling it with Reflector. This time I'm using the Visual Studio 11 Developer Preview - the version which installs alongside Visual Studio 2010 under Windows 7. (Don't ask me about any other features of Visual Studio 11 - I haven't explored it thoroughly; I've really only used it for the C# 5 bits.)

There have been quite a few changes since the CTP - they're not visible changes in terms of code that you'd normally write, but the state machine generated by the C# compiler is reasonably different. In this post I'll describe the differences, as best I understand them. There are still a couple of things I don't understand (which I'll highlight within the post) but overall, I think I've got a pretty good handle on why the changes have been made.

I'm going to assume you already have a reasonable grasp of the basic idea of async and how it works - the way that the compiler generates a state machine to represent an async method or anonymous function, with originally-local variables being promoted to instance variables within the state machine, etc. If the last sentence was a complete mystery to you, see Eduasync part 7 for more information. I don't expect you to remember the exact details of what was in the previous CTP though :)

Removal of iterator block leftovers

In the CTP, the code for async methods was based on the iterator block implementation. I suspect that's still the case, but possibly sharing just a little less code. There used to be a few methods and fields which weren't used in async methods, but now they're gone:

There's no now constructor, so no need for the "skeleton" method which replaces the real async method to pass in 0 as the initial state.
There's no Dispose method.
There's no disposing field.

It's nice to see these gone, but it's not terribly interesting. Now on to the bigger changes...

Large structural changes

There's a set of related structural changes which don't make sense individually. I'll describe them first, then look at how it all hangs together, and my guess as to the reasoning behind.

The state machine is now a struct

The declaration of the nested type for the state machine is now something like this:

[CompilerGenerated]
private struct StateMachine : IStateMachine
{
    // Fields common to all async state machines
    // (with caveats)
    private int state;
    private object awaiter;
    public AsyncTaskMethodBuilder<int> builder;
    public Action moveNextDelegate;
    private object stack;

    // Hoisted local variables

    // Methods
    [DebuggerHidden]
    public void SetMoveNextDelegate(Action action) { ... }
    public void MoveNext() { ... }
}

The caveats around the common field are in terms of the return type of the async method (which determines the type of builder used) and whether or not there are any awaits (if there are no awaits, the stack and awaiter fields aren't generated).

Note that throughout this blog post I've changed the names of fields and types - in reality they're all "unspeakable" names including angle-brackets, just like all compiler-generated names.

There's a new assembly-wide interface

As you can see from the code above, the state machine implements an interface (actually called <>t__IStateMachine). One of these is created in the global namespace in each assembly that contains at least one async method or anonymous function, and it looks like this:

[CompilerGenerated]
internal interface IStateMachine
{
void SetMoveNextDelegate(Action action);
}

The implementation for this method is always the same, and it's trivial:

[DebuggerHidden]
public void SetMoveNextDelegate(Action action)
{
this.moveNextDelegate = action;
}

Simplified skeleton method

The method which starts the state machine, which I've been calling the "skeleton" method everywhere, is now a bit simpler than it was. Something like this:

public static Task<int> FooAsync()
{
    StateMachine machine = new StateMachine();
    machine.builder = AsyncVoidMethodBuilder.Create();
    machine.MoveNext();
    return machine.builder.Task;
}

In fact if you decompile the IL, you'll see that it doesn't explicitly initialize the variable to start with - it just declares it, sets the builder field and then calls MoveNext(). That's not valid C# (as all the struct's fields aren't initialized), but it is valid IL. It's equivalent to the code above though. Note how there's nothing to set the continuation - where previously the moveNextDelegate field would be populated within the skeleton method.

Just-in-time delegate creation

Now that the skeleton method doesn't create the delegate representing the continuation, it can be done when it's first required - which is when we first encounter an await expression for an awaitable which hasn't already completed. (If the awaitable has completed before we await it, the generated code skips the continuation and just uses the results immediately and synchronously).

The code for that delegate creation is slightly trickier than you might expect, however. It looks something like this:

Action action = this.moveNextDelegate;
if (action == null)
{
    Task<int> task = this.builder.Task;
    action = new Action(this.MoveNext);
    ((IStateMachine) action.Target).SetMoveNextDelegate(action);
}

There are two oddities here, one of which I mostly understand and one of which I don't understand at all.

I really don't understand the "task" variable here. Why do we need to exercise the AsyncTaskMethodBuilder.Task property? We don't use the result anywhere... does forcing this flush some memory buffer? I have no clue on this one. (See the update at the bottom of the post...)

The part about setting the delegate via the interface makes more sense, but it's subtle. You might expect code like this:

// Looks sensible, but is actually slightly broken
Action action = this.moveNextDelegate;
if (action == null)
{
action = new Action(this.MoveNext);
this.moveNextDelegate = action;
}

That would sort of work - but we'd end up needing to recreate the delegate each time we encountered an appropriate await expression. Although the above code saves the value to the field, it saves it within the current value of the state machine... after we've boxed that value as the target of the delegate. The value we want to mutate is the one within the box - which is precisely why there's an interface, and why the code casts to it.

We can't even just unbox and then set the field afterwards - at least in C# - because the unbox operation is always followed by a copy operation in normal C#. I believe it would be possible for the C# compiler to generate IL which unboxed action.Target without the copy, and then set the field in that. It's not clear to me why the team went with the interface approach instead... I would expect that to be slower (as it requires dynamic dispatch) but I could easily be wrong. Of course, it would also make it impossible to decompile the IL to C#, which would make my talks harder, but don't expect the C# team to bend the compiler implementation for my benefit ;)

(As an aside to all of this, I've gone back and forth on whether the "slightly broken" implementation would recreate the delegate on every appropriate await, or only two. I think it would end up being on every occurrence, as even though on the second occurrence we'd be operating within the context of the first boxed instance, the new delegate would have a reference to a new boxed copy each time. It does my head in a little bit, trying to think about this... more evidence that mutable structs are evil and hard to reason about. It's not the wrong decision in this case, hidden far from the gaze of normal developers, but it's a pain to reason about.)

Single awaiter variable

In the CTP, each await expression generated a separate field within the state machine, and that field was always of the exact awaiter type. In the VS11 Developer Preview, there's always exactly one awaiter field (assuming there's at least one await expression) and it's always of type object. It's used like this:

// Single local variable used by both continuation and first-time paths
TaskAwaiter<int> localAwaiter;

...

if (conditions-for-first-time-execution)
{
      // Code before await

      localAwaiter = task.GetAwaiter();
      if (localAwaiter.IsCompleted)
      {
          goto Await1Completed;
      }
      this.state = 1;
      TaskAwaiter<int>[] awaiterArray = { localAwaiter };
      this.awaiter = awaiterArray;
      // Lazy delegate creation goes here
      awaiterArray[0].OnCompleted(action);
      return;
}
// Continuation would get into here
localAwaiter = ((TaskAwaiter<int>[]) this.awaiter)[0];
this.awaiter = null;
this.state = 0;
Await1Completed:
int result = localAwaiter.GetResult();
localAwaiter = default(TaskAwaiter<int>);

I realize there's a lot of code here, but it does make some sense:

The value of the awaiter field is always either null, or a reference to a single-element array of the awaiter type for one of the await expressions.
A single localAwaiter variable is shared between the two code paths, populated either from the awaitable (on the initial code path) or by copying the value from the array (in the second code path).
The field is always set to null and the local variable is set to its default value after use, presumably for the sake of garbage collection

It's basically a nice way of using the fact that we'll only ever need one awaiter at a time. It's not clear to me why an array is used instead of either using a reference to the awaiter for class-based awaiters, or simply by boxing for struct-based awaiters. The latter would need the same "unbox without copy" approach discussed in the previous section - so if there's some reason why that's actually infeasible, it would explain the use of an array here. We can't use the interface trick in this case, as the compiler isn't in control of the awaiter type (so can't make it implement an interface).

Expression stack preservation

This one is actually a fix to a bug in the async CTP, which I've written about before. We're used to the stack containing our local variables (in the absence of iterator blocks, captured variables etc, and modulo the stack being an implementation detail) but it's also used for intermediate results within a single statement. For example, consider this block of code:

int x = 10;
int y = 5;
int z = x + 50 * y;

That last line is effectively:

Load the value of x onto the stack
Load the value 50 onto the stack
Load the value of y onto the stack
Multiply the top two stack values (50 and y) leaving the result on the stack
Add the top two stack values (x and the previously-computed result) leaving the result on the stack
Store the top stack value into z

Now suppose we want to turn y into a Task<int>:

int x = 10;
Task<int> y = Task.FromResult(5);
int z = x + 50 * await y;

Our state machine needs to make sure that it will preserve the same behaviour as the synchronous version, so it needs the same sort of stack. In the new-style state machine, all of that stack is saved in the "stack" field. It's only one field, but may need to represent multiple different types within the code at various different await expressions - in the code above, for example, it represents two int values. As far as I can discover, the C# compiler generates code which uses the actual type of the value it needs, if it only requires a single value. If it needs multiple values, it uses an appropriate Tuple type, nesting tuples if it goes beyond the number of type parameters supported by the Tuple<...> family of types. So in our case above, we end up with code a bit like this:

// Local variable used in both paths
Tuple<int, int> tuple;

...

// Code before the await
if (conditions-for-first-time-execution)
{
    ...
    tuple = new Tuple<int, int>(this.x, 50);
    this.stack = tuple;
    ...
}

// Continuation would get into here
tuple = (Tuple<int, int>) this.stack;
// IL copies the values from the tuple onto the stack at this point
this.stack = null;

...

// Both the fast and slow code paths get here eventually
this.z = stack0 + stack1 * awaiter.GetResult()

I say it's a bit like this, because it's hard to represent the IL exactly in C# in this case. The tuple is only created if it's needed, i.e. not in the already-completed fast path. In that case, the values are loaded onto the stack but not then put into the tuple - execution skips straight to the code which uses the values already on the stack.

When the awaitable isn't complete immediately, then a Tuple<int, int> is created, stored in the "stack" field, and the continuation is handed to the awaiter. On continuation, the tuple is loaded back from the "stack" field (and cast accordingly), the values are loaded onto the stack - and then we're back into the common code path of fetching the value and performing the add and multiply operations.

Conclusion

As far as I'm aware, those are the most noticeable changes in the generated code. There may well still be a load more changes in Task<T> and the TPL in general - I wouldn't be at all surprised - but that's harder to investigate.

I'm sure all of this has been done in the name of performance (and correctness, in the case of stack preservation). The state machine is now much smaller in terms of the number of fields it requires, and objects are created locally as far as possible (including the state machine itself only requiring heap allocation if there's ever a "slow" awaitable). I suspect there's still some room for optimization, however:

Both the awaiter and the delegate use careful boxing and either arrays or a mutating interface to allow the boxed value to be changed. I suspect that using unbox with the concrete type, but without copying the value, would be more efficient. I may attempt to work this theory up into a test at some point.
If there's only one awaiter type (usually TaskAwaiter<T> for some T), that type could be used instead of object, potentially reducing heap optimization
I've no idea why the builder.Task property is explicitly fetched and then the results discarded
If there's only one await expression, the "stack" field can be strongly typed, which would also avoid boxing if only a single value needs to be within that stack
The stack field could be removed entirely when it's not needed for intermediate stack value preservation. (I believe that would be the case reasonably often.)

The use of mutable value types is really fascinating (for me, at least) - I'm sure most people on the C# team would still say they're evil, but when they're used in a carefully controlled environment where real developers don't have to reason about their behaviour, they can be useful.

Next time, I'll hopefully get back to the idea I promised to write up before, about ordering a collection of tasks in completion order... before they've completed. (Well, sort of.) Should be fun...

Update (January 16th 2012)

Stephen Toub got in touch with me after I posted the original version of this blog entry, to explain the use of the Task property. Apparently the idea is that at this point, we know we're going to return out of the state machine, so the skeleton method is going to access the Task property anyway. However, as we haven't scheduled the continuation yet we also know that nothing will be accessing the Task property on a different thread. If we access it now for the first time, we can lazily allocate the task in the same thread that created the AsyncMethodBuilder, with no risk of contention. If we can force there to be a task ready and waiting for whatever accesses it later, we don't need any synchronization in that area.

So why might we want to allocate the task lazily in the first place? Well, don't forget that we might never have to wait for an await (as it were). We might just have an async method which takes the fast path everywhere. If that's the case, then for certain cases (e.g. a non-generic, successfully completed task, or a Task<bool> which again has completed successfully) we can reuse the same instance repeatedly. Apparently this laziness isn't yet part of the VS11 Developer Preview, but the reason for the property access is in preparation for this.

Another case of micro-optimization - which is fair enough when it's at a system level :)

Awaiting CodeMash 2012

skeet — Sun, 01 Jan 2012 20:43:10 GMT

Happy New Year, everyone!

I'm attempting to make 2012 a quiet year in terms of my speaking engagements - I've turned down a few kind offers already, and I expect to do so again during the year. I may well still give user group talks in evenings if I can do so without having to take holiday, but full conferences are likely to be out, especially international ones. This is partly so I can take more time off to support my wife, Holly, who has her own books to promote. This year will be particularly important for Holly as she's one of the World Book Day 2012 authors - I'm tremendously proud of her, as you can no doubt imagine.

However, there's one international conference I decided to submit proposals for: CodeMash. I've never been to this or any other US conference, but I've heard fabulous things about it. I'm particularly excited that I'll be able to present alongside Bill Wagner, a fellow C# author (probably most famous for Effective C# which I've reviewed before now). Bill and I have never met, although we've participated jointly on a .NET Rocks show before now. I could barely hear Bill when we recorded that though, so it hardly counts :)

The conference schedule for CodeMash shows Bill and I each giving two talks: two individual ones on general C# (C# Stunt Coding by Bill, and C#'s Greatest Mistakes by me) and two sessions on the async support in C# 5... async "from the inside" and "from the outside". Although these have hitherto been shown as separate sessions, everyone involved thought it would make more sense to weave the two together... so this will be a double-length session. Bill will be presenting the "outside" view - how to use async, basically; I'll be presenting the "inside" view - how it all hangs together behind the scenes.

With any luck, this will be much more helpful to the conference attendees, as they should be able to build up confidence in the solid foundations underpinning it all at the same time as seeing how fabulously useful it'll be for developers. It also means that Bill and I can bounce ideas off each other spontaneously as we go - I intend to pay close attention and learn a thing or two myself!

It's pretty much impossible to predict how it'll all hang together, but I'm really excited about the whole shebang. I'll be fascinated to see if and how US conferences differ from the various ones this side of the pond... but it does make the whole thing that bit more nerve-wracking. If you're coming to CodeMash, please grab me and say hi - it never hurts to see a friendly face...

(Note: Bill has a similar blog post posted just before this one.)

Book Review: Fluent C# (Rebecca Riordan, Sams)

skeet — Mon, 05 Dec 2011 19:26:25 GMT

(As usual, I will be sending the publisher a copy of this review to give them and the author a chance to reply to it before I publish it to the blog. Other than including their comments and correcting any factual mistakes they may point out, I don't intend to change the review itself.)

Resources:

Publisher page (includes source code download)
Amazon / Barnes and Noble
My unofficial errata and notes
A more positive series of review blog posts (just for balance)

Introduction and disclaimers

In late October, Sams (the publisher) approached me to ask if I'd be interested in reviewing their newest introductory book on C#. Despite my burgeoning review stack, I said I was interested - I'm always on the lookout for good books to recommend. So, the first disclaimer is that this was a review copy - I didn't have to pay for it. I don't believe that has biased this review though.

Second disclaimer: obviously as C# in Depth is also "a book about C#" you might be wondering whether the two books are competitors. I don't believe this is the case: Fluent C# explicitly talks about its target audience, which is primarily complete newcomers to programming. C# in Depth pretty much requires you to know at least C# 1, or perhaps be very comfortable with a similar language such as Java. I find it hard to imagine someone for whom both books would be suitable.

Obviously that puts me firmly out of the target audience. As I've written before, if you think the two most important questions to answer in a technical book review are "Is it accurate?" and "How good is at teaching its topic?" then any one person will find it hard to answer both questions. Although I'm far from an expert in some of the areas of the book - notably WPF - I'm sure I don't have the same approach as a true newcomer. In particular, I find myself asking the questions I'd need the answers to in order to develop software professionally: how do I test it? How does the deployment model work? How does the data flow? These aren't the same concerns as someone who is coming to programming for the first time. This review should be read with that context in mind: that my approach to the subject matter won't be the same as a regular reader's.

Physical format and style

Fluent C# is very reminiscent of Head-First C# in its approach, even down to the introductory "why this book is great at teaching you" blurb. It's all very informal, with lots of pictures, diagrams and reader exercises. It's a chunky book, at nearly 900 pages including the index - which I'd expect to be pretty daunting to a newcomer. However, that isn't the main impression you come away with. Instead...

It's brown. Everywhere. The diagrams, the text, the pictures - they're all printed in brown, on off-white paper.

Combined with using multiple fonts including cursive ones, this makes for a pointlessly irritating reading experience right from the outset, however good or bad the actual content is. Now it's possible that this is actually deliberate: I was speaking to someone recently who mentioned some research that shows if you use a hard-to-read font in presentations, people tend to end up reading it several times, so you end up with better memories of the content than if it had been "clean". I don't know if that's what Sams intended with this book, but I frequently found myself longing for simple black ink on clean white paper.

Leaving that to one side, I'm not sure I'll ever really be a fan of the general tone of books like this, but I can certainly see that it's popular and therefore presumably helpful to many people. It's not clear to me whether it's possible to create a book which retains the valuable elements of this style while casting off the aspects which rub me up the wrong way. It's something about the enforced jollity which just doesn't quite sit right, but it wouldn't surprise me if that were more a peculiarity of my personality than anything about the book. Again, I've tried to set this to one side when reviewing the book, but it may come through nonetheless.

Structure

The book is broken up into the following sections, with several chapters per section:

Getting started (122 pages - finding your way around Visual Studio, debugging, deployment)
The Language (100 pages - introduction to C#)
The .NET Framework Library (162 pages - text, date/time APIs, collections - and actually more about C# as a language)
Best practice (116 pages - inheritance, some principles, design patterns)
WPF (341 pages)

I've included the page count for each section to show just how much is devoted to WPF. The book goes into much more detail about WPF than it does about the C# language itself (for example, drop shadow effects are included, but the "using" statement and nullable value types aren't). If you want to write any kind of application other than a WPF one, a large part of the book won't be useful to you. That's not to say it's useless per se - and in fact from my point of view, the WPF section was the most useful. The section on brushes is probably the best written in the whole book, for example. At time it feels to me like the author really wanted to write a book about WPF, but was asked to make it one about C# instead. That may well not be the case at all - it was just an impression.

Even though the best practice section talks briefly about MVC, MVP and MVVM, it doesn't really go into enough detail to build anything like a real application - and in fact there's no coverage of persistence of any form. No files, no XML, no database - nothing below the presentation layer, really. As such, although the book claims it's enough to get you started with application development, it actually only provides a veneer. Even though I didn't like the first edition of Head-First C# back in 2008, it did at least take the reader end-to-end - the exercises led to complete applications. The best practice section isn't entirely about architecture and design patterns, however - it's at this point that inheritance is properly introduced. While I wouldn't personally count that as a "best practice" as such, it does at least come at the start of the section, before the genuine patterns/architecture areas which would have been harder to understand without that background.

One aspect which concerned me was the emphasis on the debugger and interactive diagnostics. The author states that developers should expect to spend a large part of their time in the debugger, and she says how she prefers using MessageBox.Show for diagnostics over Console.WriteLine information appearing in the output window. While I'm all for something more sophisticated than Console.WriteLine, there are solutions which are a lot less invasive than popping up a dialog, and which can be left in the code (possibly under an execution-time configuration) to allow diagnostics to be produced for real systems.

The "testing and deployment" chapter says nothing about automated tests - it's as if the author believes that "testing" only involves "running the app in the debugger and seeing if it breaks". I hope that's not actually the case, and I can understand why newcomers ought to at least know about the debugger - but I'd have welcomed at least a few pages introducing unit testing as a way of recording and checking expectations of how your code behaves. My own preference is to spend as little time in the debugger as possible; I know that's not always practical, particularly for UI work, but I think it's a reasonable aim.

Accuracy

Anyone following me on Twitter or Google+ knows where I'm going with this section. After reading through the book, pen in hand (as I always do, even for the books I like), I decided that it was more important to get out some form of errata quickly than this review. As such, I started a Google document which is publicly available to read and add comments to. The result is over 60 pages of notes and errata, and that's excluding the introduction and table of contents. To be fair to the book, some of those notes are matters of disagreement which are more personal opinion than incontrovertible fact - but there are plenty of simple matters of inaccuracy. Some of the worst are:

Claims that String is a value type. (It's a reference type.)
Inconsistency between whether arrays are value types or reference types - but consistently claiming that arrays are immutable, with the exception of the size which can be changed (slowly) using Array.Resize. (Array types are always reference types, and they're always mutable except the size, which is fixed after creation. Array.Resize creates a new array, it doesn't change the size of the existing one.)
Incorrect syntax for chaining from one constructor to another.
The claim that all reference types are mutable. (Some aren't, and indeed I often aim for immutability. The canonical example of an immutable reference type is String.)

There are plenty more - including huge number of samples which simply won't compile. Whole double page spreads where every class declaration is missing the "class" keyword. Pieces of code using VB syntax... the list goes on. (The VB syntax errors are probably explained by the author's other book published at the same time: "Fluent Visual Basic". I suspect there was a certain amount of copy/paste, and the editing process didn't catch all the changes which were needed to reflect the differences between the languages.)

Beyond the factually incorrect statements, there's the matter of terminology. Now I'm well aware that I care more about terminology than more people - but there's simply no reason to start making up terminology or misusing the perfectly good terminology from the specification. The book has a whole section on "commands" in C#, including things like for statements, switch statements, try/catch/finally statements. Additionally, it mislabels class and namespace declarations as "statements", and even mislabels using directives as statements - although it later goes back on the latter point. The word "object" is used at various times to mean any of variable, type, class and object, with no sense of consistency that I could fathom. For example, at one point it's used in two different senses within the same sentence: "As we'll see, you can define several different kinds of objects (called TYPES) in C#, but the one you'll probably work with most often is the OBJECT."

Both accuracy and staying consistent with accepted terminology (primarily the specification) are particularly important for newcomers. If there's a typo in a relatively advanced book - or in one which is about a particular technology (e.g. MVC) rather than an introductory text on a language, the reader is fairly likely to be able to guess what should really be there based on their existing experience. If a beginner comes across the same problem, they're likely to assume it's their fault that the code won't compile. Likewise if they learn the wrong terminology to start with, they'll be severely hampered in communicating effectively with other developers - as well as when reading other books.

I don't want to make it sound like I expect perfection in a book - just yesterday someone mailed me a correction to C# in Depth, and I'd be foolish to try to hold other authors to standards I couldn't meet myself. Nor am I suggesting it's easy to be both accessible and accurate - so often an author may have an accurate picture of a complex topic, but have to simplify it in their writing, particularly for an introductory book like Fluent C#. But there are limits - and in my view this book goes well past the level of error that I'm willing to put up with.

Conclusion

I really don't like ranting. I don't like sounding mean - and I wanted to like this book. While I like C# 4.0 in a Nutshell and Essential C# 4.0, I'm still looking for a book which I can recommend to readers who want a more "lively" kind of book. Unfortunately I really can't recommend Fluent C# to anyone - it is simply too inaccurate, and I believe it will cause confusion and instil bad habits in its readers.

So, what next? I'm hoping that the publisher and author will take my errata on board for the next printing, and revise it thoroughly. At that point I still don't think I'd actually like the book due to its structure and WPF focus (and the colour scheme, which I don't expect to change), but it would at least be more a matter of taste then.

I have some reason to be hopeful - because my review of Head-First C# was somewhat like this one, and one of the authors of that book (Andrew Stellman) was incredibly good about the whole thing, and as a result the second edition of Head-First C# is a much better book than the first edition. Again, it's not quite my preferred style, but for readers who like that sort of thing, it's a much better option than Fluent C# at the moment, and one I'm happy to recommend (with the express caveat of getting the second edition).

At the same time, reading Fluent C# (and particularly thinking about its debugger-first approach) has set me something of a challenge. You see, I've mostly avoided writing for new programmers so far - but I feel it's really important to get folks off on the right foot, and I'd like to have a stab at it. In particular, I would like to see if it's possible to write an introductory text which teaches C# using unit tests wherever possible... but without being dry. Can we have a "fun" but accurate book, which tries to teach C# from scratch without giving the impression that user interfaces are the be-all and end-all of programming? Can I write in a way which is more personal but doesn't feel artificial? I can't see myself starting such a project any time in the next year, but maybe some time in 2013... Watch this space. In the meantime, I'll keep an eye out for any more introductory books which might be more promising than Fluent C#.

Eduasync part 17: unit testing

skeet — Fri, 25 Nov 2011 21:46:45 GMT

In the last post I showed a method to implement "majority voting" for tasks, allowing a result to become available as soon as possible. At the end, I mentioned that I was reasonably confident that it worked because of the unit tests... but I didn't show the tests themselves. I felt they deserved their own post, as there's a bigger point here: it's possible to unit test async code. At least sometimes.

Testing code involving asynchrony is generally a pain. Introducing the exact order of events that you want is awkward, as is managing the threading within tests. With a few benefits with async methods:

We know that the async method itself will only execute in a single thread at a time
We can control the thread in which the async method will execute, if it doesn't configure its awaits explicitly
Assuming the async method returns Task or Task<T>, we can check whether or not it's finished
Between Task<T> and TaskCompletionSource<T>, we have a way of injecting tasks that we understand

Now in our sample method we have the benefit of passing in the tasks that will be awaited - but assuming you're using some reasonably testable API to fetch any awaitables within your async method, you should be okay. (Admittedly in the current .NET framework that excludes rather a lot of classes... but the synchronous versions of those calls are also generally hard to test too.)

The plan

For our majority tests, we want to be able to see what happens in various scenarios, with tasks completing at different times and in different ways. Looking at the test cases I've implemented I have the following tests:

NullSequenceOfTasks
EmptySequenceOfTasks
NullReferencesWithinSequence
SimpleSuccess
InputOrderIsIrrelevant
MajorityWithSomeDisagreement
MajorityWithFailureTask
EarlyFailure
NoMajority

I'm not going to claim this is a comprehensive set of possible tests - it's a proof of concept more than anything else. Let's take one test as an example: MajorityWithFailureTask. The aim of this is to pass three tasks (of type Task<string>) into the method. One will give a result of "x", the second will fail with an exception, and the third will also give a result of "x". The events will occur in that order, and only when all three results are in should the returned task complete, at which point it will also have a success result of "x".

So, the tricky bit (compared with normal testing) is introducing the timing. We want to make it appear as if tasks are completing in a particular order, at predetermined times, so we can check the state of the result between events.

Introducing the TimeMachine class

Okay, so it's a silly name. But the basic idea is to have something to control the logical flow of time through our test. We're going to ask the TimeMachine to provide us with tasks which will act in a particular way at a given time, and then when we've started our async method we can then ask it to move time forward, letting the tasks complete as they go. It's probably best to look at the code for MajorityWithFailureTask first, and then see what the implementation of TimeMachine looks like. Here's the test:

[Test]
public void MajorityWithFailureTask()
{
    var timeMachine = new TimeMachine();
    // Second task gives a different result
    var task1 = timeMachine.AddSuccessTask(1, "x");
    var task2 = timeMachine.AddFaultingTask<string>(2, new Exception("Bang!"));
    var task3 = timeMachine.AddSuccessTask(3, "x");

    var resultTask = MoreTaskEx.WhenMajority(task1, task2, task3);
    Assert.IsFalse(resultTask.IsCompleted);

    // Only one result so far - no consensus
    timeMachine.AdvanceTo(1);
    Assert.IsFalse(resultTask.IsCompleted);

    // Second result is a failure
    timeMachine.AdvanceTo(2);
    Assert.IsFalse(resultTask.IsCompleted);

    // Third result gives majority verdict
    timeMachine.AdvanceTo(3);
    Assert.AreEqual(TaskStatus.RanToCompletion, resultTask.Status);
    Assert.AreEqual("x", resultTask.Result);
}

As you can see, there are two types of method:

AddSuccessTask / AddFaultingTask / AddCancelTask (not used here) - these all take the time at which they're going to complete as their first parameter, and the method name describes the state they'll reach on completion. The methods return the task created by the time machine, ready to pass into the production code we're testing.
AdvanceTo / AdvanceBy (not used here) - make the time machine "advance time", completing pre-programmed tasks as it goes. When those tasks complete, any continuations attached to them also execute, which is how the whole thing hangs together.

Now forcing tasks to complete is actually pretty simple, if you build them out of TaskCompletionSource<T> to start with. So all we need to do is keep our tasks in "time" order (which I achieve with SortedList), and then when we're asked to advance time we move through the list and take the appropriate action for all the tasks which weren't completed before, but are now. I represent the "appropriate action" as a simple Action, which is built with a lambda expression from each of the Add methods. It's really simple:

public class TimeMachine
{
    private int currentTime = 0;
    private readonly SortedList<int, Action> actions = new SortedList<int, Action>();

    public int CurrentTime { get { return currentTime; } }

    public void AdvanceBy(int time)
    {
        AdvanceTo(currentTime + time);
    }

    public void AdvanceTo(int time)
    {
        // Okay, not terribly efficient, but it's simple.
        foreach (var entry in actions)
        {
            if (entry.Key > currentTime && entry.Key <= time)
            {
                entry.Value();
            }
        }
        currentTime = time;
    }

    public Task<T> AddSuccessTask<T>(int time, T result)
    {
        TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();
        actions[time] = () => tcs.SetResult(result);
        return tcs.Task;
    }

    public Task<T> AddCancelTask<T>(int time)
    {
        TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();
        actions[time] = () => tcs.SetCanceled();
        return tcs.Task;
    }

    public Task<T> AddFaultingTask<T>(int time, Exception e)
    {
        TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();
        actions[time] = () => tcs.SetException(e);
        return tcs.Task;
    }
}

Okay, that's a fair amount of code for a blog posts (and yes, it could do with some doc comments etc!) but considering that it makes life testable, it's pretty simple.

So, is that it?

It works on my machine... with my test runner... in simple cases...

When I first ran the tests using TimeMachine, they worked almost immediately. This didn't surprise me nearly as much as it should have done. You see, when the tests execute, they use async/await in the normal way - which means the continuations are scheduled on "the current task scheduler". I have no idea what the current task scheduler is in unit tests. Or rather, it feels like something which is implementation specific. It could easily have worked when running the tests from ReSharper, but not from NCrunch, or not from the command line NUnit test runner.

As it happens, I believe all of these run tests on thread pool threads with no task scheduler allocated, which means that the continuation is attached to the task to complete "in-line" - so when the TimeMachine sets the result on a TaskCompletionSource, the continuations execute before that call returns. That means everything happens on one thread, with no ambiguity or flakiness - yay!

However, there are two problems:

The words "I believe" aren't exactly confidence-inspiring when it comes to testing that your software works correctly.
Our majority voting code only ever sees one completed task at a time - we're not testing the situation where several tasks complete so quickly together that the continuation doesn't get chance to run before they've all finished.

Both of these are solvable with a custom TaskScheduler or SynchronizationContext. Without diving into the docs, I'm not sure yet which I'll need, but the aim will be:

Make TimeMachine implement IDisposable
In the constructor, set the current SynchronizationContext (or TaskScheduler) to a custom one having remembered what the previous one was
On disposal, reset the context
Make the custom scheduler keep a queue of jobs, such that when we're asked to advance to time T, we complete all the appropriate tasks but don't execute any continuations, then we execute all the pending continuations.

I don't yet know how hard it will be, but hopefully the Parallel Extensions Samples will help me.

Conclusion

I'm not going to claim this is "the" way of unit testing asynchronous methods. It's clearly a proof-of-concept implementation of what can only be called a "test framework" in the loosest possible sense. However, I hope it gives an example of a path we might take. I'm looking forward to seeing what others come up with, along with rather more polished implementations.

Next time, I'm going to shamelessly steal an idea that a reader mailed me (with permission, of course). It's insanely cool, simple and yet slightly brain-bending, and I suspect will handy in many situations. Love it.

Eduasync part 16: Example of composition: majority voting

skeet — Tue, 22 Nov 2011 23:18:41 GMT

Note: For the rest of this series, I'll be veering away from the original purpose of the project (investigating what the compiler is up to) in favour of discussing the feature itself. As such, I've added a requirement for AsyncCtpLib.dll - but due to potential distribution restrictions, I've felt it safest not to include that in the source repository. If you're running this code yourself, you'll need to copy the DLL from your installation location into the Eduasync\lib directory before it will build - or change each reference to it.

One of the things I love about async is the compositional aspect. This is partly due to the way that the Task Parallel Library encourages composition to start with, but async/await makes it even easier by building the tasks for you. In the next few posts I'll talk about a few examples of interesting building blocks. I wouldn't be surprised to see an open source library with a proper implementation of some of these ideas (Eduasync is not designed for production usage) whether from Microsoft or a third party.

In project 26 of Eduasync, I've implemented "majority voting" via composition. The basic idea is simple, and the motivation should be reasonably obvious in this day and age of redundant services. You have (say) five different tasks which are meant to be computing the same thing. As soon as you have a single answer which the majority of the tasks agree on, the code which needs the result can continue. If the tasks disagree, or fail (or a combination leading to no single successful majority result), the overall result is failure too.

My personal experience with services requiring a majority of operations to return is with Megastore, a storage system we use at Google. I'm not going to pretend to understand half of the details of how Megastore works, and I'm certainly not about to reveal any confidential information about its internals or indeed how we use it, but basically when discussing it with colleagues at around the time that async was announced, I contemplated what a handy feature async would be when implementing a Megastore client. It could also be used in systems where each calculation is performed in triplicate to guard against rogue errors - although I suspect the chances of those systems being implemented in C# are pretty small.

It's worth mentioning that the implementation here wouldn't be appropriate for something like a stock price service, where the result can change rapidly and you may be happy to tolerate a small discrepancy, within some bounds.

The API

Here's the signatures of the methods we'll implement:

public static Task<T> WhenMajority<T>(params Task<T>[] tasks)

public static Task<T> WhenMajority<T>(IEnumerable<Task<T>> tasks)

Obviously the first just delegates to the second, but it's helpful to have both forms, so that we can pass in a few tasks in an ad hoc manner with the first overload, or a LINQ-generated sequence of tasks with the second.

The name is a little odd - it's meant to match WhenAll and WhenAny, but I'm sure there are better options. I'm not terribly interested in that at the moment.

It's easy to use within an async method:

Task<int> firstTask = firstServer.ComputeSomethingAsync(input);
Task<int> secondTask = selectServer.ComputeSomethingAsync(input);
Task<int> thirdTask = thirdServer.ComputeSomethingAsync(input);

int result = await MoreTaskEx.WhenMajority(firstTask, secondTask, thirdTask);

Or using the LINQ-oriented overload:

var tasks = servers.Select(server => server.ComputeSomethingAsync(input));
int result = await MoreTaskEx.WhenMajority(tasks);

Of course we could add an extension method (dropping the When prefix as it doesn't make as much sense there, IMO):

int result = await servers.Select(server => server.ComputeSomethingAsync(input))
.MajorityAsync();

The fact that we've stayed within the Task<T> model is what makes it all work so smoothly. We couldn't easily express the same API for other awaitable types in general although we could do it for any other specific awaitable type of course. It's possible that it would work using dynamic, but I'd rather avoid that :) Let's implement it now.

Implementation

There are two parts to the implementation, in the same way that we implemented LINQ operators in Edulinq - and for the same reason. We want to go bang immediately if there are any clear input violations - such as the sequence of tasks being null or empty. This is in line with the Task-based Asynchronous Pattern white paper:

An asynchronous method should only directly raise an exception to be thrown out of the MethodNameAsync call in response to a usage error*. For all other errors, exceptions occurring during the execution of an asynchronous method should be assigned to the returned Task.

Now it occurs to me that we don't really need to do this in two separate methods (one for precondition checking, one for real work). We could create an async lambda expression of type Func<Task<T>>, and make the method just return the result of invoking it - but I don't think that would be great in terms of readability.

So, the first part of the implementation performing validation is really simple:

public static Task<T> WhenMajority<T>(params Task<T>[] tasks)
{
    return WhenMajority((IEnumerable<Task<T>>) tasks);
}

public static Task<T> WhenMajority<T>(IEnumerable<Task<T>> tasks)
{
    if (tasks == null)
    {
        throw new ArgumentNullException("tasks");
    }
    List<Task<T>> taskList = new List<Task<T>>(tasks);
    if (taskList.Count == 0)
    {
        throw new ArgumentException("Empty sequence of tasks");
    }
    foreach (var task in taskList)
    {
        if (task == null)
        {
            throw new ArgumentException("Null task in sequence");
        }
    }
    return WhenMajorityImpl(taskList);
}

The interesting part is obviously in WhenMajorityImpl. It's mildly interesting to note that I create a copy of the sequence passed in to start with - I know I'll need it in a fairly concrete form, so it's appropriate to remove any laziness at this point.

So, here's WhenMajorityImpl, which I'll then explain:

private static async Task<T> WhenMajorityImpl<T>(List<Task<T>> tasks)
{
    // Need a real majority - so for 4 or 5 tasks, must have 3 equal results.
    int majority = (tasks.Count / 2) + 1;
    int failures = 0;
    int bestCount = 0;

    Dictionary<T, int> results = new Dictionary<T, int>();
    List<Exception> exceptions = new List<Exception>();
    while (true)
    {
        await TaskEx.WhenAny(tasks);
        var newTasks = new List<Task<T>>();
        foreach (var task in tasks)
        {
            switch (task.Status)
            {
                case TaskStatus.Canceled:
                    failures++;
                    break;
                case TaskStatus.Faulted:
                    failures++;
                    exceptions.Add(task.Exception.Flatten());
                    break;
                case TaskStatus.RanToCompletion:
                    int count;
                    // Doesn't matter whether it was there before or not - we want 0 if not anyway
                    results.TryGetValue(task.Result, out count);
                    count++;
                    if (count > bestCount)
                    {
                        bestCount = count;
                        if (count >= majority)
                        {
                            return task.Result;
                        }
                    }
                    results[task.Result] = count;
                    break;
                default:
                    // Keep going next time. may not be appropriate for Created
                    newTasks.Add(task);
                    break;
            }
        }
        // The new list of tasks to wait for
        tasks = newTasks;

        // If we can't possibly work, bail out.
        if (tasks.Count + bestCount < majority)
        {
            throw new AggregateException("No majority result possible", exceptions);
        }
    }
}

I should warn you that this isn't a particularly efficient implementation - it was just one I wrote until it worked. The basic steps are:

Work out how many results make a majority, so we know when to stop
Keep track of how many "votes" our most commonly-returned result has, along with the counts of all the votes
Repeatedly:

Wait (asynchronously) for at least of the remaining tasks to finish (many may finish "at the same time")
Start a new list of "tasks we're going to wait for next time"
Process each task in the current list, taking an action on each state:

If it's been cancelled, we'll treat that as a failure (we could potentially treat "the majority have been cancelled" as a cancellation, but for the moment a failure is good enough)
If it's faulted, we'll add the exception to the list of exceptions, so that if the overall result ends up as failure, we can throw an AggregateException with all of the individual exceptions
If it's finished successfully, we'll check the result:

Add 1 to the count for that result (the dictionary will use the default comparer for the result type, which we assume is good enough)
If this is greater than the previous "winner" (which could be for the same result), check for it being actually an overall majority, and return if so.

If it's still running (or starting), add it to the new task list

Check whether enough tasks have failed - or given different results - so ensure that a majority is now impossible. If so, throw an AggregateException to say so. This may have some exceptions, but it may not (if there are three tasks which gave different results, none of them actually failed)

Each iteration of the "repeatedly" will have a smaller list to check than before, so we'll definitely terminate at some point.

I mentioned that it's inefficient. In particular, we're ignoring the fact that WhenAny returns a Task<Task<T>>, so awaiting that will actually tell us a task which has finished. We don't need to loop over the whole collection at that point - we could just remove that single task from the collection. We could do that efficiently if we kept a Dictionary<Task<T>, LinkedListNode<Task<T>> and a LinkedList<Task<T>> - we'd just look up the task which had completed in the dictionary, remove its node from the list, and remove the entry from the dictionary. We wouldn't need to create a new collection each time, or iterate through all of the old one. However, that's a job for another day... as is allowing a cancellation token to be passed in, and a custom equality comparer.

Conclusion

So we can make this implementation smarter and more flexible, certainly - but it's not insanely tricky to write. I'm reasonably confident that it works, too - as I have unit tests for it. They'll come in the next part. The important point from this post is that by sticking within the Task<T> world, we can reasonably easily create building blocks to allow for composition of asynchronous operations. While it would be nice to have someone more competent than myself write a bullet-proof, efficient implementation of this operation, I wouldn't feel too unhappy using a homegrown one in production. The same could not have been said pre-async/await. I just wouldn't have had a chance of getting it right.

Next up - the unit tests for this code, in which I introduce the TimeMachine class.

Eduasync part 15: implementing COMEFROM with a horrible hack

skeet — Fri, 11 Nov 2011 22:15:11 GMT

Ages ago when I wrote my previous Eduasync post, I said we'd look at a pipeline model of coroutines. I've decided to skip that, as I do want to cover the topic of this post, and I've got some more "normal" async ideas to write about too. If you want to look at the pipeline coroutines code, it's project 20 in the source repository. Have fun, and don't blame me if you get confused reading it - so do I.

The code I am going to write about is horrible too. It's almost as tricky to understand, and it does far nastier things. Things that the C# 5 specification explicitly says you shouldn't do.

If it makes you feel any better when your head hurts reading this code, spare a thought for me - I haven't looked at it in over six months, and I don't have a blog post explaining how it's meant to work. I just have almost entirely uncommented code which is designed to be hard to understand (in terms of the main program flow).

On no account should any code like this ever be used for anything remotely serious.

With that health warning out of the way, let's have a look at it...

COMEFROM at the caller level

The idea is to implement the COMEFROM control structure, which is sort of the opposite of GOTO (or in my implementation, more of a GOSUB). There are two operations, effectively:

ComeFrom(label): Register interest in a particular label.
Label(label): If anyone has registered interested in the given label, keep going from their registration point (which will be within a method), then continue from where we left off afterwards.

In some senses it's a little like the observer pattern, with labels taking the place of events. However, it looks entirely different and is much harder to get your head round, because instead of having a nicely-encapsulated action which is subscribed to an event, we just have a ComeFrom call which lets us jump back into a method somewhat arbitrarily.

I have two implementations, in project 22 and project 23 in source control. Project 22 is almost sane; a little funky, but not too bad. Project 23 is where the fun really happens. In addition to the operations listed above, there's an Execute operation which is sort of an implementation detail - it allows an async method containing ComeFrom calls to be executed without returning earlier than we might want.

Let's look at some code and the output, and try to work out what's going on.

internal class Program
{
    private static void Main(string[] args)
    {
        Coordinator coordinator = new Coordinator(SimpleEntryPoint);
        coordinator.Start();
    }

    private static async void SimpleEntryPoint(Coordinator coordinator)
    {
        await coordinator.Execute(SimpleOtherMethod);

        Console.WriteLine("First call to Label(x)");
        await coordinator.Label("x");

        Console.WriteLine("Second call to Label(x)");
        await coordinator.Label("x");

        Console.WriteLine("Registering interesting in y");
        bool firstTime = true;
        await coordinator.ComeFrom("y");

        Console.WriteLine("After ComeFrom(y). FirstTime={0}", firstTime);

        if (firstTime)
        {
            firstTime = false;
            await coordinator.Label("y");
        }
        Console.WriteLine("Finished");
    }

    private static async void SimpleOtherMethod(Coordinator coordinator)
    {
        Console.WriteLine("Start of SimpleOtherMethod");

        int count = 0;
        await coordinator.ComeFrom("x");

        Console.WriteLine("After ComeFrom x in SimpleOtherMethod. count={0}. Returning.",
                          count);
        count++;
    }
}

The reason for the "Simple" prefix on the method names is that there's another example in the same file, with a more complex control flow.

Here's the output - then we can look at why we're getting it...

Start of SimpleOtherMethod
After ComeFrom x in SimpleOtherMethod. count=0. Returning.
First call to Label(x)
After ComeFrom x in SimpleOtherMethod. count=1. Returning.
Second call to Label(x)
After ComeFrom x in SimpleOtherMethod. count=2. Returning.
Registering interesting in y
After ComeFrom(y). FirstTime=True
After ComeFrom(y). FirstTime=False
Finished

So, the control flow is a bit like this:

Start SimpleEntryPoint
- Call into SimpleOtherMethod
  - Log "Start of SimpleOtherMethod"
  - Initialize the "count" variable with value 0
  - Register interest in x; ComeFrom remembers the continuation but keeps going.
  - Log "After ComeFrom x in SimpleOtherMethod. count=0. Returning."
  - Increment count to 1.
  - Return.
- Return takes us back to SimpleEntryPoint...
Log "First call to Label(x)"
Call Label("x")...
- ... which takes us back into SimpleOtherMethod (remember, the method we thought we'd finished executing?) just after ComeFrom
  - Log AfterComeFrom x in SimpleOtherMethod. count=1. Returning.
  - Increment count to 2.
  - Return.
- Return takes us back to SimpleEntryPoint...
Log "Second call to Label(x)"
Call Label("x")...
- ... which takes us back into SimpleOtherMethod again
  - Log AfterComeFrom x in SimpleOtherMethod. count=2. Returning.
  - Increment count to 3.
  - Return.
- Return takes us back to SimpleEntryPoint...
Log "Registering interest in y"
Initialize the "firstTime" variable with value true.
Register interest in y; ComeFrom remembers the continuation and keeps going
Log "After ComeFrom(y). FirstTime=True"
Check the value of firstTime... It's true, so:
- Set firstTime to false
- Call Label("y")
... which takes us back to earlier in the method (just after ComeFrom), like a normal looping construct...
Log "After ComeFrom(y). FirstTime=False"
Check the value of firstTime... It's false, so:
- Log "Finished"
- Exit!

Doing all of this has a few interesting challenges. Let's look at them one at a time... and I would strongly advise you not to try to pay too much attention to the details.

Noting a continuation and continuing regardless...

Just as a quick reminder before we get cracking, it's worth remembering that all of this is entirely synchronous, despite being implemented with async. There's only a single user thread involved here. As with previous parts, we maintain a stack of actions to call, and basically keep calling from the top until we're done - but the actions we call can create extra stack entries, of course.

ComeFrom has unusual semantics in terms of async. We want to remember the continuation and keep executing as if we didn't need to wait. We can easily do one side or the other. If we wanted to just keep going without needing to know about the continuation, we could just return true from IsCompleted. If we just want to remember the continuation, we can make the awaiter's IsCompleted property return false, and remember the continuation when it's passed to OnCompleted. How do we do both?

Well, effectively we want to remember the continuation and then call it immediately. But we can't just call it directly from OnCompleted, as otherwise each ComeFrom call would end up in a "real" execution stack from, whereas our execution stack is stored as a Stack<Action>. So instead, we need to remember the continuation and immediately put it at the top of the stack.

However, that only works if as soon as the generated code returns from the async method containing the ComeFrom call, we go back into the state machine. If we'd just called SimpleOtherMethod directly in SimpleEntryPoint, we would have continued within SimpleEntryPoint with the new stack entry just waiting around. This is why we need the Executor method: that does exactly the same thing, effectively shuffling the stack around. When it's given something to execute, it puts its own continuation on the action stack, then the action it's been asked to execute, then returns. The top level code will then pick up the original action, and we're away.

So, here's the code for Execute, which is the simplest part of the coordinator:

public ExecuteAwaiter Execute(Action<Coordinator> action)
{
    return new ExecuteAwaiter(() => action(this), this);
}

public class ExecuteAwaiter
{
    private readonly Action action;
    private readonly Coordinator coordinator;

    internal ExecuteAwaiter(Action action, Coordinator coordinator)
    {
        this.action = action;
        this.coordinator = coordinator;
    }

    public ExecuteAwaiter GetAwaiter()
    {
        return this;
    }

    // Always yield
    public bool IsCompleted { get { return false; } }

    public void OnCompleted(Action callerContinuation)
    {
        // We want to execute the action continuation, then get back here,
        // allowing any extra continuations put on the stack *within* the action
        // to be executed.
        coordinator.stack.Push(callerContinuation);
        coordinator.stack.Push(action);
    }

    public void GetResult()
    {
    }
}

All the awaitables in this project return themselves as the awaiter - when you don't need any other state, it's an easy step to take.

That's all we need to say about Execute, but how exactly are we capturing the continuation in ComeFrom?

Capturing continuations

Once we've got the action stack shuffling under our belts, there are two more problems with ComeFrom:

What happens if we ComeFrom the same label twice?
How do we really capture a continuation?

The first point didn't come up in the sample I've shown here, but it does come up in the more complex example - imagine if SimpleOtherMethod had two ComeFrom calls; when we jump back to the first one, we'll execute the second one again. I made a simple policy decision to only allow a single "return point" for any label - if a ComeFrom call tries to register the existing continuation point for a label, we ignore it; otherwise we throw an exception. So we only need to care about a single continuation for any label, which makes life easier.

The second point is trickier. If you remember back to earlier posts in this series, we saw that the state machine generated for async only really contains a single entry point (MoveNext) which is used for all continuations. A variable in the state machine is responsible for remembering where we were within it between calls. So in order to really make the continuation remember the point at which it needs to continue, we need to remember that state. We need to store an object for the continuation, which contains the delegate to invoke, and the state of the state machine when we were first passed the continuation. I've created a class for this, unimaginatively called Continuation, which looks like this:

/// <summary>
/// This hack allows a continuation to be executed more than once,
/// contrary to the C# spec. It does this using reflection to store the
/// value of the "state" field within the generated class. NEVER, EVER, EVER
/// try to use this in real code. It's purely for fun.
/// </summary>
internal sealed class Continuation : IEquatable<Continuation>
{
    private readonly int savedState;
    private readonly object target;
    private readonly FieldInfo field;
    private readonly Action action;

    internal Continuation(Action action)
    {
        target = action.Target;
        field = target.GetType().GetField("<>1__state", BindingFlags.Instance | BindingFlags.NonPublic);
        savedState = (int) field.GetValue(target);
        this.action = action;
    }

    internal void Execute()
    {
        field.SetValue(target, savedState);
        action();
    }

    // Snip Equals/GetHashCode
}

Yes, we use reflection to fish out the <>1__state variable initially, and poke the state machine with the same value when we next want to execute the continuation. All highly implementation-specific, of course.

Now the ComeFrom method is reasonably straightforward - all we need is a dictionary mapping labels to continuations. Oh, and the same action stack shuffling as for Execute:

// In the coordinator
private readonly Dictionary<string, Continuation> labels = new Dictionary<string, Continuation>();

public ComeFromAwaiter ComeFrom(string label)
{
    return new ComeFromAwaiter(label, this);
}

public struct ComeFromAwaiter
{
    private readonly string label;
    private readonly Coordinator coordinator;

    internal ComeFromAwaiter(string label, Coordinator coordinator)
    {
        this.label = label;
        this.coordinator = coordinator;
    }

    public ComeFromAwaiter GetAwaiter()
    {
        return this;
    }

    // We *always* want to be given the continuation
    public bool IsCompleted { get { return false; } }

    public void OnCompleted(Action action)
    {
        Continuation newContinuation = new Continuation(action);
        Continuation oldContinuation;
        if (!coordinator.labels.TryGetValue(label, out oldContinuation))
        {
            // First time coming from this label. Always succeeds.
            coordinator.labels[label] = newContinuation;
        }
        else
        {
            // Current semantics are to prohibit two different ComeFrom calls for the same label.
            // An alternative would be to just replace the existing continuation with the new one,
            // in which case we wouldn't need any of this - we could just use
            // coordinator.labels[label] = newContinuation;
            // unconditionally.
            if (!oldContinuation.Equals(newContinuation))
            {
                throw new InvalidOperationException("Additional continuation detected for label " + label);
            }
            // Okay, we've seen this one before. Nothing to see here, move on.
        }
        // We actually want to continue from where we were: we're only really marking the
        // ComeFrom point.
        coordinator.stack.Push(action);
    }

    public void GetResult()
    {
    }
}

There's one interesting point here which is somewhat subtle, and screwed me up for a bit...

The default value of a struct is always valid...

You may have noticed that ComeFromAwaiter is a struct. That's pretty unusual for me. However, it's also absolutely critical. Without it, we'd get a NullReferenceException when we execute the continuation the second time.

Normally, the flow of async methods looks a bit like this, for an await expression taking the "long" route (i.e. IsCompleted is false):

Call GetAwaiter() and assign the result to an awaiter field
Call IsCompleted (which returns false in this scenario)
Set the state variable to remember where we'd got to
Call OnCompleted
Return
... When we continue...
Set state to 0 (running)
Call GetResult() on the awaiter
Set the awaiter field to default(TypeOfAwaiter)
Continue

Now that's fine when we're only continuing once - but if we need to jump into the middle of that sequence a second time, we're going to call GetAwaiter() on the awaiter field after it's been set to the default value of the awaiter type. If the default value is null, we'll go bang. So we must use a struct.

Fortunately, our GetResult() call doesn't need any of the state in the awaiter - it's purely there to satisfy the normal flow of things. So we're quite happy with a "default" ComeFrom awaiter.

Finally, labels...

We've now done all the hard work. The final piece of the puzzle is Label, which just needs to check whether there's a continuation to jump to, and shuffle the action stack in the way we're now painfully accustomed to:

public LabelAwaiter Label(string label)
{
    Continuation continuation;
    labels.TryGetValue(label, out continuation);
    return new LabelAwaiter(continuation, this);
}

public class LabelAwaiter
{
    private readonly Continuation continuation;
    private readonly Coordinator coordinator;

    internal LabelAwaiter(Continuation continuation, Coordinator coordinator)
    {
        this.continuation = continuation;
        this.coordinator = coordinator;
    }

    public LabelAwaiter GetAwaiter()
    {
        return this;
    }

    // If there's no continuation to execute, just breeze through.
    public bool IsCompleted { get { return continuation == null; } }

    public void OnCompleted(Action action)
    {
        // We want to execute the ComeFrom continuation, then get back here.
        coordinator.stack.Push(action);
        coordinator.stack.Push(continuation.Execute);
    }

    public void GetResult()
    {
    }
}

Almost painfully simple, really.

So that looks like all the code that's used, right? Not quite...

Reusable builders?

As we saw in the sample code, we can end up finishing the same async method multiple times (SimpleOtherMethod completes three times). That's going to call SetResult on the AsyncVoidMethodBuilder three times... which feels like it should go bang. Indeed, when I revisited my code earlier I wondered why it didn't go bang - it's the sort of illegal state transition the framework is usually pretty good at picking up on.

Then I remembered - this isn't the framework's AsyncVoidMethodBuilder - it's mine. And my SetResult method in this project does absolutely nothing. How convenient!

Make it stop, make it stop!

Okay thiat was a pretty quick tour of some horrible code. You'll never have to do anything like this with async in sane code, but it certainly made me painfully familiar with how it all worked. Just to recap on the oddities involved:

We needed to capture a continuation and then immediately keep going, almost as if the awaiter had said the awaitable had completed already. This involved shenanigans with the execution model and an extra method (Execute)
We needed to remember the state of a continuation, which we did with reflection.
We needed to make awaiter.GetResult() a valid call after awaiter had been reset to the default value for the type
We needed to ensure that the builder created in the skeleton method could have SetResult called on it multiple times

That's all on continuations and co-routines, I promise.

Next time (hopefully soon) I'll look at an example of how composition works so neatly in async, and then show how we can unit test async methods - at least sometimes.

Laptop review: Kobalt G150

skeet — Sun, 18 Sep 2011 07:09:41 GMT

EDIT, 17th October 2011: Last week Kobalt closed down... so the choice about whether or not I'd buy from them again is now moot. However, PC Specialist sells a very similar spec, now including the matte screen...

As some of you will know, our house was burgled in April, and the thieves took three laptops (and very little else), including my main personal laptop. Obviously I ordered a replacement, partly covered by the insurance from my old laptop. However, I took the opportunity to spoil myself a little... I ordered a G150 from Kobalt Computers. Various people have taken an interest in the progress and results of this, so this post is a little review.

Specs

As I said, I spoiled myself a little... the specs are somewhat silly:

Overall, it's a G150 which is based on the Clevo P150HM chassis
Screen: 1920x1080, matte, 95% gamut
CPU: Intel Sandybridge Core-i7 2720QM; quad core 2.2-3.33GHz
Graphics: Nvidia GeForce GTX 580M
RAM: 16GB Corsair DDR3
Disk: SSD - Intel 510, 250GB
Optical: Blu-ray ROM; DVD/RW

How does it run?

Well how do you think it runs? :) Obviously it's very nippy indeed. I'm not sure I've ever used more than a couple of cores at a time yet, but it's nice to know I can test out parallelization when I want to :) While Windows Experience numbers are obviously pretty crude, they're pleasant enough that I might as well show them off:

Visual Studio 2010 still takes a while to come up (10-15 seconds) whereas Office components start pretty much instantly - so I don't know where the bottleneck for VS is. You can do an awful lot in terms of both disk and CPU in 10 seconds on this laptop, so it's a bit of a mystery. (Eclipse starts noticeably faster.) However, once running, Visual Studio is as fast as you'd expect on this machine - builds and tests are nippy, and the editor is noticeably more responsive than on the "make-do" laptop I've been using since April.

I can't say I'm much of a gamer, but my experiences in Call Of Duty: Black Ops and Portal 2 have been wonderful so far; I can put everything on high settings until it looks absolutely beautiful, and still get a good frame rate. I've never had a laptop with a really good graphics card before, and the one in this beast is one of the most powerful out there, so I've really got no excuse for not getting into gaming more, other than my obvious lack of free time. I'm also looking forward to investigating the possibility of writing code in C# to be executed on the GPU - I believe there are a couple of projects around that, so it'll be fun to look into.

With a fast SSD, the boot time is fabulously fast - although it does take a while to go to sleep, as I use hybrid sleep mode and it needs to dump memory to disk first. That's one downside of having a large amount of memory, of course. There's still a lot of debate around the longevity of solid state drives, but the improved performance is so noticeable that I'd definitely not go back to a "normal" hard drive now. I chose the Intel 510 over some slightly faster drives as the 510 is generally reckoned to be more reliable - so I'm hedging my bets somewhat. I suspect the difference in performance between "stupidly fast" and "ridiculously fast" is irrelevant to me.

The screen is beautiful - just "really nice" for normal desktop work, but amazing for games and video - that's where the matte nature really wins out. The contrast is particularly nice, at least in the short tests I've performed so far. The hinge feels pleasantly firm but not stiff - it's hard to judge this early, but hopefully it'll prove robust over time. This screen is one of the reasons I chose Kobalt - I believe they're the only UK company selling machines with this screen, and I'd certainly recommend that anyone who has the chance to go for the matte screen should do so.

Personally I use a separate keyboard most of the time (see below) but the keyboard on the G150 itself is a nice chiclet style one. I'm not terribly fond of the layout of the cursor keys of the fact that there's no separate home / end / page up / page down keys, but it's not a big deal. The feeling of the keys themselves is good, and not too loud. The trackpad is fine - I've turned off "tap to click" as it always ends up activating when I don't want to, but that's not specific to this particular laptop - I always find the same thing. Maybe I type with my palms particularly close to the trackpad, or something like that.

A few more random, esoteric points:

The power socket is "grippy" which makes it slightly harder to pull out the power, but does give a feeling of security. This is clearly a deliberate decision, and while it's not one which would suit everyone, I'm pretty happy with it.
The fan comes on and goes off reasonably regularly, which can prove a little distracting sometimes, but is the natural result of having a fast/hot laptop, I guess. The fan itself is fairly quiet under normal load, so I'd probably be fine with it being constantly on - it's the stop / start nature that jars a little. Not a big deal once you get used to it.
The webcam is really washed out - I don't think I'd really want to use it, to be honest. I don't know whether it's my particular hardware, the general make/model, or the settings (which I've played with and improved somewhat, but not to really acceptable levels)
The built-in microphone is located on the keyboard, which is a little bizarre and obviously not helpful for any time you'd be typing as well as talking. There's a lot of white noise with it compared with actual signal - I couldn't get a Skype test call to be audible without it also having huge amounts of hiss. Fortunately, this isn't a problem for me - I have a standalone microphone which I use for screencasts etc. That's previously been problematically quiet with other laptops, possibly due to drawing a lot of power - but it works perfectly with this laptop. I'm also getting a Corsair headset, which should be handy both for gaming and podcast recordings.
The machine itself is fairly bulky, and the power brick is huge - but the feeling of the chassis is a very attractive matte black. If you're looking for a sleek laptop to carry around a lot, this probably wouldn't be the best choice, but most of the time I keep my laptop on the same table at home. I went for a 15" rather than 17" as it makes a big difference when carrying it around to conferences, but the extra thickness required to house and cool the powerful components doesn't really bother me.

Overall, I'm really pleased with the laptop. As far as I can tell so far, the build quality is excellent - no problems at all. The poor quality of the microphone and webcam are a niggly disappointment, but not one that bothers me enough to find out whether they're "working as expected" or not.

The buying experience

This is where some of you may be relishing the prospect of reading a rant against Kobalt - but I'm not going to air lots of dirty laundry here. It did take a very long time for the laptop to arrive - over three months - but the causes of this were varied, and are worth mentioning at least in passing. I'm hoping that a summary of frustrations and the good parts will give the right impression without getting ugly.

My first cause of frustration occurred very early - before I'd even received a detailed order confirmation from Kobalt. They'd suffered from a high proportion of staff going down with norovirus around the time I ordered. This is the sort of thing which will obviously hit a small company like Kobalt rather more than bigger ones, but it wasn't a great start; for a week all I had was an email saying that I'd paid Kobalt for something, but I couldn't even check whether the details were right.

Some of the delays actually put Kobalt into a better light as far as I'm concerned. In particular, I'd originally ordered an AMD 6970 graphics card and a Vertex 3 SSD. Kobalt withdrew both of these components from sale: the 6970 was failing too often in testing, and the Vertex 3 was causing blue screens, sometimes in testing and occasionally on customer machines, due to an issue between the laptop chipset and the disk. Some other vendors would no doubt have kept selling these components and let the customer take the risk of losing the use of the laptop while it went back for repair, and I applaud Kobalt for not doing this.

Likewise my order was actually built twice: the first one failed testing - the motherboard failed, so had to be built from scratch. Again, I'm very happy about this - I'd obviously rather have a delay but get a working laptop in the end than get a defective one sooner. This also worked to my advantage in terms of the graphics card; although I'd only ordered a 485M, the first one was used in another customer's machine while waiting for a new motherboard for me... by which time the 485M was no longer readily available. Kobalt swapped in the 580M for no extra charge.

Other delays were only partially under Kobalt's control - for example, their order management system blew up in August. Can you blame a company for their internal systems failing? It's hard to say - and I'll be the first to admit I don't have the details. Was it due to cutting corners by getting a cheap ordering system which might be expected to be flaky? Was it due to something catastrophic which would only happen once in a million years? Should there have been better "emergency backup" procedures? I don't know - but it feels like something that customers shouldn't be exposed to.

One benefit of the delays was that I was able to change my order a couple of times - upping the CPU and memory, choosing a different graphics card and disk drive etc. Kobalt have been very flexible around this; it was considerably easier to change the configuration than I suspect it would have been with somewhere like Dell.

My main issue through all of this was communication - which wasn't all bad, but was definitely flaky. I suspect Kobalt would argue that I had unreasonable expectations, whereas I'd say it's just part of providing good customer service. The problems that Kobalt experienced obviously made all of this much worse than normal, but I still think there's a mismatched set of expectations there. I clearly wasn't the only one getting frustrated - the forums had a lot of posts complaining of a lack of updates - but equally, satisfied customers don't tend to post much to provide balance. It's very obvious on the forums that while people have been frustrated with the buying process, almost everyone's really happy with the machine they get in the end, and Kobalt are actually really good at answering questions about drivers etc afterwards.

My own experience of communicating with Kobalt was negative until the reasonably late stages of the order, but I was then phoned to be informed of the laptop coming out of testing and again to check shipping dates, which was good. (In this case it was particularly important as without the check, the laptop would have been delivered to the office on Saturday, where there may well not have been anyone prepared to sign for it.)

For a week or so after I received my laptop I still saw quite a few frustrated posts from other customers, but now that seems to have gone down significantly. It's possible that I'm just not seeing the other complaining posts (as such posts are often deleted - leading to the customer in question getting more frustrated, of course). I'm currently hopeful that I happen to have just ordered at a really bad time where Kobalt was suffering a series of unrelated problems. Whether they handled those as well as they could have done is up for debate, but hopefully new customers wouldn't see the same problems.

It should be noted that Kobalt is definitely trying to get better, too. In August they introduced a new Customer Promise around price, upgrades, and delivery times. In particular, if your order takes more than 6 weeks, you can choose between various games and accessories as a gift. (I chose two games from Steam.) Also, they're actively recruiting, so hopefully that will help on the communications front, too.

Accessories

As tends to happen while waiting for something, I got itchy and started buying accessories to go with the new laptop. I thought I might as well mention those at the same time...

External USB 3 drive: Western Digital MyPassport. I would probably have bought a eSata drive if I'd found one with as neat a form factor as this, but there just don't seem to be many eSata drives around yet. Hopefully this will change, as I do notice my USB mouse/keyboard responding sluggishly while I'm putting a lot of traffic through the drive - but apart from that, it's lovely. It's a really nice form factor, and seems to take advantage of the USB 3 ports on my laptop to deliver pretty reasonable performance. I'm expecting this to be used primarily for VMs - I've heard mixed reports of using VMs with SSDs, including the possibility that the two really don't play nicely, leading to early drive failure. I don't know whether this is accurate or not, but I'm being cautious. Overall, I'm pretty happy with this, although it's reasonably hard to get excited about a disk drive...

Keyboard: I do quite a bit of typing, and while I'm used to laptop keyboards, they're obviously somewhat constrained. I had previously been using a Logitech K340 which is nice, but I treated myself to a K800 for the new machine. Both of these use Logitech's "Unifying" receiver, which is wonderful - it's a tiny little receiver which I just leave permanently in the USB port. It works with quite a few Logitech peripherals, so I share the same receiver for my keyboard and the Anywhere MX mouse I use. The K800 keyboard is really nice - a lovely action, a sensible layout of Ins/Del/Home/End/PgUp/PgDn (which is its main benefit over the K340, to be honest) and it's rechargable via USB. The backlighting is a nice extra, although it's probably not going to actually be useful for me. It's fun to just wave your hand over it and watch it light up though... I'm easily pleased :)

I also bought a Belkin Screencast WiDi 2.0, which turns out to have been a mistake. I had thought that because I was using a Sandybridge laptop with an appropriate Intel wifi card, I'd be able to use WiDi - a technology which allows you to transmit video and sound to a receiver which can then plug into the TV. Yay, I can display Youtube etc on the TV without leaving the comfort of the sofa, right? Not so much - it turns out that this only works if you're also using the integrated graphics card; as I'm using a separate GPU, it's a no-go. This wasn't made as obvious as it might be on Intel's web site about WiDi - it's there if you dig, but it's not obvious. Just to be clear, this is in no way Kobalt's fault - they never claimed the new laptop would be WiDi compatible. I've now sent the Screencast (which was no use to me for anything else) to Kobalt so they can try it out with other laptops. (I suspect the GS150 may work with it, for example.)

VM experiment

As I've tweeted before, I did have one hope for actually using most of the 16GB of memory. I don't want to run VMs directly from the SSD, as I mentioned before - but I had a thought of having the virtual disk on the SSD, but then mounting it as a ram drive. That way I'd only need to write to the disk after shutting down the VM - one big write instead of frequent spraying access.

That would only work with a small drive, of course... but I hoped I'd just about be able to get Windows 7 Home Premium + Visual Studio into a small enough drive. With 1GB of memory for the VM and 2GB of memory for the host machine I can have a 13GB ram drive - and I can install Windows 7 on that using Virtual PC, but Virtual PC also uses disk space alongside the VHD for memory for the VM, which obviously takes another 1GB off the usable size. I nearly managed it, but not quite. I may give it another go with Virtual Box and the Express edition of VS11... I'll blog again if I get it working, but I didn't want to hold up this post forever...

In terms of getting anything working, it took a little while - DataRam's RAMDisk product kept hanging while closing down; imdisk gave me access problems even after trying all the suggested tweaks, but VSuite Ramdisk (server edition) seems to do the job. It's not hugely cheap (and I need the server edition to support a drive over 4GB) but if I can get everything working, I may go with it. Currently I'm using the trial edition.

Conclusion

I guess the obvious question to ask is "If I had my time again, would I take the same action?"

Well, it's obviously been a frustrating experience, but the results should keep me happy for a long time. I think I would be cautious about buying from Kobalt again, but probably less so than you might expect. I'd probably hang out in the forums for a while to see whether folks were generally happy at the time. I'm hoping I was just unlucky, and hit a particularly nasty time in Kobalt's history - I can't imagine the staff there have enjoyed those three months any more than I did - and that normally everything runs smoothly. If I were in a real hurry I'd probably go for an off-the-shelf solution, but that's a different matter - when you buy a custom machine you should expect it to take a bit longer. Just not three months, normally :)

I'd certainly be happy to buy from Kobalt again in terms of the quality of the product - it's a lovely laptop, and I'm delighted with its performance, display and general handling. Obviously I regret buying the Screencast, but all my other decisions - memory, disk, external keyboard etc - have turned out well so far.

Upcoming speaking engagements

skeet — Fri, 02 Sep 2011 16:53:17 GMT

It's just occurred to me that I've forgotten to mention a few of the things I'll be up to in the near-ish future. (I've talked about next week's Progressive .NET session before.) This is just a quick rundown - follow the links for more blurb and details.

.NET Developer Network - Bristol, September 21st (evening)

I'll be talking about async in Bristol - possibly at a high level, possibly in detail, depending on the audience experience. This is my first time talking with this particular user group, although I'm sure there'll be some familiar faces. Come along if you're in the area.

Øredev 2011 - Malmö, November 9th

It's a whistle-stop trip to Sweden as I'm running out of vacation days; I'm flying out on the Tuesday evening and back on the Wednesday evening, but while I'm there I'll give two talks:

Async 101 (yes, more async; I wonder at what point I'll have given as many talks about it as Mads)
Effective technical communication (not a particularly technical talk, but definitely specific to technical communication)

Last year I had an absolute blast - looking forward to this year, even though I won't have as much time for socializing.

Stack Overflow Dev Days 2011 - London, November 14th - cancelled!

Update: Dev Days has been cancelled. I'm still hoping to do something around this topic, and there may be small-scale meet-ups in London anyway.

Two years ago I talked about how humanity had let the world of software engineering down. This was one of the best talks I've ever given, and introduced the world to Tony the Pony. Unfortunately that puts the bar relatively high for this year's talk - at least, high by my own pretty low standards.

In a somewhat odd topic for a Christian and a happy employee of a company with a code of conduct which starts "Don't be evil," this year's talk is entitled "Thinking in evil." As regular readers are no doubt aware, I love torturing the C# language and forcing the compiler to work with code which would make any right-thinking software engineer cringe. I was particularly gratified recently when Eric Lippert commented on one of my Stack Overflow answers that this was "the best abuse of C# I've seen in a while." I'm looking forward to talking about why I think it's genuinely a good idea to think about nasty code like this - not to use it, but to get to know your language of choice more intimately. Like last time, I have little idea of exactly what this talk will be like, but I'm really looking forward to it.

Optimization and generics, part 2: lambda expressions and reference types

skeet — Mon, 22 Aug 2011 23:06:18 GMT

As with almost any performance work, your mileage may vary (in particular the 64-bit JIT may work differently) and you almost certainly shouldn't care. Relatively few people write production code which is worth micro-optimizing. Please don't take this post as an invitation to make code more complicated for the sake of irrelevant and possibly mythical performance changes.

It took me a surprisingly long time to find the problem described in the previous blog post, and almost no time at all to fix it. I understood why it was happening. This next problem took a while to identify at all, but even when I'd found a workaround I had no idea why it worked. Furthermore, I couldn't reproduce it in a test case... because I was looking for the wrong set of triggers. I've now found at least some of the problem though.

This time the situation in Noda Time is harder to describe, although it concerns the same area of code. In various places I need to create new delegates containing parsing steps and add them to the list of steps required for a full parse. I can always use lambda expressions, but in many cases I've got the same logic repeatedly... so I decided to pull it out into a method. Bang - suddenly the code runs far slower. (In reality, I'd performed this refactoring first, and "unrefactored" it to speed things up.)

I think the problem comes down to method group conversions with generic methods and a type argument which is a reference type. The CLR isn't very good at them, and the C# compiler uses them more than it needs to.

Show me the benchmark!

The complete benchmark code is available of course, but fundamentally I'm doing the same thing in each test case: creating a delegate of type Action which does nothing, and then checking that the delegate reference is non-null (just to avoid the JIT optimizing it away). In each case this is done in a generic method with a single type parameter. I call each method in two ways: once with int as the type argument, and once with string as the type argument. Here are the different cases involved:

Use a lambda expression: Action foo = () => {};
Fake what I expected the compiler to do: keep a separate generic cache class with a static variable for the delegate; populate the cache once if necessary, and thereafter use the cache field
Fake what the compiler is actually doing with the lambda expression: write a separate generic method and perform a method group conversion to it
Do what the compiler could do: write a separate non-generic method and perform a method group conversion to it
Use a method group conversion to a static (non-generic) method on a generic type
Use a method group conversion to an instance (non-generic) method on a generic type, via a generic cache class with a single field in referring to an instance of the generic class

(Yes, the last one is a bit convoluted - but the line in the method itself is simple: Action foo = ClassHolder<T>.SampleInstance.NoOpInstance;

Remember, we're doing each of these in a generic method, and calling that generic method using a type argument of either int or string. (I've run a few tests, and the exact type isn't important - all that matters is that int is a value type, and string is a reference type.)

Importantly, we're not capturing any variables, and the type parameter is not involved in either the delegate type or any part of the implementation body.

Benchmark results

Again, times are in milliseconds - but this time I didn't want to run it for 100 million iterations, as the "slow" versions would have taken far too long. I've run this on the x64 JIT as well and seen the same effect, but I haven't included the figures here.

Times in milliseconds for 10 million iterations

Test	TestCase<int>	TestCase<string>
Lambda expression	180	29684
Generic cache class	90	288
Generic method group conversion	184	30017
Non-generic method group conversion	178	189
Static method on generic type	180	29276
Instance method on generic type	202	299

Yes, it's about 150 times slower to create a delegate from a generic method with a reference type as the type argument than with a value type... and yet this is the first I've heard of this. (I wouldn't be surprised if there were a post from the CLR team about it somewhere, but I don't think it's common knowledge by any means.)

Conclusion

One of the tricky things is that it's hard to know exactly what the C# compiler is going to do with any given lambda expression. In fact, the method which was causing me grief earlier on isn't generic, but it's in a generic type and captures some variables which use the type parameters - so perhaps that's causing a generic method group conversion somewhere along the way.

Noda Time is a relatively extreme case, but if you're using delegates in any performance-critical spots, you should really be aware of this issue. I'm going to ping Microsoft (first informally, and then via a Connect report if that would be deemed useful) to see if there's an awareness of this internally as potential "gotcha", and whether there's anything that can be done. Normal trade-offs of work required vs benefit apply, of course. It's possible that this really is an edge case... but with lambdas flying everywhere these days, I'm not sure that it is.

Maybe tomorrow I'll actually be able to finish getting Noda Time moved onto the new system... all of this performance work has been a fun if surprising distraction from the main job of shipping working code...

Optimization and generics, part 1: the new() constraint (updated: now with CLR v2 results)

skeet — Mon, 22 Aug 2011 21:57:55 GMT

I've been doing quite a bit of work on Noda Time recently - and have started getting my head round all the work that James Keesey has put into the parsing/formatting. I've been reworking it so that we can do everything without throwing any exceptions, and also to work on the idea of parsing a pattern once and building a sequence of actions for both formatting and parsing from the action. To format or parse a value, we then just need to apply the actions in turn. Simples.

Given that this is all in the name of performance (and I consider Noda Time to be worth optimizing pretty hard) I was pretty cross when I ran a complete revamp through the little benchmarking tool we use, and found that my rework had made everything much slower. Even parsing a value after parsing the pattern was slower than parsing both the value and the pattern together. Something was clearly very wrong.

In fact, it turns out that at least two things were very wrong. The first (the subject of this post) was easy to fix and actually made the code a little more flexible. The second (the subject of the next post, which may be tomorrow) is going to be harder to work around.

The new() constraint

In my SteppedPattern type, I have a generic type parameter - TBucket. It's already constrained in terms of another type parameter, but that's irrelevant as far as I'm aware. (After today though, I'm taking very little for granted...) The important thing is that before I try to parse a value, I want to create a new bucket. The idea is that bits of information end up in the bucket as they're being parsed, and at the very end we put everything together. So each parse operation requires a new bucket. How can we create one in a nice generic way?

Well, we can just call its public parameterless constructor. I don't mind the types involved having such a constructor, so all we need to do is add the new() constraint, and then we can call new TBucket():

// Somewhat simplified...
internal sealed class SteppedPattern<TResult, TBucket> : IParsePattern<TResult>
    where TBucket : new()
{
    public ParseResult<TResult> Parse(string value)
    {
        TBucket bucket = new TBucket();

        // Rest of parsing goes here
    }
}

Great! Nice and simple. Unfortunately, it turned out that that one line of code was taking 75% of the time to parse a value. Just creating an empty bucket - pretty much the simplest bit of parsing. I was amazed when I discovered that.

Fixing it with a provider

The fix is reasonably easy. We just need to tell the type how to create an instance, and we can do that with a delegate:

// Somewhat simplified...
internal sealed class SteppedPattern<TResult, TBucket> : IParsePattern<TResult>
{
    private readonly Func<TBucket> bucketProvider;

    internal SteppedPattern(Func<TBucket> bucketProvider)
    {
        this.bucketProvider = bucketProvider;
    }

    public ParseResult<TResult> Parse(string value)
    {
        TBucket bucket = bucketProvider();

        // Rest of parsing goes here
    }
}

Now I can just call new SteppedPattern(() => new OffsetBucket()) or whatever. This also means I can keep the constructor internal, not that I care much. I could even reuse old parse buckets if that wouldn't be a semantic problem - in other cases it could be useful. Hooray for lambda expressions - until we get to the next post, anyway.

Show me the figures!

You don't want to have to run Noda Time's benchmarks to see the results for yourself, so I wrote a small benchmark to time just the construction of a generic type. As a measure of how insignificant this would be for most apps, these figures are in milliseconds, performing 100 million iterations of the action in question. Unless you're going to do this in performance-critical code, you just shouldn't care.

Anyway, the benchmark has four custom types: two classes, and two structs - a small and a large version of each. The small version has a single int field; the large version has eight long fields. For each type, I benchmarked both approaches to initialization.

The results on two machines (32-bit and 64-bit) are below, for both the v2 CLR and v4. The 64-bit machine is much faster in general - you should only compare results within one machine, as it were.)

CLR v4: 32-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	689	1225
Large struct	11188	7273
Small class	16307	1690
Large class	17471	3017

CLR v4: 64-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	473	868
Large struct	2670	2396
Small class	8366	1189
Large class	8805	1529

CLR v2: 32-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	703	1246
Large struct	11411	7392
Small class	143967	1791
Large class	143107	2581

CLR v2: 64-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	510	686
Large struct	2334	1731
Small class	81801	1539
Large class	83293	1896

(An earlier version of this post had a mistake - my original tests used structs for everything, despite the names.)

Others have reported slightly different results, including the new() constraint being better for both large and small structs.

Just in case you hadn't spotted them, look at the results for classes. Those are the real results - it took over 2 minutes to run the test using the new() constraint on my 32-bit laptop, compared with under two seconds for the provider. Yikes. This was actually the situation I was in for Noda Time, which is built on .NET 2.0 - it's not surprising that so much of my benchmark's time was spent constructing classes, given results like this.

Of course you can download the benchmark program for yourself and see how it performs on your machine. It's a pretty cheap-and-cheerful benchmark, but when the differences are this big, minor sources of inaccuracy don't bother me too much. The simplest way to run under CLR v2 is to compile with the .NET 3.5 C# compiler to start with.

What's going on under the hood?

As far as I'm aware, there's no IL to give support for the new() constraint. Instead, the compiler emits a call to Activator.CreateInstance<T>. Apparently, that's slower than calling a delegate - presumably due to trying to find an accessible constructor with reflection, and invoking it. I suspect it could be optimized relatively easily - e.g. by caching the results per type it's called with, in terms of delegates. I'm slightly surprised this hasn't (apparently) been optimized, given how easy it is to cache values by generic type. No doubt there's a good reason lurking there somewhere, even if it's only the memory taken up by the cache.

Either way, it's easy to work around in general.

Conclusion

I wouldn't have found this gotcha if I didn't have before and after tests (or in this case, side-by-side tests of the old way and the new way of parsing). The real lesson of this post shouldn't be about the new() constraint - it should be how important it is to test performance (assuming you care), and how easy it is to assume certain operations are cheap.

Next post: something much weirder.