Jon Skeet: Coding Blog : LINQ

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

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

Well, this is embarrassing.

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

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

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

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

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

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

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

What's in a name?

skeet — Fri, 27 Feb 2009 11:29:00 GMT

T.S. Eliot had the right idea when he wrote "The naming of cats":

The Naming of Cats is a difficult matter,
It isn't just one of your holiday games
...
When you notice a cat in profound meditation,
The reason, I tell you, is always the same:
His mind is engaged in a rapt contemplation
Of the thought, of the thought, of the thought of his name:
His ineffable effable
Effanineffable
Deep and inscrutable singular Name.

Okay, so developers may not contemplate their own names much, but I know I've certainly spent a significant amount of time recently trying to work out the right name for various types and methods. It always feels like it's just out of reach; tauntingly, tantalisingly close.

Recently I've been thinking a bit about what the goals might be in coming up with a good name. In particular, I seem to have been plagued with the naming problem more than usual in the last few weeks.

Operations on immutable types

A while ago I asked a question on Stack Overflow about naming a method which "adds" an item to an immutable collection. Of course, when I say "adds" I mean "returns a new collection whose contents is the old collection and the new item." There's a really wide range of answers (currently 38 of them) which mostly seem to fall into four categories:

Use Add because it's idiomatic for .NET collections. Developers should know that the type is immutable and act accordingly.
Use Cons because that's the term functional programming has used for this exact operation for decades.
Use a new method name (Plus being my favourite at the moment) which will be obvious to non-functional developers, but without being so familiar that it suggests mutability.
Use a constructor taking the old collection and the new item.

