Sunday, September 20, 2009

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

by skeet via Jon Skeet: Coding Blog on 9/20/2009 8:48:00 PM

Well, this is embarrassing.

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

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

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

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

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

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

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