В c# стандартные итераторы наследуюется от класса Iterator - суть которого контролировать, что все циклы foreach получат разные экземпляры итераторов если будут вызывать GetEnumerator из разных потоков. Для начала нужно вспомнить во что разворачивается foreach в C#
В цикле foreach используется утиная типизация, т.е:
class DuckEnumerator : IDisposable
{
public int Current { get; }
public bool MoveNext()
{
throw new Exception();
}
public void Dispose()
{
}
}
class Duck
{
public DuckEnumerator GetEnumerator() => null;
}
foreach (var item in new Duck()) // <- компилируется
{
Console.WriteLine(item);
}Если в типе нет метода GetEnumerator возвращающего объект у которое есть свойство Current, метод bool MoveNext(), то он должен реализовывать IEnumerable, таким образом утиная типизация имеет приоритет над вызовом метода интерфейса, это сделано в угоду производительности, если DuckEnumerator структура - то она не будет упакована при касте к IEnumerator
Поясню: Как проверить упакована ли структура на примере ListEnumerator'a(это структура):
var x = new { Items = ((IEnumerable<int>)new List<int> { 1, 2, 3 }).GetEnumerator() };
while (x.Items.MoveNext())
{
Console.WriteLine(x.Items.Current);
}
// 1 2 3
//
var x = new { Items = new List<int> { 1, 2, 3 }.GetEnumerator() };
while (x.Items.MoveNext())
{
Console.WriteLine(x.Items.Current);
}
// 0 0 0 0 ... (бесконечно)
// Почему так? Для начала в первом случае возвращается объект типа IEnumerator<int> - за этим интерфейсом скрывается структура
// Во втором случае возвращается сама структура без приведения к интерфейсу
// Items - свойство с открытым геттером и без сеттера, можно интерпретировать x.Items как вызов метода x.get_Items().
// Методы в C# возвращает либо указатель на объект в куче либо копию структуры на стеке, в первом случае будет возвращен указатель
// на упакованную структуру, во втором - выполнено копирование структуры(не упакованной).
// Таким образом в первом случае мы сможем менять объект имея указатель на него, а во втором будем помещать в стек копию структуру,
// мутировать ее и извлекать из стекаТакже на вызов интерфейсного метода приходится больше накладных расходов, чем невиртуального метода напрямую
Приведенный пример с Duck, раскручивается вот в такое(не на C#, а в IL, это просто логическое содермиое кода)
foreach (var item in new Duck()) // <- компилируется
{
Console.WriteLine(item);
}
////////
var enumerator = new Duck().GetEnumerator();
try
{
while (enumerator.MoveNext())
{
Console.WriteLine(enumerator.Current);
}
}
finally
{
enumerator.Dispose();
}
Если тип DuckEnumerator не реализует IDisposable - try finally сгенерирован не будет
В C# есть возможность вернуть из метода IEnumerator, IEnumerator или IEnumerable, IEnumerable не создавая никаких коллекций, используя ключевые слова yield return, yield break; Рассмотрим способ генерации IEnumerable
static IEnumerable<int> GetEnumerableUseIterators()
{
yield return 1;
if (new Random().Next() % 2 == 0)
yield break;
yield return 2;
}Будет сгенерирован вот такой класс:
Основное внимание нужно обратить на его поля, метод MoveNext и метод GetEnumerator. Начнем с полей
-
В поля автосгенерированного класса передаются все аргументы метода, если в методе идет обращение к полям класса, то также передается контекст this, поскольку конечный автомат генерируется внутри класса, то имеет доступ ко всем приватным переменным. Под локальные переменные метода также создаются поля, но их инициализация происходит при вервом вызове метода MoveNext;
-
MoveNext. Это главный метод в интерфесы IEnumerable, при использовании блоков итераторов, происходит генерация конечного автомата, вход которого - состояние 0, running - состояние -1, suspended(после вызова MoveNext) - состояние n, где n от 1 до количества использований ключевых слов yield return в коде метода. При каждом вызове метода MoveNext происходит сначала выставление состояния в running, после этого шаг итератора(инициализациия current) и выставление состояние в следующее. При этом yield break сразу возвращает false и оставляет машину в состоянии state = -1, тем самым при попытке повторного использования итератора - последовательность будет завернута.
-
Метод GetEnumerator - вот тут интересная деталь, если экземпляр автосгенерированного класса был создан в том же потоке, в каком вызвался метод GetEnumerator - будет возвращен this(поскольку Enumerator и Enumerable совмещены в один класс), если же метод вызывается из другого потока, либо уже был вызван потоком-создателем - будет создан еще один экземпляр автосгенерированного класса, туда будут скопированы все необходимые переменные и он будет возвращен, зачем это нужно? С потоками понятно - так IEnumerable становится потокобезопасным, поскольку каждое обращение к методы GetEnumerator возвращает новый объект, а самый частый вариант(когда обращение одно), ничего не аллоцирует и сразу возвращает себя. Также если тот же поток вызовет GetEnumerator второй раз ему будет возвращен новый enumerator, это архитектурное решение, которое кажется логичным.
Но сам итератор не threadsafe даже несмотря на то, что переключает состояние this.state = -1; каждый раз при выполнении MoveNext, не threadsafe он из-за архитектуры MoveNext и Current, т.e мы двигаем Current вызывая MoveNext, получаем значение true и забираем Current. В промежутке между вызовом MoveNext и вызовом Current другой поток может также вызвать MoveNext - получаем, что разные потоки будут получать одинаковые значения.
Также метод, использующий yield может возвращать и IEnumerator, в таком случае все сложности с методом GetEnumerator отпадают и генерируется более простой класс, реализующий интерфейсы IEnumerator, IEnumerator
Зачем интерфейс IDisposable? он нужен вот в таких случаях:
Также отмечу, что Dispose может быть вызван только в состоянии, когда перечисление активно, если оно не началось или уже завершилось он вызван не будет(логично)
Тут важно, чтобы программист пользовался foreach, который разворачивается в try finally и в finally вызывает Dispose итератора, поскольку __fault будет выполнен только если ошибка произошла в методе MoveNext, а не в вызывающем коде
Вообще при рассмотрении итераторов нужно обратить внимание на три основные коллекции - List, Array и абстрактный IEnumerable, потому что код для трех видов разный.
Начнем с List
Вообще все итераторы наследуются от Iterator - это тип, который реализует IEnumerable и IEnumerator и в котором определена логика начала создания итератора. Она такая же как и в автосгенерированных классах, если поток создал класс Iterator и берет у него Enumerator, вернуть this, в остальных случаях создать новый экземпляр себя и вызвать на нем GetEnumerator. Таким образом достигается потокобезопасность коллекции. Также там определена реализация IEnumerable(ссылается на IEnumerable) и IEnumerator, для потомков оставлены абстрактные методы:
- public bool MoveNext - метод IEnumerator'a
- public Iterator Clone - вызывается в GetEnumerator, если нужно создать новый итератор для последовательность
Но кроме этого в Iterator'e есть методы Select и Where.
Казалось бы для чего они нужны? На самом деле это послезные методы, но чтобы понять для чего они нужны нужна сначала понять как рабоют итераторы, для этого я приведу пример своих extension методов поверх IEnurable со своими итераторами
public abstract class BaseIterator<T> : IEnumerator<T>, IEnumerable<T>
{
public abstract bool MoveNext();
public void Reset()
{
throw new System.NotImplementedException();
}
protected T _current;
public T Current => _current;
object? IEnumerator.Current => Current;
public void Dispose()
{
}
protected abstract BaseIterator<T> Clone();
public IEnumerator<T> GetEnumerator()
{
return Clone().GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
public class WhereEnumerable<T> : BaseIterator<T>
{
internal readonly Func<T, bool> _predicate;
internal readonly IEnumerator<T> _baseIterator;
public WhereEnumerable(Func<T, bool> predicate, IEnumerator<T> baseIterator)
{
_predicate = predicate;
_baseIterator = baseIterator;
}
public override bool MoveNext()
{
if (!(_baseIterator.MoveNext() && _predicate(_baseIterator.Current)))
return false;
_current = _baseIterator.Current;
return true;
}
protected override BaseIterator<T> Clone() => new WhereEnumerable<T>(_predicate, _baseIterator);
}
public class SelectEnumerable<T, TR> : BaseIterator<TR>
{
private readonly IEnumerator<T> _enumerator;
private readonly Func<T, TR> _selector;
public SelectEnumerable(IEnumerator<T> enumerator, Func<T, TR> selector)
{
_enumerator = enumerator;
_selector = selector;
}
public override bool MoveNext()
{
if (!_enumerator.MoveNext()) return false;
_current = _selector(_enumerator.Current);
return true;
}
protected override BaseIterator<TR> Clone() => new SelectEnumerable<T, TR>(_enumerator, _selector);
}
public class SelectWhereEnumerable<T, TR> : BaseIterator<TR>
{
private readonly IEnumerator<T> _enumerator;
private readonly Func<T, bool> _predicate;
private readonly Func<T, TR> _selector;
public SelectWhereEnumerable(IEnumerator<T> enumerator, Func<T, bool> predicate, Func<T, TR> selector)
{
_enumerator = enumerator;
_predicate = predicate;
_selector = selector;
}
public override bool MoveNext()
{
if (!(_enumerator.MoveNext() && _predicate(_enumerator.Current)))
return false;
_current = _selector(_enumerator.Current);
return true;
}
protected override BaseIterator<TR> Clone()
{
return new SelectWhereEnumerable<T, TR>(_enumerator, _predicate, _selector);
}
}
public static class MyEnumerableExtensions
{
public static IEnumerable<T> MyWhere<T>(this IEnumerable<T> enumerable, Func<T, bool> predicate)
{
return new WhereEnumerable<T>(predicate, enumerable.GetEnumerator());
}
public static IEnumerable<R> MySelect<T, R>(this IEnumerable<T> enumerable, Func<T, R> selector)
{
return new SelectEnumerable<T, R>(enumerable.GetEnumerator(), selector);
}
public static IEnumerable<R> MyClearSelect<T, R>(this IEnumerable<T> enumerable, Func<T, R> selector)
{
// На самом деле можно создать другой extension метод принимающий тип WhereEnumerable<T>, но у разработчиков языка такого выбора не было
if (enumerable is WhereEnumerable<T> whereEnumerable)
{
return new SelectWhereEnumerable<T, R>(whereEnumerable._baseIterator, whereEnumerable._predicate,
selector);
}
return new SelectEnumerable<T, R>(enumerable.GetEnumerator(), selector);
}
}
public class ExampleUsage
{
public void Start()
{
// плохо, вложенные итераторы, растет стек поскольку SelectInterator будет вызывать MoveNext WhereIterator'a
var e = Enumerable.Range(1, 1000000)
.MyWhere(x => x < 1000000)
.MySelect(x => x * 2)
.ToArray();
// Хорошо, один итератор
var ee = Enumerable.Range(1, 1000000)
.MyWhere(x => x < 1000000)
.MySelect(x => x * 2)
.ToArray();
}
}
Основная проблема подхода IEnumerable - вложенные итераторы, раздувают стек, поэтому два поля в Iterator сделаны для того, чтобы склеить итераторы Where и Select, ведь их легко можно склеть когда выражения вида en.Where(predicate).Select(selector), также можно их склеить когда выражение видов:
en.Where(predicate).Select(selector)
en.Where(predicate).Where(predicate1) ...
en.Select(selector).Select(selector) ...Разработчики также задумались над этим, и добавили виртуальные методы Select И Where, на данный момент это работает так: SelectIterator переопределяет метод Select, в котором создает копию себя комбинируя селекторы:
// у SelectEnumerableIterator, SelectListIterator и SelectArrayIterator они делают одно и тоже
public override IEnumerable<TResult2> Select<TResult2>(Func<TResult, TResult2> selector) =>
new SelectEnumerableIterator<TSource, TResult2>(_source, CombineSelectors(_selector, selector));
public static Func<TSource, TResult> CombineSelectors<TSource, TMiddle, TResult>(Func<TSource, TMiddle> selector1, Func<TMiddle, TResult> selector2) =>
x => selector2(selector1(x)); Так что бесконечные вызовы Select не раздуют стек, а что насчет Where, Where-iterator'ы Также переопределяют метод Where, комбинируя предикаты, но у них также перегружен метод Select(привожу пример на WhereEnumerableIterator'e, для WhereListIterator и WhereArrayIterator'a все тоже самое:
public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector) =>
new WhereSelectArrayIterator<TSource, TResult>(_source, _predicate, selector);А у WhereSelectIterator'a перегружен только метод Select:
Получается мы можем сколько угодно комбинировать en.Where(...).Select(...).Select(...). ... и при этом это будет один итератор, но как только придется сделать en.Where(...).Select(...).Select(...). ....Where(...) - появится второй итератор - WhereEnumerableIterator, который будет вызывать SelectWhereEnumerableIterator в MoveNext. На самом деле можно было написать распрямнение таких последовательностей, но в этом нет смысла, люди обычно не пишут более одного Select и Where и вычислении.
Но при этом .Select(...).Where(...) - содержит два вложенных итератор'a, а .Where(...).Select(...) - один, интуитивно это хорошо понятно.
Теперь посмотрим на extension метод Select:
Если enumerable реализует Iterator - вызываем его метод Select
Далее если это массив возвращаем новый SelectArrayEnumerator - который реализует Iterator
Далее если это лист возвращаем новый SelectListEnumerator - который реализует Iterator
Далее если это реализует IList - используем SelectIListIterator - который реализует Iterator ( его метод MoveNext делает тоже самое, что и метод MoveNext в классе SelectIListEnumerator).ПОЧЕМУ ОНИ ЭТО ОДНО И ТО ЖЕ???
Далее если enumerable реализует IPartition, то делаем что-то с этим интерфейсом
Далее возвращаем работу с абстрактным IEnumerable
Самое интересное, что у массива также есть enumerator, Но он даже не вызывается, чтение идет напрямую из массива через обращение к индексатору, для которого в IL коде есть специальные команды.
Теперь рассмотрим интерфейс IPartition -
internal interface IPartition<TElement> : IIListProvider<TElement>
{
// Нужен для метода Skip,SkipTake
IPartition<TElement> Skip(int count);
// Нужен для метода Take,SkipTake
IPartition<TElement> Take(int count);
// Нужен для метода ElementAt, TryElementAt
TElement TryGetElementAt(int index, out bool found);
// Нужен для метода First,FirstOrDefault
TElement TryGetFirst(out bool found);
// Нужен для метода Last,LastOrDefault
TElement TryGetLast(out bool found);
}
internal interface IIListProvider<TElement> : IEnumerable<TElement>
{
// Нужен для метода ToArray
TElement[] ToArray();
// Нужен для метода ToList
List<TElement> ToList();
// Нужен для метода Count
int GetCount(bool onlyIfCheap);
}Тем самым реализация коллекцией интерфейса IPartition сразу же дает возможность использовать основные LINQ методы
В итоге в методе Select, если встречается последовательность, которая реализует IPartition, создается новый SelectIPartitionIterator на базе переданной последовательности(которая реализует IPartition, тем самым создается своеобразный адаптер, который переопределяет вызов каждой функции интерфейса IPartition, прелесть адаптера - поддержка Take, Skip,First,Last и т.д:
Как в c# можно создать последовательность реализующую IPartition? Вызвав у любого IEnumerable методы Skip или Take, можно получить такую последовательность, но, опять же, есть нюансы
- Если вы вызываете Skip, Take на коллекции которая реализует IList будет создан ListPartition, этот итератор реализован достаточно интересно:
var a = arr.Skip(1); // <- настоящий тип а - ListPartition
var b = a.Take(2); // <- настоящий тип b - ListPartition, будет вызван метод Take у a, тем самым проиниализированы поля _minInclusiveIndex и _maxInclusiveIndexОчевидно что вызов Take().Skip() в данном случае меняет только _minInclusiveIndex, _maxInclusiveIndex - будет int.MaxValue.
- Если вы вызываете Skip, Take на коллекции которая не реализует IList, а реализует только IEnumerable, будет создан EnumerablePartition, который не сможет обращаться по индексу и будет вынужен в методе MoveNext сначала просто повызывать метод MoveNext последовательности, которую ему передали и только тогда, когда он вызовет ее _minIndexInclusive раз, начнет реально возвращать результаты
Становится понятно насколько менее выгодно работать с абстрактной последовательностью
Рассмотрим методы First, Last, это простые методы, которые либо вызывают TryGetFirst, TryGetLast, если последовательность реализует IPartition, либо вызывают ilist[0], ilist[ilist.Count-1], если последовательность реализует IList, либо начинает перечислять, если последовательность реализует только IEnumerable, также заметим, что в последнем случае вызов Last может быть крайне непроизводителен
Теперь посмотрим методы, которые вынуждены вычислять последовательность, такие как OrderBy, GroupBy, Count.
Насчем с OrderBy - его реализация довольно интересна, реализация метода GetEnumerator такая:
Интересная деталь это как разделены OrderedEnumerable<TElement,TKey> и OrderedEnumerable, дело в том, что OrderedEnumerable выделен в базовый класс для того, чтобы хранить ссылку на следующий OrderedEnumerable, поскольку скорее всего у этих двух последовательностей будут разные TKey, поэтому хранить их вместе не удастся, для этого используется базовый класс без TKey, который определяет только то, что последовательность сортируется, а за то как именно сортируется - отвечает наследник.
Также и с EnumerableSorter<TElement,TKey>:EnumerableSorter, это параллельная иерархия, задача которой отсортировать исходную последовательность, но нужно также выстроить правильную иерархия enumerableSorter'ов, по которой первый OrderBy имеет высший приоритет, второй ThenBy - приоритет ниже, третий ThenBy - приоритет еще ниже и так далее.
Это делается в методе GetEnumerableSorter:
В итоге если будет вызван enumerator этой последовательности, то будет аллоцировано как минимум 4 массива, buffer, map, результирующий массив и массив ключей, поэтому чтобы не аллоцировать 4 массив метод ToArray и ToList на OrderedEnumerable дублирует метод GetEnumerator:
Из некоторых оптимизаций, если после orderBy идет skip или take, то вычисление будет оптимизировано, в новом core, была запилена поддержка IPartition для OrderedIEnumerable, при последовательности arr.OrderBy(x=>x).Skip(1):
И соответсвенно вызываются другие методы для сортировки, которым не нужно перебирать всю последовательность, достаточно отсортировать только часть
Также оптимизированы методы First и Last, и аналоги OrDefault, поскольку теперь OrderedEnumerable реализует IPartition, то эти методы вызывают:
(* ошибка CachingComparer возвращает true или false учитывая это, правильно - CachingComparer возвращает число >0 или <0 учитывая это *)
На самом деле это очень простой метод, он просто создает внутри себя Lookup, метод GetEnumerator замыкается на метод GetEnumerator у Lookup, возвращает либо последовательность IEnumerable<IGrouping<TKey, TValue>>, либо IEnumerable<TValue> , зависит от перегрузки
А выглядит вот так:
На самом деле это одна из возможных перегрузок, метод GroupBy очень удобен:
Рассмотрим последнюю:
Заметьте, что если передается предикат, то вычисление Count становится крайне не выгодно, но все-равно выгоднее чем
time(enumerable.Where(predicate).Count()) > time(enumerable.Count(predicate)
На этом все, в итоге понятно, что LINQ очень хорошо оптимизирован и может выпрямлять и оптимизировать вычисления, когда это возможно (Where().Select()....Select() или OrderBy().Skip().Take()). Это достигается интерфейсами IPartition, IIListProvider и классом Iterator, также умной реализацией классов-итераторов
На List все забили, он имеет крайне неоптимальный вариант выделения памяти, например нужны выполнить вставку 100 элементов, будем делать в лоб
for(int i=0;i<100'i++) _list.Add(i);В итоге на это все будет выделено 6 массивов с длинами 4 8 16 32 64 128, и в итоге List будет хранить 100 элементов. На каждом шаге выполняется копирование, если это копирование структур, представьте сколько памяти придется перемещать, но зато обращение к элементам очень быстрое
ToList работает так, если enumerable реализует IIListProvider, то вызывает IIListProvider.ToList, если нет то вызывается конструктор List(Ienumerable), в котором проверяется реализует ли enumerable ICollection, если да, то вызывает метод ICollection.CopyTo, если же нет то берется enumerator и начинают выделяться массивы, сначала 4 элемента, потом массив удваивается и происходит копирование всех старых элементов в новый.Эта вакханалия заканчивается когда общий размер массива становится более 0X7FEFFFFF(2146435071), тогда массив начинает расти на это количество элементов, максимальный размер нельзя задать самостоятельо, но зато можно задать изначально, если воспользоваться конструктором new List(int capacity), тогда сразу выделится массив в capacity элементов и нужно будет вручную выполнить его заполнение(кстати такого метода расширения не существует)
Теперь о том как работает ToArray();
- Если enumerable реализует IIListProvider, вызвать метод IIListProvider.ToArray, если нет
- Если нет, выполнить EnumerableHelpers.ToArray(), который
- Проверяет реализует ли последовательность ICollection, если да выполняет копирование вызывая ICollection.Copy, если нет
- Создает структуру LargeArrayBuilder, которая
- Берет enumerator, выделяет массив длинной 8 элементов и начинает его заполнять, при расширении не копирует весь массив, а создает новый размером (min(_current.Length, _maxCapacity - current.Length))