Part of the reasoning for Add being okay is that I originally posted the question purely about "an immutable collection" - e.g. a type which would have a name like ImmutableList<T>. I then revealed my true intention (which I should have done from the start) - to use this in MiniBench, where the "collection" would actually be a TestSuite. Everything in MiniBench is immutable (it's partly an exploration in functional programming, as it seems to fit very nicely) but I don't want to have to name every single type as Immutable[Whatever]. There's the argument that a developer should know at least a little bit about any API they're using, and the immutability aspect is one of the first things they should know. However, MiniBench is arguably an extreme case, because it's designed for sharing test code with people who've never seen it before.

I'm pretty sure I'm going to go with Plus in the end:

It's close enough to Add to be familiar
It's different enough to Add to suggest that it's not quite the same thing as adding to a normal collection
It sounds like it returns something - a statement which just calls Plus without using the result sounds like it's wrong (and indeed it would be)
It's meaningful to everyone
I have a precedent in the Joda Time API

Another option is to overload the + operator, but I'm not really sure I'm ready to do that just yet. It would certainly leave brief code, but is that really the most important thing?

Let's look at a situation with some of the same issues...

LINQ operators

Work on MoreLINQ has progressed faster than expected, mostly because the project now has four members, and they've been expending quite a bit of energy on it. (I must do a proper consistency review at some point - in particular it would be nice to have the docs refer to the same concepts in the same way each time. I digress...)

Most of the discussion in the project hasn't been about functionality - it's been about naming. In fact, LINQ is particularly odd in this respect. If I had to guess at how the time has been spent (at least for the operators I've implemented) I'd go for:

15% designing the behaviour
20% writing the tests
10% implementation
5% writing the documentation (just XML docs)
50% figuring out the best name

It really is that brutal - and for a lot of the operators we still haven't got the "right" name yet, in my view. There's generally too much we want to convey in a word or two. As an example, we've got an operator similar to the oft-implemented ForEach one, but which yields the input sequence back out again. Basically it takes an action, and for each element it calls the action and then yields the element. The use case is something like logging. We've gone through several names, such as Pipe, Tee, Via... and just this morning I asked a colleague who suggested Apply, just off the top of his head. It's better than anything we'd previously thought of, but does it convey both the "apply an action" and "still yield the original sequence" aspects?

The old advice of "each method should only do one thing" is all very well, and it clearly helps to make naming simpler, but with situations like this one there are just naturally more concepts which you want to get across in the name.

Let's stay on the LINQ topic, but stray a bit further from the well-trodden path...

The heart of Push LINQ: IDataProducer

I've probably bored most of you with Push LINQ by now, and I'm not actively developing it at the moment, but there's still one aspect which I'm deeply uncomfortable with: the core interface. IDataProducer represents a stream of data which can be observed. Basically clients subscribe to events, and their event handlers will be called when data is "produced" and when the stream ends.

I know IDataProducer is an awful name - but so far I haven't found anything better. IObservable? Ick. Overused and isn't descriptive. IPushEnumerable? Sounds like the client can iterate over the data, which they can't. The actual event names (DataProduced/EndOfData) are okay but there must be something better than IDataProducer. (Various options have been suggested in the past - none of them have been so obviously "right" as to stick in my head...)

This situation is slightly different to the previous ones, however, simply because it's such a pivotal type. You would think that the more important the type, the more important the name would be - but in some ways the reverse is true. You see, Push LINQ isn't a terribly "obvious" framework. I say that without shame - it's great at what it does, but it takes a few mental leaps before you really grok it. You're really going to have to read some documentation or examples before you write your own queries.

Given that constraint, it doesn't matter too much what the interface is called - it's going to be explained to you before you need it. It doesn't need to be discoverable - whereas when you're picking method names to pop up in Intellisense, you really want the developer to be able to guess its purpose even before they hover over it and check the documentation.

I haven't given up on IDataProducer (and I hope to be moving Push LINQ into MoreLINQ, by the way - working out a better name is one of the blockers) but it doesn't feel like quite as much of a problem.

Read-only or not read-only?

This final example came up at work, just yesterday - after I'd started writing this post. I wanted to refactor some code to emphasize which methods only use the read-only side of an interface. This was purely for the sake of readability - I wanted to make it easier to reason about which areas of the code modified an object and which didn't. It's a custom collection - the details don't matter, but for the sake of discussion let's call it House and pretend we're modelling the various things which might be in a house. (This is Java, hence House rather than IHouse.)

I'm explicitly not doing this for safety - I don't mind the fact that the reference could be cast to a mutable interface. The point is just to make it self-documenting that if a method only has a parameter in the non-mutating form, it's not going to change the contents of the house.

So, we have two interfaces, like this:

public interface NameMePlease
{
    Color getDoorColor();
    int getWindowCount();

    // This already returned a read-only collection
    Set<Furniture> getFurniture();
}

public interface House extends NameMePlease
{
    void setDoorColor(Color doorColor);
    void setWindowCount(int windows);
    void addFurniture(Furniture item);
}

Obviously the challenge is to find a name for NameMePlease. One option is to use something like ImmutableHouse or ReadOnlyHouse - but the inheritance hierarchy makes liars of both of those names. How can it be a ReadOnlyHouse if there are methods in an implementation which change it? The interface should say what you can do with the type, rather than specifying what you can't do - unless part of the contract of the interface is that the implementation will genunely prohibit changes.

Thinking of this "positive" aspect led me to ReadableHouse, which is what I've gone with for the moment. It states what you can do with it - read information. Again, this is a concept which Joda Time uses.

Another option is to make it just House, and change the mutable interface to MutableHouse or something similar. In this particular situation the refactoring involved would have been enormous. Simple to automate, but causing a huge check-in for relatively little benefit. Almost all uses are actually mutating ones. The consensus within the Google Java mailing list seems to be that this would have been the preferred option, all things being equal. One interesting data point was that although Joda Time uses ReadableInstant etc, the current proposals for the new date/time API which will be included in Java 7, designed by the author of Joda Time, don't use this convention. Presumably the author found it didn't work quite as well as he'd hoped, although I don't have know of any specific problems.

Conclusion

You'll probably be unsurprised to hear that I don't have a recipe for coming up with good names. However, in thinking about naming I've at least worked out a few points to think about:

Context is important: how discoverable does this need to be? Is accuracy more important than brevity? Do you have any example uses (e.g. through tests) which can help to see whether the code feels right or not?
Think of your audience. How familiar will they be with the rest of the code you're writing? Are they likely to have a background in other areas of computer science where you could steal terminology? Can you make your name consistent with other common frameworks they're likely to use? The reverse is true too: are you reusing a familiar name for a different concept, which could confuse readers?
Work out the information the name is trying to convey. For types, this includes working out how it participates in inheritance. Is it trying to advertise capabilities or restrictions?
Is it possible to make correct code look correct, and buggy code look wrong? This is rarely feasible, but it's one of the main attractions of "Plus" in the benchmark case. (I believe this is one of the main selling points of true Hungarian Notation for variable naming, by the way. I'm not generally a fan, but I like this aspect.)

I may expand this list over time...

I think it's fitting to close with a quote from Phil Karlton:

There are only two hard things in Computer Science: cache invalidation and naming things.

Almost all of us have to handle naming things. Let's hope most of us don't have to mess with cache invalidation as well.

Designing LINQ operators

skeet — Fri, 23 Jan 2009 23:40:39 GMT

I've started a small project (I'll post a link when I've actually got something worthwhile to show) with some extra LINQ operators in - things which I think are missing from LINQ to Objects, basically. (I hope to include many of the ideas from an earlier blog post.) That, and a few Stack Overflow questions where I've effectively written extra LINQ operators and compared them with other solutions, have made me think about the desirable properties of a LINQ operator - or at least the things you should think about when implementing one. My thoughts so far:

Lazy/eager execution

If you're returning a sequence (i.e. another IEnumerable<T> or similar) the execution should almost certainly be lazy, but the parameter checking should be eager. Unfortunately with the limitations of the (otherwise wonderful) C# iterator blocks, this usually means breaking the method into two, like this:

public static IEnumerable<T> Where(this IEnumerable<T> source,
                                   Func<T, bool> predicate)
{
    // Eagerly executed
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    return WhereImpl(source, predicate);
}

private static IEnumerable<T> WhereImpl(IEnumerable<T> source,
                                        Func<T, bool> predicate)
{
    // Lazily executed
    foreach (T element in source)
    {
        if (predicate(element))
        {
            yield return element;
        }
    }
}

Obviously aggregates and conversions (Max, ToList etc) are generally eager anyway, within normal LINQ to Objects. (Just about everything in Push LINQ is lazy. They say pets look like their owners...)

Streaming/buffering

One of my favourite features of LINQ to Objects (and one which doesn't get nearly the publicity of deferred execution) is that many of the operators stream the data. In other words, they only consume data when they absolutely have to, and they yield data as soon as they can. This means you can process vast amounts of data with very little memory usage, so long as you use the right operators. Of course, not every operator can stream (reversing requires buffering, for example) but where it's possible, it's really handy.

Unfortunately, the streaming/buffering nature of operators isn't well documented in MSDN - and sometimes it's completely wrong. As I've noted before, the docs for Enumerable.Intersect claim that it reads the whole of both sequences (first then second) before yielding any data. In fact it reads and buffers the whole of second, then streams first, yielding intersecting elements as it goes. I strongly encourage new LINQ operators to document their streaming/buffering behaviour (accurately!). This will limit future changes in the implementation admittedly (Intersect can be implemented in a manner where both inputs are streamed, for example) but in this case I think the extra guarantees provided by the documentation make up for that restriction.

Once-only evaluation

When I said that reversing requires buffering earlier on, I was sort of lying. Here's an implementation of Reverse which doesn't buffer any data anywhere:

public static IEnumerable<T> StreamingReverse<T>(this IEnumerable<T> source)
{
    // Error checking omitted for brevity
    int count = source.Count();
    for (int i = count-1; i >= 0; i--)
    {
        yield return source.ElementAt(i);
    }
}

If we assume we can read the sequence as often as we like, then we never need to buffer anything - just treat it as a random-access list. I hope I don't have to tell you that's a really, really bad idea. Leaving aside the blatant inefficiency even for sequences like lists which are cheap to iterate over, some sequences are inherently once-only (think about reading from a network stream) and some are inherently costly to iterate over (think about lines in a big log file - or the result of an ordering).

I suspect that developers using LINQ operators assume that they'll only read the input data once. That's a good assumption - wherever possible, we ought to make sure that it's correct, and if we absolutely can't help evaluating a sequence twice (and I can't remember any times when I've really wanted to do that) we should document it in large, friendly letters.

Mind your complexity

In some ways, this falls out of "try to stream, and try to only read once" - if you're not storing any data and you're only reading each item once, it's quite hard to come up with an operator which isn't just O(n) for a single sequence. It is worth thinking about though - particularly as most of the LINQ operators can work with large amounts of data. For example, to find the smallest element in a sequence you can either sort the whole sequence and take the first element of the result or you can keep track of a "current minimum" and iterate through the whole sequence. Clearly the latter saves a lot of complexity (and doesn't require buffering) - so don't just take the first idea that comes into your head. (Or at least, start with that and then think how you could improve it.)

Again, documenting the complexity of the operator is a good idea, and call particular attention to anything which is unintuitively expensive.

Conclusion

Okay, so there's nothing earth-shattering here. But the more I use LINQ to answer Stack Overflow questions, and the more I invent new operators in the spirit of the existing ones, the more powerful I think it is. It's amazing how powerful it can be, and how ridiculously simple the code (sometimes) looks afterwards. It's not like the operator implementation is usually hard, either - it's just a matter of thinking of the right concepts. I'm going to try to follow these principles when I implement my extra operator library, and I hope you'll bear them in mind too, should you ever feel that LINQ to Objects doesn't have quite the extension method you need...

You don't have to use query expressions to use LINQ

skeet — Wed, 07 Jan 2009 17:32:24 GMT

LINQ is clearly gaining a fair amount of traction, given the number of posts I see about it on Stack Overflow. However, I've noticed an interesting piece of coding style: a lot of developers are using query expressions for every bit of LINQ they write, however trivial.

Now, don't get the wrong idea - I love query expressions as a helpful piece of syntactic sugar. For instance, I'd always pick the query expression form over the "dot notation" form for something like this:

var query = from file in Directory.GetFiles(logDirectory, "*.log")
            from line in new LineReader(file)
            let entry = new LogEntry(line)
            where entry.Severity == Severity.Error
            select file + ": " + entry.Message;

(Yes, it's yet another log entry example - it's one of my favourite demos of LINQ, and particularly Push LINQ.) The equivalent code using just the extension methods would be pretty ugly, especially given the various range variables and transparent identifiers involved.

However, look at these two queries instead:

var query = from person in people
where person.Salary > 10000m
select person;

var dotNotation = people.Where(person => person.Salary > 10000m);

In this case, we're just making a single method call. Why bother with three lines of query expression? If the query becomes more complicated later, it can easily be converted into a query expression at that point. The two queries are exactly the same, even though the syntax is different.

My guess is that there's a "black magic" fear of LINQ - many developers know how to write query expressions, but aren't confident about what they're converted into (or even the basics of what the translation process is like in the first place). Most of the C# 3.0 and LINQ books that I've read do cover query expression translation to a greater or lesser extent, but it's rarely given much prominence.

I suspect the black magic element is reinforced by the inherent "will it work?" factor of LINQ to SQL - you get to write the query in your favourite language, but you may well not be confident in it working until you've tried it; there will always be plenty of little gotchas which can't be picked up at compile time. With LINQ to Objects, there's a lot more certainty (at least in my experience). However, the query expression translation shouldn't be part of what developers are wary of. It's clearly defined in the spec (not that I'm suggesting that all developers should learn it via the spec) and benefits from being relatively dumb and therefore easy to predict.

So next time you're writing a query expression, take a look at it afterwards - if it's simple, try writing it without the extra syntactic sugar. It may just be sweet enough on its own.

November 19th: London .NET User Group, Push LINQ!

skeet — Fri, 07 Nov 2008 21:51:23 GMT

On November 19th, I'll be speaking at the London .NET User Group about Push LINQ. I was quite pleasantly surprised by being able to explain it to some extent in Copenhagen, and this evening will be entirely about Push LINQ, so I'll be able to go into a lot more detail. Skills Matter will be hosting the event (near Farringdon station). It starts at 6.30pm, and registration is now open.

Should be fun. Please come and heckle.

What other Enumerable extension methods would you like to see?

skeet — Thu, 23 Oct 2008 20:50:39 GMT

A few questions on Stack Overflow have suggested to me that there might be some bits missing from LINQ to Objects. There's the idea of a "zip" operator, which pairs up two sequences, for instance. Or the ability to apply the set operators with projections, e.g. DistinctBy, IntersectBy etc (mirroring OrderBy). They're easy to implement, but it would be nice to get a list of what people would like to see.

So, what's missing?

DeveloperDeveloperDeveloper: Registration now open (hurry!)

skeet — Wed, 22 Oct 2008 09:53:34 GMT

The registration page for DeveloperDeveloperDeveloper Day 2008 (Reading, November 22nd) is now open. In the past this has been heavily oversubscribed, so if you want to come you'll need to register quickly.

I've got a speaking slot in the afternoon: implementing LINQ to Objects in 60 minutes. As always, I'm very much looking forward to it.

DotNetRocks interview

skeet — Tue, 07 Oct 2008 16:33:49 GMT

Last Monday evening I had a chat with the guys from DotNetRocks, and today the show has gone live.

I wouldn't claim to have said anything particularly earth-shattering, and regular readers will probably be familiar with many of the themes anyway, but I thoroughly enjoyed it and hope you will too. Amongst other things, we talked about:

Protocol buffers
Implicit typing and anonymous types
Why it doesn't bother me that Office hasn't been ported to .NET
C# 4
My wishlist for C#
Threading and Parallel Extensions
Working for Google
How to learn LINQ
C# in Depth

Feedback welcome. And yes, I know I sound somewhat like a stereotypical upper-class idiot at times. Unfortunately there's not a lot I can do about that. Only the "idiot" part is accurate :)

Book review: Pro LINQ - Language Integrated Query in C# 2008, by Joe Rattz

skeet — Mon, 22 Sep 2008 00:57:00 GMT

I'm trying something slightly different this time. Joe (the author) has reacted to specific points of my review, and I think it makes sense to show those reactions. I'd originally hoped to present them so that you could toggle them on or off, but this blog server apparently wants to strip out scripts etc, so the comments are now permanently visible.

Resources

Buy from Amazon or Barnes and Noble
Author's web site
Apress page (errata submissions etc)

Introduction and disclaimer

As usual, I first need to give the disclaimer that as the author of a somewhat-competing book, I may be biased and certainly will have different criteria to most people. In this case the competition aspect is less direct than normal - this book is "LINQ with the C# 3 bits as necessary" whereas my book is "C# 2 and 3 with LINQ API where necessary". However, it's still perfectly possible that a potential reader may try to choose between the two books and buy just one. If you're in that camp, I suggest you buy my book try to find an impartial opinion instead of trusting my review.

A second disclaimer is needed this time: I didn't buy my copy of this book; it was sent to me by Apress at the request of Joe Rattz, specifically for review (and because Joe's a nice guy). I hope readers of my other reviews will be confident that this won't change the honest nature of the review; where there are mistakes or possible improvements, I'm happy to point them out.

Content, audience and overall approach

This book is simply aimed at existing C# developers who want to learn LINQ. There's an assumption that you're already reasonably confident in C# 2 - knowledge of generics is taken as read, for example - but there is brief coverage of using iterator blocks to return sequences. No prior experience of LINQ is required, but the LINQ to XML and LINQ to SQL sections assume (not unreasonably) that you already know XML and SQL.

The book is divided into five parts:

Introduction and C# 3.0 features (50 pages)
LINQ to Objects (130 pages)
LINQ to XML (152 pages)
LINQ to DataSet (42 pages)
LINQ to SQL (204 pages)

The approach to the subject matter changes somewhat through the book. Sometimes it's a concept-by-concept "tutorial style" approach, but for most of the book (particularly the LINQ to Objects and LINQ to XML parts) it reads more like an API reference. Joe recommends that readers tackle the book from cover to cover, but that falls down a bit in the more reference-oriented sections.

[Joe] Early in the development of my book, a friend asked me if it was going to be a tutorial-style book or a reference book. I initially found the question odd because I never really viewed books as being exclusively one or the other. Perhaps I am different than most readers, but when I buy a programming book, I usually read a bit, start coding, and then refer to the book as a reference when needed. This is how I envision my book being used by readers and the type of book I would like for it to be. I see it as both a tutorial and a reference. I want it to be a book that gets used repeatedly, not read once and shelved. Some books work better for this than others. I rarely read a programming book cover to cover because I just don't have time for that. I think ultimately, most authors write the book they would want to read, and that is what I did. I hope that if someone buys my book, in two years it will be tattered and worn from use as a reference, as well as read cover to cover.

I would disagree that the majority of the book reads like an API reference. Certainly, chapters 4 and 5 (deferred and nondeferred operators) work better as a reference because there isn't a lot of connective context between the approximately 50 different standard query operators. At best it would be an eclectic tutorial with little continuity. So I decided to make those two chapters (the ones covering the standard query operators) function more like a reference. I knew that I (and hopefully my readers) would refer to it time and time again for information about the operators, and based on most of the reviews I have seen, this appears to have been a good choice. I know I refer to it myself quite frequently. I would not consider the chapters on LINQ to XML to be reference oriented although I could see why someone might feel they are. My discussion of LINQ to XML is tutorial based as I approach the different tasks a developer would need to accomplish when working with XML, such as how to construct XML, how to output XML, how to input XML, how to traverse XML, etc. However, within a task, like traversing XML, I do list the API calls and discuss them, so this is probably why it feels reference-like to some readers, and will function pretty well as a reference.

For example, take the ordering operators in LINQ - OrderBy, ThenBy, OrderByDescending and ThenByDescending. (Interestingly, one of the Amazon reviews picks up on the same example. I already had it in mind before reading that review.) These four LINQ to Objects operators take 15 pages to cover because every method overload is used, but a lot of it is effectively repeated between different examples. I think more depth could have been achieved in a shorter space by talking about the group as a whole - we only really need to see what happens when a custom comparison is used once, not four times - whereas every example of ThenBy/ThenByDescending used an identity projection, instead of showing how you can make the secondary ordering use some completely different projection (without necessarily using a custom comparer). Likewise I don't remember seeing anything about tertiary orderings, or what the descending orderings tend to do with nulls, or emphasis on the fact that descending orderings aren't just reversed ascending orderings (due to the stability of the sort - the stability was mentioned, but not this important corollary). Having an example for each overload is useful for a reference work, but not for a "read through from start to finish" book.

The set operators (Distinct, Except, Intersect, Union and SequenceEqual) as applied to DataSets suffer a similar problem - the five descriptions of why custom comparers are needed are all basically the same, and could be dealt with once. In particular, one paragraph is repeated verbatim for each operator. Again, that's fine for a reference - but cutting and pasting like this makes for an irritating read when you see the exact same text several times in one reading session.

[Joe] A few readers have complained about some of the redundancies that you have pointed out, but I think most of the readers have appreciated my attempt to provide material for each operator/method. I think one of the words you will see most often in the Amazon reviews is "thorough".

Now, it's important that I don't give the wrong impression here. This is certainly not just a reference book, and there's enough introduction to topics to help readers along. If I'd been coming to C# 3 and LINQ without any other information, I think I'd have followed things, for the most part. (I'm not a fan of the way Joe presented the query expression translations, but I'm enormously pleased that he did it at all. I think I might have got lost at that point, which was unfortunately early in the book. It might have been better as just an appendix.) Anyone reading the book thoroughly should come away with a competent knowledge of LINQ and the ability to use it profitably. They may well be less comfortable with the new features of C# 3, as they're only covered briefly - but that's entirely appropriate given the title and target of the book. (To be blunt and selfish, I'm entirely in favour of books which leave room for more depth at a language level - that should be a good thing for sales of my own book!)

[Joe] Jon, if you only knew how difficult it was getting those query expression translations into the book. ;-) You can read in my acknowledgments where I specifically thank Katie Stence and her team for them. They were a very painful effort and in hindsight, I probably would not include them if I were to start the book from scratch. I agree with you that the translations are complex, as the book states. Perhaps the most important part of that section is when I state "Allow me to provide a word of warning. The soon to be described translation steps are quite complicated. Do not allow this to discourage you. You no more need to fully understand the translation steps to write LINQ queries than you need to know how the compiler translates the foreach statement to use it. They are here to provide additional translation information should you need it, which should be rarely, or never."

