SavePearlHarbor

Ленивый LINQ: разбираем yield и ленивые вычисления по кирпичикам. Часть 2

—

от автора

admin

В первой части мы разобрали, как компилятор превращает yield return в конечные автоматы, и посмотрели, как строятся цепочки вызовов. Мы также изучили методы с частичной буферизацией, которые хитро используют HashSet, но остаются честными итераторами.

Если вы не еще ознакомились с первой частью статьи, рекомендую вам это сделать, так как понимание того, о чем я повествовал там, сильно поможет в понимании более сложных методов LINQ, про которые пойдет речь здесь

Но сегодня мы перейдём к «тяжёлой артиллерии» — методам с полной буферизацией: OrderBy, GroupBy и Join.

Конец иллюзии ленивости

До этого момента мы жили в красивой иллюзии: LINQ ленив, поэтому длинные цепочки не бьют по памяти. Но зададим себе простой вопрос: как OrderBy может отдать нам первый отсортированный элемент, если он ещё не видел последний?

Никак. Чтобы отсортировать данные, алгоритм физически обязан прочитать их до конца. В этот момент магия yield разбивается о реальность: методы с полной буферизацией вынуждены материализовать (скопировать в память) всю входную последовательность, прежде чем вернуть хоть один элемент.

Звучит как приговор для производительности? Не совсем. Разработчики .NET сделали эту неизбежную материализацию максимально эффективной. В этой статье мы заглянем под капот и разберём:

  1. OrderBy: Почему первый вызов MoveNext() на самом деле выполняет всю работу по сортировке, и как она устроена.

  2. GroupBy: Как LINQ строит словари «на лету» и почему результат группировки — это не просто коллекция, а коллекция коллекций со скрытым состоянием.

  3. Join: Как реализован Hash Join, почему порядок аргументов имеет значение и какую из двух последовательностей LINQ решает буферизовать в память.

Мы снова напишем упрощённые, но рабочие реализации этих методов, чтобы на практике увидеть, где заканчивается элегантность yield и начинается работа с массивами, словарями и скрытыми аллокациями.

Поехали!

OrderBy/ThenBy

Нам необходимо реализовать сортировку, которая сортирует последовательность по ключу. Причем такую, которая позволяет добавлять дополнительные уровни сортировки. Сигнатура самих этих методов довольно проста. Отличается она только тем, что возвращаемый тип в данном случае — это не IEnumerable<T>, а IOrderedEnumerable<T>. Посмотрим на него:

public interface IOrderedEnumerable<out TElement> : IEnumerable<TElement>{    IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(        Func<TElement, TKey> keySelector,        IComparer<TKey>? comparer,        bool descending);}

То есть это все тот же самый IEnumerable<T>, только с добавленным методом CreateOrderedEnumerable<TKey>(...).

Получается, из методов OrderBy/ThenBy нужно возвращать реализацию IOrderedEnumerable<T>, которая при обращении к ней будет:

  1. Считывать всю последовательность в массив (без этого шага никак)

  2. Проходить по всей цепочке и вычисляет ключи сортировки

  3. Сортировать полученный массив, отдавай больший приоритет родительскому уровню

  4. И наконец, отдавать полученный массив поэлементно

Проблема: как связать уровни с разными типами?

Нам нужно где‑то хранить цепочку критериев сортировки. Давайте подумаем, как бы мы реализовали это «в лоб». Первое, что приходит в голову — создать список селекторов:

List<Func<TSource, TKey>> _keySelectors;

Но тут же возникает стена: тип ключа TKey на каждом уровне может быть разным! В OrderBy мы сортируем по int, а в ThenBy — по string. Мы не можем положить их в один List<T>, потому что TKey — это строгий дженерик.

Как же разработчики.NET выкрутились из этой ситуации? Они разделили ответственность, используя паттерн, напоминающий связный список.

