Category Archives: Stack Overflow

Diagnostics, General, Stack Overflow

Diagnosing weird problems – a Stack Overflow case study

15 Comments

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

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

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

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

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

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

Reproducing the problem

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

I ran md5sums on c:WindowsSystem32calc.exe, and got the same result as the poster. Handy.

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

Looking for obvious problems

The code has four main areas:

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

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

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

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

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

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

Initial checks around the file

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

MessageDigest md5 = MessageDigest.getInstance(“MD5”);

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

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

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

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

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

The result showed the number of bytes being read as the command prompt did when I ran “dir c:WindowsSystem32Calc.exe” – so again, everything looks like it’s okay.

Desperate times call for stupid measures

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

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

I then reran md5sums on the copied file… and it gave the same result as Java. In other words, running “md5sums c:WindowsSystem32Calc.exe” gave one result, but “md5sums CopyOfCalc.exe” gave a different result. At this point we’ve moved from Java looking like it’s behaving weirdly to md5sums looking suspicious.

Proving the root cause

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

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

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

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

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

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

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

Explaining the root cause

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

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

Conclusion

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

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

C#, Evil code, Speaking engagements, Stack Overflow

Upcoming speaking engagements

8 Comments

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

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

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

Øredev 2011 – Malmö, November 9th

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

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

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

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

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

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

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

General, Stack Overflow

Writing the perfect question

102 Comments

Please note: this blog post is not a suitable place to post a development question. You should probably be doing that on Stack Overflow – after reading this post, of course. I’ve received a truly astonishing number of comments on this post which are basically misplaced questions. Such comments are simply marked as spam – they don’t belong here.

TL;DR: If you don’t have time to read this post fully, I have a checklist version. I’d strongly encourage you to read this post fully though, when you have time.

I’ve added a tinyurl to this post for easy reference:
http://tinyurl.com/stack-hints. Nice and easy to remember :)

A while ago, I wrote a blog entry on how to answer questions helpfully on sites like Stack Overflow. Recently I saw a meta question about bad questions and thought it would be worth following up with another blog post on asking questions. For the sake of convenience – and as Stack Overflow is so popular – I will assume the question is going to be asked on Stack Overflow or a similar Stack Exchange site. Most of the post doesn’t actually depend on that, but if you’re asking elsewhere you may need to tweak the advice a little.

There are plenty of similar resources around, of course – in particular, How to Ask Questions the Smart Way by Eric Raymond and Rick Moen is a perennial favourite. Still, I think I can bring something to the table.

The Golden Rule: Imagine You’re Trying To Answer The Question

If you don’t remember anything else from this post, remember this bit. Everything else follows from here. (And yes, this does smack somewhat of Matthew 7:12.)

Once you’ve finished writing your question, read it through. Imagine you were coming to it fresh, with no context other than what’s on the screen. Does it make sense? Is it clear what’s being asked? Is it easy to read and understand? Are there any obvious areas you’d need to ask about before providing an answer? You can usually do this pretty well however stuck you are on the actual question. Just apply common sense. If there’s anything wrong with the question when you’re reading it, obviously that will be a problem for whoever’s actually trying to answer it. So fix the problems. Improve the question until you can read it and think, “If I only knew the answer to the question, it would be a pleasure to provide that answer.” At that point, post and wait for the answers to come rolling in.

Obviously this is somewhat easier to do if you have a certain amount of experience answering questions, particularly on the forum where you’re about to post. So, what should you be looking out for?

Question title

When a reader first sees your question, they’re likely to be scrolling down a list of snippets. The most eye-catching part of the snippet will be the title – so use that text wisely. While you can include language or platform information, you should only do so naturally – not as a sort of “header”. For example, this is bad:

Java: Why are bytes signed?

But this is okay:

Why are bytes signed in Java?

Of course, you should also include this information in tags, as it will help people who pay particular attention to specific tags.

Ideally, a question title should be a question – but frankly that’s not always feasible. I would recommend favouring a short, descriptive title which captures the theme of the question without actually being a question instead of really trying to crowbar it into the form of a question when it really doesn’t want to be. That’s not an excuse for laziness though – it’s usually possible to come up with a good title which is genuinely a question.

It’s important that the question title is specific though, and has at least some meaning with no other information. A question such as “Why doesn’t this work?” makes absolutely no sense without the rest of the question. Likewise a “question” title of “Please help” is unlikely to do well.

Context

