Jon Skeet: Coding Blog : CSharpDev, LINQ, CSharpDevCenter

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.

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.