Они ввели абстрактный базовый класс OrderedEnumerable<TElement> (без указания типа ключа!). Он хранит ссылку на исходную последовательность и ссылку на родительский уровень сортировки. 

public abstract class OrderedEnumerable<TElement> : IOrderedEnumerable<TElement>{    protected readonly IEnumerable<TElement> Source;    protected readonly OrderedEnumerable<TElement>? Parent;    protected OrderedEnumerable(        IEnumerable<TElement> source,        OrderedEnumerable<TElement>? parent)    {        Source = source;        Parent = parent;    }    protected int[] SortedMap(TElement[] elements)    {        var count = elements.Length;        ComputeKeys(elements, count);           var map = new int[count];        for (var i = 0; i < count; i++)             map[i] = i;        Array.Sort(map, (a, b) =>        {            var cmp = CompareKeys(a, b);            return cmp != 0 ? cmp : a - b;        });        return map;    }    public IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(        Func<TElement, TKey> keySelector,        IComparer<TKey>? comparer,        bool descending)        => new OrderedEnumerable<TElement, TKey>(Source, keySelector, comparer, descending, this);    internal abstract void ComputeKeys(TElement[] elements, int count);    internal abstract int CompareKeys(int index1, int index2);        public abstract IEnumerator<TElement> GetEnumerator();    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();}

Базовый класс ничего не знает о типе ключа. Эту ответственность мы делегируем конкретному наследнику — OrderedEnumerable<TElement, TKey>. Благодаря этому трюку каждый новый уровень (ThenBy) может иметь свой собственный тип ключа, оставаясь при этом в одной типобезопасной цепочке через общего нетипизированного предка.

Базовый класс определяет два абстрактных метода: ComputeKeys и CompareKeys — они будут реализованы наследниками, но сам базовый класс уже содержит общий алгоритм сортировки индексов (SortedMap), который использует эти методы. Сортируем индексы, а не сами элементы, потому что это:

  • эффективно по памяти (не копируем тяжёлые объекты),

  • гарантирует стабильность сортировки (при равенстве индексы сохраняют исходный порядок),

  • упрощает каскадное сравнение (каждый уровень работает со своим массивом ключей, обращаясь к родительскому при необходимости)

В конкретном наследнике мы будем хранить селектор ключа, компаратор и направление, а также массив вычисленных ключей. В его методах ComputeKeys и CompareKeys кроется самая красивая часть. Они работают по принципу рекурсии:

  • ComputeKeys: Сначала вызывает родительский метод, чтобы все вышестоящие уровни заполнили свои массивы ключей, а затем вычисляет свои собственные ключи для каждого элемента буфера.

  • CompareKeys: Сначала запрашивает результат сравнения у родителя. И только если родитель вернул 0 (то есть элементы равны по всем предыдущим уровням), сравнивает свои ключи с учётом направления (по возрастанию или убыванию).

public sealed class OrderedEnumerable<TElement, TKey> : OrderedEnumerable<TElement>{    private readonly Func<TElement, TKey> _keySelector;    private readonly IComparer<TKey> _comparer;    private readonly bool _descending;    private TKey[] _keys = [];    public OrderedEnumerable(        IEnumerable<TElement> source,        Func<TElement, TKey> keySelector,        IComparer<TKey>? comparer,        bool descending,        OrderedEnumerable<TElement>? parent)        : base(source, parent)    {        _keySelector = keySelector;        _comparer = comparer ?? Comparer<TKey>.Default;        _descending = descending;    }    internal override void ComputeKeys(TElement[] elements, int count)    {        Parent?.ComputeKeys(elements, count);                _keys = new TKey[count];        for (var i = 0; i < count; ++i)            _keys[i] = _keySelector(elements[i]);    }    internal override int CompareKeys(int index1, int index2)    {        if (Parent != null)        {            var cmp = Parent.CompareKeys(index1, index2);            if (cmp != 0) return cmp;        }                var compare = _comparer.Compare(_keys[index1], _keys[index2]);        return _descending ? -compare : compare;    }    public override IEnumerator<TElement> GetEnumerator()    {        var buffer = Source.ToArray();        if (buffer.Length == 0) yield break;                var map = SortedMap(buffer);                foreach (var index in map)            yield return buffer[index];    }}

