Jon Skeet: Coding Blog : Wacky Ideas

Contract classes and nested types within interfaces

skeet — Sat, 31 Oct 2009 22:04:54 GMT

I've just been going through some feedback for the draft copy of the second edition of C# in Depth. In the contracts section, I have an example like this:

[ContractClass(typeof(ICaseConverterContracts))]
public interface ICaseConverter
{
    string Convert(string text);
}

[ContractClassFor(typeof(ICaseConverter))]
internal class ICaseConverterContracts : ICaseConverter
{
    string ICaseConverter.Convert(string text)
    {
        Contract.Requires(text != null);
        Contract.Ensures(Contract.Result<string>() != null);
        return default(string);
    }

    private ICaseConverterContracts() {}
}

public class InvariantUpperCaseFormatter : ICaseConverter
{
    public string Convert(string text)
    {
        return text.ToUpperInvariant();
    }
}

The point is to demonstrate how contracts can be specified for interfaces, and then applied automatically to implementations. In this case, ICaseConverter is the interface, ICaseConverterContracts is the contract class which specifies the contract for the interface, and InvariantUpperCaseFormatter is the real implementation. The binary rewriter effectively copies the contract into each implementation, so you don't need to duplicate the contract in the source code.

The reader feedback asked where the contract class code should live - should it go in the same file as the interface itself, or in a separate file as normal? Now normally, I'm firmly of the "one top-level type per file" persuasion, but in this case I think it makes sense to keep the contract class with the interface. It has no meaning without reference to the interface, after all - it's not a real implementation to be used in the normal way. It's essentially metadata. This does, however, leave me feeling a little bit dirty. What I'd really like to be able to do is nest the contract class inside the interface, just like I do with other classes which are tightly coupled to an "owner" type. Then the code would look like this:

[ContractClass(typeof(ICaseConverterContracts))]
public interface ICaseConverter
{
    string Convert(string text);

    [ContractClassFor(typeof(ICaseConverter))]
    internal class ICaseConverterContracts : ICaseConverter
    {
        string ICaseConverter.Convert(string text)
        {
            Contract.Requires(text != null);
            Contract.Ensures(Contract.Result<string>() != null);
            return default(string);
        }

        private ICaseConverterContracts() {}
    }
}

public class InvariantUpperCaseFormatter : ICaseConverter
{
    public string Convert(string text)
    {
        return text.ToUpperInvariant();
    }
}

That would make me feel happier - all the information to do with the interface would be specified within the interface type's code. It's possible that with that as a convention, the Code Contracts tooling could cope without the attributes - if interface IFoo contains a nested class IFooContracts which implements IFoo, assume it's a contract class and handle it appropriately. That would be sweet.

You know the really galling thing? I'm pretty sure VB does allow nested types in interfaces...

Iterating atomically

skeet — Fri, 23 Oct 2009 21:20:00 GMT

The IEnumerable<T> and IEnumerator<T> interfaces in .NET are interesting. They crop up an awful lot, but hardly anyone ever calls them directly - you almost always use a foreach loop to iterate over the collection. That hides all the calls to GetEnumerator(), MoveNext() and Current. Likewise iterator blocks hide the details when you want to implement the interfaces. However, sometimes details matter - such as for this recent Stack Overflow question. The question asks how to create a thread-safe iterator - one that can be called from multiple threads. This is not about iterating over a collection n times independently on n different threads - this is about iterating over a collection once without skipping or duplicating. Imagine it's some set of jobs that we have to complete. We assume that the iterator itself is thread-safe to the extent that calls from different threads at different times, with intervening locks will be handled reasonably. This is reasonable - basically, so long as it isn't going out of its way to be thread-hostile, we should be okay. We also assume that no-one is trying to write to the collection at the same time.

Sounds easy, right? Well, no... because the IEnumerator<T> interface has two members which we effectively want to call atomically. In particular, we don't want the collection { "a", "b" } to be iterated like this:

Thread 1	Thread 2
MoveNext()
	MoveNext()
Current
	Current

That way we'll end up not processing the first item at all, and the second item twice.

There are two ways of approaching this problem. In both cases I've started with IEnumerable<T> for consistency, but in fact it's IEnumerator<T> which is the interesting bit. In particular, we're not going to be able to iterate over our result anyway, as each thread needs to have the same IEnumerator<T> - which it won't do if each of them uses foreach (which calls GetEnumerator() to start with).

Fix the interface

First we'll try to fix the interface to look how it should have looked to start with, at least from the point of view of atomicity. Here are the new interfaces:

public interface IAtomicEnumerable<T>
{
IAtomicEnumerator<T> GetEnumerator();
}

public interface IAtomicEnumerator<T>
{
bool TryMoveNext(out T nextValue);
}

One thing you may notice is that we're not implementing IDisposable. That's basically because it's a pain to do so when you think about a multi-threaded environment. Indeed, it's possibly one of the biggest arguments against something of this nature. At what point do you dispose? Just because one thread finished doesn't mean that the rest of them have... don't forget that "finish" might mean "an exception was thrown while processing the job, I'm bailing out". You'd need some sort of co-ordinator to make sure that everyone is finished before you actually do any clean-up. Anyway, the nice thing about this being a blog post is we can ignore that little thorny issue :)

The important point is that we now have a single method in IAtomicEnumerator<T> - TryMoveNext, which works the way you'd expect it to. It atomically attempts to move to the next item, returns whether or not it succeeded, and sets an out parameter with the next value if it did succeed. Now there's no chance of two threads using the method and stomping on each other's values (unless they're silly and use the same variable for the out parameter).

It's reasonably easy to wrap the standard interfaces in order to implement this interface:

/// <summary>
/// Wraps a normal IEnumerable[T] up to implement IAtomicEnumerable[T].
/// </summary>
public sealed class AtomicEnumerable<T> : IAtomicEnumerable<T>
{
    private readonly IEnumerable<T> original;

    public AtomicEnumerable(IEnumerable<T> original)
    {
        this.original = original;
    }

    public IAtomicEnumerator<T> GetEnumerator()
    {
        return new AtomicEnumerator(original.GetEnumerator());
    }

    /// <summary>
    /// Implementation of IAtomicEnumerator[T] to wrap IEnumerator[T].
    /// </summary>
    private sealed class AtomicEnumerator : IAtomicEnumerator<T>
    {
        private readonly IEnumerator<T> original;
        private readonly object padlock = new object();

        internal AtomicEnumerator(IEnumerator<T> original)
        {
            this.original = original;
        }

        public bool TryMoveNext(out T value)
        {
            lock (padlock)
            {
                bool hadNext = original.MoveNext();
                value = hadNext ? original.Current : default(T);
                return hadNext;
            }
        }
    }
}

Just ignore the fact that I never dispose of the original IEnumerator<T> :)

We use a simple lock to make sure that MoveNext() and Current always happen together - that nothing else is going to call MoveNext() between our TryMoveNext() calling it, and it fetching the current value.

Obviously you'd need to write your own code to actually use this sort of iterator, but it would be quite simple:

T value;
while (iterator.TryMoveNext(out value))
{
// Use value
}

However, you may already have code which wants to use an IEnumerator<T>. Let's see what else we can do.

Using thread local variables to fake it

.NET 4.0 has a very useful type called ThreadLocal<T>. It does basically what you'd expect it to, with nice features such as being able to supply a delegate to be executed on each thread to provide the initial value. We can use a thread local to make sure that so long as we call both MoveNext() and Current atomically when we're asked to move to the next element, we can get back the right value for Current later on. It has to be thread local because we're sharing a single IEnumerator<T> across multiple threads - each needs its own separate storage.

This is also the approach we'd use if we wanted to wrap an IAtomicEnumerator<T> in an IEnumerator<T>, by the way. Here's the code to do it:

public class ThreadSafeEnumerable<T> : IEnumerable<T>
{
    private readonly IEnumerable<T> original;