In most cases, anyone answering the question will need to know what language and platform you’re using. The basics should usually be communicated through tags, but it may very well be worth providing more information:

  • Language version (e.g. C# 4)
  • Platform version (e.g. .NET 3.5; note that this isn’t always implicit from the language version, or vice versa)
  • Operating system, if it could be relevant (e.g. particular permissions issues)
  • Any other relevant software (e.g. database type and version, the IDE you’re using, web server you’re connecting to)
  • Any other constraints. This is particularly important. It’s really annoying to give a perfectly good answer to a question, only to be told that you’re not allowed to use feature X or Y which provide the obvious solution.
    • If you have unusual constraints, it’s worth explaining why. Not only does this answer the obvious follow-up comment, but it also gives more information about what other solutions may not be applicable.

Describe what you’ve already tried and the results of any research. (You have searched for a solution to your problem before asking it, haven’t you? Stack Overflow isn’t meant to replace basic search skills.) Often there will be other people in a similar situation, but the answers didn’t quite match your situation. Just like the above point about unusual constraints, it saves time if you can point out differences between your situation and other common ones. It’s even worth referring to other related questions explicitly – particularly if they’re on the same forum. Aside from anything else, this shows a certain amount of “due diligence” – people are generally more willing to help you if can show you’ve already put some effort in.

You should absolutely make sure that you tag the question appropriately. If you’re not sure which exact tags are appropriate, see what gets auto-suggested and look at samples for each one. If that sounds like a lot of work, just remember how much time you may be able to save yourself in the long run. It gets easier over time, of course.

Problem statement

Make sure it’s obvious what you’re trying to get out of the question. Too many “questions” are actually just statements: when I do X, something goes wrong.

Well, what did you expect it to do? What are you trying to accomplish? What have you already tried? What happened in those attempts? Be detailed: in particular, if something didn’t work, don’t just state that: tell us how it failed. If it threw an exception, what was the exception? (Don’t just give the type – give the error message and say which line threw it. If there’s a nested exception, post that too.)

If at all possible, write a sort of “executive summary” at the start of your question, followed by a more detailed description. Remember that on the list of questions, the first few sentences will appear as a snippet. If you can get a sense of the question across in that snippet, you’re more likely to attract views from people who can answer the question.

One trap that many posters fall into is to ask how to achieve some “small” aim, but never say what the larger aim is. Often the smaller aim is either impossible or rarely a good idea – instead, a different approach is needed. Again, if you provide more context when writing your problem statement, we can suggest better designs. It’s fine to specify how you’re currently trying to solve your bigger problem, of course – that’s likely to be necessary detail – but include the bigger goal too.

Sample code and data

I may be biased on this one. I’m a huge believer in sample code, both for questions and answers… and I probably use it in an unconventional way. I usually paste it into a text editor, and try to compile it from the command line. If that’s not likely to work (and the problem isn’t obvious by inspection), I’m unlikely to bother too much with it. Firing up Eclipse or Visual Studio and finding an existing project I don’t care about or starting a new one is going to take much more time.

That means if you want me to look at code, it should:

  • Be standalone. Don’t try to talk to a database unless you really have to. (Obviously for database questions, that’s kinda hard :) If you use sample XML, provide a short but complete XML file for us to reproduce the issue with. (And the same for other file types, obviously.)
  • Be complete. If there are missing imports or using directives, that’s really annoying
  • Actually compile (unless the compilation error is the reason for the question). Don’t give me code which is “something like” the real code but which clearly isn’t the real code, and may well not exhibit the same symptoms by the time I’ve fixed it so that it compiles.
  • Ideally not bring up a UI. Unless your code is about a UI issue, don’t bring one up. Console apps are simpler, and simplicity is a huge benefit when trying to hunt down a problem.
  • Demonstrate the problem. You should be able to say, “I expected the result to be X, it’s actually Y.” (You should actually say that too, so that we can check that we get the same results.)
  • Be as short as possible. If I have to wade through hundreds of lines of code to find the problem, I’m doing work that you should be doing. Often if you work hard to reduce the problem to a short but complete program, you’ll find the issue yourself. You can absolutely do this without knowing what the problem is; you should be looking to the community for their expertise, not their willingness to spend time on your problem doing the work that you can do yourself.

Yes, this is a relatively onerous list. It doesn’t all apply to every problem, but it does apply in a great many situations. While I get put off by reams of irrelevant, badly formatted code, some of which clearly won’t compile, the inverse is true as well: if I can tell by looking at the question that the code can go through a copy/paste/compile/run cycle really quickly, I’m much more likely to pay the question significant attention.

In data-oriented questions, it’s very often helpful to give some sample data. Cut out anything irrelevant (if your real table has 50 columns, you only need to include relevant ones) but make sure that you give enough sample input for it to be meaningful. For example, if you’re trying to group some data by a PersonID column, it’s pretty useless if there’s only one PersonID given, or if each PersonID only appears once. If you are giving examples of expected input and corresponding output, make sure it’s clear why that’s the expected output. Often I see questions which give a small number of samples, and there are various ways they could be interpreted. This is one area where it’s particularly important to reread the question from a stranger’s point of view: while a brief summary of the desired results may well make sense to someone who already knows what your app is trying to achieve, it may be gobbledygook to those trying to answer your question.

Spelling, grammar and formatting

I know not everyone speaks English natively. My own command of non-English languages is lamentably poor – I’m incredibly lucky that my native tongue happens to be the lingua franca of the technical world. However, if you’re trying to communicate on an English-language forum, you owe it to yourself to make an effort to write at least reasonably correct English.

  • Please use capital letters where appropriate. It really can make a big difference in the readability of text.
  • Please split your text into paragraphs. Imagine this blog post as one big paragraph – it would be almost impossible to read.
  • Please write actual words. There are undoubtedly some abbreviations which are acceptable to most readers – IMO, IIRC etc –  there’s no reason to switch into text-speak with “gr8”, “bcoz”, “u” and so forth. It’s unlikely that you’re actually writing your question on a phone with only a primitive keyboard; show your readers respect by writing properly. It may take you a few more seconds, but if it means you get an answer quicker, it’s surely worth the extra effort.
  • Most browsers have built-in spelling checkers these days, or at least have plug-ins or extensions available to check your text. Technical text often creates a lot of false positives for checkers, but if your spelling isn’t generally great, it’s worth looking at the suggestions.

Having said all of this, you’re not trying to create a literary masterpiece. You’re trying to communicate your question as effectively as possible. If you’re faced with the choice between an unambiguous but ugly sentence, or a phrase which stirs the soul but leaves the reader confused about exactly what you mean, go for the unambiguous option every time.

One way a huge number of questions can be improved with very little effort is simply formatting them properly. Stack Overflow’s markdown editor is very good – the preview below your input box is almost always accurate in terms of the eventual result, and you can always edit the question later if anything doesn’t quite work. The exact details of the markdown is beyond the scope of this article – Stack Overflow has a detailed guide though – if you’re new to the site, I’d recommend you at least skim through it.

By far the most important kind of formatting is making code look like code. Within a text paragraph, simply surround the code with backticks `like this`. For blocks of code, just indent everything by four spaces. If you’re cutting and pasting code, it may already be indented (for example if you’re copying code within a class) but if not, the easiest way to indent everything is to paste it, select the whole code block, and then press Ctrl-K or the “{ }” button just above the editor.

One of the important things about code formatting is that it means angle brackets (and some other symbols) are preserved instead of being swallowed by the markdown formatter. In some cases this can mean all the difference between a question which is easy to answer and one which doesn’t make any sense, particularly in terms of generics in Java and C# or templates in C++. For example, like this

Why can’t I convert an expression of type List<string> to List<object>?

makes no sense at all if the type arguments are removed:

Why can’t I convert an expression of type List to List?

Often experienced members of the site will recognise what’s going on and edit your question for you, but obviously it’s better if they don’t have to.

Making a good impression

Leaving aside the main body of the question, there are a few simple ways to get the community “on your side” and therefore more likely to give you a useful answer quickly.

  • Register as a user and give yourself a meaningful name. It doesn’t have to be your real name, but frankly names like “Top Coder” or “Coding Guru” look pretty silly when you’re asking a question which others find simple. That’s still better than leaving yourself as “user154232” or whatever identifier is assigned to you by default though. Aside from anything else, it shows a certain amount of commitment to the question and/or site: if you’ve bothered to give yourself a name, you’re less likely to be an “ask-and-run” questioner.
  • Keep an eye on your question. There may well be requests for clarification – and of course, answers! If you receive an answer which wasn’t quite what you were looking for, explain carefully (and politely) why it’s not suitable for your purposes. Consider going back and editing your question to make it clearer for subsequent users.
  • Don’t add your own answer unless it really is an answer. Often users add extra details in an “answer” when they should really have just edited their question. Likewise editing your question is generally a better idea than adding a long comment to an existing answer – particularly if that comment contains a block of code (which won’t work well in a comment). If you do change the question in response to an answer though, it’s worth adding a comment to the answer just to let the user know that you’ve updated it though… you may well find they quickly edit their answer to match the revised question.
  • There’s no need to include greetings and sign-offs such as “Hi everyone!” and “Thanks – hope to get an answer soon” in the question. These will often be edited out by other users, as they’re basically a distraction. Greetings at the start of a question are particularly useless as they can take up valuable space in the snippet displayed in the question list.
  • Above all, be polite. Remember that no-one is getting paid to answer your question. Users are giving up their time to help you – so please be appreciative of that. If you’re asking a homework question, explain why you’re asking for help with something that traditionally you’d have to answer all by yourself. If a user suggests that your general approach is wrong and that there’s a better way of doing things, don’t take it personally: they’re trying to help you improve your code. By all means disagree robustly, but don’t start into ad hominem arguments. (This advice applies to answerers as well, of course.)
  • (Somewhat specific to Stack Overflow.) If an answer is particularly helpful or solves your problem, accept it by clicking on the tick mark by it. This gives extra credit to the person who provided that answer, as well as giving more information to future readers.

Conclusion and feedback

Stack Overflow is an amazing resource (along with other Q&A sites, of course). The idea that you can get a good answer to a wide range of questions within minutes is pretty staggering… but there’s an obvious correlation between the quality of a question and the likelihood that you’ll get quick, helpful answers. Put that extra bit of effort in yourself, and it will probably pay for itself very quickly.

I’m hoping to keep this blog post up to date with suggestions received – if I’ve missed out anything, over- or under-emphasized a specific point, or generally gone off track, let me know either in the comments here or mail me (skeet@pobox.com). If this document ends up elsewhere, then that copy may end up being the “canonical” one which is edited over time – in which case I’ll indicate that here.

C#, Evil code, Stack Overflow, Wacky Ideas

“Magic” null argument testing

51 Comments

Warning: here be dragons. I don’t think this is the right way to check for null arguments, but it was an intriguing idea.

Today on Stack Overflow, I answered a question about checking null arguments. The questioner was already using an extension similar to my own one in MiscUtil, allowing code like this:

public void DoSomething(string name)
{
    name.ThrowIfNull("name");

    // Normal code here
}

That’s all very well, but it’s annoying to have to repeat the name part. Now in an ideal world, I’d say it would be nice to add an attribute to the parameter and have the check performed automatically (and when PostSharp works with .NET 4.0, I’m going to give that a go, mixing Code Contracts and AOP…) – but for the moment, how far can we go with extension methods?

I stand by my answer from that question – the code above is the simplest way to achieve the goal for the moment… but another answer raised the interesting prospect of combining anonymous types, extension methods, generics, reflection and manually-created expression trees. Now that’s a recipe for hideous code… but it actually works.

The idea is to allow code like this:

public void DoSomething(string name, string canBeNull, int foo, Stream input)
{
    new { name, input }.CheckNotNull();

    // Normal code here
}

That should check name and input, in that order, and throw an appropriate ArgumentNullException – including parameter name – if one of them is null. It uses the fact that projection initializers in anonymous types use the primary expression’s name as the property name in the generated type, and the value of that expression ends up in the instance. Therefore, given an instance of the anonymous type initializer like the above, we have both the name and value despite having only typed it in once.

Now obviously this could be done with normal reflection – but that we be slow as heck. No, we want to effectively find the properties once, and generate strongly typed delegates to perform the property access. That sounds like a job for Delegate.CreateDelegate, but it’s not quite that simple… to create the delegate, we’d need to know (at compile time) what the property type is. We could do that with another generic type, but we can do better than that. All we really need to know about the value is whether or not it’s null. So given a "container" type T, we’d like a bunch of delegates, one for each property, returning whether that property is null for a specified instance – i.e. a Func<T, bool>. And how do we build delegates at execution time with custom logic? We use expression trees…

I’ve now implemented this, along with a brief set of unit tests. The irony is that the tests took longer than the implementation (which isn’t very unusual) – and so did writing it up in this blog post. I’m not saying that it couldn’t be improved (and indeed in .NET 4.0 I could probably make the delegate throw the relevant exception itself) but it works! I haven’t benchmarked it, but I’d expect it to be nearly as fast as manual tests – insignificant in methods that do real work. (The same wouldn’t be true using reflection every time, of course.)

The full project including test cases is now available, but here’s the (almost completely uncommented) "production" code.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Linq.Expressions;

public static class Extensions
{
    public static void CheckNotNull<T>(this T container) where T : class
    {
        if (container == null)
        {
            throw new ArgumentNullException("container");
        }
        NullChecker<T>.Check(container);
    }

    private static class NullChecker<T> where T : class
    {
        private static readonly List<Func<T, bool>> checkers;
        private static readonly List<string> names;

        static NullChecker()
        {
            checkers = new List<Func<T, bool>>();
            names = new List<string>();
            // We can’t rely on the order of the properties, but we
            // can rely on the order of the constructor parameters
            // in an anonymous type – and that there’ll only be
            // one constructor.
            foreach (string name in typeof(T).GetConstructors()[0]
                                             .GetParameters()
                                             .Select(p => p.Name))
            {
                names.Add(name);
                PropertyInfo property = typeof(T).GetProperty(name);
                // I’ve omitted a lot of error checking, but here’s
                // at least one bit…
                if (property.PropertyType.IsValueType)
                {
                    throw new ArgumentException
                        ("Property " + property + " is a value type");
                }
                ParameterExpression param = Expression.Parameter(typeof(T), "container");
                Expression propertyAccess = Expression.Property(param, property);
                Expression nullValue = Expression.Constant(null, property.PropertyType);
                Expression equality = Expression.Equal(propertyAccess, nullValue);
                var lambda = Expression.Lambda<Func<T, bool>>(equality, param);
                checkers.Add(lambda.Compile());
            }
        }

        internal static void Check(T item)
        {
            for (int i = 0; i < checkers.Count; i++)
            {
                if (checkers[i](item))
                {
                    throw new ArgumentNullException(names[i]);
                }
            }
        }
    }
}

Oh, and just as a miracle – the expression tree worked first time. I’m no Marc Gravell, but I’m clearly improving :)