However, I would personally have preferred to see a more conceptual approach which spent more time focused on getting the ideas through at a deep level and less time making sure that every overload was covered. After all, MSDN does a reasonable job as a reference - and the book's web site could have contained an example for every overload if necessary without everything making it into print. The kind of thing I'd have liked to see explored more fully is the buffering vs streaming nature of data flow in LINQ. Some operators - Select and Where, for example - stream all their data through. They never keep look at more than one item of data at a time. Others (Reverse and OrderBy, for example) have to buffer up all the data in the sequence before yielding any of it. Still others use two sequences, and may buffer one sequence and stream the other - Join and Intersect work that way at the moment, although as we saw in my last blog post Intersect can be implemented in a way which streams both sequences (but still needs to keep a buffer of data it's already seen). When you're working with an infinite (or perhaps just very large - much bigger than memory) sequence you really need to be aware of this distinction, but it isn't covered in Pro LINQ as far as I remember. In the interests of balance, I should point out that the difference between immediate and deferred execution is explained, repeatedly and clearly - including the semi-immediate execution which can occur sometimes in LINQ to SQL.

[Joe] I wanted my book to cover each overload because I can't read MSDN in the bathroom, or when at the beach without an internet connection, or when curled up in a chair by the fireplace. I also wanted to provide examples for every method and overload because I find it frustrating when a book shows the simplest one and I have to figure out the one I need. Granted, depth could be added too, but you have to draw the line somewhere. Apress (at the time, not sure if this is still the plan) has the concept of three levels of book; Foundations, Pro, and Expert. I considered some information beyond the scope of the Pro level that my book is aimed at. The buffering versus streaming issue is an interesting one and would make an excellent additional column in Table 3-1, if I can get it to fit.

I'm unable to really judge the depth to which LINQ to SQL was explored, given that a lot of it was beyond my own initial knowledge (which is a good thing!). I'm slightly perturbed by the idea that it can be comprehensively tackled in a couple of hundred pages, whereas books on other ORMs are often much bigger and tackle topics such as session lifetimes and caching in much more depth. I suspect this is more due to the technologies than the writing here - LINQ to SQL is a relatively feature-poor ORM compared with, say, Hibernate - but a bit more attention to "here are options to consider when writing an application" would have been welcome.

Accuracy and code style

Most of Pro LINQ is pretty accurate. Joe is occasionally a bit off in terms of terminology, but that probably bothers most readers less than it bothers me. There are a few things which changed between the beta version of VS2008 against which the book was clearly developed and the release version, which affect the new features of C# 3. For instance, automatically implemented properties aren't mentioned at all (and would have been much nicer to see in examples than public fields) and collection initializers are described with the old restrictions (the collection type has to implement ICollection<T>) rather than the new ones (the collection type has to implement IEnumerable and have appropriate Add methods). Other errors include trusting the documentation too much (witness the behaviour of Intersect) and an inconsistency (stating correctly that OrderBy is stable on one page, then incorrectly warning that it's unstable on another). In my normal fashion, I'll give Joe an exhaustive list of everything I've found and leave it up to him to see which he'd like to fix for the next printing, but overall Pro LINQ does pretty well. I suspect this may be partly due to covering a great deal of area but with relatively little depth and some repetition - Accelerated C# had a higher error rate, but was delving into more treacherous waters, for example.

[Joe] Since my book is not meant to be a C# 3.0 book, but rather a LINQ book, I only cover the new C# 3.0 features which were added to support LINQ. Since automatic properties were not one of those features, I do not cover them. You may notice that my chapter dedicated to the new C# 3.0 features is titled C# 3.0 Language Enhancements For LINQ. Just for your reader's knowledge, the ordering is now specified to be stable. Initially it was unstable, and was later changed to be stable but I was told it would be specified to be unstable, but apparently at some point, the specification was changed to be stable. My book was updated but apparently I missed a spot.

Most of the advice given throughout the book is reasonable, although I take issue with one significant area. Joe recommends using the OfType operator instead of the Cast operator, because when a nongeneric collection contains the "wrong type of object," OfType will silently skip it whereas Cast will throw an exception. I recommend using Cast for exactly the same reason! If I've got an object of an unexpected type in my collection, I want to know about it as soon as possible. Throwing an exception tells me what's going on immediately, instead of hiding the problem. It's usually the better behaviour, unless you explicitly have reason to believe that you will legitimately have objects of different types in the collection and you really want to only find objects of the specified type.

[Joe] Yes, I should have known better than to provide that advice (prefer OfType to Cast) without more explanation, more disclaimers, and more caveats. My preference would be to use Cast in development and debug built code for the exact reasons you mention, but to use OfType in production code. I would prefer my applications to handle unexpected data more gracefully in production than I would in development.

As well as "headline" pieces of advice which are advertised right up to the table of contents, there are many hints and tips along the way, most of which really do add value. I believe they'd actually add more value if they weren't sometimes buried within reference-like material - but as we've already seen, my personal preference is for a more narrative style of book anyway.

The code examples are in "snippet" form (i.e. without using directives, Main method declarations etc) but are complete aside from that. At the start of each chapter there's a detailed list of which namespaces and references are involved, so there's no guesswork required. In fact, I'd expect most of them to work in Snippy given an appropriate environment. Some examples are a bit longwinded - we only really need to see the 7 lines showing the list of presidents once or twice, not over and over again - but that's a minor issue. Another niggle is Joe's choices when it comes to a few bits of coding convention. There are various areas where we differ, but a few repeatedly bothered me: overuse (to my mind) of parentheses, "old-style" delegate creation (i.e. something.Click += new EventHandler(Foo) instead of just something.Click += Foo) and the explicit specification of type parameters on LINQ operators which don't need them. Here's one example which demonstrates the first and the last of these issues - as well as introducing an unnecessary cast:

// This is the code in the book (in listing 7-30)
XElement outOfPrintParticipant = xDocument
.Element("BookParticipants")
.Elements("BookParticipant")
.Where(e => ((string)((XElement)e).Element("FirstName")) == "Joe"
&& ((string)((XElement)e).Element("LastName")) == "Rattz")
.Single<XElement>();

// This is what I'd have preferred
XElement outOfPrintParticipant = xDocument
.Element("BookParticipants")
.Elements("BookParticipant")
.Where(e => (string)e.Element("FirstName") == "Joe"
&& (string)e.Element("LastName") == "Rattz")
.Single();

Check out the penultimate line of the original - a whopping 5 opening brackets and 6 closing ones. This issue looks even worse to me when it's used to make return and throw look like method calls:

// From GetStringFromDb (P388)
throw (new Exception(
String.Format("Unexpected exception executing query [{0}].", sqlQuery)));

// (Insert more code here) - same listing

return (result);

These just look odd and wrong. Of course they're perfectly valid, but not pleasant to read in my view. On a more minor matter, Joe tends to close SQL connections, commands etc with an explicit try/finally block instead of the more idiomatic (to my mind) using statement, but again that probably bothers me more than others.

The source code is all available on the web site, and it's easy to find each listing. (The zip file is about 10 times larger than it needs to be because it contains all the bin/obj directories with all the compiled code in rather than just the source, but that's a tiny niggle.)

