Tag: LINQ

I Am an OzCode Magician and I Have a New LINQ Trick

It has probably not gone unnoticed by those whoocm_logo know me that I really like the OzCode extension to Visual Studio. Now, I have an awesome glass brick with my name etched in it as proof1. I am happy to announce that I was recently invited to be a part of the OzCode Magician Program; an award in recognition of my genuine enthusiasm and support for OzCode over the last couple of years.

linqBug

What I really like about this is that I get to occasionally preview a new feature or two. Of course, sometimes I will be sworn to secrecy on what those features are, but thankfully, the current feature I have been allowed to play with is no secret at all. It was showcased in OzCode's recent webinar and recently made publicly available as an EAP2, so you can try it too. To whet your appetite, here is a sneak preview of the new magical LINQ debugging support.

numericIndicators

In this latest update to OzCode, we get some really nice visualizations of our LINQ queries, enabling us to see the queries step-by-step. No more refactoring code just to see what that Where will do.

quickDatatip

The new LINQ debugging allows a user to step into a specific part of the query chain on a specific iteration and see exactly what the outcome is, and it can show you how inputs map to outputs on many of the most common LINQ operations.

detailsQueryToolWindow

At the time of writing, the EAP only supports fluent syntax LINQ but I am assured that query syntax support is on its way. So, go register for the EAP now and give it a try for yourself. It's magical!

  1. also weighty enough to be a prop in an episode of CSI [↩]
  2. Early Access Preview [↩]

C#6: Using Static Types and Extension Methods

This week I thought I would continue from the last couple of posts on the new language features introduced in C#6 and look at the changes to the `using` keyword.

Up until the latest syntax, `using` was overloaded in three different ways1.

  1. To import types from a specific namespace, reducing the need to fully quality those types when referencing them in subsequent code. 
    using System.Collections;
  2. To alias namespaces and types in order to resolve ambiguities when types share a name but different namespaces. 
    using Drawing = System.Windows.Drawing; // Namespace alias
using RectangleShape = System.Windows.Shapes.Rectangle; // Type alias
  3. To define a scope at the end of which an object will be disposed 
    using (var stream = new MemoryStream())
{
    // Stuff using the stream
}

With C#6 comes an additional overload that allows us to import methods from within a specific static class. By specifying the `static` keyword after `using`, we can give the name of a static class containing the members we want to import. Doing this allows us to reference the methods as though they were members of our class.

Using Static

Consider `System.Math`; prior to this updated syntax, using the various methods on the `System.Math` class would require either specifying the fully qualifed type name, `System.Math` or, if `using System` were specified, just the type name, `Math`. Now, by specifying `using static System.Math` we can reference the methods of the `Math` class as though they were members of the class invoking them (without a `System.Math` or `Math` prefix). In this example, `Math.Abs()` is called as just `Abs()`.

using static System.Math;

public class MyClass
{
    public void DoStuff(int value)
    {
        var absoluteValue = Abs(value);
        Console.WriteLine(absoluteValue);
    }
}

As with other additions in C#6, this seems to be aimed at improving developer productivity as it leads to less overall typing when using the methods of a static class. However, the new `using static` syntax also allows for very targeted inclusion of static classes without the rest of their containing namespace, previously only possible with an alias, such as `using Math = System.Math`. This targeting ability, while not really adding anything for regular static methods, makes a significant difference for extension methods.

Extension Methods

As you probably know, extension methods are just fancy static methods, they can even be invoked as would a regular static method. However, extension methods can also be invoekd as though they where member methods of a variable or literal value. For example, both the following examples compile to the same code (assuming we have an enumerable called `list`).

list.Where(x <= 5);
Enumerable.Where(list, x <= 5);

However, before the `using static` syntax, including extension methods was a bit uncontrolled. If you wanted the extension methods in `System.Linq.Enumerable`, you had to include the entire `System.Linq` namespace; there was no way to include only the `Enumerable` static class. In some circumstances, this inability to include just the static class led to annoying type name clashes and occasionally unexpected overload resolution ambiguities or surprises. Now, with `using static` we can specify the exact class of extension methods we want to include and ignore the rest of the containing namespace.

With all that said, there is a notable difference between including regular methods of a static class and extension methods of a static class when importing via `using static <namespace>.<static class>`2.

Subtle Difference

