Tigraine

Daniel Hoelbling-Inzko talks about programming

Do you really know what LinQ does?

Posted by Daniel Hölbling on March 6, 2009

LinQ is by far the most empowering language technology I’ve seen in years, and it has really helped me in many cases get to a more functional style of programming, enabling clearer syntax and better overall code.

But, it also has it’s pitfalls.
Since LinQ attaches a .Count method to any enumerable, why would you still use IList for read-only collections? It’s so damn easy to simply write code like this:

IEnumerable<string> strings = new[] {"hello", "world"};
Console.WriteLine("Number of Strings: {0}", strings.Count());


What would be the benefit when using a IList<string> or ICollection<string> like this?

IList<string> strings = new[] {"hello", "world"};
Console.WriteLine("Number of Strings: {0}", strings.Count());

IEnumerable<T>.Count() would be a O(n) operation if it would follow the IEnumerable semantics through enumerating through all items. Since the definition of a Enumerable is that you need to iterate over every item in a linked list to determine it’s length.
Actually, the implementation (I looked with Reflector into the Count() method) does exactly that:

int num = 0;
using (IEnumerator<TSource> enumerator = source.GetEnumerator())
{
    while (enumerator.MoveNext())
    {
        num++;
    }
}
return num;

But, that would always guarantee a O(n) execution time and would slow most applications to a crawl (since it’s so easy to use .Count() everywhere) Microsoft implemented a little shortcut right before the above code:

ICollection<TSource> is2 = source as ICollection<TSource>;
if (is2 != null)
{
    return is2.Count;
}

So, they are breaking the Liskov Substitution Principle on purpose to speed up the execution time of .Count().


That’s why calling .Count() doesn’t hurt so much as long as you are calling it on a IEnumerable that’s also an ICollection, all you’re doing is a cast and a field read.

That’s also why in my testing IEnumerable.Count() wasn’t soo much slower than IList.Count since the only difference that slowed IEnumerable was the typecast (I’m too lazy to generate some data on a non ICollection IEnumerable with a real O(n) execution time).

 image

Just keep in mind that once you are iterating over a “real” IEnumerable that has no collection underneath, you should try to avoid calling .Count() too often since it’s not only a cast/read but a iteration over all elements of a list.
Also keep in mind that usually when working with the extension methods on IEnumerable you risk to perform a O(n) operation, so use it wisely (especially when you don’t control the source of your IEnumerable<T>, you could get passed anything).

Filed under net, programmierung
comments powered by Disqus

My Photography business

Projects

dynamic css for .NET

Archives

more