    public ThreadSafeEnumerable(IEnumerable<T> original)
    {
        this.original = original;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ThreadSafeEnumerator(original.GetEnumerator());
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private sealed class ThreadSafeEnumerator : IEnumerator<T>
    {
        private readonly IEnumerator<T> original;
        private readonly object padlock = new object();
        private readonly ThreadLocal<T> current = new ThreadLocal<T>();

        internal ThreadSafeEnumerator(IEnumerator<T> original)
        {
            this.original = original;
        }

        public bool MoveNext()
        {
            lock (padlock)
            {
                bool ret = original.MoveNext();
                if (ret)
                {
                    current.Value = original.Current;
                }
                return ret;
            }
        }

        public T Current
        {
            get { return current.Value; }
        }

        public void Dispose()
        {
            original.Dispose();
            current.Dispose();
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public void Reset()
        {
            throw new NotSupportedException();
        }
    }
}

I'm going to say it one last time - we're broken when it comes to disposal. There's no way of safely disposing of the original iterator at "just the right time" when everyone's finished with it. Oh well.

Other than that, it's quite simple. This code has the serendipitous property of actually implementing IEnumerator<T> slightly better than C#-compiler-generated implementations from iterator blocks - if you call the Current property without having called MoveNext(), this will throw an InvalidOperationException, just as the documentation says it should. (It doesn't do the same at the end, admittedly, but that's fixable if we really wanted to be pedantic.

Conclusion

I found this an intriguing little problem. I think there are better ways of solving the bigger picture - a co-ordinator which takes care of disposing exactly once, and which possibly mediates the original iterator etc is probably the way forward... but I enjoyed thinking about the nitty gritty.

Generally speaking, I prefer the first of these approaches. Thread local variables always feel like a bit of a grotty hack to me - they can be useful, but it's better to avoid them if you can. It's interesting to see how an interface can be inherently thread-friendly or not.

One last word of warning - this code is completely untested. It builds, and I can't immediately see why it wouldn't work, but I'm making no guarantees...

An object lesson in blogging and accuracy; was: Efficient "vote counting" with LINQ to Objects - and the value of nothing

skeet — Sun, 20 Sep 2009 20:48:00 GMT

Well, this is embarrassing.

Yesterday evening, I excitedly wrote a blog post about an interesting little idea for making a particular type of LINQ query (basically vote counting) efficient. It was an idea that had occurred to me a few months back, but I hadn't got round to blogging about it.

The basic idea was to take a completely empty struct, and use that as the element type in the results of a grouping query - as the struct was empty, it would take no space, therefore "huge" arrays could be created for no cost beyond the fixed array overhead, etc. I carefully checked that the type used for grouping did in fact implement ICollection<T> so that the Count method would be efficient; I wrote sample code which made sure my queries were valid... but I failed to check that the empty struct really took up no memory.

Fortunately, I have smart readers, a number of whom pointed out my mistake in very kind terms.

Ben Voigt gave the reason for the size being 1 in a comment:

The object identity rules require a unique address for each instance... identity can be shared with super- or sub- class objects (Empty Base Optimization) but the total size of the instance has to be at least 1.

This makes perfect sense - it's just a shame I didn't realise it before.

Live and learn, I guess - but apologies for the poorly researched post. I'll attempt to be more careful next time.

Generic constraints for enums and delegates

skeet — Thu, 10 Sep 2009 20:09:00 GMT

As most readers probably know, C# prohibits generic type constraints from referring to System.Object, System.Enum, System.Array, System.Delegate and System.ValueType. In other words, this method declaration is illegal:

public static T[]GetValues<T>() where T : struct, System.Enum
{
return (T[]) Enum.GetValues(typeof(T));
}

This is a pity, as such a method could be useful. (In fact there are better things we can do... such as returning a read-only collection. That way we don't have to create a new array each time the method is called.) As far as I can tell, there is no reason why this should be prohibited. Eric Lippert has stated that he believes the CLR doesn't support this - but I think he's wrong. I can't remember the last time I had cause to believe Eric to be wrong about something, and I'm somewhat nervous of even mentioning it, but section 10.1.7 of the CLI spec (ECMA-335) partition II (p40) specifically gives examples of type parameter constraints involving System.Delegate and System.Enum. It introduces the table with "The following table shows the valid combinations of type and special constraints for a representative set of types." It was only due to reading this table that I realized that the value type constraint on the above is required (or a constructor constraint would do equally well) - otherwise System.Enum itself satisfies the constraint, which would be a Bad Thing.

It's possible (but unlikely) that the CLI doesn't fully implement this part of the CLR spec. I'm hoping that Eric's just wrong on this occasion, and that actually there's nothing to stop the C# language from allowing such constraints in the future. (It would be nice to get keyword support, such that a constraint of "T : enum" would be equivalent to the above, but hey...)

The good news is that ilasm/ildasm have no problem with this. The better news is that if you add a reference to a library which uses those constraints, the C# compiler applies them sensibly, as far as I can tell...

Introducing UnconstrainedMelody

(Okay, the name will almost surely have to change. But I like the idea of it removing the constraints of C# around which constraints are valid... and yet still being in the key of C#. Better suggestions welcome.)

I have a plan - I want to write a utility library which does useful things for enums and delegates (and arrays if I can think of anything sensible to do with them). It will be written in C#, with methods like this:

public static T[]GetValues<T>() where T : struct, IEnumConstraint
{
return (T[]) Enum.GetValues(typeof(T));
}

(IEnumConstraint has to be an interface of course, as otherwise the constraint would be invalid.)

As a post-build step, I will:

Run ildasm on the resulting binary
Replace every constraint using EnumConstraint with System.Enum
Run ilasm to build the binary again

If anyone has a simple binary rewriter (I've looked at PostSharp and CCI; both look way more complicated than the above) which would do this, that would be great. Otherwise ildasm/ilasm will be fine. It's not like consumers will need to perform this step.

As soon as the name is finalized I'll add a project on Google Code. Once the infrastructure is in place, adding utility methods should be very straightforward. Suggestions for utility methods would be useful, or just join the project when it's up and running.

Am I being silly? Have I overlooked something?

A couple of hours later...

Okay, I decided not to wait for a better name. The first cut - which does basically nothing but validate the idea, and the fact that I can still unit test it - is in. The UnconstrainedMelody Google Code project is live!

The "dream book" for C# and .NET

skeet — Thu, 20 Aug 2009 16:57:40 GMT

This morning I showed my hand a little on Twitter. I've had a dream for a long time about the ultimate C# book. It's a dream based on Effective Java, which is my favourite Java book, along with my experiences of writing C# in Depth.

Effective Java is written by Josh Bloch, who is an absolute giant in the Java world... and that's both the problem and the opportunity. There's no-one of quite the equivalent stature in the .NET world. Instead, there are many very smart people, a lot of whom blog and some of whom have their own books.

There are "best practices" books, of course: Microsoft's own Framework Design Guidelines, and Bill Wagner's Effective C# and More Effective C# being the most obvious examples. I'm in no way trying to knock these books, but I feel we could do even better. The Framework Design Guidelines (also available free to browse on MSDN) are really about how to create a good API - which is important, but not the be-all-and-end-all for many application developers who aren't trying to ship a reusable class library and may well have different concerns. They want to know how to use the language most effectively, as well as the core types within the framework.

Bill's books - and many others which cover the core framework, such as CLR via C#, Accelerated C# 2008 and C# 3.0 in a Nutshell - give plenty of advice, but often I've felt it's a little one-sided. Each of these books is the work of a single person (or brothers in the case of Nutshell). Reading them, I've often wanted to give present a different point of view - or alternatively, to give a hearty "hear, hear." I believe that a book giving guidance would benefit greatly from being more of a conversation: where the authors all agree on something, that's great; where they differ, it would be good to hear about the pros and cons of various approaches. The reader can then weigh up those factors as they apply to each particular real-world scenario.

Scope

So what would such a book contain? Opinions will vary of course, but I would like to see:

Effective ways of using language features such as lambda expressions, generic type inference (and indeed generics in general), optional parameters, named arguments and extension methods. Assume that the reader knows roughly what C# does, but give some extra details around things like iterator blocks and anonymous functions.
Guidance around class design (in a similar fashion to the FDG, but with more input from others in the community)
Core framework topics (again, assume the basics are understood):

Resource management (disposal etc)
Exceptions
Collections (including LINQ fundamentals)
Streams
Text (including internationalization)
Numeric types
Time-related APIs
Concurrency
Contracts
AppDomains
Security
Performance

I would prefer to avoid anything around the periphery of .NET (WPF, WinForms, ASP.NET, WCF) - I believe those are better handled in different topics.

Obstacles and format

There's one big problem with this idea, but I think it may be a saving grace too. Many of the leading authors work for different publishers. Clearly no single publisher is going to attract all the best minds in the C# and .NET world. So how could this work in practice? Well...

Imagine a web site for the book, paid for jointly by all interested publishers. The web site would be the foremost delivery mechanism for the content, both to browse and probably to download in formats appropriate for offline reading (PDF etc). The content would be edited in a collaborative style obviously, but exactly how that would work is a detail to be thrashed out. If you've read the annotated C# or CLI specifications, they have about the right feel - opinions can be attributed in places, but not everything has a label.

Any contributing publisher could also take the material and publish it as hard copy if they so wished. Quite how this would work - with potentially multiple hard copy editions of the same content - would be interesting to see. There's another reason against hard copy ever appearing though, which is that it would be immovable. I'd like to see this work evolve as new features appear and as more best practices are discovered. Publishers could monetize the web site via adverts, possibly according to how much they're kicking into the site.

I don't know how the authors would get paid, admittedly, and that's another problem. Would this cannibalize the sales of the books listed earlier? It wouldn't make them redundant - certainly not for the Nutshell type of book, which teaches the basics as well as giving guidance. It would hit Effective C# harder, I suspect - and I apologise to Bill Wagner in advance; if this ever takes off and it hurts his bottom line, I'm very sorry - I think it's in a good cause though.

Dream Team

So who would contribute to this? Part of me would like to say "anyone and everyone" in a Wikipedia kind of approach - but I think that practically, it makes sense for industry experts to take their places. (A good feedback/comments mechanism for anyone to use would be crucial, however.) Here's a list which isn't meant to be exhaustive, but would make me happy - please don't take offence if your name isn't on here but should be, and I wouldn't expect all of these people to be interested anyway.

Anders Hejlsberg
Eric Lippert
Mads Torgersen
Don Box
Brad Abrams
Krzysztof Cwalina
Joe Duffy
Vance Morrison
Rico Mariani
Erik Meijer
Don Symes
Wes Dyer
Jeff Richter
Joe and Ben Albahari
Andrew Troelsen
Bill Wagner
Trey Nash
Mark Michaelis
Jon Skeet (yeah, I want to contribute if I can)

I imagine "principal" authors for specific topics (e.g. Joe Duffy for concurrency) but with all the authors dropping in comments in other places too.

Dream or reality?

I have no idea whether this will ever happen or not. I'd dearly love it to, and I've spoken to a few people before today who've been encouraging about the idea. I haven't been putting any work into getting it off the ground - don't worry, it's not been delaying the second edition of C# in Depth. One day though, one day...

Am I being hopelessly naïve to even consider such a venture? Is the scope too broad? Is the content valuable but not money-making? We'll see.

Faking COM to fool the C# compiler

skeet — Tue, 07 Jul 2009 22:28:46 GMT

C# 4 has some great features to make programming against COM components ~~bearable~~ fun and exciting. In particular:

PIA linking allows you to embed just the relevant bits of the Primary Interop Assembly into your own assembly, so the PIA isn't actually required at execution time
Named arguments and optional parameters make life much simpler for APIs like Office which are full of methods with gazillions of parameters
"ref" removal allows you to pass an argument by value even though the parameter is a by-reference parameter (COM only, folks - don't worry!)
Dynamic typing allows you to remove a load of casts by converting every parameter and return type of "object" into "dynamic" (if you're using PIA linking)

I'm currently writing about these features for the book (don't forget to buy it cheap on Friday) but I'm not really a COM person. I want to be able to see these compiler features at work against a really simple type. Unfortunately, these really are COM-specific features... so we're going to have to persuade COM that the type really is a COM type.

I got slightly stuck on this first, but thanks to the power of Stack Overflow, I now have a reasonably complete demo "fake" COM type. It doesn't do a lot, and in particular it doesn't have any events, but it's enough to show the compiler features:

using System;
using System.Runtime.InteropServices;

// Required for linking into another assembly (C# 4)
[assembly:Guid("86ca55e4-9d4b-462b-8ec8-b62e993aeb64")]
[assembly:ImportedFromTypeLib("fake.tlb")]

namespace FakeCom
{
    [Guid("c3cb8098-0b8f-4a9a-9772-788d340d6ae0")]
    [ComImport, CoClass(typeof(FakeImpl))]
    public interface FakeComponent
    {
        object MakeMeDynamic(object arg);

        void Foo([Optional] ref int x,
                 [Optional] ref string y);
    }

    [Guid("734e6105-a20f-4748-a7de-2c83d7e91b04")]
    public class FakeImpl {}
}

We have an interface representing our COM type, and a class which the interface claims will implement it. Fortunately the compiler doesn't actually check that, so we can get away with leaving it entirely unimplemented. It's also worth noting that our optional parameters can be by-reference parameters (which you can't normally do in C# 4) and we haven't given them any default values (as those are ignored for COM anyway).

This is compiled just like any other assembly:

csc /target:library FakeCom.cs

Then we get to use it with a test program:

using FakeCom;

class Test
{
    static void Main()
    {
        // Yes, that is calling a "constructor" on an interface
        FakeComponent com = new FakeComponent();

        // The boring old fashioned way of calling a method
        int i = 0;
        string j = null;
        com.Foo(ref i, ref j);

        // Look ma, no ref!
        com.Foo(10, "Wow!");

        // Who cares about parameter ordering?
        com.Foo(y: "Not me", x: 0);

        // And the parameters are optional too
        com.Foo();

        // The line below only works when linked rather than
        // referenced, as otherwise you need a cast.
        // The compiler treats it as if it both takes and
        // returns a dynamic value.
        string value = com.MakeMeDynamic(10);
    }
}

This is compiled either in the old "deploy the PIA as well" way (after adding a cast in the last line):

csc /r:FakeCom.dll Test.cs

... or by linking the PIA instead:

csc /l:FakeCom.dll Test.cs

(The difference is just using /l instead of /r.)

When the test code is compiled as a reference, it decompiles in Reflector to this (I've added whitespace for clarity):

private static void Main()
{
    FakeComponent component = (FakeComponent) new FakeImpl();

    int x = 0;
    string y = null;
    component.Foo(ref x, ref y);

    int num2 = 10;
    string str3 = "Wow!";
    component.Foo(ref num2, ref str3);

    string str4 = "Not me";
    int num3 = 0;
    component.Foo(ref num3, ref str4);

    int num4 = 0;
    string str5 = null;
    component.Foo(ref num4, ref str5);

    string str2 = (string) component.MakeMeDynamic(10);
}

Note how the compiler has created local variables to pass by reference; any changes to the parameter are ignored when the method returns. (If you actually pass a variable by reference, the compiler won't take that away, however.)

When the code is linked instead, the middle section is the same, but the construction and the line calling MakeMeDynamic are very different:

private static void Main()
{
    FakeComponent component = (FakeComponent) Activator.CreateInstance(Type.GetTypeFromCLSID
        (new Guid("734E6105-A20F-4748-A7DE-2C83D7E91B04")));

    // Middle bit as before

    if (<Main>o__SiteContainer6.<>p__Site7 == null)
    {
        <Main>o__SiteContainer6.<>p__Site7 = CallSite<Func<CallSite, object, string>>
            .Create(new CSharpConvertBinder
                       (typeof(string),
                        CSharpConversionKind.ImplicitConversion, false));
    }
    string str2 = <Main>o__SiteContainer6.<>p__Site7.Target.Invoke
        (<Main>o__SiteContainer6.<>p__Site7, component.MakeMeDynamic(10));
}

The interface is embedded in the generated assembly, but with a slightly different set of attributes:

[ComImport, CompilerGenerated]
[Guid("C3CB8098-0B8F-4A9A-9772-788D340D6AE0"), TypeIdentifier]
public interface FakeComponent
{
object MakeMeDynamic(object arg);
void Foo([Optional] ref int x, [Optional] ref string y);
}

The class isn't present at all.

I should point out that doing this has no practical benefit in real code - but the ability to mess around with a pseudo-COM type rather than having to find a real one with the exact members I want will make it a lot easier to try a few corner cases for the book.

So, not a terribly productive evening in terms of getting actual writing done, but interesting nonetheless...

A different approach to inappropriate defaults

skeet — Thu, 14 May 2009 17:03:52 GMT

I've had a couple of bug reports about my Protocol Buffers port - both nicely detailed, and one including a patch to fix it. (It's only due to my lack of timeliness in actually submitting the change that the second bug report occurred. Oops.)

The bug was in text formatting (although it also affected parsing). I was using the default ToString behaviour for numbers, which meant that floats and doubles were being formatted as "50,15" in Germany instead of "50.15". The unit tests caught this, but only if you ran them on a machine with an appropriate default culture.

Aaargh. I've been struggling with a similar problem in a library I can't change, which uses the system default time zone for various calculations in Java. When you're running server code, the default time zone is almost never the one you want to use, and it certainly isn't in my case.

A similar problem is Java's decision to use the system default encoding in all kinds of bizarre places - FileReader doesn't even let you specify the encoding, which makes it almost entirely useless in my view.

So I've been wondering how we could fix this and problems like it. One option is to completely remove the defaults. If you always had to pass in a CultureInfo/Locale, TimeZoneInfo/TimeZone, Encoding/Charset when you call any method which might be culturally sensitive.

Making life easier (in .NET)

It strikes me that .NET has a useful abstraction here: the assembly as the unit of deployment. (Java's closest equivalent is probably a jar file, which probably gets messier.)

Within one assembly, I suspect in many cases you always want to make the same decision. For example, in protocol buffers I would like to use the invariant culture all the time. It would be nice if I could say that, and then get the right behaviour by default. Here are the options I'd like to be able to apply (for each of culture, time zone and character encoding - there may be others):

Use a culture-neutral default (the invariant culture, UTF-8, UTC)
Use a specific set of values (e.g. en-GB, Windows-1252, "Europe/London")
Use the system default values
Use whatever the calling assembly is using

Of course you should still have the option of specifying overrides on a per call basis, but I think this might be a way forward.

Thoughts? I realise it's almost certainly too late for this to actually be implemented now, but would it have been a good idea? Or is it just an alternative source of confusion?

Go on, ask me anything

skeet — Tue, 24 Mar 2009 17:22:32 GMT

This afternoon, I found a comment which had been trapped in the spam bin for this blog. It was from Andrew Rimmer, in reply to my "micro-celebrity" post, pointing me at http://askjonskeet.com

The world has officially become extremely silly. The surprising thing is, it's actually useful - at least for me. A number of times I've wanted to find my old answers to questions, so I can either just refer to them in a new answer or mark the new question as a dupe. You might have thought that a simple search such as

exceptions site:stackoverflow.com "jon skeet"

would suffice - but that finds what other people have said about exceptions in the same questions that I've been active in, and it also picks up any questions which happened to get one of the FinalBuilder adverts when the spider fetched them. The equivalent search on AskJonSkeet.com gets good results.

I've no idea how useful it will be for anyone else, but personally I love it. Ego? What ego?

Side note to self, puncturing ego slightly: don't blog on the tube. It's way too easy to miss your stop...

Breaking Liskov

skeet — Mon, 16 Mar 2009 17:48:04 GMT

Very recently, Barbara Liskov won the Turing award, which makes it a highly appropriate time to ponder when it's reasonable to ignore her most famous piece of work, the Liskov Substitution (or Substitutability) Principle. This is not idle speculation: I've had a feature request for MiscUtil. The request makes sense, simplifies the code, and is good all round - but it breaks substitutability and documented APIs.

The substitutability principle is in some ways just common sense. It says (in paraphrase) that if your code works for some base type T, it should be able to work with subtype of T, S. If it doesn't, S is breaking substitutability. This principle is at the heart of inheritance and polymorphism - I should be able to use a Stream without knowing the details of what its underlying storage is, for example.

Liskov's formulation is:

Let q(x) be a property provable about objects x of type T. Then q(y) should be true for objects y of type S where S is a subtype of T.

So, that's the rule. Sounds like a good idea, right?

Breaking BinaryReader's contract

My case in point is EndianBinaryReader (and EndianBinaryWriter, but the arguments will all be the same - it's better to focus on a single type). This is simply an equivalent to System.IO.BinaryReader, but it lets you specify the endianness to use when converting values.

Currently, EndianBinaryReader is a completely separate class to BinaryReader. They have no inheritance relationship. However, as it happens, BinaryReader isn't sealed, and all of the appropriate methods are virtual. So, can we make EndianBinaryReader derive from BinaryReader and use it as a drop-in replacement? Well... that's where the trouble starts.

There's no difficulty technically in doing it. The implementation is fairly straightforward - indeed, it means we can drop a bunch of methods from EndianBinaryReader and let BinaryReader handle it instead. (This is particularly handy for text, which is fiddly to get right.) I currently have the code in another branch, and it works fine.

And I would have gotten away with it if it weren't for that pesky inheritance...

The problem is whether or not it's the right thing to do. To start with, it breaks Liskov's substitutability principle, if the "property" we consider is "the result of calling ReadInt32 when the next four bytes of the underlying stream are 00, 00, 00, 01" for example. Not having read Liskov's paper for myself (I really should, some time) I'm not sure whether this is the intended kind of use or not. More on that later.

The second problem is that it contradicts the documentation for BinaryReader. For example, the docs for ReadInt32 state: "BinaryReader reads this data type in little-endian format." That's a tricky bit of documentation to understand precisely - it's correct for BinaryReader itself, but does that mean it should be true for all subclasses too?

When I've written in various places about the problems of inheritance, and why if you design a class to be unsealed that means doing more design work, this is the kind of thing I've been talking about. How much detail does it make sense to specify here? How much leeway is there for classes overriding ReadInt32? Could a different implementation read a "compressed" Int32 instead of always reading four bytes, for example? Should the client care, if they make sure they've obtained an appropriate BinaryReader for their data source in the first place? This is basically the same as asking how strictly we should apply Liskov's substitutability principle. If two types are the same in every property, surely we can't distinguish between them at all.

I wonder whether most design questions of inheritance basically boil down to defining which properties should obey Liskov's substitutability principle and which needn't, for the type you're designing. Of course, it's not just black and white - there will always be exceptions and awkward points. Programming is often about nuance, even if we might wish that not to be the case.

Blow it, let's do it anyway...

Coming back to BinaryReader, I think (unless I can be persuaded otherwise) that the benefits from going against the documentation (and strict substitutability) outweigh the downsides. In particular, BinaryReaders don't tend to be passed around in my experience - the code which creates it is usually the code which uses it too, or it's at least closely related. The risk of breaking code by passing it a BinaryReader using an unexpected endianness is therefore quite low, even though it's theoretically possible.

So, am I miles off track? This is for a class library, after all - should I be more punctilious about playing by the rules? Or is pragmatism the more important principle here?

RFID: What I really want it for

skeet — Sat, 24 Jan 2009 19:28:40 GMT

This isn't really coding related, but it's technology related at least. There's been a lot of fuss made about how great or awful RFID is and will be in the future, in terms of usefuless and privacy invasion respectively. There's one use which I haven't seen discussed, but which seems pretty obvious to me - but with further enhancements available.

Basically, I want RFID on clothes to tell me useful stuff. Suppose each item of clothing were uniquely tagged, and you had a bunch of scanners in your home linked up to one system which stored metadata about the clothes. Suddenly the following tasks become easier:

Working out which wash cycle to use for a whole washing basket. Can't see the dark sock hidden in the white wash? The RFID scanner could alert you to it. Likewise tumbledrying - no need to check each item separately, just attach the scanner over the tumbledryer door and wait for it to beep as you try to put something in which shouldn't be tumbled.
Separating clothes to put them away after they're clean and dry. Admittedly this is more of a chore for our household than others (with twin boys and an older brother, where some items of clothing could belong to any of them) but it would be really, really useful for us.
Remembering who you've borrowed which clothes from. Kids grow out of clothes very quickly; we have a number of friends who lend us clothes from their children, and likewise we lend plenty of clothes to them and others. You've then got to remember what you borrowed from who, which can become tricky when you've got a loft full of bags of clothing. Wouldn't it be nice to just "label" all the clothes in a bag with the owner's name when you first receive them, and then just pass a scanner near everything quickly later on?

The privacy issues of all of this would have to be worked out carefully (as the simplest solution would allow your movements to be traced just by which clothes you're wearing) but if it does end up being possible, I'll be hugely grateful for this.

(Next up, benchmarking of for vs foreach in various situations. In other words, back to our regular schedule :)

Quick rant: why isn't there an Exception(string, params object[]) constructor?

skeet — Fri, 23 Jan 2009 21:42:52 GMT

This Stack Overflow question has reminded me of something I often wish existed in common exception constructors - an overload taking a format string and values. For instance, it would be really nice to be able to write:

throw new IOException("Expected to read {0} bytes but only {1} were available",
requiredSize, bytesRead);

Of course, with no way of explicitly inheriting constructors (which I almost always want for exceptions, and almost never want for anything else) it would mean yet another overload to copy and paste from another exception, but the times when I've actually written it in my own exceptions it's been hugely handy, particularly for tricky cases where you've got a lot of data to include in the message. (You'd also want an overload taking a nested exception first as well, adding to the baggage...)

Horrible grotty hack: returning an anonymous type instance

skeet — Fri, 09 Jan 2009 07:52:14 GMT

One of the reasons I don't view anonymous types as being too bad is that they're nicely confined to methods. You can't declare the type that you're returning from a method if it's anonymous (or if one of its type arguments is generic, e.g. a List<T> where T is an anonymous type and T isn't a type parameter to the method itself). However, you can get around this if you're sneaky.

I've always known that it's perfectly easy to return an instance of an anonymous type by declaring that the method will return object. However, it hadn't occurred to me before today that you can actually cast back to that type afterwards. Of course, you can't just use a normal cast expression - that requires the name of the type to be known at compile-time. But you can do a cast in a generic method... and you can use type inference to supply a type argument... and two anonymous type instance creation expressions will use the same type within the same assembly if the order, names and types of the properties are the same.

Behold the evil cheesecake factory!

using System;

static class GrottyHacks
{
    internal static T Cast<T>(object target, T example)
    {
        return (T) target;
    }
}

class CheesecakeFactory
{
    static object CreateCheesecake()
    {
        return new { Fruit="Strawberry", Topping="Chocolate" };
    }

    static void Main()
    {
        object weaklyTyped = CreateCheesecake();
        var stronglyTyped = GrottyHacks.Cast(weaklyTyped,
            new { Fruit="", Topping="" });

        Console.WriteLine("Cheesecake: {0} ({1})",
            stronglyTyped.Fruit, stronglyTyped.Topping);
    }
}

The important thing to note here is that the stronglyTyped variable really is of the same anonymous type as the one used in the CreateCheesecake method. When we use the Fruit and Topping properties in the last statement, that's checked at compile-time.

Of course, it all goes pear-shaped if you make the slightest of errors when giving the Cast method an example of what you want to cast to - if you got the order of the properties wrong, for example, the code would still compile, but the cast would throw an exception at execution time.

How useful is this? Ooh, probably not at all. Please do not use this "technique" in your code. If you do, at least don't mention my name anywhere near it. It's all fun though, isn't it?

Value types and parameterless constructors

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

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

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

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

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

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

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

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

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

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

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

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

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

When does the parameterless constructor get called?

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

using System;
using System.Runtime.CompilerServices;

class Test
{
    static Oddity staticField;
    Oddity instanceField;

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

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

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

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

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

And here are the results:

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

So, to split these out:

Operations which do call the constructor

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

Operations which don't call the constructor

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

Conclusions

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

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

Redesigning System.Object/java.lang.Object

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

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

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

What's in System.Object?

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

Life-cycle and type identity

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

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

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

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

Comparison methods

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

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

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

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

Monitors and threading

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

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

String representations

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

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

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

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

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

MemberwiseClone

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

Conclusion

To summarise, in an ideal world:

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

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

Jaffa bugs

skeet — Thu, 06 Nov 2008 17:15:57 GMT

Currently I'm working on a problem found by one of our testers. Unfortunately, it's hard to reproduce. Inspired by the fact that yesterday our micro-kitchen had jaffa cakes in, I propose that if we're going to be frustrated by bugs like this, we might as well at least mock them.

I propose that we call them jaffa bugs, and will work hard to promote this jargon until it takes over the world. Insert evil laugh here.

(Just in case the etymology here isn't clear, see the Wikipedia "Only Fools and Horses" entry.)

C# 4.0: dynamic ?

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

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

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

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

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

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

dynamic<IMessageRouter> router = GetRouter();

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

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

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

Update

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

I'm Sorry, I Haven't a Cluestick

skeet — Fri, 20 Jun 2008 16:22:39 GMT

Unless you've listened to I'm Sorry, I Haven't a Clue, the BBC Radio 4 "antidote to panel games" which was chaired by the recently departed (and much missed) Humphrey Lyttelton, this post may not make a lot of sense to you. That's not intended to guarantee that it'll make any sense to you even if you have listened to it, mind you.

ISIHAC was full of very silly improvisation games. I was listening to an episode last night, and thought a developer version could be equally silly. Games played might include the following: (links show the Wikipedia description of the original)

One language to the API of another: Not so much a joke as a strategy now at both Microsoft and Sun, but I'm sure it could be taken to extremes. Ever fancied using the ZX Spectrum BASIC functions from C#? How about SmallTalk from Java?
Singleton Crescent: Players name design patterns, seemingly at random to the unenlightened observer, until one of them declares "Singleton". Multiple variations exist, such as Gamma's Folly: "After a diagonal move ending on a creational pattern, a behavioural pattern is not permitted."
Fluent Gorge: Players start with a single method call and add additional expressions. The player who inadvertently completes the statement is the loser. This game is already played at lunchtime in many ISVs, some of whom accidentally check in the tortuous code afterwards.
Pick-up algorithm: A player begins copying code out of a book, which is then removed after a few lines. They then have to continue coding as accurately as possible until the book is brought back. Points are awarded if they're within a gnat's semi-colon of the original. Bonus points used to be awarded if the resulting code had fewer bugs in than the printed original, but this practice has recently been discontinued as being a near-trivial way of achieving a high score.
Call my bluff: One player is given a single-line project goal, and then several sets of requirements purporting to support that goal. The player has to guess which set of requirements is the real one for the project. The twist is that none of the sets of requirements is even slightly realistic. Again, this game is in widespread use, played by Business Analysts on unsuspecting developers.

Right, that's more than enough silliness. Something more serious next time, I promise.

Mandelbrot revisited - benchmark edition

skeet — Sun, 18 May 2008 21:44:00 GMT

I've had fun with the Mandelbrot set in this blog before, using it as an example of an embarrassingly parallelisable problem and demonstrating Parallel LINQ with it.

This morning, over breakfast, I described the problem to Christian Brunschen, a colleague of mine who has some parallelisation experience through implementing OpenMP in a portable manner. He immediately suggested a few possible changes to the way that I've approached things. Given the number of different attempts I've now had, I thought it would make sense to write a litte benchmarking app which could easily be expanded as further implementations were considered. The benchmark is available for download so you can play around with it yourself. (As is often the case with this kind of thing, it's not the nicest code in the world for various reasons - the duplication of the sequence generation method, for example... Please don't use it as a tutorial on actual coding and organisation.)

Benchmark implementation details

The benchmark allows you to vary the size of the generated image and the maximum number of iterations per point. The images can be displayed after the test run, but only the time taken to populate a byte array is recorded. The byte arrays are all allocated before any tests are run, and the garbage collector is invoked (as far as it can be) between tests. The images themselves are only generated after the tests have all completed. Each implementation is given a tiny "dummy run" (creating an image 10 pixels across, with a maximum of 2 iterations per point) first to hopefully remove JITting from the benchmarking times. I won't pretend that this puts everything on a completely level playing field (benchmarking is hard) but hopefully it's a good start. We check the similarity between the results of each test and the first one - in some cases they could be "nearly all the same" without there being a bug, due to the subtleties of floating point operations and inlining.

The base class that all the generators use takes care of working out the height from the width, remembering the various configuration options, allocating the array, and also providing a simple imperative method to obtain the value of a single point, without using anything fancy.

I originally wanted to put the whole thing in a nice UI, but after wasting nearly an hour trying to get WPF to behave, I decided to go for a simple console app. One day I really must learn how to write GUIs quickly...

Okay, enough introduction - let's look at the implementations we're testing, and then the results. The idea is to get a look at how a number of areas influence the results, as well as seeing some nifty ways of expressing things functionally.

SingleThreadImperativeSimple

This is the most trivial code you could write, basically. As the base class provides the calculation method, we just go through each row and column, work out the value, and store it in the array. The only attempt at optimisation is keeping the "current index" into the array rather than calculating it for every point.

public override void Generate()
{
    int index = 0;
    for (int row = 0; row < Height; row++)
    {
        for (int col = 0; col < Width; col++)
        {
            Data[index++] = ComputeMandelbrotIndex(row, col);
        }
    }
}

where ComplexMandelbrotIndex is in the base class:

protected byte ComputeMandelbrotIndex(int row, int col)
{
    double x = (col * SampleWidth) / Width + OffsetX;
    double y = (row * SampleHeight) / Height + OffsetY;

    double y0 = y;
    double x0 = x;

    for (int i = 0; i < MaxIterations; i++)
    {
        if (x * x + y * y >= 4)
        {
            return (byte)((i % 255) + 1);
        }
        double xtemp = x * x - y * y + x0;
        y = 2 * x * y + y0;
        x = xtemp;
    }
    return 0;
}

SingleThreadImperativeInline

This is largely the same code as SingleThreadImperativeSimple, but with everything inlined. Within the main body, there's no access to anything other than local variables, and no method calls. One further optimisation is available: points which will have a value of 0 aren't stored (we assume we'll always start with a cleared array).

public override void Generate()
{
    int width = Width;
    int height = Height;
    int maxIterations = MaxIterations;
    int index = 0;
    byte[] data = Data;

    for (int row = 0; row < height; row++)
    {
        for (int col = 0; col < width; col++)
        {
            double x = (col * SampleWidth) / width + OffsetX;
            double y = (row * SampleHeight) / height + OffsetY;

            double y0 = y;
            double x0 = x;

            for (int i = 0; i < maxIterations; i++)
            {
                if (x * x + y * y >= 4)
                {
                    data[index] = (byte)((i % 255) + 1);
                    break;
                }
                double xtemp = x * x - y * y + x0;
                y = 2 * x * y + y0;
                x = xtemp;
            }
            // Leave data[index] = 0 by default
            index++;
        }
    }
}

MultiThreadUpFrontSplitImperative

This should be pretty efficient - work out how many cores we've got, split the work equally between them (as chunks of rows, which helps in terms of locality and just incrementing an index in the byte array each time), and then run. Wait until all the threads have finished, and we're done. Shouldn't be a lot of context switching required normally, and no synchronization is required. However, if some cores are busy with another process, we'll end up context switching for no gain.

public override void Generate()
{
    int cores = Environment.ProcessorCount;

    int rowsPerCore = Height / cores;

    List<Thread> threads = new List<Thread>();
    for (int i = 0; i < cores; i++)
    {
        int firstRow = rowsPerCore * i;
        int rowsToCompute = rowsPerCore;
        if (i == cores - 1)
        {
            rowsToCompute = Height-(rowsPerCore*(cores-1));
        }
        Thread thread = new Thread(() =>
            {
                int index = firstRow * Width;
                for (int row = firstRow; row < firstRow + rowsToCompute; row++)
                {
                    for (int col = 0; col < Width; col++)
                    {
                        Data[index++] = ComputeMandelbrotIndex(row, col);
                    }
                }
            });
        thread.Start();
        threads.Add(thread);
    }

    threads.ForEach(thread => thread.Join());
}

MultiThreadRowFetching

Again, we use a fixed number of threads - but this time we start off with a queue of work - one task per row. The queue has to be synchronized every time we use it, and we also have to check whether or not it's empty. Plenty of scope for lock contention here, particularly as the number of cores increases.

public override void Generate()
{
    Queue<int> rowsLeft = new Queue<int>(Enumerable.Range(0, Height));

    List<Thread> threads = new List<Thread>();
    for (int i = 0; i < Environment.ProcessorCount; i++)
    {
        Thread thread = new Thread(() =>
            {
                while (true)
                {
                    int row;
                    lock (rowsLeft)
                    {
                        if (rowsLeft.Count == 0)
                        {
                            break;
                        }
                        row = rowsLeft.Dequeue();
                    }
                    int index = row * Width;
                    for (int col = 0; col < Width; col++)
                    {
                        Data[index++] = ComputeMandelbrotIndex(row, col);
                    }
                }
            });
        thread.Start();
        threads.Add(thread);
    }

    threads.ForEach(thread => thread.Join());
}

SingleThreadLinqSimple

This is the first version of Mandelbrot generation I wrote since thinking of using LINQ, tweaked a litte to dump the output into an existing array instead of creating a new one. It's essentially the same as SingleThreadImperativeSimple but with the for loops replaced with a query expression.

public override void Generate()
{
    var query = from row in Enumerable.Range(0, Height)
                from col in Enumerable.Range(0, Width)
                select ComputeMandelbrotIndex(row, col);

    int index=0;
    foreach (byte b in query)
    {
        Data[index++] = b;
    }
}

ParallelLinqRowByRowWithCopy

My first attempt using Parallel LINQ was somewhat disastrous due to the nature of PLINQ's ordering. To combat this effect, I initially computed a row at a time, then copying each row into place afterwards:

private byte[] ComputeMandelbrotRow(int row)
{
    byte[] ret = new byte[Width];
    for (int col = 0; col < Width; col++)
    {
        ret[col] = ComputeMandelbrotIndex(row, col);
    }
    return ret;
}

public override void Generate()
{
    var query = from row in Enumerable.Range(0, Height).AsParallel(ParallelQueryOptions.PreserveOrdering)
                select ComputeMandelbrotRow(row);

    int rowStart = 0;
    foreach (byte[] row in query)
    {
        Array.Copy(row, 0, Data, rowStart, Width);
        rowStart += Width;
    }
}

ParallelLinqRowByRowInPlace

An obvious potential improvement is to write the data to the eventual target array as we go, to avoid creating the extra array creation and copying. At this point we have less of a purely functional solution, but it's interesting anyway. Note that to use this idea in a query expression we have to return something even though it's not useful. Likewise we have to make the query execute fully - so I use Max() to ensure that all the results will be computed. (I originally tried Count() but that didn't work - presumably because the count of the results is known before the actual values are.) As we're writing the data to the right place on each iteration, we no longer need to preserve ordering.

private int ComputeMandelbrotRow(int row)
{
    int index = row * Width;
    for (int col = 0; col < Width; col++)
    {
        Data[index++] = ComputeMandelbrotIndex(row, col);
    }
    return 0;
}

public override void Generate()
{
    var query = from row in Enumerable.Range(0, Height).AsParallel()
                select ComputeMandelbrotRow(row);

    query.Max();
}

ParallelLinqWithSequenceOfPoints

After this initial foray into Parallel LINQ, Nicholas Palladinos suggested that I could adapt the original idea in a more elegant manner by treating the sequence of points as a single input sequence, and asking Parallel LINQ to preserve the order of that whole sequence.

public override void Generate()
{
    var points = from row in Enumerable.Range(0, Height)
                 from col in Enumerable.Range(0, Width)
                 select new { row, col };

    var query = from point in points.AsParallel(ParallelQueryOptions.PreserveOrdering)
                select ComputeMandelbrotIndex(point.row, point.col);

    int index=0;
    foreach (byte b in query)
    {
        Data[index++] = b;
    }
}

SingleThreadLinqWithGenerator

My next step was to try to put the whole guts of the algorithm into the query expression, using a Complex value type and a generator to create a sequence of complex numbers generated from the starting point. This is quite a natural step, as the value is computed by just considering this infinite sequence and seeing how quickly it escapes from the circle of radius 2 on the complex plane. Aside from anything else, I think it's a nice example of deferred execution and streaming - the sequence really would go on forever if we didn't limit it with the Take and TakeWhile calls, but the generator itself doesn't know it's being limited. This version uses a sequence of points as per ParallelLinqWithSequenceOfPoints to make it easier to parallelise later.

It's not exactly an efficient way of doing things though - there's a huge amount of calling going on from one iterator to another. I'm actually quite surprised that the final results aren't worse than they are.

public override void Generate()
{
    var points = from row in Enumerable.Range(0, Height)
                 from col in Enumerable.Range(0, Width)
                 select new { row, col };

    var query = from point in points
                // Work out the initial complex value from the row and column
                let c = new Complex((point.col * SampleWidth) / Width + OffsetX,
                                    (point.row * SampleHeight) / Height + OffsetY)
                // Work out the number of iterations
                select GenerateSequence(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
                                                          .Take(MaxIterations)
                                                          .Count() into count
                // Map that to an appropriate byte value
                select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);

    int index = 0;
    foreach (byte b in query)
    {
        Data[index++] = b;
    }
}

public static IEnumerable<T> GenerateSequence<T>(T start, Func<T, T> step)
{
    T value = start;
    while (true)
    {
        yield return value;
        value = step(value);
    }
}

ParallelLinqWithGenerator

From the previous implementation, parallelisation is simple.

public override void Generate()
{
    var points = from row in Enumerable.Range(0, Height)
                 from col in Enumerable.Range(0, Width)
                 select new { row, col };

    var query = from point in points.AsParallel(ParallelQueryOptions.PreserveOrdering)
                // Work out the initial complex value from the row and column
                let c = new Complex((point.col * SampleWidth) / Width + OffsetX,
                                    (point.row * SampleHeight) / Height + OffsetY)
                // Work out the number of iterations
                select GenerateSequence(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
                                                          .Take(MaxIterations)
                                                          .Count() into count
                // Map that to an appropriate byte value
                select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);

    int index = 0;
    foreach (byte b in query)
    {
        Data[index++] = b;
    }
}

SingleThreadImperativeWithComplex

Having already seen how slow the generator version was in the past, I thought it would be worth checking whether or not this was due to the use of the Complex struct - so this is a version which uses that, but is otherwise just like the very first implementation (SingleThreadImperativeSimple).

public override void Generate()
{
    int index = 0;
    for (int row = 0; row < Height; row++)
    {
        for (int col = 0; col < Width; col++)
        {
            Data[index++] = ComputeMandelbrotIndexWithComplex(row, col);
        }
    }
}

byte ComputeMandelbrotIndexWithComplex(int row, int col)
{
    double x = (col * SampleWidth) / Width + OffsetX;
    double y = (row * SampleHeight) / Height + OffsetY;

    Complex start = new Complex(x, y);
    Complex current = start;

    for (int i = 0; i < MaxIterations; i++)
    {
        if (current.SquareLength >= 4)
        {
            return (byte)((i % 255) + 1);
        }
        current = current * current + start;
    }
    return 0;
}

UnorderedParallelLinqSimple

This is where my colleague, Christian, came in. He suggested that instead of ordering the results, we just return the point as well as its value. We can then populate the array directly, regardless of the order of the results. The first version just uses an anonymous type to represent the combination:

public override void Generate()
{
    var query = from row in Enumerable.Range(0, Height).AsParallel()
                from col in Enumerable.Range(0, Width)
                select new { row, col, value = ComputeMandelbrotIndex(row, col) };

    foreach (var x in query)
    {
        Data[x.row * Width + x.col] = x.value;
    }
}

UnorderedParallelLinqWithStruct

Creating a new garbage-collected object on the heap for each point isn't the world's greatest idea. A very simple transformation is to use a struct instead. Without knowing the PLINQ implementation, it seems likely that the values will still end up on the heap somehow (how else could they be communicated between threads?) but I'd still expect a certain saving from this simple step.

public override void Generate()
{
    var query = from row in Enumerable.Range(0, Height).AsParallel()
                from col in Enumerable.Range(0, Width)
                select new Result (row, col, ComputeMandelbrotIndex(row, col));

    foreach (var x in query)
    {
        Data[x.Row * Width + x.Column] = x.Value;
    }
}

struct Result
{
    internal int row, col;
    internal byte value;

    internal int Row { get { return row; } }
    internal int Column { get { return col; } }
    internal byte Value { get { return value; } }

    internal Result(int row, int col, byte value)
    {
        this.row = row;
        this.col = col;
        this.value = value;
    }
}

UnorderedParallelLinqInPlace

Why bother returning the data at all? We can just write the data in place, like we did earlier with ParallelLinqRowByRowInPlace but in a more aggressive fashion (and the disadvantage of computing the index for each point). Again, we have to return a dummy value and iterate through those dummy results to force all the computations to go through.

public override void Generate()
{

    var query = from row in Enumerable.Range(0, Height).AsParallel()
                from col in Enumerable.Range(0, Width)
                // Note side-effect!
                select Data[row*Width + col] = ComputeMandelbrotIndex(row, col);

    // Force iteration through all results
    query.Max();
}

UnorderedParallelLinqInPlaceWithDelegate

UnorderedParallelLinqInPlace feels slightly nasty - we've clearly got a side-effect within the loop, it's just that we know the side-effects are all orthogonal. We can make ourselves feel slightly cleaner by separating the side-effect from the main algorithm, by way of a delegate. The loop can hold its hands up and say, "I'm side-effect free if you are." It's not hugely satisfactory, but it'll be interesting to see the penalty we pay for this attempt to be purer.

IEnumerable<T> Generate<T>(Func<int, int, T> transformation)
{
    var query = from row in Enumerable.Range(0, Height).AsParallel()
                from col in Enumerable.Range(0, Width)
                // Side-effect only if transformation contains one...
                select transformation(row, col);

    return query;
}

public override void Generate()
{
    // Transformation with side-effect
    Func<int,int,byte> transformation = (row, col) => Data[row * Width + col] = ComputeMandelbrotIndex(row, col);

    Generate(transformation).Max();
}

UnorderedParallelLinqInPlaceWithGenerator

We can easily combine the earlier generator code with any of these new ways of processing the results. Here we use our "algorithm in the query" approach but process the results as we go to avoid ordering issues.

public override void Generate()
{
    var query = from row in Enumerable.Range(0, Height).AsParallel()
                from col in Enumerable.Range(0, Width)
                // Work out the initial complex value from the row and column
                let c = new Complex((col * SampleWidth) / Width + OffsetX,
                                    (row * SampleHeight) / Height + OffsetY)
                // Work out the number of iterations
                let count = GenerateSequence(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
                                                               .Take(MaxIterations)
                                                               .Count()
                // Map that to an appropriate byte value - and write it in place
                select Data[row * Width + col] = (byte)(count == MaxIterations ? 0 : (count % 255) + 1);

    // Force execution
    query.Max();
}

ParallelForLoop

The Parallel Extensions library doesn't just contain Parallel LINQ. It also has various other building blocks for parallelism, including a parallel for loop. This allows very simple parallelism of our very first generator - we just turn the outside loop into a parallel for loop, turning the previous inner loop into a delegate. We need to move the index variable into the outer loop so there'll be one per row (otherwise they'd trample on each other) but that's about it:

public override void Generate()
{
    Parallel.For(0, Height, row =>
    {
        int index = row * Width;
        for (int col = 0; col < Width; col++)
        {
            Data[index++] = ComputeMandelbrotIndex(row, col);
        }
    });
}

Results

A benchmark is nothing without results, so here they are on my dual core laptop, from three test runs. The first is the "default" settings I used to develop the benchmark - nothing hugely strenuous, but enough to see differences. I then tried a larger image with the same maximum number of iterations, then the original size with a larger number of iterations. The results are in alphabetical order because that's how the test prints them :) Times are in milliseconds.

Implementation	Width=1200; MaxIterations=200	Width=3000; MaxIterations=200	Width=1200; MaxIterations=800
MultiThreadRowFetching	380	2479	1311
MultiThreadUpFrontSplitImperative	384	2545	2088
ParallelForLoop	376	2361	1292
ParallelLinqRowByRowInPlace	378	2347	1295
ParallelLinqRowByRowWithCopy	382	2376	1288
ParallelLinqWithGenerator	4782	29752	16626
ParallelLinqWithSequenceOfPoints	549	3413	1462
SingleThreadImperativeInline	684	4352	2455
SingleThreadImperativeSimple	704	4353	2372
SingleThreadImperativeWithComplex	2795	16720	9800
SingleThreadLinqSimple	726	4522	2438
SingleThreadLinqWithGenerator	8902	52586	30075
UnorderedParalleLinqInPlace	422	2586	1317
UnorderedParallelLinqInPlaceWithDelegate	509	3093	1392
UnorderedParallelLinqInPlaceWithGenerator	5046	31657	17026
UnorderedParallelLinqSimple	556	3449	1448
UnorderedParalelLinqWithStruct	511	3227	1427

Conclusions

So, what have we learned? Well... bearing in mind that benchmarks like this are often misleading compared with real applications, etc it's still interesting that:

Parallel Extensions rocks. If I were trying to include a Mandelbrot generation implementation in a production setting, I'd definitely go for the parallel for loop - it's simple, but works just as well as anything else.
The micro-optimisation of SingleThreadImperativeInline really doesn't help much, but makes the code harder to understand - just like so many micro-optimisations.
The "generator" form of LINQ really doesn't perform well at all. It does parallelise pretty well, as you'd expect, but it's just plain slow.
Part of the slowness is almost certainly due to the use of the Complex struct, given the results of SingleThreadImperativeWithComplex. Not sure what's going on there.
The extra abstraction step from UnorderedParallelLinqInPlace to UnorderedParallelLinqInPlaceWithDelegate does have a significant impact, at least when the maximum number of iterations per point isn't the dominant force. That doesn't mean it would be a bad idea in production, of course - just somewhere to consider when running against performance issues.

I suspect I've missed some notable points though - comments?

Visualising the Mandelbrot set with LINQ - yet again

skeet — Tue, 26 Feb 2008 20:16:28 GMT

I've been thinking about ranges again, particularly after catching a book error just in time, and looking at Marc's generic complex type. It struck me that my previous attempts were all very well, and demonstrated parallelisation quite neatly, but weren't very LINQy. In particular, they certainly didn't use LINQ for the tricky part in the same way that Luke Hoban's ray tracer does.

The thing is, working out the "value" of a particular point in the Mandelbrot set visualisation is actually quite well suited to LINQ:

Start with a complex value
Apply a transformation to it (square the current value, add the original value from step 1).
Does the result have a modulus > 2? If so, stop.
Have we performed as many iterations as we're willing to? If so, stop.
Take our new value, and go back to 2.

We only need two "extra" bits of code to implement this: a Complex type, and a way of applying the same transformation repeatedly.

Well, here's the Complex type - it contains nothing beyond what we need for this demo, but it'll do. Obviously Marc's generic implementation is rather more complete.

public struct Complex
{
    readonly double real;
    readonly double imaginary;

    public Complex(double real, double imaginary)
    {
        this.real = real;
        this.imaginary = imaginary;
    }

    public static Complex operator +(Complex c1, Complex c2)
    {
        return new Complex(c1.real + c2.real, c1.imaginary + c2.imaginary);
    }

    public static Complex operator *(Complex c1, Complex c2)
    {
        return new Complex(c1.real*c2.real - c1.imaginary*c2.imaginary,
                           c1.real*c2.imaginary + c2.real*c1.imaginary);
    }

    public double SquareLength
    {
        get { return real * real + imaginary * imaginary; }
    }
}

Simple stuff, assuming you know anything about complex numbers.

The other new piece of code is even simpler. It's just a generator. It's a static method which takes an initial value, and a delegate to apply to one value to get the next. It then lazily returns the generated sequece - forever.

public static IEnumerable<T> Generate<T>(T start, Func<T, T> step)
{
    T value = start;
    while (true)
    {
        yield return value;
        value = step(value);
    }
}

Just as an example of use, remember Enumerable.Range which starts at a particular integer, then adds one repeatedly until it's yielded as many results as you've asked for? Well, here's a possible implementation, given the Generate method:

public static IEnumerable<int> Range(int start, int count)
{
return Generate(start, x => x + 1).Take(count);
}

These are all the building blocks we require to build our Mandelbrot visualisation. We want a query which will return a sequence of bytes, one per pixel, where each byte represents the colour to use. Anything which goes beyond our maximum number of iterations ends up black (colour 0) and other values will cycle round the colours. I won't show the drawing code, but the query is now more self-contained:

var query = from row in Enumerable.Range(0, ImageHeight)
            from col in Enumerable.Range(0, ImageWidth)
            // Work out the initial complex value from the row and column
            let c = new Complex((col * SampleWidth) / ImageWidth + OffsetX,
                                (row * SampleHeight) / ImageHeight + OffsetY)
            // Work out the number of iterations
            select Generate(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
                                              .Take(MaxIterations)
                                              .Count() into count
            // Map that to an appropriate byte value
            select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);

(The various constants used in the expression are defined elsewhere.) This works, and puts the Mandelbrot logic directly into the query. However, I have to admit that it's much slower than my earlier versions. Heck, I'm still proud of it though.

As ever, full source code is available for download, should you so wish.

Boxing day

skeet — Wed, 26 Dec 2007 20:58:19 GMT

Here in the UK (and possibly elsewhere - I'm too lazy to check Wikipedia) December 26th is called Boxing Day. I want to know why only this one aspect of .NET is given its own public holiday. Expanding the opportunities to language features as well as those of the runtime, I'd like to see:

Null coalescing day ("Take 3 nulls into the shower? Not me. I just coalesce and go!")
Type inference day (not popular with HR)
Garbage collection day (as a proper holiday, not just when the bins are collected)
Just-In-Time day (arguably every day for procrastinators such as myself)
Lambda expression day (get those lambdas out of the closet)

I could go on, but it's a pretty thin joke and dinner is ready.