Update: Marc Gravell pointed out that the order of the results of Type.GetProperties isn’t guaranteed – something I should have remembered myself. However, the order of the constructor parameters will be the same as in the anonymous type initialization expression, so I’ve updated the code above to reflect that. Marc also showed how it could almost all be put into a single expression tree which returns either null (for no error) or the name of the "failing" parameter. Very clever :)

C#, General, Stack Overflow

Just how spiky is your traffic?

13 Comments

No, this isn’t the post about dynamic languages I promise. That will come soon. This is just a quick interlude. This afternoon, while answering a question on Stack Overflow1 about the difference between using an array and a Dictionary<string, string> (where each string was actually the string representation of an integer) I posted the usual spiel about preferring readable code to micro-optimisation. The response in a comment – about the performance aspect – was:

Well that’s not so easily said for a .com where performance on a site that receives about 1 million hits a month relies on every little ounce of efficiency gains you can give it.

A million hits a month, eh? That sounds quite impressive, until you actually break it down. Let’s take a month of 30 days – that has 30 * 24 * 60 * 60 = 2,592,000 seconds2. In other words, a million hits a month is less than one hit every two seconds. Not so impressive. At Google we tend to measure traffic in QPS (queries per second, even if they’re not really queries – the search terminology becomes pervasive) so this is around 0.39 QPS. Astonished that someone would make such a claim in favour of micro-optimisation at that traffic level, I tweeted about it. Several of the replies were along the lines of "yeah, but traffic’s not evenly distributed." That’s entirely true. Let’s see how high we can make the traffic without going absurd though.