Writing style

Joe's writing style is very informal - or at least, while most of the text is in "normal" formal prose, there are plenty of informal pieces of writing there too. As readers of my book will know, I'm much the same - I try to keep things from getting too dry, despite that being the natural state for technical teaching. I have no idea how well I succeed for most readers, but Joe certainly manages. He occasionally takes it a little too far for my personal taste, usually around listing outputs. They're often introduced as if Joe didn't really know what the output would be, with a kind of "wow, it worked, who'd have thought?" comment afterwards. I suspect I've got some of this in my book too, but Joe lays it on a little too thickly for my liking. I don't know whether it would be fairer to present a "medium-level" example of this rather than one which really grated, but this is the one (from page 257) made such an impression that I remembered it over 300 pages later:

This should output the language attribute. Let's see:
language="English"
Groovy! I have never actually written the word groovy before. I had to let the spelling checker spell it for me.

Now, I really want to stress that that's a "worst case" rather than the average case, and indeed many listings don't have anything "cutesy" about them. I just wanted to give an example of the kind of thing that didn't work for me.

[Joe] Let me see if I get this straight. So you are saying you got to learn something about LINQ and how to spell groovy, and it stuck for over 300 pages and you are upset? Man, you know how to spell groovy now, what's the problem? 8-D Would it annoy you less if I told you that is a reference to Austin Powers? My book is riddled with references to movies and TV shows, and that one is for Austin Powers. Maybe you didn't catch that, or maybe you don't like Austin Powers, or maybe you just still don't like it. One reader was irritated when I said "Dude, Sweet" because he didn't recognize that as a reference to Dude, Where's My Car. I have references to Office Space, Arrested Development, Bottle Rocket, Seinfeld, The Matrix, Wargames, Tron, etc. In fact, on page 455, I actually use the word "moo" instead of "moot" in reference to Friends. My copy editor actually corrected that for me, but once I explained it, she let me have it back. So if you see something goofy, like "groovy" just know it is a reference to something and begin your investigation in your spare time. And if you see an error, it is intentional to make sure you are paying attention. ;-) As you have already pointed out, technical writing can be dry. I made an effort to inject humor into the book in the form of references to pop culture, most specifically movies and television. Sometimes the reference is in a comment like "groovy", and sometimes it's in the sample data like a character's name. Like any comedian, every joke or reference can't be a hit with everyone. I will say though that I have heard more from those that recognized the references and appreciated them (which helps carry a reader through the lesser interesting parts) than I have from those that found them annoying.