When a static class is imported with `using static`, the way a method can be invoked depends on whether it is an extension method or not. For example, imagine we have a static class called `MyStaticClass` and it has a regular3 static method on it called `Print` that takes a `string`. When included via `using static`, `Print` could be used like this:

void Main()
{
    MyStaticClass.Print("this string");
    // or...
    Print("this string");
}

However, if instead `Print` were an extension method on type `string`, including `MyStaticClass` via `using static` would limit `Print` to being used like this:

void Main()
{
    MyStaticClass.Print("this string");
    // or...
    "this string".Print();
}

Note how in both examples , `Print` can be invoked as a traditional static method when the containing type is referenced, as in `MyStaticClass.Print()`, but their invocation varies when `using static` imports the class. In that second scenario, non-extension static methods are invoked as though they are methods on the current type, where as extension methods are invoked only as though they are methods on a variable. For the extension method version of `Print`, the following is not allowed:

Print("this string");

To use this argument-style syntax with an extension method, we must resort to the same syntax we would have used before `using static`, specifying the type name before the method:

MyStaticClass.Print("this string");

Though I feel it is clear and intuitive, this is a subtle difference worth understanding, as it can lead to breaking changes. Consider if you were refactoring the methods of a static class from extension method to regular static method or vice versa, and that class were imported somewhere with `using static`; any invocations that were not prefixed with the static class name would fail to compile.

In Conclusion

Overall, I like the new `using static` syntax; I believe the differences in method invocation from how static class methods are normally invoked makes sense and I hope you do too. Like all the other features of C#, there will be times to use this feature and times to let it go in favour of something clearer and more appropriate. For me, the ability to pluck a specific class and its extension methods from a namespace without importing the rest of that namespace is the most useful aspect of `using static` and probably what I will use most. How about you? Do you see yourself adding `using static` to your coding arsenal, or is it going to languish in your scrapbook of coding evil? Do tell.

  1. The MSDN docs say two different ways, but it was clearly three and is now three and a halfish [↩]
  2. However, unlike the subtle difference I highlighted in my last post, thankfully, the compiler will catch this one [↩]
  3. as in not an extension method [↩]

LINQ: Notation, Syntax, and Snags

Welcome to the final post in my four part series on LINQ. So far, we've talked about:

For our last look into LINQ (at least for this mini-series), I want to tackle the mini-war of "dot notation" versus "query syntax", and look at some of the pitfalls that can be avoided by using LINQ responsibly.

Let Battle Commence…

For anyone who has written LINQ using C# (or VB.NET), you are probably aware that there is more than one way to express the query (two of which, sane people might use):

  1. Old school static method calls
  2. Method syntax
  3. Query syntax

No one in their right mind should be using the first of these options; extension methods were invented to alleviate the pain that would be caused by writing LINQ this way1. Extension methods, static methods that can be called as though member methods, are the reason why we have the second option of method syntax (more commonly known as dot notation or fluent notation). The final option, query syntax, is also known as "syntactical sugar", some language keywords that can make coding easier. These keywords map to concepts found in LINQ methods and query syntax is what gives LINQ it's name; Language INtegrated Query2.

They all map to the same thing, a sequence of methods that can be executed, or translated into an expression tree, evaluated by a LINQ provider, and executed. Anything written in one of these approaches can be written using the others. There is often contention on whether to use dot notation or query syntax, as if one is inherently better than the other, but as we all know, only the Sith deal in absolutes3.  Hopefully, by the end of these examples you will see how each has its merits.

Why are LINQ queries not always called like regular methods?

Because sometimes, such as in LINQ-to-SQL or LINQ-to-Entity Framework, the method calls need to be translated into SQL or some other querying syntax, allowing queries to take advantage of server-side querying optimizations. For a more in-depth look at all things LINQ, including the way the language keywords map to the method calls, I recommend looking at Jon Skeet's Edulinq series, which is available as a handy e-book.

Before we begin, here is a quick summary of the C# keywords that we have for writing queries in query syntax: `from`, `group`, `orderby`, `let`, `join`, `where` and `select`.  There are also contextual keywords to be used in conjunction with one or two of the main keywords:`in`, `into`, `ascending`, `descending`, `by`, `on` and `equals`. Each of these keywords has a corresponding equivalent method or methods in LINQ although it can sometimes be a little more complicated as we shall see.

So, let us look at an example and see how it can be expressed using dot notation and query syntax4). For an example, let us look at a simple projection of people to their last names.