Let’s suppose this is a site which is only relevant on weekdays – that cuts us down to 20 days in the month. Now let’s suppose it’s only relevant for one hour per day – it’s something people look at when they get to work, and most of the users are in one time zone. That’s a pretty massive way of spiking. We’ve gone down from 30 full days of traffic to 20 hours – or 20 * 60 * 60 = 72000 seconds, giving 14 QPS. Heck, let’s say the peak of the spike is double that – a whopping 28 QPS.

Three points about this:

  • 28 QPS is still not a huge amount of traffic.
  • If you’re really interested in handling peak traffic of ~28 QPS without latency becoming huge, it’s worth quoting that figure rather than "a million hits a month" because the latter is somewhat irrelevant, and causes us to make wild (and probably wildly inaccurate) guesses about your load distribution.
  • If you’re going to bring the phrase "a .com" into the picture, attempting to make it sound particularly important, you really shouldn’t be thinking about hosting your web site on one server – so the QPS gets diluted again.
  • Even at 28 QPS, the sort of difference that would be made here is tiny. A quick microbenchmark (with all the associated caveats) showed that on my laptop (hardly a server-class machine) I could build the dictionary and index into it 3 times 2.8 million times in about 5 seconds. If every request needed to do that 100 times, then the cost of doing it 28 requests per second on my laptop would still only be 0.5% of that second – not a really significant benefit, despite the hugely exaggerated estimates of how often we needed to do that.

There are various other ways in which it’s not a great piece of code, but the charge against premature optimization still stands. You don’t need to get every little ounce of efficiency out of your code. Chances are, if you start guessing at where you can get efficiency, you’re going to be wrong. Measure, measure, measure – profile, profile, profile. Once you’ve done all of that and proved that a change reducing clarity has a significant benefit, go for it – but until then, write the most readable code you can. Likewise work out your performance goals in a meaningful fashion before you worry too much – and hits per months isn’t a meaningful figure.

Performance is important – too important to be guessed about instead of measured.

1 I’m not linking to it because the Streisand effect would render this question more important than it really is. I’m sure you can find it if you really want to, but that’s not the point of the post.

2 Anyone who wants to nitpick and talk about months which are a bit longer or shorter than that due to daylight saving time changes (despite still being 30 days) can implement that logic for me in Noda Time.

Benchmarking, C#, Parallelization, Stack Overflow

Revisiting randomness

19 Comments

Almost every Stack Overflow question which includes the words "random" and "repeated" has the same basic answer. It’s one of the most common "gotchas" in .NET, Java, and no doubt other platforms: creating a new random number generator without specifying a seed will depend on the current instant of time. The current time as measured by the computer doesn’t change very often compared with how often you can create and use a random number generator – so code which repeatedly creates a new instance of Random and uses it once will end up showing a lot of repetition.

One common solution is to use a static field to store a single instance of Random and reuse it. That’s okay in Java (where Random is thread-safe) but it’s not so good in .NET – if you use the same instance repeatedly from .NET, you can corrupt the internal data structures.