What really did work was including hints and tips which explicitly said where Joe had received unexpected results with slightly different code. If anything is unexpected to the author, it may well be unexpected to readers too, so I really appreciated reading that sort of thing. (It would be wearing if Joe were stupid and expected all kinds of silly results, but that's not the case at all.)

Conclusion

Pro LINQ is a good book. It has enough niggles to keep me from using superlatives about it, but it's good nonetheless. It's Joe's first book (just like C# in Depth is the first one I can truly call "mine") and I hope he writes more. Having read it from cover to cover, I think it'll be more useful as a reference for individual methods (when MSDN doesn't quite cut it) than to reread whole chapters, but that's not a problem. My slight complaints above certainly don't stop it from being a book I'm pleased to own.

[Joe] I'll take it as a compliment that you think my book would be useful for those times that MSDN isn't good enough!

This is the first LINQ book I've reviewed - I already have LINQ in Action, which is also on the list to review at some point. (I've read large chunks of it in soft copy, but I haven't been through the finished hard copy yet.) It will be interesting to see how the two compare. Next up will probably be "Programming C# 3.0" by Jesse Liberty, however.

Logging enumeration flow

skeet — Tue, 09 Sep 2008 07:18:45 GMT

I'm currently reading Pro LINQ: Language Integrated Query in C# 2008 by Joe Rattz and yesterday I came across a claim about Enumerable.Intersect which didn't quite ring true. I consulted MSDN and the documentation is exactly the same as the book. Here's what it says:

When the object returned by this method is enumerated, Intersect enumerates first, collecting all distinct elements of that sequence. It then enumerates second, marking those elements that occur in both sequences. Finally, the marked elements are yielded in the order in which they were collected.

(first is the first parameter, the one which the method appears to be called on when using it as an extension method. second is the second parameter - the other sequence involved.)

This seems to be needlessly restrictive. In particular, it doesn't allow you to work with an infinite sequence on either side. It also means loading the whole of both sequences into memory at the same time. Given the way that Join works, I was surprised to see this. So I thought I'd test it. This raised the question of how you trace the flow of a sequence - how do you know when data is being pulled from it? The obvious answer is to create a new sequence which fetches from the old one, logging as it goes. Fortunately this is really easy to implement:

using System;
using System.Collections.Generic;

public static class Extensions
{
    public static IEnumerable<T> WithLogging<T>(this IEnumerable<T> source,
                                                string name)
    {
        foreach (T element in source)
        {
            Console.WriteLine("{0}: {1}", name, element);
            yield return element;
        }
    }
}

We keep a name for the sequence so we can easily trace which sequence is being pulled from at what point. Now let's apply this logging to a call to Intersect:

using System;
using System.Linq;
using System.Collections.Generic;

// Compile alongside the Extensions class

class Test
{
    static void Main()
    {
        var first = Enumerable.Range(1, 5).WithLogging("first");
        var second = Enumerable.Range(3, 5).WithLogging("second");
        foreach (int i in first.Intersect(second))
        {
            Console.WriteLine("Intersect: {0}", i);
        }
    }
}

As you can see, we're intersecting the numbers 1-5 with the numbers 3-7 - the intersection should clearly be 3-5. We'll see a line of output each time data is pulled from either first or second, and also when the result of Intersect yields a value. Given the documentation and the book, one would expect to see this output:

// Theoretical output. It doesn't really do this
first: 1
first: 2
first: 3
first: 4
first: 5
second: 3
second: 4
second: 5
second: 6
second: 7
Intersect: 3
Intersect: 4
Intersect: 5

Fortunately, it actually works exactly how I'd expect: the second sequence is evaluated fully, then the first is evaluated in a streaming fashion, with results being yielded as they're found. (This means that, if you're sufficiently careful with the result, e.g. by calling Take with a suitably small value, the first sequence can be infinite.) Here's the actual output demonstrating that:

// Actual output.
second: 3
second: 4
second: 5
second: 6
second: 7
first: 1
first: 2
first: 3
Intersect: 3
first: 4
Intersect: 4
first: 5
Intersect: 5

Initial Conclusion

There are two interesting points here, to my mind. The first is demonstrating that the documentation for Intersect is wrong - the real code is more sensible than the docs. That's not as important as seeing how easy it is to log the flow of sequence data - as simple as adding a single extension method and calling it. (You could do it with a Select projection which writes the data and then yields the value of course, but I think this is neater.)

I'm hoping to finish reading Joe's book this week, and write the review over the weekend, by the way.

Update (Sept. 11th 2008)

Frederik Siekmann replied to this post with a thrilling alternative implementation to stream the intersection, which takes alternating elements from the two sequences involved. It's a bit more memory hungry (with three sets of elements to remember instead of just one) but it means that we can deal with two infinite streams, if we're careful. Here's a complete example:

using System;
using System.Collections.Generic;
using System.Linq;

public static class Extensions
{
    public static IEnumerable<T> AlternateIntersect<T>(this IEnumerable<T> first, IEnumerable<T> second)
    {
        var intersection = new HashSet<T>();
        var firstSet = new HashSet<T>();
        var secondSet = new HashSet<T>();
        using (IEnumerator<T> firstEnumerator = first.GetEnumerator())
        {
            using (IEnumerator<T> secondEnumerator = second.GetEnumerator())
            {
                bool firstHasValues = firstEnumerator.MoveNext();
                bool secondHasValues = secondEnumerator.MoveNext();
                while (firstHasValues && secondHasValues)
                {
                    T currentFirst = firstEnumerator.Current;
                    T currentSecond = secondEnumerator.Current;

                    if (!intersection.Contains(currentFirst) &&
                        secondSet.Contains(currentFirst))
                    {
                        intersection.Add(currentFirst);
                        yield return currentFirst;
                    }
                    firstSet.Add(currentFirst);
                    if (!intersection.Contains(currentSecond) &&
                        firstSet.Contains(currentSecond))
                    {
                        intersection.Add(currentSecond);
                        yield return currentSecond;
                    }
                    secondSet.Add(currentSecond);
                    firstHasValues = firstEnumerator.MoveNext();
                    secondHasValues = secondEnumerator.MoveNext();
                }
                if (firstHasValues)
                {
                    do
                    {
                        T currentFirst = firstEnumerator.Current;
                        if (!intersection.Contains(currentFirst) &&
                            secondSet.Contains(currentFirst))
                        {
                            intersection.Add(currentFirst);
                            yield return currentFirst;
                        }
                    } while (firstEnumerator.MoveNext());
                }
                if (secondHasValues)
                {
                    do
                    {
                        T currentSecond = secondEnumerator.Current;
                        if (!intersection.Contains(currentSecond) &&
                            firstSet.Contains(currentSecond))
                        {
                            intersection.Add(currentSecond);
                            yield return currentSecond;
                        }
                    } while (secondEnumerator.MoveNext());
                }
            }
        }
    }

    public static IEnumerable<T> WithLogging<T>(this IEnumerable<T> source, string name)
    {
        foreach (T element in source)
        {
            Console.WriteLine(string.Format("{0}: {1}", name, element));
            yield return element;
        }
    }
}

class Test
{
    static void Main()
    {
        var positiveIntegers = Enumerable.Range(0, int.MaxValue);

        var multiplesOfTwo = positiveIntegers.Where(x => (x%2) == 0)
                                             .WithLogging("Twos");
        var multiplesOfThree = positiveIntegers.Where(x => (x%3) == 0)
                                               .WithLogging("Threes");

        foreach (int x in multiplesOfTwo.AlternateIntersect(multiplesOfThree).Take(10))
        {
            Console.WriteLine ("AlternateIntersect: {0}", x);
        }
    }
}

Most of the code is the alternating intersection - the test at the end just shows intersection of the sequence 2, 4, 6, 8... with 3, 6, 9, 12... The output shows elements being taken from both sequences, and yielded when a match is found. It's important that we limit the output in some way - in the above code we call Take(10) but anything which prevents the loop from just executing until we run out of memory is fine.

Twos: 0
Threes: 0
AlternateIntersect: 0
Twos: 2
Threes: 3
Twos: 4
Threes: 6
Twos: 6
Threes: 9
AlternateIntersect: 6
Twos: 8
Threes: 12
Twos: 10
Threes: 15
Twos: 12
Threes: 18
AlternateIntersect: 12
Twos: 14
Threes: 21
Twos: 16
Threes: 24
Twos: 18
Threes: 27
AlternateIntersect: 18
(etc)

That's really neat. Quite how often it'll be useful is a different matter, but I find this kind of thing fascinating to consider. Thanks Frederik!

Mandelbrot revisited - benchmark edition

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

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

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

Benchmark implementation details

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

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

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

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

SingleThreadImperativeSimple

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

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

where ComplexMandelbrotIndex is in the base class:

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

    double y0 = y;
    double x0 = x;

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

SingleThreadImperativeInline

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

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

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

            double y0 = y;
            double x0 = x;

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

MultiThreadUpFrontSplitImperative

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

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

    int rowsPerCore = Height / cores;

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

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

MultiThreadRowFetching

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

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

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

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

SingleThreadLinqSimple

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

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

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

ParallelLinqRowByRowWithCopy

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

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

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

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

ParallelLinqRowByRowInPlace

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

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

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

    query.Max();
}

ParallelLinqWithSequenceOfPoints

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

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

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

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

SingleThreadLinqWithGenerator

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

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

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

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

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

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

ParallelLinqWithGenerator

From the previous implementation, parallelisation is simple.

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

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

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

SingleThreadImperativeWithComplex

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

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

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

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

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

UnorderedParallelLinqSimple

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

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

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

UnorderedParallelLinqWithStruct

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

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

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

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

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

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

UnorderedParallelLinqInPlace

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

public override void Generate()
{

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

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

UnorderedParallelLinqInPlaceWithDelegate

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

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

    return query;
}

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

    Generate(transformation).Max();
}

UnorderedParallelLinqInPlaceWithGenerator

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

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

    // Force execution
    query.Max();
}