public struct Person
{
    public Person(string first, string last, DateTimeOffset dateOfBirth) : this()
    {
        FirstName = first;
        LastName = last;
        DateOfBirth = dateOfBirth;
    }
    
    public string FirstName { get; private set; }
    public string LastName { get; private set; }
    public DateTimeOffset DateOfBirth { get; private set; }
}

public static class Data
{
    public static IEnumerable<Person> People = new[] {
        new Person("John", "Smith", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 34 )),
        new Person("Bill", "Smith", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 20 )),
        new Person("Sarah", "Allans", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 19 )),
        new Person("John", "Johnson", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 44 )),
        new Person("James", "Jones", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 78 )),
        new Person("Alex", "Jones", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 30 )),
        new Person("Mabel", "Thomas", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 29 )),
        new Person("Sarah", "Brown", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 23 )),
        new Person("Gareth", "Smythe", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 100 )),
        new Person("Gregory", "Drake", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 90 )),
        new Person("Michael", "Johnson", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 56 )),
        new Person("Alex", "Smith", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 22 )),
        new Person("William", "Pickwick", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 17 )),
        new Person("Marcy", "Dickens", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 18 )),
        new Person("Erica", "Waters", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 26 ))
    };
}
Data.People.Select(p => p.LastName);
from person in Data.People
select person.LastName;

These two queries do the exact same thing, but I find that the dot notation wins out because it takes less typing and it looks clearer. However, if we decide we want to only get the ones that were born before 1980, things look a little more even.

Data.People
    .Where(p => p.DateOfBirth.Year < 1980)
    .Select(p => p.LastName)
from person in Data.People
where person.DateOfBirth.Year < 1980
select person.LastName;

Here, there is not much difference between them, so I'd probably leave this to personal preference5. However, as soon as we want a distinct list, the dot notation starts to win out again because C# does not contain a `distinct` keyword (though VB.NET does).

Mixing dot notation and query syntax in a single query can look messy, as shown here:

(from person in Data.People
where person.DateOfBirth.Year < 1980
select person.LastName).Distinct()

So, I prefer to settle on just one style of LINQ declaration for any particular query, or to use intermediate variables and separate the query into parts (this is especially useful on complex queries as it also provides clarity; being terse is cool, but it is unnecessary, and a great way to get people to hate you and your code).

Data.People
    .Where(p => p.DateOfBirth.Year < 1980)
    .Select(p => p.LastName)
    .Distinct();
var lastNames = from person in Data.People
                where person.DateOfBirth.Year < 1980
                select person.LastName;
lastNames.Distinct();

The `Distinct()` method is not the only LINQ method that has no query syntax alternative, there are plenty of others like `Aggregate()`, `Except()`, or `Range()`. This often means dot notation wins out or is at least part of a query written in query syntax. So, thus far, dot notation seems to have the advantage in the battle against query syntax. It is starting to look like some of my colleagues are right, query syntax sucks. Even if we use ordering or grouping, dot notation seems to be our friend or at least is no more painful than query syntax:

Data.People
    .OrderBy (p => p.LastName)
    .ThenBy (p => p.FirstName)
    .GroupBy(p=>p.DateOfBirth.Year);
from person in Data.People
orderby person.LastName,
        person.FirstName
group person by person.DateOfBirth.Year;

However, it is not always so easy. What if we want to introduce variables, group something other than the original object, or use more than one source collection? It is in these scenarios where query syntax irons a lot more of the complexity. Let's assume we have another collection containing newsletters that we need to send out to all our people. To generate the individual mailings, we would need to combine these two collections6.

Data.People.SelectMany(
    person => newsletters,
    (person, newsletter) => new {person,newsletter} );
from person in Data.People
from newsletter in newsletters
select new {person, newsletter};

I know which one is clearer to read and easier to remember when I need to write a similar query. The dot notation example makes me think for a minute what it is doing; projecting each person to the newsletters collection and, using `SelectMany()`, flattening the list then selecting one result per person/newsletter combination. Our query syntax example is doing the same thing, but I don't need to think too hard to see that. Query syntax is starting to look useful.

If we were to throw in some mid-query variables (useful to avoid calculating something multiple times or to improve clarity), or join collections, query syntax becomes really useful. What if each newsletter is on a different topic and we only want to send newsletters to people who are interested in that topic?