A long time ago, I created a StaticRandom class in MiscUtil – essentially, it was just a bunch of static methods (to mirror the instance methods found in Random) wrapping a single instance of Random and locking appropriately. This allows you to just call StaticRandom.Next(1, 7) to roll a die, for example. However, it has a couple of problems:

  • It doesn’t scale well in a multi-threaded environment. When I originally wrote it, I benchmarked an alternative approach using [ThreadStatic] and at the time, locking won (at least on my computer, which may well have only had a single core).
  • It doesn’t provide any way of getting at an instance of Random, other than by using new Random(StaticRandom.Next()).

The latter point is mostly a problem because it encourages a style of coding where you just use StaticRandom.Next(…) any time you want a random number. This is undoubtedly convenient in some situations, but it goes against the idea of treating a source of randomness as a service or dependency. It makes it harder to get repeatability and to see what needs that dependency.

I could have just added a method generating a new instance into the existing class, but I decided to play with a different approach – going back to per-thread instances, but this time using the ThreadLocal<T> class introduced in .NET 4.0. Here’s the resulting code:

using System;
using System.Threading;

namespace RandomDemo
{
    /// <summary>
    /// Convenience class for dealing with randomness.
    /// </summary>
    public static class ThreadLocalRandom
    {
        /// <summary>
        /// Random number generator used to generate seeds,
        /// which are then used to create new random number
        /// generators on a per-thread basis.
        /// </summary>
        private static readonly Random globalRandom = new Random();
        private static readonly object globalLock = new object();

        /// <summary>
        /// Random number generator
        /// </summary>
        private static readonly ThreadLocal<Random> threadRandom = new ThreadLocal<Random>(NewRandom);

        /// <summary>
        /// Creates a new instance of Random. The seed is derived
        /// from a global (static) instance of Random, rather
        /// than time.
        /// </summary>
        public static Random NewRandom()
        {
            lock (globalLock)
            {
                return new Random(globalRandom.Next());
            }
        }

        /// <summary>
        /// Returns an instance of Random which can be used freely
        /// within the current thread.
        /// </summary>
        public static Random Instance { get { return threadRandom.Value; } }

        /// <summary>See <see cref="Random.Next()" /></summary>
        public static int Next()
        {
            return Instance.Next();
        }

        /// <summary>See <see cref="Random.Next(int)" /></summary>
        public static int Next(int maxValue)
        {
            return Instance.Next(maxValue);
        }

        /// <summary>See <see cref="Random.Next(int, int)" /></summary>
        public static int Next(int minValue, int maxValue)
        {
            return Instance.Next(minValue, maxValue);
        }

        /// <summary>See <see cref="Random.NextDouble()" /></summary>
        public static double NextDouble()
        {
            return Instance.NextDouble();
        }

        /// <summary>See <see cref="Random.NextBytes(byte[])" /></summary>
        public static void NextBytes(byte[] buffer)
        {
            Instance.NextBytes(buffer);
        }
    }
}

The user can still call the static Next(…) methods if they want, but they can also get at the thread-local instance of Random by calling ThreadLocalRandom.Instance – or easily create a new instance with ThreadLocalRandom.NewRandom(). (The fact that NewRandom uses the global instance rather than the thread-local one is an implementation detail really; it happens to be convenient from the point of view of the ThreadLocal<T> constructor. It wouldn’t be terribly hard to change this.)

Now it’s easy to write a method which needs randomness (e.g. to shuffle a deck of cards) and give it a Random parameter, then call it using the thread-local instance:

public void Shuffle(Random rng)
{
    …
}
…
deck.Shuffle(ThreadLocalRandom.Instance);

The Shuffle method is then easier to test and debug, and expresses its dependency explicitly.

Performance

I tested the "old" and "new" implementations in a very simple way – for varying numbers of threads, I called Next() a fixed number of times (from each thread) and timed how long it took for all the threads to finish. I’ve also tried a .NET-3.5-compatible version using ThreadStatic instead of ThreadLocal<T>, and running the original code and the ThreadStatic version on .NET 3.5 as well.

Threads StaticRandom (4.0b2) ThreadLocalRandom (4.0b2) ThreadStaticRandom (4.0b2) StaticRandom(3.5) ThreadStaticRandom (3.5)
1 11582 6016 10150 10373 16049
2 24667 7214 9043 25062 17257
3 38095 10295 14771 36827 25625
4 49402 13435 19116 47882 34415

A few things to take away from this:

  • The numbers were slightly erratic; somehow it was quicker to do twice the work with ThreadStaticRandom on .NET 4.0b2! This isn’t the perfect benchmarking machine; we’re interested in trends rather than absolute figures.
  • Locking hasn’t changed much in performance between framework versions
  • ThreadStatic has improved massively between .NET 3.5 and 4.0
  • Even on 3.5, ThreadStatic wins over a global lock as soon as there’s contention

The only downside to the ThreadLocal<T> version is that it requires .NET 4.0 – but the ThreadStatic version works pretty well too.

It’s worth bearing in mind that of course this is testing the highly unusual situation where there’s a lot of contention in the global lock version. The performance difference in the single-threaded version where the lock is always uncontended is still present, but very small.

Update

After reading the comments and thinking further, I would indeed get rid of the static methods elsewhere. Also, for the purposes of dependency injection, I agree that it’s a good idea to have a factory interface where that’s not overkill. The factory implementation could use either the ThreadLocal or ThreadStatic implementations, or effectively use the global lock version (by having its own instance of Random and a lock). In many cases I’d regard that as overkill, however.

One other interesting option would be to create a thread-safe instance of Random to start with, which delegated to thread-local "normal" implementations. That would be very useful from a DI standpoint.

Speaking engagements, Stack Overflow

OMG Ponies!!! (Aka Humanity: Epic Fail)

68 Comments

(Meta note: I tried to fix the layout for this, I really did. But my CSS skills are even worse than Tony’s. If anyone wants to send me a complete sample of how I should have laid this out, I’ll fix it up. Otherwise, this is as good as you’re going to get :)

Last week at Stack Overflow DevDays, London I presented a talk on how humanity had made life difficult for software developers. There’s now a video of it on Vimeo – the audio is fairly poor at the very start, but it improves pretty soon. At the very end my video recorder ran out of battery, so you’ve just got my slides (and audio) for that portion. Anyway, here’s my slide deck and what I meant to say. (A couple of times I forgot exactly which slide was coming next, unfortunately.)