ParallelForLoop

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

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

Results

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

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

Conclusions

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

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

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

Odd query expressions

skeet — Fri, 29 Feb 2008 12:36:00 GMT

Yesterday, I was proof reading chapter 11 of the book (and chapter 12, and chapter 13 - it was a long night). Reading my own text about how query expressions work led me to wonder just how far I could push the compiler in terms of understanding completely bizarre query expressions.

Background

Query expressions in C# 3 work by translating them into "normal" C# first, then applying normal compilation. So, for instance, a query expression of:

from x in words
where x.Length > 5
select x.ToUpper()

... is translated into this:

words.Where(x => x.Length > 5)
.Select(x => x.ToUpper())

Now, usually the source expression (words in this case) is something like a variable, or the result of a method or property call. However, the spec doesn't say it has to be... let's see what else we could do. We'll keep the query expression as simple as possible - just from x in source select x.

Types

What if the source expression is a type? The query expression would then compile to TypeName.Select(x => x) which of course works if there's a static Select method taking an appropriate delegate or expression tree. And indeed it works:

using System;

public class SourceType
{
    public static int Select(Func<string,string> ignored)
    {
        Console.WriteLine("Select called!");
        return 10;
    }
}

class Test
{
    static void Main()
    {
        int query = from x in SourceType
                    select x;
    }
}

That compiles and runs, printing out Select called!. query will be 10 after the method has been called.

So, we can call a static method on a type. Anything else? Well, let's go back to the normal idea of the expression being a value, but this time we'll change what Select(x => x) actually means. There's no reason it has to be a method call. It looks like a method call, but then so do delegate invocations...

Delegates via properties

Let's create a "LINQ proxy" which has a property of a suitable delegate type. Again, we'll only provide Select but it would be possible to do other types - for instance the Where property could be typed to return another proxy.

using System;
using System.Linq.Expressions;

public class LinqProxy
{
    public Func<Expression<Func<string,string>>,int> Select { get; set; }
}

class Test
{
    static void Main()
    {
        LinqProxy proxy = new LinqProxy();

        proxy.Select = exp =>
        {
            Console.WriteLine ("Select({0})", exp);
            return 15;
        };

        int query = from x in proxy
                    select x;
    }
}

Again, it all compiles and runs fine, with an output of "Select(x => x)". If you wanted, you could combine the two above approaches - the SourceType could have a static delegate property instead of a method. Also this would still work if we used a public field instead of a property.

What else is available?

Looking through the list of potential expressions, there are plenty more we can try to abuse: namespaces, method groups, anonymous functions, indexers, and events. I haven't found any nasty ways of using these yet - if we could have methods or properties directly in namespaces (instead of in types) then we could use from x in SomeNamespace but until that time, I think sanity is reasonably safe. Of course, if you can find any further examples, please let me know!