people.SelectMany(
    person => person.Value,
    ( person, topic ) => new
    {
        person,
        topic
    } ).Join(
        newsletters,
        t => t.topic,
        newsletter => newsletter.Value,
        ( t, newsletter ) => new
        {
            t.person,
            newsletter
        } );
from person in Data.People
from topic in person.Topics
join newsletter in newsletters on topic equals newsletter.Topic
select new {person, newsletter};

I know for sure I would need to go look up how to do that in dot notation7. Query syntax is an easier way to write more complex queries like this and provided that you understand your query chain, you can declare clear, performant queries.

 

In conclusion…

In this post I have attempted to show how both dot notation and query syntax (aka fluent notation) have their vices and their virtues, and in turn, armed you with the knowledge to choose wisely.

So, think about whether someone can read and maintain what you have written. Break down complex queries into parts. Consider moving some things to lazily evaluated methods. Understand what you are writing; if you look at it and have to think about why it works, it probably needs reworking. Always favour clarity and simplicity over dogma and cleverness; to draw inspiration from Jurassic Park, even though you could, stop to think whether you should.

LINQ is a complex feature of C# and .NET (and all the other .NET languages) and there are many things I have not covered. So, if you have any questions, please leave a comment. If I can't answer it, I will hopefully be able to direct you to someone who can. Alternatively, check out Edulinq by the inimitable Jon Skeet, head over to StackOverflow where there is an Internet of people waiting to help (including Jon Skeet), or get binging (googling, yahooing, altavistaring, whatever…)8.

