Coding Sanity

I recently was sent this article where Shawn Hargreaves discusses the performance implications of using the LINQ Count() operator versus the Count property of a collection, he uses Stack<T> as an example. The article has several issues with it that I tried to address in a somewhat dismissive comment that he chose not to publish. So, I’m going to expand on the ideas in that comment a little more, and hopefully do so in a more respectful tone. I want to make it clear I am not attacking him at all. I applaud anyone willing to spend time investigating fundamentals of .NET that we often take for granted. Nor am I attacking his overall conclusion that we should know what we’re doing when we use abstractions like LINQ. What I’m not happy with is how he got there. He feels that we should be careful because LINQ is much slower, which firstly I don’t agree with, and secondly I don’t think that’s necessarily a good reason to avoid it even if it is.

So, I’ll call out each of his major problems and discuss them in a bit more detail. Here he’s discussing the differences between the Count() and Stack<T>.Count:

Is it:

1. No difference: both return the number of elements on the specified stack

2. The first is a property of Stack<T>, while the second is a LINQ extension method

3. The first uses 3 IL instructions, while the second uses 34

4. The first runs in constant time, while the second is O(n)

5. The second version generates garbage, while the first does not

Answer: all of the above.

No difference: both return the number of elements on the specified stack

Well this is actually wrong. Stack<T>.Count does indeed do this, but the LINQ Count() returns the number of items in an abstract IEnumerable<T>. In this special case that is indeed the stack, but it need not be. We could count the number of items in the stack which have a text of “Sanity”, which Stack<T>.Count would not be able to help us with. Count() then gives us a higher level of abstraction than Stack<T>.Count. Now, abstractions are not always a good thing, you can easily get leaky abstractions which can cause problems.

But one nice thing about this abstraction is that it can operate on iterators, and thus often save processing time that is not required or not waste memory storing items that are not needed.

The first is a property of Stack<T>, while the second is a LINQ extension method

I don’t think this is a complaint to be honest, but since we’re looking at performance let me just point out that the overhead of calling a LINQ extension method is virtually nothing. They are baked in at compile time and are static calls. Static calls are marginally faster than virtual method calls because they don’t have to go through a vtable lookup. When compared with non-virtual calls (like the Count property on Stack<T>) they would be about the same speed or very slightly faster.

The first uses 3 IL instructions, while the second uses 34

So what? Firstly, do we know how those IL instructions wind up on the machine? It may be 3 vs 34 IL instructions and 5 vs 15 machine instructions for all we know, or 1 vs 250. Even if there was a 1 to 1 mapping between IL and machine instructions the performance difference would be minimal. An Intel Core i7 Extreme 965EE executes just over 76 billion instructions per second. So, the difference between these two would be about a 400 millionths of a second, about 4 shakes, or about how long fusion takes in an exploding hydrogen bomb.

So, unless you’re running this in a loop at least a million times, those 31 instructions aren’t going to make a huge difference. And yes, I do know that it’d be likely a lot more than 31 machine instructions, but even at an order of magnitude more, it still wouldn’t be worth worrying about unless you were in a very tight loop which sat in the hot path of your application.

The first runs in constant time, while the second is O(n)

Yes, this could indeed become a problem if your application was dealing with hundreds of thousands of items in your stack. In such a situation I would have to ask why you were keeping so many items in a stack though. Secondly, whilst Stack<T>.Count does indeed run in constant time, that is not a given for all implementations of ICollection.Count. For example if you look at the concurrent collections in the Task Parallel Library, their Count properties do not run in O(1), but in O(N).

However, this complaint is also completely misinformed. LINQ’s Count() operator actually checks to see if it’s dealing with an ICollection and if so, it calls the Count property. So, in fact LINQ’s Count() runs in O(1) time wherever possible. Oh, and in such a case, it does it in only 10 IL instructions too!

The second version generates garbage, while the first does not

