Extending LINQ to Objects : Writing a Single Element Operator (part 1) - Building Our Own Last Operator

The role of a single element operator is to add an extension method to any type that implements IEnumerable<T> and return a single element from that collection. The built-in standard query operators First, Last and ElementAt are examples of this category of operator, returning the first element, the last element, or the element at a given index position, respectively.

Understanding how Microsoft constructed the standard query operators is the first step to understanding how to write custom operators. To explore Microsoft’s approach to operator construction, let’s build our own version of the Last operator before moving onto building a more complex operator.

Building Our Own Last Operator

To learn how to build an operator that returns a single element, let’s first look at how the built-in standard query operator Last is implemented. The shortest compilable implementation for the Last operator is shown in Listing 1.

Listing 1. Shortest compilable Last operator implementation

Whether to Use Foreach or GetEnumerator Looping Syntax

In the Last example, I chose to manually create and use the enumerator based on the IEnumerable interface pattern. Using a foreach loop in this example would also have worked and may have made the code easier to read. There is some (not much, but some) performance improvement when using the pure enumerator pattern over the foreach style of looping. Here is an implementation using the foreach syntax:

Operators are often used in loops, and attention to performance should be a goal. Other developers will assume that these operators are optimized, and we shouldn’t disappoint.

The code in Listing 1 satisfies the compiler and is completely functional. It simply takes an IEnumerable<T> collection as its source, iterates to the last element, and returns that element as its result. The one error condition trapped by this implementation is the case where there are no elements in the source collection. Throwing an InvalidOperationException is the standard pattern used by Microsoft’s operator implementations, and custom operators should follow this pattern for consistency (omitting the InvalidOperationException in the previous code would cause an error in compilation because not all code paths return a value, so it is not really optional).

Another error condition to be handled is when the source collection is itself null (not empty, but uninitialized). The pattern used by Microsoft in this case is to throw an ArgumentNullException and to test the source argument for this condition at the beginning of any operator, as the following code demonstrates:

This implementation is fully functional and follows all of the error condition patterns that Microsoft employs in their operators. Once the error conditions are satisfied, performance improvement can be explored.

The current implementation iterates the entire source collection to get to the last element, all 100,000 of them if that is the size of the source collection. If the collection has a high element count, this could be considered a performance issue. For many collection types, the last element can be retrieved with a single statement. Many collections that implement IEnumerable<T> also implement the interface IList<T>. IList<T> collections allow access by element index position, a zero-based count from the first element. If a collection implements IList<T>, then custom operators should first exhaust that avenue of processing before using the slower IEnumerable<T> enumeration algorithm approach. The code shown in Listing 2 demonstrates how to use index position if possible (otherwise using the enumeration pattern of choice).

Listing 2. Last operator implementation with recommended error handling and performance optimizations

This implementation first tries to cast the source collection to the IList<T> interface; if it is successful, it uses that interface to resolve the last element in a single statement. If the collection does not implement IList<T>, the do-while enumeration pattern using the IEnumerable<T> interface is employed. The same error-handling patterns are followed, and this implementation is equivalent to the patterns used by Microsoft in its operator implementations.

Does the LINQ to Objects Provider Have Built-in Performance Optimizations?

More detail is available in the blog posting, but Table 1 covers the main points.

Table 1. LINQ to Objects Built-in Performance Optimizations

Throwing an exception when there are no source collection elements (an empty sequence) may not be desirable behavior when using single element return operators. It is difficult dealing with exceptions from within a query expression (nowhere to put the try-catch statement). Many operators implement a variant of these operators that return a null value or a default value you specify. The operators FirstOrDefault and LastOrDefault are examples that carry out the basic function of their partners, but instead of throwing an exception when the source sequence is empty, they return the default value of the type by calling the default keyword on the specific underlying generic type. For our Last implementation, we would add an operator called LastOrDefault, and the code for this operator would be (the only alteration from the code for the final Last operator is the operator’s name and the last line):

What Does the Default Keyword Return?

The default keyword solves the issue of not knowing what default value to initially assign to a generic type and returns null for reference types and zero for numeric value types. For structs, it will return each member of the struct initialized to zero or null, depending on whether they are value or reference types.