And that brings us to the end of this series on LINQ. From deferred execution and the query chain to dot notation versus query syntax, I hope that I have managed to paint a favourable picture of LINQ, and helped to clear up some of the prejudices and confusions that surround it. LINQ is a powerful weapon in the arsenal of a .NET programmer; to not use it, would be a waste.

  1. Just the thought of the nested method calls or high number of placeholder variables makes me shudder [↩]
  2. I guess LIQ was too suggestive for Microsoft [↩]
  3. That statement is an absolute, Obi Sith Kenobi [↩]
  4. I am definitely leaving the nested static methods approach to you as an exercise (in futility [↩]
  5. Though if you changed the `person` variable to `p`, there is less typing in the query syntax , if that is a metric you are concerned with [↩]
  6. Yes, a nested `foreach` can achieve this simple example, but this is just illustrative, and I'd argue cleaner than a `foreach` approach [↩]
  7. That's why I cheated and wrote it in query syntax, then used Resharper to change it to dot notation for me [↩]
  8. Back in my day, it was called searching…grumble grumble [↩]

LINQ: Understanding Your Query Chain

This is part of a short series on the basics of LINQ:

This is the third part in my small series on LINQ and it covers what I feel is the most important thing to understand when using LINQ, query chains. We are going to build on the deferred execution concepts discussed in the last entry and look at why it is important to know your query operations.

Each method in a LINQ query is either immediately executed or deferred. When deferred, a method is either lazily evaluated one element at a time or eagerly evaluated as the entire collection. Usually, you can determine which is which from the documentation or, if that fails, a little experimentation. Why does it matter? This question from StackOverflow provides us with an example:

For those that did not read it or do not understand the problem, let me summarize. The original poster had a problem where values they had obtained from a LINQ query result, when passed into the `Except()` method on that same query, did not actually exclude anything. It was as if they had taken the sequence `1,2,3,4`, called `Exclude(2)`, and that had returned `1,2,3,4` instead of the expected `1,3,4`. On the surface, the code looked like it should work, so what was going on? To explain, we need a little more detail.

The example code has a class that described a user. An XML file contained user details and this is loaded into a sequence of `User` instances using LINQ-to-XML.

IEnumerable<IUser> users = doc.Element("Users").Elements("User").Select
        (u => new User
            { ID = (int)u.Attribute("id")
              Name = (string)u.Attribute("name")
            }
        ).OfType<IUser>();       //still a query, objects have not been materialized

As noted in the commentary, the poster understood that at this point, the query is not yet evaluated. With their query ready to be iterated, they use it to determine which users should be excluded using a different query.

public static IEnumerable<IUser> GetMatchingUsers(IEnumerable<IUser> users)
{
     IEnumerable<IUser> localList = new List<User>
     {
        new User{ ID=4, Name="James"},
        new User{ ID=5, Name="Tom"}
     }.OfType<IUser>();
     var matches = from u in users
                   join lu in localList
                       on u.ID equals lu.ID
                   select u;
     return matches;
}

And then using those results, the originally loaded list of users is filtered.

var excludes = users.Except(matches);    // excludes should contain 6 users but here it contains 8 users

Now, it is clear this code is not perfect and we could rewrite it to function without so many LINQ queries (I will give an example of that later in this post), but we do not care about the elegance of the solution; we are using this code as an example of why it is important to understand what a LINQ query is doing.

As noted in the commentary, when the line declaring the initial `users` query is executed, the query it defines has not. The query does not actually become a real list of users until it gets consumed1. Where does that happen? Go on, guess.

If you guessed `GetMatchingUsers`, you are wrong. All that method does is build an additional level of querying off the initial query and return that new query. If you guessed the `Except()` method, that's wrong too, because `Except()` is also deferred. In fact, the example only implies that something eventually looks at the results of `Except()` and as such, the query is never evaluated. So, for us to continue, let's assume that after the `excludes` variable (containing yet another unexecuted query), we have some code like this to consume the results of the query:

foreach (var user in excludes)
{
   Console.WriteLine(user.ID);
}

By iterating over `excludes`,  the query is executed and gives us some results. Now that we are looking at the query results, what happens?

First, the `Except()` method takes the very first element from the `users` query, which in turn, takes the very first `User` element from the XML document and turns it into a `User` instance. This instance is then cast to `IUser` using `OfType`2.

Next, the `Except()` method takes each of the elements in the `matches` query result and compares it to the item just retrieved from the `users` collection. This means the entire `matches` query is turned into a concrete list. This causes the `users` query to be reevaluated to extract the matched users. The instances of `User` created from the `matches` query are compared with each instance from the `users` query and the ones that do not match are returned for us to output to the console.

It seems like it should work, but it does not, and the key to why is in how queries and, more importantly, deferred execution work.

Each evaluation of a deferred query is unique. It is very important to remember this when using LINQ. If there is one thing to take away from reading my blog today, it is this. In fact, it's so important, I'll repeat it:

Each evaluation of a deferred query is unique.

It is important because it means that each evaluation of a deferred query (in most cases) results in an entirely new sequence with entirely new items. Consider the following iterator method:

IEnumerable<object> GetObject()
{
    yield return new Object();
}

It returns an enumerable that upon being consumed will produce a single `Object` instance. If we had a variable of the result of `GetObject()`, such as `var obj  = GetObject()` and then iterated `obj` several times, each time would give us a different `Object` instance. They would not match because on each iteration, the deferred execution is reevaluated.

If we go back to the question from StackOverflow armed with this knowledge, we can identify that `users` is evaluated twice by the `Except()` call. One time to get the list of exceptions out of the `matches` query and another to process the list that is being filtered. It is the equivalent of this:

IEnumerable<object> GetObjects()
{
    return new[]
    {
        new Object(),
        new Object(),
        new Object(),
        new Object(),
        new Object()
    };
}

void main()
{
   var objects = GetObjects().Except(GetObjects());
   foreach (var o in objects)
   {
        Console.WriteLine(o);
   }
}

From this code, we would never expect `objects` to contain nothing since the two calls to the immediately executed `GetObjects` would return collections of completely different instances. When execution is deferred, we get the same effect; each evaluation of a query is as if it were a separate method call.

To fix this problem, we need to make sure our query is executed once to make the results "concrete", then use those concrete results to do the rest of the work. This is not only important to ensure that the objects being manipulated are the same in all uses of the queried data, but also to ensure that we don't do work more than once3. To make the query concrete, we call an immediately executed method such as `ToList()`, evaluating the query and capturing its results in a collection.

This is our solution, as the original poster of our StackOverflow question indicated. If we change the original `users` query to be evaluated and stored, everything works as it should. With the help of some investigation and knowledge of how LINQ works, we now also know why.

Now that we understand a little more about LINQ we can consider how we might rewrite the original poster's example code. For example, we really should not to iterate the `users` list twice at all; we should see the failure of `Except()` as a code smell that we are iterating the collection too often. Though making it concrete with `ToList()` fixes the bug, it does not fix this inefficiency.

To do that, we can rewrite it to something like this:

public static bool IsMatchingUser(User user)
{
     var localList = new List<User> {
        new User{ ID=4, Name="James"},
        new User{ ID=5, Name="Tom"} }
      .Cast<IUser>()
      .AsReadOnly();

    return localList.Any(u=>u.ID == user.ID && u.Name == user.Name);
}

var users = doc
    .Element("Users")
    .Elements("User")
    .Select(u => new User {
        ID = (int)u.Attribute("id")
        Name = (string)u.Attribute("name") })
    .Where(u => IsMatchingUser(u));

This update only iterates over each user once, resulting in a collection that excludes the users we don't want4.

In conclusion…

My intention here was to show why it is fundamental to know which methods are immediately executed, which ones are deferred, and whether those deferred methods are lazily or eagerly evaluated. At the end of this post are some examples of each kind of LINQ method, but a good rule of thumb is that if the method returns a type other than `IEnumerable` or `IQueryable` (e.g. `int` or `List`), it is immediately executed; all other cases are probably using deferred execution. If a method does use deferred execution, it is also helpful to know which ones iterate the entire collection every time and which ones stop iterating when they have their answer, but for this you will need to consult documentation and possibly experiment with some code.

Just knowing these different types of methods can be a part of your query will often be enough to help you write better LINQ and debug queries faster.  By knowing your LINQ methods, you can improve performance and reduce memory overhead, especially when working with large data sets and slow network resources. Without this knowledge, you are likely to evaluate queries and iterate sequences too often, and instantiate objects too many times.

Hopefully you were able to follow this post and it has helped you get a better grasp on LINQ. In the final post of this series, I will ease up on the deep code analysis, and look at query syntax versus dot notation (aka fluent notation). In the meantime, if you have any comments, I'd love to read them.

Examples of LINQ Method Varieties

Immediate Execution

`Count()`, `Last()`, `ToList()`, `ToDictionary()`, `Max()`, `Aggregate()`
Immediate iterate the entire collection every time

`Any()`, `All()`, `First()`, `Single()`
Iterate the collection until a condition is or is not met

Deferred Execution, Eager Evaluation

`Distinct()`, `OrderBy()`, `GroupBy()`
Iterate the entire collection but only when the query is evaluated

Deferred Execution, Lazy Evaluation

`Select()`,`Where()`
Iterate the entire collection

`Take()`,`Skip()`
Iterate until the specified count is reached

  1. "consumed" is often used as an alternative to "iterated" [↩]
  2. `Cast()` should have been used here since all the objects loaded are of the same type [↩]
  3. This is something that becomes very important when working with large queries that can be time or resource consuming to run [↩]
  4. with more effort, I am certain there are more things that could be done to improve this code, but we're not here for that, so I'll leave is as an exercise for you; I'm generous like that [↩]

LINQ: Deferred Execution

This is part of a short series on the basics of LINQ:

In the first rant post of this short series on LINQ, I explained the motivation behind writing this series in the first place, which can be summarised as:

People don't know LINQ and that impacts my ability to make use of it; I should try to fix that.

To start, I'm going to explain what I believe is the most important concept in LINQ; deferred execution.

So, what is deferred execution?

Deferred execution code is not executed until the result is needed; the execution is put off (deferred) until later. By doing this we can combine a series of actions without actually executing any of them, then execute them at the time we need a result. This allows us to limit the execution of computationally expensive operations until we absolutely need them.

That's my description, here is one from an MSDN tutorial on LINQ-to-XML that perhaps puts it more clearly:

Deferred execution means that the evaluation of an expression is delayed until its realized value is actually required. Deferred execution can greatly improve performance when you have to manipulate large data collections, especially in programs that contain a series of chained queries or manipulations. In the best case, deferred execution enables only a single iteration through the source collection.

Some may be surprised to know that deferred execution was not new when LINQ arrived, it had already been around for quite some time in the form of iterator methods. In fact, it is iterator methods that give LINQ its deferred execution. Before we look at an iterator method, let's look at an example of immediate execution. For this example, we will give ourselves the task of taking a collection of people and outputting a collection of unique last names for all those born before 1980.

public struct Person
{
    public Person(string first, string last, DateTimeOffset dateOfBirth) : this()
    {
        FirstName = first;
        LastName = last;
        DateOfBirth = dateOfBirth;
    }
	
    public string FirstName { get; private set; }
    public string LastName { get; private set; }
    public DateTimeOffset DateOfBirth { get; private set; }
}

public static class Data
{
    public static IEnumerable<Person> People = new[] {
        new Person("John", "Smith", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 34 )),
        new Person("Bill", "Smith", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 20 )),
        new Person("Sarah", "Allans", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 19 )),
        new Person("John", "Johnson", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 44 )),
        new Person("James", "Jones", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 78 )),
        new Person("Alex", "Jones", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 30 )),
        new Person("Mabel", "Thomas", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 29 )),
        new Person("Sarah", "Brown", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 23 )),
        new Person("Gareth", "Smythe", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 100 )),
        new Person("Gregory", "Drake", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 90 )),
        new Person("Michael", "Johnson", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 56 )),
        new Person("Alex", "Smith", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 22 )),
        new Person("William", "Pickwick", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 17 )),
        new Person("Marcy", "Dickens", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 18 )),
        new Person("Erica", "Waters", DateTimeOffset.Now - TimeSpan.FromDays( 365 * 26 ))
    };
}