Why is this useful?

It's not. It's really, really not - at least not in any way I can think of. The "proxy with delegate properties" might just have some weird, twisted use, but I'd have to see it to believe it. Of course, these are useful examples to prove what the compiler's actually doing, and the extent to which query expressions really are just syntactic sugar (but sooo sweet) - but that doesn't mean there's a good use for the technique in real code.

Again, if you can find a genuine use for this, please mail me. I'd love to hear about such oddities.

Implementing deferred execution, and a potential trap to avoid

skeet — Thu, 28 Feb 2008 00:32:18 GMT

When talking about LINQ recently, I doodled an implementation of OrderBy on a whiteboard. Now, I know the real OrderBy method has to support ThenBy which makes life slightly tougher, but let's suppose for a moment that it didn't. Let's further suppose that we don't mind O(n²) efficiency, but we do want to abide by the restriction that the sort should be stable. Here's one implementation:

public static IEnumerable<TSource> OrderBy<TSource,TKey>
    (this IEnumerable<TSource> source,
     Func<TSource,TKey> keySelector)
{
    IComparer<TKey> comparer = Comparer<TKey>.Default;
    List<TSource> buffer = new List<TSource>();
    foreach (TSource item in source)
    {
        // Find out where to insert the element -
        // immediately before the first element that
        // compares as greater than the new one.
        TKey key = keySelector(item);

        int index = buffer.FindIndex
            (x => comparer.Compare(keySelector(x), key) > 0);

        buffer.Insert(index==-1 ? buffer.Count : index, item);
    }

    return buffer;
}

What's wrong with it? Well, it compiles, and seems to run okay - but it doesn't defer execution. As soon as you call the method, it will suck all the data from the source and sort it. List<T> implements IEnumerable<T> with no problems, so we're fine to just return buffer... but we can very easily make it defer execution. Look at the end of this code (the actual sorting part is the same):

It seems odd to be manually iterating over buffer instead of just returned it to be iterated over by the client - but suddenly we have deferred execution. None of the above code will run until we actually start asking for data.

The moral of the story? I suspect many developers would change the second form of code into the first, thinking they're just refactoring - when in fact they're changing a very significant piece of behaviour. Be careful when implementing iterators!

Data pipelines as a conceptual stepping stone to higher order functions

skeet — Thu, 28 Feb 2008 00:08:40 GMT

I was explaining data pipelines in LINQ to Objects to a colleague yesterday, partly as the next step after explaining iterator blocks, and partly because, well, I love talking about C# 3 and LINQ. (Really, it's becoming a serious problem. Now that I've finished writing the main text of my book, my brain is properly processing the stuff I've written about. I hadn't planned to be blogging as actively as I have been recently - it's just a natural result of thinking about cool things to do with LINQ. It's great fun, but in some ways I hope it stops soon, because I'm not getting as much sleep as I should.)

When I was describing how methods like Select take an iterator and return another iterator which, when called, will perform appropriate transformations, something clicked. There's a conceptual similarity between data pipelines using deferred execution, and higher order functions. There's a big difference though: I can get my head round data pipelines quite easily, whereas I can only understand higher order functions for minutes at a time, and only if I've had a fair amount of coffee. I know I'm not the only one who finds this stuff tricky.

So yes, there's a disconnect in difficulty level - but I believe that the more comfortable one is with data pipelines, the more feasible it is to think of higher order functions. Writing half the implementation of Push LINQ (thanks go to Marc Gravell for the other half) helped my "gut feel" understanding of LINQ itself significantly, and I believe they helped me cope with currying and the like as well.

I have a sneaking suspicion that if everyone who wanted to use LINQ had to write their own implementation of LINQ to Objects (or at least a single overload of each significant method) there'd be a much greater depth of understanding. This isn't a matter of knowing the fiddly bits - it's a case of grokking just why OrderBy needs to buffer data, and what deferred execution really means.