Когда вызывается GetEnumerator, последний уровень в цепочке берёт исходную последовательность, копирует её в массив (та самая полная буферизация), а затем сортирует массив индексов, используя каскадное сравнение. После сортировки итератор просто проходит по отсортированным индексам и отдаёт элементы из буфера в нужном порядке.

Таким образом, абстрактный класс выступает связующим звеном: он обеспечивает общий механизм, не навязывая тип ключа. Мы можем строить цепочки с произвольным количеством уровней, сохраняя типобезопасность и производительность.

Реализуем теперь сами методы:

public static partial class EnumerableExtensions{    public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(        this IEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        IComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(source);        ArgumentNullException.ThrowIfNull(keySelector);        return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, false, null);    }        public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(        this IEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        IComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(source);        ArgumentNullException.ThrowIfNull(keySelector);        return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, true, null);    }        public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(        this IOrderedEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        IComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(source, nameof(source));        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));                return source.CreateOrderedEnumerable(keySelector, comparer, false);    }    public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey>(        this IOrderedEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        IComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(source, nameof(source));        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));                return source.CreateOrderedEnumerable(keySelector, comparer, true);    }  }

Обратите внимание на ThenBy: ему вообще не нужно знать, как устроена сортировка. Он просто вызывает CreateOrderedEnumerable у источника, передавая себя в качестве parent. Вся магия инкапсулирована внутри классов OrderedEnumerable.

GroupBy

Как и OrderBy, метод GroupBy относится к методам с полной буферизацией. Логика здесь железная: чтобы сгруппировать все элементы по ключу, мы физически обязаны прочитать всю последовательность до конца. Мы не можем отдать первую группу, пока не убедимся, что в самом конце исходной коллекции не спрятан элемент с тем же ключом.

Но как именно хранить эти группы в памяти, пока мы их собираем?

Первое, что приходит в голову любому разработчику — использовать стандартный словарь:

var dict = new Dictionary<TKey, List<TElement>>();

Этот вариант рабочий, но в недрах .NET он не прижился по двум фатальным причинам:

  1. Пожирание памяти. Для каждой новой группы создается отдельный объект List<TElement>. У каждого List есть свой оверхед (внутренний массив, счетчик). Плюс сам Dictionary хранит массив Entry для разрешения коллизий. Когда уникальных ключей тысячи, эти микро‑аллокации складываются в огромное давление на GC.

  2. Потеря порядка. LINQ имеет строгий контракт: порядок возвращаемых групп должен строго соответствовать порядку первого появления уникальных ключей в исходной последовательности. Стандартный Dictionary не гарантирует порядок при итерации. Более того, при внутреннем Resize (расширении) он может полностью перемешать элементы.

Разработчики .NET поняли: готовые коллекции не подходят. Им пришлось написать специализированную хеш‑таблицу с нуля, которая одновременно решает проблему памяти и жестко фиксирует порядок вставки.

Знакомьтесь: Lookup<TKey, TElement> и Grouping<TKey, TElement>

Grouping: три роли в одном классе

Класс Grouping представляет собой одну группу (все элементы с одинаковым ключом). Но если вы заглянете в его исходники, то удивитесь: это не просто обертка над массивом. Один объект Grouping выполняет сразу три роли: 