I have no idea what the author is referring to when he talks about generating garbage here. As I have shown, Count() is very nearly as efficient as calling Stack<T>.Count and also offers a level of abstraction higher than collections. Since it operates on iterators it can be vastly more efficient than a collection which has sparse items of interest, by which I mean we loaded lots of items into it, and then filter for a small subset which we want. What Shawn is discussing here is the fact that it generates objects on the heap, a serious concern for game developers like him. Happily, if the item being Count()ed is an ICollection, it won't do any such thing, and for most of the rest of us it probably doesn't matter that much.

I don’t know about you, but an efficient abstraction offering those kinds of advantages is a great idea in my book, not garbage!

Conclusion

So, do I think you should always use Count() instead of the Count property? Of course not! If you know you are dealing with a Stack<T>, then you should use its Count property. Any collection is likely to implement Count in the manner most effective for it. The Count() can approach the efficiency of the Count property, but since it’s best-case is to invoke the Count property, it is marginally more efficient to just use that property directly.

However, often it’s worth our while to operate at a higher level of abstraction. In such a case use Count() and it’s friends without guilt, they’re actually pretty damn quick. In short, don’t prematurely optimize.

Google have announced that they're going to launch a new operating system called Google Chrome OS. When I heard this, I was quite interested actually. I was fascinated to see what direction they would go with their OS. Microkernel, Nanokernel, Monolithic? Since they claimed they'd be making viruses and malware a thing of the past, I was interested to see how they'd implement security. How were they going to manage the transition between their existing web applications and local computing resources? I really like the Chrome browser, and use it for preference, finding it's clean lines, responsiveness and reliability a welcome break from Windows *Crash* Explorer and SlowFox.

Given the fact that Microsoft had released the ground-breaking managed research OS Singularity 2 years ago, Google had a pretty high bar to jump, but they are nothing if not surprising. Singularity's used of managed code to avoid user/kernel mode switches yet remain secure was an innovation I had got hugely excited about when it came out, and I was expecting nothing less interesting from Mountain View. Well, I can say I was surprised. I was surprised to be so thoroughly disappointed with the reality. The Google Chrome OS is Linux with the Chrome browser included. Wow. Oh, wait, and a new window manager. I cannot stand the excitement. I am so enthused I might just ... *snore*

C'mon! What the hell is this? If you listen to the media, you'd think that some monstrously powerful OS had reared it's head and was thumping Microsoft six ways from Sunday. For goodness sakes, they're putting a little lipstick on an operating system that has been notably unable to make any significant inroads onto the desktop in 13 years of trying. An operating system that has already been thumped off netbooks because consumers didn't like it.

Ah well, at least they're finished right? Ooops, no. They've just announced the project, and they need "a lot of help from the open source community to accomplish this vision", so it doesn't sound like they've done an awful lot so far. So, they already have Chrome running on Linux, there are already stripped-down Linux distros, so what work exactly is required? It looks like they want to make a window manager. Another one. To add to the list of KDE, GNOME, CDE, XFCe, GTK, the Apple skin and all the many, many others. Soon, every single Linux user will be able to have their very own window manager, which will be a fitting end for an operating system characterised by more splits than a nuclear reaction and bigger egos than Paris Hilton's friends.

No, sorry, this is a blowout announcement signifying nothing. If they had the cajones to truly take Microsoft and Linux on, it'd be news; this is boredom wrapped in disinterest. Another operating system where I can't play games, can't use Office, and can't play music. Yay!

After the fun and games of trying to get MS to implement an XML comparison based vaguely on standards, I decided to roll my own. It is implemented as an Extension Method called DeepEquals on XNodes, and it takes a enum parameter ComparisonOptions:

• NamespacePrefix : This indicates that the namespace prefix of the element will be used to compare equality. In other words the following two fragments would compare as being different:

<test xmlns:x1='1'>
  <x1:first />
  <x1:second />
</test>
<test xmlns:x2='1'>
  <x2:first />
  <x2:second />
</test>