Click on any thumbnail for a larger view.

Good afternoon. This talk will be a little different from the others we’ve heard today… Joel mentioned on the podcast a long time ago that I’d talk about something "fun and esoteric" – and while I personally find C# 4 fun, I’m not sure that anyone could really call it esoteric. So instead, I thought I’d rant for half an hour about how mankind has made our life so difficult.

By way of introduction, I’m Jon Skeet. You may know me from questions such as Jon Skeet Facts, Why does Jon Skeet never sleep? and a few C# questions here and there. This is Tony the Pony. He’s a developer, but I’m afraid he’s not a very good one.

(Tony whispers) Tony wants to make it clear that he’s not just a developer. He has another job, as a magician. Are you any better at magic than development then? (Tony whispers) Oh, I see. He’s not very good at magic either – his repertoire is extremely limited. Basically he’s a one trick pony.

Anyway, when it comes to software, Tony gets things done, but he’s not terribly smart. He comes unstuck with some of the most fundamental data types we have to work with. It’s really not his fault though – humanity has let him down by making things just way too complicated.

You see, the problem is that developers are already meant to be thinking about difficult things… coming up with a better widget to frobjugate the scarf handle, or whatever business problem they’re thinking about. They’ve really got enough to deal with – the simple things ought to be simple.

Unfortunately, time and time again we come up against problems with core elements of software engineering. Any resemblance between this slide and the coding horror logo is truly coincidental, by the way. Tasks which initially sound straightforward become insanely complicated. My aim in this talk is to distribute the blame amongst three groups of people.

First, let’s blame users – or mankind as a whole. Users always have an idea that what they want is easy, even if they can’t really articulate exactly what they do want. Even if they can give you requirements, chances are those will conflict – often in subtle ways – with requirements of others. A lot of the time, we wouldn’t even think of these problems as "requirements" – they’re just things that everyone expects to work in "the obvious way". The trouble is that humanity has come up with all kinds of entirely different "obvious ways" of doing things. Mankind’s model of the universe is a surprisingly complicated one.

Next, I want to blame architects. I’m using the word "architect" in a very woolly sense here. I’m trying to describe the people who come up with operating systems, protocols, libraries, standards: things we build our software on top of. These are the people who have carefully considered the complicated model used by real people, stroked their beards, and designed something almost exactly as complicated, but not quite compatible with the original.

Finally, I’m going to blame us – common or garden developers. We have four problems: first, we don’t understand the complex model designed by mankind. Second, we don’t understand the complex model designed by the architects. Third, we don’t understand the applications we’re trying to build. Fourth, even when we get the first three bits right individually, we still screw up when we try to put them together.

For the rest of this talk, I’m going to give three examples of how things go wrong. First, let’s talk about numbers.

You would think we would know how numbers work by now. We’ve all been doing maths since primary school. You’d also think that computers knew how to handle numbers by now – that’s basically what they’re built on. How is it that we can search billions of web pages in milliseconds, but we can’t get simple arithmetic right? How many times are we going to see Stack Overflow questions along the lines of "Is double multiplication broken in .NET?"

I blame evolution.

We have evolved with 8 fingers and 2 thumbs – a total of 10 digits. This was clearly a mistake. It has led to great suffering for developers. Life would have been a lot simpler if we’d only had eight digits.

Admittedly this gives us three bits, which isn’t quite ideal – but having 16 digits (fourteen fingers and two thumbs) or 4 digits (two fingers and two thumbs) could be tricky. At least with eight digits, we’d be able to fit in with binary reasonably naturally. Now just so you don’t think I’m being completely impractical, there’s another solution – we could have just counted up to eight and ignored our thumbs. Indeed, we could even have used thumbs as parity bits. But no, mankind decided to count to ten, and that’s where all the problems started.

Now, Tony – here’s a little puzzle for you. I want you to take a look at this piece of Java code (turn Tony to face screen). (Tony whispers) What do you mean you don’t know Java? All right, here’s the C# code instead…

Is that better? (Tony nods enthusiastically) So, Tony, I want you to tell me the value of d after this line has executed. (Tony whispers)

Tony thinks it’s 0.3 Poor Tony. Why on earth would you think that? Oh dear. Sorry, no it’s not.

No, you were certainly close, but the exact value is:

0.299999 – Well, I’m not going to read it all out, but that’s the exact value. And it is an exact value – the compiler has approximated the 0.3 in the source code to the nearest number which can be exactly represented by a double. It’s not the computer’s fault that we have this bizarre expectation that a number in our source code will be accurately represented internally.

Let’s take a look at two more numbers… 5 and a half in both cases. Now it doesn’t look like these are really different – but they are. Indeed, if I were representing these two numbers in a program, I’d quite possibly use different types for them. The first value is discrete – there’s a single jump from £5.50 to £5.51, and those are exact amounts of money… whereas when we measure the mass of something, we always really mean “to two decimal places” or something similar. Nothing weighs exactly five and a half kilograms. They’re fundamentally different concepts, they just happen to have the same value. What do you do with them? Well, continuous numbers are often best represented as float/double, whereas discrete decimal numbers are usually best represented using a decimal-based type.

Now I’ve ignored an awful lot of things about numbers which can also trip us up – signed and unsigned, overflow, not-a-number values, infinities, normalised and denormal numbers, parsing and formatting, all kinds of stuff. But we should move on. Next stop, text.

Okay, so numbers aren’t as simple as we’d like them to be. Text ought to be easy though, right? I mean, my five year old son can read and write – how hard can it be? One bit of trivia – when I originally copied this out by hand, I missed out "ipsum." Note to self: if you’re going to copy out "lorem ipsum" the two words you really, really need to get at least those words right. Fail.

Of course, I’m sure pretty much everyone here knows that text is actually a pain in the neck. Again, I will blame humanity. Here we have two sets of people using completely different characters, speaking different languages, and quite possibly reading in different directions. Apologies if the characters on the right accidentally spell a rude word, by the way – I just picked a few random Kanji characters from the Unicode charts. (As pointed out in the comments, these aren’t actually Kanji characters anyway. They’re Katakana characters. Doh!) Cultural diversity has screwed over computing, basically.