public class Grouping<TKey, TElement> : IGrouping<TKey, TElement>{    internal TKey _key = default!;    internal int _hashCode;    // 1. Динамический массив (аналог List<T>, но без лишнего оверхеда)    // Хранит сами элементы группы    private TElement[] _elements = new TElement[1];     private int _count;    // 2. Связный список для разрешения коллизий хеш-таблицы    internal Grouping<TKey, TElement>? _hashNext;    // 3. Связный список для сохранения порядка вставки групп!    internal Grouping<TKey, TElement>? _next;    // ...}

Обратите особое внимание на поле _next. Именно оно связывает все объекты Grouping в циклический односвязный список. Это гениальный ход: он позволяет обходить все группы строго в том порядке, в котором они были созданы (то есть в порядке первого появления ключа), совершенно не завися от того, как они распределены по бакетам в хеш-таблице.

Класс Grouping реализовывает интерфейс IGrouping<TKey, TElement>. Посмотрим на него:

public interface IGrouping<out TKey, out TElement> : IEnumerable<TElement>, IEnumerable{    TKey Key { get; }}

То есть, это тот же самый IEnumerable, только с добавлением поля Key. В самом классе Grouping этому ключу присваивается значение по умолчанию, но, как мы увидим позже, это поле заполняется немного в другом месте из-за оптимизаций.

Заметим, что IEnumerable<> добавляет в класс Grouping метод GetEnumerator() и позволяет итерироваться по массиву элементов _elements:

public IEnumerator<TElement> GetEnumerator(){    for (var i = 0; i < _count; ++i)        yield return _elements[i];}

Также есть метод Add(), с помощью которого можно добавить элемент в группу.

Lookup: хэш-таблица, которая помнит всё

Класс Lookup — это контейнер, который управляет всеми группами. По сути, это кастомная хеш-таблица, где в качестве значений выступают не отдельные элементы, а целые группы. Посмотрим на ее поля:

private readonly IEqualityComparer<TKey> _comparer;// 0. Сравниватель ключейprivate Grouping<TKey, TElement>?[] _buckets;      // 1. Массив бакетов (сама хеш-таблица)private Grouping<TKey, TElement>? _lastGrouping;   // 2. Хвост циклического спискаprivate int _count;                                // 3. Счетчик (но не элементов, а групп!)

Массив _buckets — это классическая хеш‑таблица. Но так как могут случаться коллизии (хеши разных ключей могут совпадать), то в одну ячейку массива может попасть несколько разных групп. Именно для решения этой проблемы и нужно поле _hashNext в классе Grouping.

Каждая ячейка _buckets[i] хранит ссылку на первый Grouping, который в нее попал. Если в ту же ячейку попадает вторая группа (коллизия), она записывается в поле hashNext первой группы. Получается обычный односвязный список.

Вся эта магия происходит в методе GetGrouping, который достает группу по ключу и, если группы с таким ключом нет, создает новую.

public Grouping<TKey, TElement>? GetGrouping(TKey key, bool create){    var hashCode = ...;   // Вычисление хэша    var bucketIndex = hashCode % _buckets.Length;    // 1. Ищем группу в хеш-таблице (разрешаем коллизии через _hashNext)    for (var group = _buckets[bucketIndex]; group != null; group = group._hashNext)    {        if (group._hashCode == hashCode && _comparer.Equals(group._key, key))            return group; // Группа уже есть, просто вернем её    }    if (!create) return null;    // Если массива не хватает для создания новой группы, увеличиваем массив    if (_count == _buckets.Length)        Resize();    bucketIndex = hashCode % _buckets.Length;    // 2. Группы нет. Создаем новую!    // Обратите внимание, что значение поля _key мы указываем именно отсюда!    // Мы не используем конструктор с параметрами для максимальной производительности    var newGroup = new Grouping<TKey, TElement> { _key = key, _hashCode = hashCode };        // Вставляем в хеш-таблицу (в начало списка коллизий текущего бакета)    newGroup._hashNext = _buckets[bucketIndex];    _buckets[bucketIndex] = newGroup;    // 3. Вставляем в циклический список, чтобы сохранить порядок!    if (_lastGrouping is null)    {        // Если это самая первая группа, она замыкается сама на себя        newGroup._next = newGroup;     }    else    {        // Вставляем новую группу в конец циклического списка        newGroup._next = _lastGrouping._next;        _lastGrouping._next = newGroup;    }    _lastGrouping = newGroup; // Сдвигаем указатель "хвоста"    return newGroup;}

Отдельное внимание обратим на пугающий метод Resize(). Он вызывается, когда количество уникальных групп (_count) достигает длины массива _buckets, и занимается тем, что увеличивает этот самый массив, сохраняя порядок групп.

private void Resize(){    // Создаем новый массив бакетов большего размера    var newBuckets = new Grouping<TKey, TElement>?[checked(_count * 2 + 1)];    var group = _lastGrouping!;        // Проходим по всем группам...    do    {        group = group._next!; // ...используя циклический список для обхода!                // Пересчитываем новый индекс бакета        var bucketIndex = group._hashCode % newBuckets.Length;                // Перестраиваем ТОЛЬКО цепочки коллизий (_hashNext)        group._hashNext = newBuckets[bucketIndex];        newBuckets[bucketIndex] = group;            } while (group != _lastGrouping); // Пока не пройдем полный круг        _buckets = newBuckets;}

Обратите внимание на две критически важные вещи:

  1. Для обхода всех групп при ресайзе используется циклический список (_next), а не старый массив _buckets. Это гениально, потому что старый массив сейчас бесполезен, а циклический список содержит все группы без исключений.

  2. При ресайзе мы перестраиваем только_hashNext. Поля _next вообще не трогаются!

Именно поэтому Lookup гарантированно сохраняет порядок групп. Даже когда хеш‑таблица внутри него полностью перекраивается и расширяется, циклический список, отвечающий за порядок, остается нетронутым. В стандартном Dictionary при Resize элементы физически перемещаются, что и ломает порядок.

Стоит упомянуть, что мы должны уметь итерироваться по Lookup. Это значит, что класс Lookup должен реализовывать интерфейс IEnumerable<>, и вот как он его реализует: 

public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator(){    if (_lastGrouping == null) yield break;        // Стартуем с "головы" (элемент сразу после хвоста)    var group = _lastGrouping;    do    {        group = group._next!;        yield return group;    } while (group != _lastGrouping); // Идем, пока не вернемся к хвосту}

Мы просто идем по циклическому списку. Никаких массивов, никаких словарей. Чистый O(N) обход с нулевыми дополнительными аллокациями.

Ну и напоследок, в классе Lookup есть фабричный метод Lookup.Create. Именно здесь происходит тот самый «момент истины», где LINQ жадно поглощает исходные данные. Здесь происходит полная материализация последовательности. 

public static Lookup<TKey, TElement> Create<TSource>(...){    var lookup = new Lookup<TKey, TElement>(comparer);        // Жадное поглощение всей последовательности!    foreach (var item in source)     {        var key = keySelector(item);        var group = lookup.GetGrouping(key, create: true);        group?.Add(elementSelector(item));    }        return lookup;},

Мы проходимся по всему source и делаем всю тяжелую работу:

  1. Из элемента source достаем ключ

  2. Достаем из lookup нужную группу по ключу. Если такой нет, то создаем ее.

  3. Добавляем выбранный элемент в эту группу

Но несмотря на всю свою сложность, класс Lookup — это шедевр оптимизации

Если сравнить Lookup с наивным Dictionary<TKey, List<TElement>>, преимущества кастомной реализации становятся очевидны. Вместо сотен отдельных List<T> и массивов Entry словаря, Lookup аллоцирует ровно K объектов Grouping, чьи внутренние массивы растут только по мере необходимости, что сильно экономит память.

В отличие от Dictionary, который ломает порядок при Resize, циклический список _next в Lookup железобетонно гарантирует порядок первого появления ключей. И хотя оба решения ищут за O(1), Lookup делает это без оверхеда на проверку версий коллекций, используя более плотную структуру данных.

Именно поэтому LINQ не использует готовые классы, а разворачивает этот специализированный и невероятно эффективный Lookup.

Теперь, когда мы понимаем, какой титанический труд скрывается за кулисами, давайте посмотрим на сам метод‑расширение GroupBy: 

public static partial class EnumerableExtensions{    public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(        this IEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        IEqualityComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(source, nameof(source));        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));        return GroupByIterator(source, keySelector, x => x, comparer);    }        public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(        this IEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        Func<TSource, TElement> elementSelector,        IEqualityComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(source, nameof(source));        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));        ArgumentNullException.ThrowIfNull(elementSelector, nameof(elementSelector));        eturn GroupByIterator(source, keySelector, elementSelector, comparer);    }    private static IEnumerable<IGrouping<TKey, TElement>> GroupByIterator<TSource, TKey, TElement>(        IEnumerable<TSource> source,        Func<TSource, TKey> keySelector,        Func<TSource, TElement> elementSelector,        IEqualityComparer<TKey>? comparer = null)    {        var lookup = Models.Lookup<TKey, TElement>.Create(            source,            keySelector,            elementSelector,            comparer);                foreach (var group in lookup)            yield return group;    }}

В данном случае yield используется исключительно для отложенного старта. Он не дает GroupBy начать работу, пока вы не спросите у него первый элемент. Но как только вы спросите — он мгновенно материализует в памяти всю последовательность целиком.

Join: финальный босс

Как бы мы написали Join «в лоб», не зная никаких секретов? Скорее всего, мы бы использовали два вложенных цикла: 

// Наивная реализация (O(N * M))foreach (var outerItem in outer)    foreach (var innerItem in inner)        if (outerKeySelector(outerItem).Equals(innerKeySelector(innerItem)))            yield return resultSelector(outerItem, innerItem);

Это работает, но сложность такого алгоритма — O(N×M). Если в каждой коллекции по 10 000 элементов, нам придется сделать 100 000 000 сравнений. Это катастрофически медленно.

В реляционных базах данных для таких задач используется алгоритм Hash Join. Его суть проста: мы берем одну таблицу, строим по ней хеш‑таблицу (чтобы искать за O(1)), а затем просто проходимся по второй таблице и ищем совпадения в хеш‑таблице. Сложность падает до O(N+M).

Но перед разработчиками LINQ встал архитектурный вопрос: какую из двух коллекций превращать в хеш‑таблицу, а по какой идти потоком?

Выбор LINQ: буферизуем Inner, читаем Outer потоком

LINQ всегда делает один и тот же выбор: вторая коллекция (inner) полностью буферизуется в Lookup, а по первой (outer) мы идем лениво, элемент за элементом.

Почему именно так? Потому что outer (внешняя коллекция) — это обычно наш «основной» поток данных. Если мы его полностью загрузим в память, мы потеряем главное преимущество LINQ — возможность обрабатывать бесконечные или огромные потоки данных. Превращая в Lookup только inner, мы жертвуем памятью под одну коллекцию, но сохраняем способность лениво стримить outer.

Давайте посмотрим, как это выглядит в коде:

private static IEnumerable<TResult> JoinIterator<TOuter, TInner, TKey, TResult>(...){    // 1. Получаем перечислитель для outer    using var outerEnumerator = outer.GetEnumerator();        // 2. Оптимизация №1: Если outer пуст, мы даже не трогаем inner!    if (!outerEnumerator.MoveNext())        yield break;    // 3. Превращаем inner в хеш-таблицу (Lookup)    var lookup = Models.Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);        // 4. Оптимизация №2: Если inner оказался пуст, смысла продолжать нет    if (lookup.Count == 0)        yield break;    // 5. Проходим по outer потоком    do    {        var outerItem = outerEnumerator.Current;              // 6. Ищем совпадения в Lookup (create: false - ничего не создаем!)        var group = lookup.GetGrouping(outerKeySelector(outerItem), create: false);        if (group is null) continue;        // Если группа нашлась, отдаем все пары        foreach (var innerItem in group)            yield return resultSelector(outerItem, innerItem);    }    while (outerEnumerator.MoveNext());}

Если присмотреться к коду, можно заметить несколько тонких моментов, которые отличают профессиональный код от учебного:

  1. Досрочное прерывание: Строка if (!outerEnumerator.MoveNext()) yield break; делает один шаг по outer. Если он пуст, мы даже не читаем inner и не тратим память на создание Lookup.

  2. CreateForJoin: Это удобная обертка над Create с селектором x => x, так как в Join элементы inner хранятся как есть, без дополнительных проекций.

  3. Магия create: false: Самая важная деталь. При поиске ключа из outer мы вызываем GetGrouping(..., create: false). Если бы флаг был true, для каждого элемента outer, не нашедшего пару, мы бы аллоцировали новую пустую группу, устроив утечку памяти.

  4. Цикл do-while: Используется вместо привычного foreach, потому что мы уже сделали один MoveNext() на шаге проверки. Это позволяет не сдвигать каретку дважды для первого элемента.

Ну и сам метод будет выглядеть вот так:

public static partial class EnumerableExtensions{    public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>(        this IEnumerable<TOuter> outer,        IEnumerable<TInner> inner,        Func<TOuter, TKey> outerKeySelector,        Func<TInner, TKey> innerKeySelector,        Func<TOuter, TInner, TResult> resultSelector,        IEqualityComparer<TKey>? comparer = null)    {        ArgumentNullException.ThrowIfNull(outer, nameof(outer));        ArgumentNullException.ThrowIfNull(inner, nameof(inner));        ArgumentNullException.ThrowIfNull(outerKeySelector, nameof(outerKeySelector));        ArgumentNullException.ThrowIfNull(innerKeySelector, nameof(innerKeySelector));        ArgumentNullException.ThrowIfNull(resultSelector, nameof(resultSelector));        return JoinIterator(outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);    }}

Заключение

Во второй части мы разрушили последнюю иллюзию о «всегда ленивом» LINQ. Мы увидели, что за элегантными цепочками .OrderBy().GroupBy().Join() скрывается титаническая работа по управлению памятью.

Мы разобрали три ключевых метода с полной буферизацией и поняли, почему они вынуждены нарушать заветы ленивости:

  1. OrderBy — использует абстрактный класс и каскадное сравнение, чтобы сортировать индексы, а не сами объекты. Это экономит память и гарантирует стабильность.

  2. GroupBy — разворачивает в памяти специализированный Lookup с циклическим связным списком. Это позволяет сохранить порядок первого появления ключей и избежать лишних аллокаций, которые были бы при использовании Dictionary<TKey, List<T>>.

  3. Join — применяет асимметричный Hash Join. Он полностью буферизует inner коллекцию в Lookup, но зато позволяет лениво стримить outer, сохраняя возможность работать с огромными или даже бесконечными потоками данных.

Понимание этих механизмов — не просто академическое упражнение. Это инструмент, который спасает от реальных проблем.

Теперь, когда вы знаете, как устроен LINQ изнутри, я призываю вас сделать ещё один шаг. Откройте исходники.NET на GitHub и попробуйте прочитать реализацию OrderBy или GroupBy, да и других методов LINQ своими глазами. Обещаю: то, что раньше казалось заклинаниями, теперь читается как логичный, красивый и понятный инженерный код.

Спасибо, что прошли этот путь вместе со мной! Если статья была полезной — ставьте лайк, делитесь с коллегами и подписывайтесь, чтобы не пропустить новые разборы.

А в комментариях расскажите: какой метод LINQ казался вам самой большой магией, пока вы не узнали, как он устроен?

Репозиторий с полной реализацией всех методов, о которых шла речь: [ссылка]

ссылка на оригинал статьи https://habr.com/ru/articles/1062802/