• AttributeOrdering: This option indicates that the order of attributes is important for comparing equality.

• CommentsAndNotations; This option indicates that comments will be used in determining whether two documents are equal.

• EmptyTagStyle: This option determines whether the style of an empty tag would be used. In other words whether the following two fragments would compare as being different:

<test />

<test></test>

• ElementOrdering: Like AttributeOrdering, this option indicates whether element ordering is important for equality.

Since these are Flags enumeration options, there are also a couple of combined enums:

• StandardsBased: Consists of ElementOrdering and EmptyTagStyle.

• MicrosoftImplementation: Consists of NamespacePrefix, AttributeOrdering, CommentsAndNotations, EmptyTagStyle and ElementOrdering.

• SemanticCompare: Contains none of the above options.

Performance-wise mine is slower than Microsofts, which is understandable since I piggyback on top of their infrastructure a lot. However, if you're interested in comparing two documents in much the same way as Microsoft does, I've provided a method called FastMicrosoftXNodeCompare. Basically, I used this to prove to myself that Microsoft's implementation effectively implements a text comparison.

FastMicrosoftXNodeCompare takes two streams or files and iterates them looking for differences. It ignores spaces and considers the two styles of quotes ' and " to be equivalent. It does not validate the XML, it does not check whether opening quotes and braces are closed or anything like that. It is also not Unicode compliant. As I say, I wrote it more to prove something to myself than anything else. It does compare documents twice as fast as XNodeEqualityComparer though.

You can download the project here.

Next time you wonder to yourself why a bug exists in Microsoft software, consider the possibility that Microsoft simply want it that way. Some time ago, I wanted to compare two XML documents. Growing despondent about the idea of writing such a system myself, I cast around for options, and encountered the XNodeEqualityComparer. I was thrilled, and made use of it throughout my code.

Some time later I started encountering problems. It seemed that the comparer was marking documents that were identical as being different. When we investigated, we found that this comparer was failing on two main issues. This first was the closing style of tags. It was picking up these two fragments as different:

<setting></setting>

<setting/> 

I must admit I was a bit surprised. Virtually no software that I am aware of sees these two as different, although they are very slightly different according to the W3C specification. This was annoying, but not a complete show stopper. The next error was a little more of a problem. It seems that the XNodeEqualityComparer also picks up attribute ordering as making the documents different.

Thus it would see these two fragments as different:

      <setting name="DefaultFileAcquisitionFolderPath" serializeAs="String">

Now, this one was a killer for me. Our XML was coming from various systems and they had slight differences in their attribute ordering. We could do nothing about these differences whatsoever. I logged the issue with Microsoft, wrote a workaround and forgot about it. After a short while it came back that they wouldn't fix it, they pretty much said that their implementation was correct. This startled me, since I was pretty sure that XML attribute ordering means absolutely nothing. I did some investigation and found this part of the W3C Specification section 3.1:

[Definition: The beginning of every non-empty XML element is marked by a start-tag.]

Start-tag

[40]	STag	::=	'<' Name (S Attribute)* S? '>'	[WFC: Unique Att Spec]
[41]	Attribute	::=	Name Eq AttValue	[VC: Attribute Value Type]
				[WFC: No External Entity References]
				[WFC: No < in Attribute Values]

The Name in the start- and end-tags gives the element's type. [Definition: The Name-AttValue pairs are referred to as the attribute specifications of the element], [Definition: with the Name in each pair referred to as the attribute name ] and [Definition: the content of the AttValue (the text between the ' or " delimiters) as the attribute value.] Note that the order of attribute specifications in a start-tag or empty-element tag is not significant.

Please re-read that last line: "Note that the order of attribute specifications in a start-tag or empty-element tag is not significant."

Accordingly, I recreated the bug report (since there is no way to request one to be reopened), and included the above information. In the arguments that followed I pointed out that despite all the code that XNodeEqualityComparer calls (specifically the abstract DeepEquals on XElement), it to all intents and purposes does the following: