Will LINQ use specialized/optimized versions of functions based on the type of the input?

Question

If I do the something like the following with LINQ:

void DoSomeStuffWithHashSet()
{
  HashSet<int> set = new HashSet<int>();
  for (int i = 0; i < 100; ++i) set.Add(i);
  if (Lookup(set, new Random().NextInt(200))
     System.Console.WriteLine("Yey");
  else
     System.Console.WriteLine("Ney");
}

bool Lookup(IEnumerable<int> haystack, int needle)
{
  // O(N) search or HashSet<int>.Contains()?
  return Enumerable.Contains(collection, needle);
}

Will Enumerable.Contains() resolve to the optimized implementation on HashSet or will a simple search be performed regardless of the input?

Answer 1

Yes, it will use HashSet<T>.Contains. HashSet<T> implements ICollection<T> and per the documentation for Enumerable.Contains:

If the type of source implements ICollection<T>, the Contains method in that implementation is invoked to obtain the result. Otherwise, this method determines whether source contains the specified element.

always, Always, ALWAYS check the documentation!

Answer 2

Yes, it does - in some cases. Not always when you think it might be able to though.

As part of writing Edulinq, I wrote two posts (part 40; part 42) on optimization. Basically what counts as a valid optimization isn't always obvious - but there are definitely plenty of cases where LINQ to Object optimizes based on the execution-time type of the collection. This is mostly the case for methods returning a single value rather than a sequence.