Производительность LINQ и кэширование

Как уже написал в комментариях tym32167, одна из причин - JIT-компиляция кода CIL.

То есть при исполнении вот этой строки:

var res1 = lst2.Where(a => !lst1.Select(l => l.Count).Contains(a.Count));

сперва компилируются все эти методы: Where, Select, Contains. Классы List<A>, A и его свойство Count уже использовались выше по коду, поэтому они уже скомпилированы.

Что важно: недостаточно просто вызвать эти методы, например, так:

var list = new List<string>();
var test = list.Where(a => a == null).Select(a => a).Contains(null);

Результат замеров от этого не изменится. Хотя, казалось бы, использованы именно эти методы, но нет, у них другая сигнатура, а именно: с параметром List<string>.

А если взять наш класс A:

var list = new List<A>();
var test = list.Where(a => a == null).Select(a => a).Contains(null);

то это сразу скажется на результате замеров со Stopwatch.

А теперь самое важное. Вот эта строка:

var res1 = lst2.Where(a => !lst1.Select(l => l.Count).Contains(a.Count));

ничего не делает (JIT-компиляция не в счёт). Здесь просто создаётся linq-запрос.

А выполнение этого запроса выполняется при вызове метода Count() в этой строке:

Console.WriteLine(res1.Count() + " " + sw.Elapsed);

Это так называемые lazy evaluation (ленивое вычисление) и deferred execution (отложенное выполнение).

Увеличьте количество итераций (размер списка) на порядок в самом первом цикле:

for (int i = 0; i < 100000; i++)

и это сразу станет заметно на глаз. Паузы между итерациями будут по много секунд, а замеренное время sw.Elapsed - доли миллисекунд.

Добавлю ещё вот что. Всё сказанное относится к Linq To Objects - запросам поверх IEnumerable.

Но есть ещё и Linq To Sql (Entity Framework и т. п.) - запросы поверх IQueryable. Они конструируются на клиенте, а выполняются на сервере. И вот тут уже действуют другие правила. План запросов может кэшироваться на сервере и прочее.