However, let’s take the fact that we’ve got lots of characters as a given. Unicode sorts all that out, right? Let’s see. Time for a coding exercise – Tony, I’d like you to write some code to reverse a string. (Tony whispers) No, I’m not going to start up Visual Studio for you. (Tony whispers) You’ve magically written it on the next slide? Okay, let’s take a look.

Well, this looks quite promising. We’re taking a string, converting it into a character array, reversing that array, and then building a new string. I’m impressed, Tony – you’ve avoided pointless string concatenation and everything. (Tony is happy.) Unfortunately…

… it’s broken. I’m just going to give one example of how it’s broken – there are lots of others along the same lines. Let’s reverse one of my favourite musicals…

Here’s one way of representing Les Miserables as a Unicode string. Instead of using one code point for the “e acute”, I’ve used a combining character to represent the accent, and then an unaccented ASCII e. Display this in a GUI, and it looks fine… but when we apply Tony’s reversing code…

… the combining character ends up after the e, so we get an “s acute” instead. Sorry Tony. The Unicode designers with their fancy schemes have failed you.

EDIT: In fact, not only have the Unicode designers made things difficult, but so have implementers. You see, I couldn’t remember whether combining characters came before or after base characters, so I wrote a little Windows Forms app to check. That app displayed "Les Misu0301erables" as "Les Misérables". Then, based on the comments below, I checked with the standard – and the Unicode combining marks FAQ indicates pretty clearly that the base character comes before the combining character. Further failure points to both me and someone in Microsoft, unless I’m missing something. Thanks to McDowell for pointing this out in the comments. If I ever give this presentation again, I’ll be sure to point it out. WPF gets it right, by the way. Update: this can be fixed in Windows Forms by setting the UseCompatibleTextRendering property to false (or setting the default to false). Apparently the default is set to false when you create a new WinForms project in VS2008. Shame I tend to write "quick check" programs in a plain text editor…

Of course the basic point about reversal still holds, but with the correct starting string you’d end up with an acute over the r, not the s.

It’s not like the problems are solely in the realm of non-ASCII characters though. I present to you…

A line break. Or rather, one of the representations of a line break. As if the natural cultural diversity of humanity hasn’t caused enough problems, software decided to get involved and have line break diversity. Heck, we’re not even just limited to CR, LF and CRLF – Unicode has its own special line terminator character as well, just for kicks.

To prove this isn’t just a problem for toy examples, here’s something that really bit me, back about 9 or 10 years ago. Here’s some code which tries to do a case-insensitive comparison for the text "MAIL" in Java. Can anyone spot the problem?

It fails in Turkey. This is reasonably well known now – there’s a page about the “Turkey test” encouraging you to try your applications in a Turkish locale – but at the time it was a mystery to me. If you’re not familiar with this, the problem is that if you upper-case an “i” in Turkish, you end up with an “I” with a dot on it. This code went into production, and we had a customer in Turkey whose server was behaving oddly. As you can imagine, if you’re not aware of that potential problem, it can take a heck of a long time to find that kind of bug.

Here’s some code from a newsgroup post. It’s somewhat inefficient code to collapse multiple spaces down to a single one. Leaving aside the inefficiency, it looks like it should work. This was before we had String.Contains, so it’s using IndexOf to check whether we’ve got a double space. While we can find two spaces in a row, we’ll replace any occurrence of two spaces with a single space. We’re assigning the result of string.Replace back to the same variable, so that’s avoided one common problem… so how could this fail?

This string will cause that code to go into a tight loop, due to this evil character here. It’s a "zero-width non-joiner" – basically a hint that the two characters either side of it shouldn’t be squashed up too closely together. IndexOf ignores it, but Replace doesn’t. Ouch.

Now I’m not showing these examples to claim I’m some sort of Unicode expert – I’m really, really not. These are just corner cases I happen to have run into. Just like with numbers, I’ve left out a whole bunch of problems like bidi, encodings, translation, culture-sensitive parsing and the like.

Given the vast array of writing systems the world has come up with – and variations within those systems – any attempt to model text is going to be complicated. The problems come from the inherent complexity, some additional complexity introduced by things like surrogate pairs, and developers simply not having the time to become experts on text processing.

So, we fail at both numbers and text. How about time?

I’m biased when it comes to time-related problems. For the last year or so I’ve been working on the Google’s implementation of ActiveSync, mostly focusing on the calendar side of things. That means I’ve been exposed to more time-based code than most developers… but it’s still a reasonably common area, as you can tell from the number of related questions on Stack Overflow.

To make things slightly simpler, let’s ignore relativity. Let’s pretend that time is linear – after all, most systems are meant to be modelling the human concept of time, which definitely doesn’t include relativity.

Likewise, let’s ignore leap seconds. This isn’t always a good idea, and there are some wrinkles around library support. For example, Java explicitly says that java.util.Date and Calendar may or may not account for leap seconds depending on the host support. So, it’s good to know how predictable that makes our software… I’ve tried reading various explanations of leap seconds, and always ended up with a headache. For the purposes of this talk, I’m going to assert that they don’t exist.

Okay, so let’s start with something simple. Tony, what’s the time on this slide? (Tony whispers) Tony doesn’t want to answer. Anyone? (Audience responds.) Yes, about 5 past 3 on October 28th. So what’s the difference between now and the time on this slide? (Audience response.) No, it’s actually nearly twelve hours… this clock is showing 5 past 3 in the morning. Tony’s answer was actually the right one, in many ways… this slide has a hopeless amount of ambiguity. It’s not as bad as it might be, admittedly. Imagine if it said October 11th… Jeff and Joel would be nearly a month out of sync with the rest of us. And then even if we get the date and the time right, it’s still ambiguous… because of time zones.