(This is moving off the topic slightly, but I really don't believe it's inconceivable to suggest that "average" developers implement most of LINQ to Objects themselves. It sounds barmy, but the tricky bit with LINQ to Objects is the design, not the implementation. Suggesting that people implement LINQ to SQL would be a different matter, admittedly. One idea I've had for a talk, whether at an MVP open day or a Developer Developer Developer day is to see how much of LINQ to Objects I could implement in a single talk/lecture slot, explaining the code as I went along. I'd take unit tests but no pre-written implementation. I really think that with an experienced audience who didn't need too much hand-holding around iterator blocks, extension methods etc to start with, we could do most of it. I'm not saying it would be efficient (thinking particularly of sorting in a stable fashion) but it would be feasible, and I think it would encourage people to think about it more themselves. Any thoughts from any of you? Oh, and yes, I did see the excellent video of Luke Hoban doing Select and Where. I'd try to cover grouping, joins etc as well.)

I'm hoping that the more experience I have with writing funky little sequence generators/processors, the more natural functional programming with higher order functions will feel. For those of you who are already comfortable with higher order functions, does this sound like a reasonable hope/expectation? Oh, and is the similarity between the two situations anything to do with monads? I suspect so, but I don't have a firm enough grasp on monads to say for sure. It's obviously to do with composition, either way.

Visualising the Mandelbrot set with LINQ - yet again

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

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

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

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

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

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

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

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

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

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

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

Simple stuff, assuming you know anything about complex numbers.

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

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

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

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

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

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

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

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

LambdaExpression - source code would be nice

skeet — Thu, 21 Feb 2008 22:19:59 GMT

Just taking a quick break from proof-reading to post a thought I had yesterday. Visual LINQ uses ToString() to convert an expression tree's body into readable text. In some cases it works brilliantly, reproducing the original source code exactly - but in other cases it's far from useful. For instance, from this expression tree representation:

(Convert(word.get_Chars(0)) = 113)

I suspect you wouldn't have guessed that the original code was:

word[0] == 'q'

Personally I don't find it terrifically obvious, even though I can see how it works. Here's a thought though - suppose the LambdaExpression class had a Source property which the compiler could optionally provide as a constructor argument, so that you could get at the original source code if you needed it. The use in Visual LINQ is obvious, but would it be useful elsewhere?

Well, suppose that LINQ to SQL couldn't translate a particular query expression into SQL. Wouldn't it be nice if it could report the part of the query expression it was having trouble with in the language it was originally written in? So a VB expression would give source in VB, a C# expression would give source in C# etc.

All of this would have to be optional, and I suspect some people would have intellectual property concerns about their source leaking out (most of which would be silly, due to the logic effectively being available with a call to ToString() anyway). I think it would be quite handy in a few situations though.

Visual LINQ: Watch query expressions as they happen!

skeet — Wed, 20 Feb 2008 01:22:00 GMT

Critical link (in case you can't find it): Source Code Download

Update: Dmitry Lyalin has put together a screencast of Visual LINQ in action - it gives a much better idea of what it's like than static pictures do. There's music, but no speech - so you won't be missing any important information if you mute it.

I was going to save this until it was rather more polished, but I've just started reading the first proofs of C# in Depth, so it's unlikely I'll have much time for coding in the near future. I'm too excited about the results of Monday night to keep them until the book's done :)

After my Human LINQ experiment, I was considering how it my be possible to watch queries occurring on a computer. I had the idea of turning LINQ to Objects into WPF animations... and it just about works. The initial version took about 3 hours on Monday night, and it's had a few refinements since. It's very definitely not finished, but I'll go into that in a minute.

The basic idea is that you write a nearly-normal query expression like this:

VisualSource<string> words = new VisualSource<string>
    (new[] { "the", "quick", "brown", "fox", "jumped",
             "over", "the", "lazy", "dog" },
     canvas, "words");

var query = from word in words
            where word.Length > 3
            select new { Word = word, Length = word.Length};

pipeline = query.End();

... and then watch it run. At the moment, the code is embedded in the constructor for MainWindow, but obviously it needs to be part of the UI at some point in the future. To explain the above code a little bit further, the VisualSource class displays a data source on screen, and calling End() on a query creates a data sink which will start fetching data as soon as you hit the relevant "Go!" button in the UI. Speaking of which, here's what you see when you start it:

When you tell it to go, words descend from the source, and hit the "where" clause:

As you can see, "the" doesn't meet the criterion of "word.Length > 3", so the answer "False" is fading up. Fast forward a few seconds, and we'll see the first passing result has reached the bottom, with the next word on its way down:

Results accumulate at the bottom so you can see what's going on:

To be honest, it's better seen "live" as an animation... but the important thing is that none of the text above is hand-specified (other than the data and the source name). If you change the query and rebuild/run, the diagram will change - so long as I've actually implemented the bits you use. So far, you can use:

select
where
group (with trivial or non-trivial elementSelector)
multiple "from" clauses (invoking SelectMany)

Select and Where have the most polish applied to them - they've got relatively fancy animations. Grouping works, but it appears to be just swallowing data until it spews it all out later - I want to build up what it's going to return visually as it's doing it. SelectMany could be a lot prettier than it is.

So, what's wrong with it? Well:

Ordering isn't implemented
Join isn't implemented
GroupJoin isn't implemented
The animation could do with tweaking (a lot!)
The code itself is fairly awful
The UI is unpolished (but functional) - my WPF skills are sadly lacking
It would be nice to lay the query out more sensibly (it gets messy with multiple sources for multiple "from" clauses)
Allow the user to enter a query (and their own data sources)

Despite all of that though, I'm really pleased with it. It uses expression trees to create a textual representation of the logic, then compiles them to delegates for the actual projection etc. A bit of jiggery pokery was needed to make anonymous types look nice, and I dare say there'll be more of that to come.

Interested yet? The source code is available so you can play with it yourself. Let me know if you plan to make any significant improvements, and we could consider starting a SourceForge project for it.

Human LINQ

skeet — Thu, 14 Feb 2008 23:49:32 GMT

Last night I gave a talk about C# 3 and LINQ, organised by Iterative Training and NxtGenUG. I attempted to cover all the features of C# 3 and the basics of LINQ in about an hour and a half or so. It's quite a brutal challenge, and obviously I wasn't able to go into much detail about anything. It went down reasonably well, but I can't help feeling there's a lot of room for improvement. That said, there was one part of the talk which really did go well, and made the appropriate points effectively.

I had demonstrated the following LINQ query in code:

using System;
using System.Linq;

class Test
{
    static void Main(string[] args)
    {
        var words = new[] {"the", "quick", "brown", "fox",
                "jumped", "over", "the", "lazy", "dog"};

        var query = from x in words
                    where x.Length > 3
                    where x[0] != 'q'
                    select x.ToUpper();


        foreach (string word in query)
        {
            Console.WriteLine(word);
        }
    }
}

I know it would have been easy to combine the two "where" clauses, but separating them helped with the second part of the demonstration.

In the pizza break, I had prepared sheets of paper - some with the words on ("the", "quick" etc), and some with clauses ("from x in words", "where x.Length > 3" etc). I asked for 5 volunteers, who I arranged in a line, facing the rest of the audience. I stood at "audience left" with the sheets of words, gave the next person the "from" clause, then the first "where" clause etc. The person at the far end didn't have a sheet of paper, but they were acting as the foreach loop.

I suspect you can see what's coming - we ran possibly the slowest LINQ query in the world. However, we did it reasonably accurately: when the next piece of information was needed, a person would turn to their neighbour and request it; the request would pass up the line until it got to me, whereupon I'd hand over a sheet of paper with a word on. If a "where" clause filtered out a word, they just dropped the piece of paper. When a word reached the far end, the guy shouted it out.

With this, I was able to illustrate:

Deferred execution (nothing starts happening until the foreach loop executes)
Streaming (only a single word was ever on the move at once)

Next we added an "orderby" clause in just before the end. Sure enough, we then see buffering in action - the guy representing the ordering can't return any data to the "select" clause until he's actually got all the data.

Finally, we removed the "orderby" clause again, but added a call to Count(). We didn't have time to go into a lot of detail, but I think people understood why that led to immediate execution rather than the deferred execution we had earlier.

I suspect I'm not the first person to do something like this, but I'm still really pleased with it. If you're ever talking about LINQ and people's eyes are glazing over, it's a fun little demo. It wasn't perfect though; there are things I'd change:

Put the upper case version of the word on the back of the paper. We had to imagine the result of the projection.
Having two "where" clauses is useful for the first demo, but slows things down after that.
Possibly use fewer words - it takes quite a while, and having been through it three times, the audience may grow impatient.
Explain deferred execution more in terms of the result type - it'll make it easier to contrast with immediate execution

Overall, it was a really fun night. I did a little interview with Dave McMahon afterwards, which should go up on the NxtGenUG site at some point. I suspect I was talking rather too quickly for the whole time, but we'll see how it pans out.

Extension methods on lamdba expressions don't work, unfortunately

skeet — Tue, 08 Jan 2008 23:37:30 GMT

Over the Christmas holidays, I thought I'd experiment with something I'd been thinking about a little - sorting a generic IList<T>. Now, before anyone gets huffy, I'm well aware of OrderBy in LINQ to Objects. However, sometimes you want to sort collections in-place, and as IList<T> provides random access, there's no reason we shouldn't be able to. Now, I do like the way that OrderBy allows multiple criteria to be specified, whether they should be applied in an ascending or descending fashion, and by way of just "compare by this projection" rather than having to actually implement the comparison yourself. I thought I could probably make use of those ideas again.

Unlike in LINQ to Objects, the sort would occur immediately, which means I couldn't use quite the chained syntax of OrderBy(...).ThenBy(...).ThenByDescending(...) but my plan was to allow code like this:

List<Person> myList = ...;

myList.SortBy((person => person.Name).Ascending(),
(person => person.DateOfBirth).Descending(),
(person => person.SocialSecurityNumber).Ascending());

Because each of the different output types involved might be different, that would only work for as many overloads as I'd implement. An alternative would be:

Comparer<Person> sorter = Comparer.By(person => person.Name)
.ThenByDescending(person => person.DateOfBirth)
.ThenBy(person => person.SocialSecurityNumber);

sorter.Sort(myList);

I did like the idea of the Ascending and Descending extension methods though, operating on Func<T1,T2>. Unfortunately, the dot operator doesn't work on lambda expressions, even though the expression itself is implicitly convertible to Func<T1,T2>.

My plan isn't entirely scuppered - the latter syntax will still work, and there are probably some alternatives I can work out. I think there are nice possibilities around extension methods and delegates though, and it's a shame they're not useful for lambda expressions. Ah well.

LINQ to Objects - not just for in-memory collections

skeet — Tue, 08 Jan 2008 23:21:41 GMT

I've just seen LINQ to Objects described as the LINQ provider for "in-memory collections" again. It's a fairly frequent occurrence, and I may have done it myself on occasion. It doesn't do LINQ to Objects justice. An example I've used in a few places is a query which runs over log files. Something along the lines of:

var query = from file in Directory.GetFiles(@"c:\logs", "*.log")
            from line in new LineReader(file)
            let entry = new LogEntry(line)
            where entry.Severity = Severity.Critical
            select entry;

Where's the in-memory collection here? I suppose there's the array of log file names, but that's about it. LINQ to Objects isn't restricted to datasets which fit comfortably in memory. The above query could process many gigs of data very easily, limited basically by disk speed (and date/time parsing speed in my experience, but that's a topic for another post).

What LINQ to Objects does is in-process querying of enumerable sequences of data. More of a mouthful than "querying in-memory collections" but more accurate, IMO.

Rant over. Well, for a couple of minutes.