IEnumerable<string> GetLastNamesImmediate()
{
    var distinctNamesToReturn = new List<string>();
    foreach (var person in Data.People)
    {
        if (person.DateOfBirth.Year < 1980 && !distinctNamesToReturn.Contains(person.LastName))
        {
            distinctNamesToReturn.Add(person.LastName);
        }
    }
    return distinctNamesToReturn;
}

When this method is called, it iterates over the entire collection and then returns its result, which also can then be iterated. If the collection of people were huge and we only cared about the first five names, this would be incredibly slow. To turn this into deferred execution, we can write it like this:

IEnumerable<string> GetLastNamesLazyDeferredWithoutLINQ()
{
    var lastNamesWeHaveSeen = new List<string>();
    foreach (var person in Data.People)
    {
        if (person.DateOfBirth.Year < 1980 && !lastNamesWeHaveSeen.Contains(person.LastName))
        {
            lastNamesWeHaveSeen.Add(person.LastName);
            yield return person.LastName;
        }
    }
}

Now, none of the code in this method is executed until the first time something calls `MoveNext()` on the returned enumerable. This means we could take the first five names without processing the entire collection of people, giving us a potentially enormous performance gain. If each item in the generated collection were computationally expensive to produce, without lazy evaluation, that expense would be multiplied by the total number of items in the collection on every call to the generator method; however, with lazy evaluation, the consumer of the collection gets to decide how many items are computed and therefore, how much work gets done. This ability to defer and control computationally expensive operations is the power of deferred execution.