Ah, time zones. My favourite source of WTFs. I could rant for hours about them – but I’ll try not to. I’d just like to point out a few of the idiosyncrasies I’ve encountered. Let’s start off with the time zones on this slide. Notice anything strange? (Audience or whisper from Tony) Yes, CST is there three times. Once for Central Standard Time in the US – which is UTC-6. It’s also Central Standard Time in Australia – where it’s UTC+9.30. It’s also Central Summer Time in Australia, where it’s UTC+10.30. I think it takes a special kind of incompetence to use the same acronym in the same place for different offsets.

Then let’s consider time zones changing. One of the problems I face is having to encode or decode a time zone representation from a single pattern – something like "It’s UTC-3 or -2, and daylight savings are applied from the third Sunday in March to the first Sunday in November". That’s all very well until the system changes. Some countries give plenty of warning of this… but on October 7th this year, Argentina announced that it wasn’t going to use daylight saving time any more… 11 days before its next transition. The reason? Their dams are 90% full. I only heard about this due to one of my unit tests failing. For various complicated reasons, a unit test which expected to recognise the time zone for Godthab actually thought it was Buenos Aires. So due to rainfall thousands of miles away, my unit test had moved Greenland into Argentina. Fail.

If you want more time zone incidents, talk to me afterwards. It’s a whole world of pain. I suggest we move away from time zones entirely. In fact, I suggest we adopt a much simpler system of time. I’m proud to present my proposal for coffee time. This is a system which determines the current time based on the answer to the question: "Is it time for coffee?" This is what the clock looks like:

This clock is correct all over the world, is very cheap to produce, and is guaranteed to be accurate forever. Batteries not required.

So where are we?

The real world has failed us. It has concentrated on local simplicity, leading to global complexity. It’s easy to organise a meeting if everyone is in the same time zone – but once you get different continents involved, invariably people get confused. It’s easy to get writing to work uniformly left to right or uniformly right to left – but if you’ve got a mixture, it becomes really hard to keep track of. The diversity which makes humanity such an interesting species is the curse of computing.

When computer systems have tried to model this complexity, they’ve failed horribly. Exhibit A: java.util.Calendar, with its incomprehensible set of precedence rules. Exhibit B: .NET’s date and time API, which until relatively recently didn’t let you represent any time zone other than UTC or the one local to the system.

Developers have, collectively, failed to understand both the models and the real world. We only need one exhibit this time: the questions on Stack Overflow. Developers asking questions around double, or Unicode, or dates and times aren’t stupid. They’ve just been concentrating on other topics. They’ve made an assumption that the core building blocks of their trade would be simple, and it turns out they’re not.

This has all been pretty negative, for which I apologise. I’m not going to claim to have a complete solution to all of this – but I do want to give a small ray of hope. All this complexity can be managed to some extent, if you do three things.

First, try not to take on more complexity than you need. If you can absolutely guarantee that you won’t need to translate your app, it’ll make your life a lot easier. If you don’t need to deal with different time zones, you can rejoice. Of course, if you write a lot of code under a set of assumptions which then changes, you’re in trouble… but quite often you can take the "You ain’t gonna need it" approach.

Next, learn just enough about the problem space so that you know more than your application’s requirements. You don’t need to know everything about Unicode – but you need to be aware of which corner cases might affect your application. You don’t need to know everything about how denormal number representation, but you may well need to know how rounding should be applied in your reports. If your knowledge is just a bit bigger than the code you need to write, you should be able to be reasonably comfortable.

Pick the right platforms and libraries. Yes, there are some crummy frameworks around. There are also some good ones. What’s the canonical answer to almost any question about java.util.Calendar? Use Joda Time instead. There are similar libraries like ICU – written by genuine experts in these thorny areas. The difference a good library can make is absolutely enormous.

None of this will make you a good developer. Tony’s still likely to mis-spell his "main" method through force of habit. You’re still going to get off by one errors. You’re still going to forget to close database connections. But if you can at least get a handle on some of the complexity of software engineering, it’s a start.

Thanks for listening.

C#, Parallelization, Stack Overflow, Wacky Ideas

Iterating atomically

33 Comments

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…

C#, Evil code, Stack Overflow

API design: choosing between non-ideal options

10 Comments

So, UnconstrainedMelody is coming on quite nicely. It now has quite a few useful options for flags enums, "normal enums" and delegates. However, there are two conflicting limitations which leave a couple of options. (Other related answers on Stack Overflow have suggested alternative approaches, basically.)

Currently, most of the enums code is in two classes: Flags and Enums. Both are non-generic: the methods within them are generic methods, so they have type parameters (and constraints). The main benefit of this is that generic type inference only applies to generic methods, and I definitely want that for extension methods and anywhere else it makes sense.

The drawback is that properties can’t be generic. That means my API is entirely expressed in terms of methods, which can be a pain. The option to work around this is to have a generic type which properties in. This adds confusion and guesswork – what call is where?

To recap, the options are:

// Option 1 (current): all methods in a nongeneric class:
// Some calls which are logically properties end up
// as methods…
IList<Foo> foos = Enums.GetValues<Foo>();
// Type infererence for extenion methods
// Note that we couldn’t have a Description property
// as we don’t have extension properties
string firstDescription = foos[0].GetDescription();
        
// Option 2: Use just a generic type:
// Now we can use a property…
IList<Foo> foos = Enums<Foo>.Values;
// But we can’t use type inference
string firstDescription = Enums<Foo>.GetDescription(foos[0]);
        
// Option 3: Use a mixture (Enums and Enums<T>):
IList<Foo> foos = Enums<Foo>.Values;
// All looks good…
string firstDescription = foos[0].GetDescription();
// … but the user has to know when to use which class

All of these are somewhat annoying. If we only put extension methods into the nongeneric class, then I guess users would never need to really think about that – they’d pretty much always be calling the methods via the extension method syntactic sugar anyway. It still feels like a pretty arbitrary split though.

Any thoughts? Which is more important – conceptual complexity, or the idiomatic client code you end up with once that complexity has been mastered? Is it reasonable to make design decisions like this around what is essentially a single piece of syntactic sugar (extension methods)?

(By the way, if anyone ever wanted justification for extension properties, I think this is a good example… Description feels like it really should be a property.)

C#, Stack Overflow, Wacky Ideas

Generic constraints for enums and delegates

56 Comments

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!