However, not every deferred action necessarily has low overhead. Deferred execution actually comes in two flavours; eager evaluation and lazy evaluation (the example above is an example of lazy evaluation)1. Every action in a deferred execution chain uses either lazy or eager evaluation. Though lazy evaluation is preferred, sometimes it is not possible to evaluate one item at a time, such as when sorting. Eagerly evaluated deferred execution allows us to at least defer the effort until we want it done.

An eagerly evaluated version of the iterator method we have been looking at might look like this:

IEnumerable<string> GetLastNamesEagerDeferredWithoutLINQ()
{
    var distinctNamesToReturn = new List<string>();
    foreach (var person in Data.People)
    {
        if (person.DateOfBirth.Year < 1980 && !distinctNamesToReturn.Contains(person.LastName))
        {
            distinctNamesToReturn.Add(person.LastName);
        }
    }
	
    foreach (var name in distinctNamesToReturn)
    {
        yield return name;
    }
}

In this example, because it is still an iterator method (it returns its results using `yield return`), none of the code is executed until the very first time the `MoveNext()` method is called on the returned enumerable, and therefore, the execution is deferred. When `MoveNext()` gets called for the first time, the entire collection of data is processed at once and then the results are output one by one as needed. The difference between this and the immediate execution equivalent we first looked at is that in this version, no work is done until a result is demanded.

Allowing the consumer of a collection to control how much work is done rather than work being dictated by the collection generator allows us to manage data more efficiently by building chains of operations and then processing the result in one go when needed. Lazy evaluation gives us the additional ability to spread the effort across each call to `MoveNext()`. The key to writing good LINQ is understanding which actions are immediate, which are deferred and lazily evaluated, which are deferred and eagerly evaluated, and why it matters. We will take a look at that next time.

  1. Quite often, people use 'deferred execution' and 'lazy evaluation' interchangeably, but they are not actually synonymous, nor is 'immediate execution' synonymous with 'eager evaluation'. [↩]