среда, 1 августа 2012 г.

Duck typing или “так ли прост старина foreach?”

Я думаю, что многие разработчики знают, что цикл foreach в языке C# не так прост, каким он кажется на первый взгляд. Для начала давайте ответим на вопрос: «А что нужно, чтобы конструкция foreach успешно компилировалась?». Интуитивным ответом на этот вопрос кажется что-то типа: «Реализация классом интерфейса IEnumerable или IEnumerable<T>.». Однако, это не так, ну, или не совсем так.

Полный ответ на этот вопрос такой: «Для того чтобы конструкция foreach успешно компилировалась необходимо, чтобы у объекта был метод GetEnumerator(), который вернет объект с методом MoveNext() и свойством Current, а если такого метода нет, то тогда будем искать интерфейсы IEnumerable и IEnumerable<T>».

Причин у такого «утиного» поведения две.

Давайте вспомним старые времена языка C# 1.0, когда язык был простым и понятным, и в нем не было никаких обобщений (generics), LINQ-ов и других замыканий. Но раз не было generic-ов, то «обобщение» и повторное использование было основано на полиморфизме и типе object, что, собственно и делалось в классах коллекций и их итераторов.

В качестве этих самых итераторов выступали пара интерфейсов IEnumerable и IEnumerator, при этом последний в свойстве Current возвращал object. А раз так, то использование интерфейса IEnumerator для перебора элементов строго типизированной коллекции значимых типов приводило бы к упаковке и распаковке этого значения на каждой итерации, что, согласитесь, может быть весьма накладно, когда речь идет о столь распространенной операции как перебор элементов.

Чтобы решить эту проблему и было принято решение использовать хак с утиной типизацией, и забить немного на принципы ООП в угоду производительности. В таком случае, класс мог реализовать интерфейс IEnumerable явно и предоставить дополнительный метод GetEnumerator(), который бы возвращал строготипизированный енумератор, свойство Current которого возвращало конкретный тип, например, DateTime без какой либо упаковки.

Ок. Мы разобрались с «динозаврами», а как насчет реального мира? Ведь на дворе, все же не каменный век, СОМ-ы уже дали дуба, Дон Бокс уже не пишет книг, и в нашу с вами дверь уже во всю ломятся гики, навязывая нам всякие функциональные вкусности. Есть ли какие-то выгоды от подобного поведения сейчас?

Можно подумать, что после появления обобщенных версий интерфейсов IEnumerable<T> и IEnumerator<T> трюк с утиной типизацией уже не нужен, но это не совсем так. Если посмотреть внимательно на классы коллекций, такие как List<T>, то можно обратить внимание, что этот класс (как и все остальные коллекции в BCL) реализуют интерфейс IEnumerable<T> явно (explicitely), предоставляя при этом дополнительный метод GetEnumerator():

// Псевдокод!
public class List<T> : IEnumerable
<T>
{
   
// Итератор класса List<T>
    // Это структура, причем изменяемая!!!
    public struct Enumerator : IEnumerator<T>, IDisposable
    { }

   
public List<T>.Enumerator GetEnumerator() { return new Enumerator(this
); }

   
// Явная реализация интерфеса
    IEnumerator<T> IEnumerator
<T>.GetEnumerator()
    {
       
return GetEnumerator();
    }
}

Да, все правильно. Метод GetEnumerator() возвращает экземпляр итератора, который является изменяемой структурой (ведь итератор содержит «указатель» на текущий элемент списка). А изменяемые значимые типы по мнению многих, являются самой острой пилой на платформе .NET, способной искалечить ногу даже весьма опытным разработчикам.

ПРИМЕЧАНИЕ
Да-да. Я знаю, что я уже все уши прожужжал изменяемыми енумераторами вообще и изменяемыми значимыми типами в частности, но здесь-то мы с вами помимо всего прочего попробуем найти объяснение причин такого поведения. Так что потерпите еще немного:)

Все дело в том, что использование структуры в качестве итератора совместно с «утиной» природой цикла foreach предотвращает от выделения памяти в куче при использовании этой конструкции:

var list = new List<int> { 1, 2, 3 };

// Вызываем List<T>.Enumerator GetEnumerator
foreach (var i in
list)
{ }

// Вызываем IEnumerable<T> GetEnumerator
foreach (var i in (IEnumerable<int>)list)
{ }

В первом примере, за счет «утиной» природы вызывается метод GetEnumerator() класса List, возвращающий объект значимого типа, который будет спокойно себе жить в стеке без каких либо дополнительных выделений памяти в управляемой куче. Во втором же случае, мы приводим переменную list к интерфейсу, что приведет к вызову метода интерфейса и, соответственно, упаковке итератора. Да, разработчики языка C# положили на полиморфизм и ряд других принципов ООП только ради повышения эффективности.

var list = new List<int> {1, 2, 3};

var x1 = new { Items = ((IEnumerable<int>)list).GetEnumerator() };
while
(x1.Items.MoveNext())
{
   
Console
.WriteLine(x1.Items.Current);
}
           

Console
.ReadLine();

var x2 = new { Items = list.GetEnumerator() };
while
(x2.Items.MoveNext())
{
   
Console.WriteLine(x2.Items.Current);
}

Именно по этой причине первый цикл while выведет ожидаемые 1, 2, 3, а второй цикл while … ну, проверьте сами.

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

ПРИМЕЧАНИЕ
Только не стоит сразу же пользоваться этим примером при реализации собственных итераторов или других вспомогательных классов. Использование структур – это оптимизация сама по себе, использование же изменяемых структур – это серьезнейшее решение, так что вы должны очень четко отдавать себе отчет в том, какие выгоды вы получаете, что готовы настолько пожертвовать безопасностью.

Небольшое дополнение: а для чего нужен вызов Dispose?

Еще одной особенностью реализации цикла foreach является то, что он вызывает метод Dispose итератора. Ниже представлена упрощенная версия кода, генерируемая компилятором при переборе переменной list в цикле foreach:

{
   
var
enumerator = list.GetEnumerator();
   
try
    {
       
while
(enumerator.MoveNext())
        {
           
int
current = enumerator.Current;
           
Console
.WriteLine(current);
        }
    }
   
finally
    {
        enumerator.Dispose();
    }
}

Может возникнуть резонный вопрос о том, откуда у итератора могут возникнуть управляемые ресурсы? Ну, да, при переборе коллекции в памяти и правда им взяться не откуда, но не стоит забывать, что енумераторы в языке C# могут использовать не только как итераторы для коллекций в памяти; нам никто не мешает сделать итератор, возвращающий построчно содержимое файла:

public static class FileEx
{
   
public static IEnumerable<string> ReadByLine(string
path)
    {
       
if (path == null
)
           
throw new ArgumentNullException("path"
);
       
return
ReadByLineImpl(path);
    }

   
private static IEnumerable<string> ReadByLineImpl(string
path)
    {
       
using (var sr = new StreamReader
(path))
        {
           
string
s;
           
while ((s = sr.ReadLine()) != null
)
               
yield return
s;
        }
    }
}



foreach (var line in FileEx.ReadByLine("D:\\1.txt"
))
{
   
Console.WriteLine(line);
}

Итак, у нас есть метод ReadByLine, в котором мы открываем файл, безусловно, являющийся ресурсом и закрывает … когда? Явно не каждый раз, когда управление покидает метод ReadByLineImpl, ведь тогда я закрою его столько раз, сколько в этом файле находится строк.

На самом деле, файл будет закрыт один раз, как раз таки при вызове метода Dispose итератора, который происходит в блоке finally цикла foreach. Это один из тех редких случаев на платформе .NET, когда блок finally не вызывается автоматически, а вызывается исключительно «ручками». Так что если вы вдруг будете итерироваться по некоторой последовательности вручную, то не стоит забывать о том, что итератор может-таки содержать ресурсы, и было бы очень даже неплохо очистить их с помощью явного вызова метода Dispose итератора.

ПРИМЕЧАНИЕ
Подробнее об итераторах в языке C# можно почитать в заметке … Итераторы в языке C#.

З.Ы. А кто сразу сможет ответить на такой вопрос: а зачем мне нужно два метода ReadByLine и ReadByLineImpl, почему бы мне не воспользоваться лишь одним методом?

З.Ы.Ы. Кстати, блок foreach это далеко не единственный пример утиной типизации в языке C#, а сколько еще примеров вы можете вспомнить?

20 комментариев:

  1. >>а сколько еще примеров вы можете вспомнить?
    Ну лично я только два, один из которых еще не зарелизился.
    linq и async/await

    ОтветитьУдалить
  2. @jack128: в смысле foreach и async/await? Или 2 помимо foreach?

    ОтветитьУдалить
  3. 1) linq. Чтобы использовать query syntax применительно к т ипу MyLinqType нужно реализовать в типе(или в виде extension методов) методы Select/Where/SelectMany/Join/OrderBy ect определенной сигнатуры. Причем не обязательно реализовывать все методы, можно лишь некоторые из них.
    И тогда можно будет писать так:
    MyLinqType myVar = ..
    var .. = from x in myVar where .. select ...

    2) async/await. Там, AFAIK суть таже самая. У типа MyAwaitType должен быть метод GetAwaitor() который имеет какой то там(не помню) набор методов. И тогда можно будет написать
    MyAwaitType myAwaitVar = ...
    await myAwaitVar;

    ОтветитьУдалить
  4. @jack128: да, все верно.

    Я, навскидку, помню еще как минимум один случай использования duck typing.

    ОтветитьУдалить
  5. >>СОМ-ы уже дали дуба
    За это тебя надо лишить MVP )

    ОтветитьУдалить
  6. >>З.Ы. А кто сразу сможет ответить на такой вопрос: а зачем мне нужно два метода ReadByLine и ReadByLineImpl, почему бы мне не воспользоваться лишь одним методом?

    Чтоб эксепшен был в месте вызова, а при попытке итерации?

    ОтветитьУдалить
  7. >> А кто сразу сможет ответить на такой вопрос: а зачем мне нужно два метода ReadByLine и ReadByLineImpl, почему бы мне не воспользоваться лишь одним методом?
    В вашем случае исключение будет бросаться при попытке создать итератор, а если бы вы всё впихнули в один метод, то исключение бы бросалось при попытке совершить первую итерацию. Такова природа компиляции блока итераторов
    >> Кстати, блок foreach это далеко не единственный пример утиной типизации в языке C#, а сколько еще примеров вы можете вспомнить?
    Кроме уже перечисленных - dynamic, но в runtime

    ОтветитьУдалить
  8. @Max: "нет, нет, все что угодно, но только не это" (с)

    Дык, уже лет этак надцать даже Дон Бокс не может на эти COM-ы смотреть:))

    @Victor H, @Unknown: Да, по поводу исключений - все верно.

    @Unknown: ну, dynamic представляет собой утиную типизацию не на уровне компилятора, а на уровне рантайма (как вы сами об этом и заметили). я же имел ввиду другие места использования утиной типизации компилятором.

    ОтветитьУдалить
  9. попробую угадать:
    1) конструирование ExpressionTree, компилятор не требует, чтобы тип System.Linq.Expression с фабричными методами Constant\Convert etc находился в System.Core.
    2) System.Runtime.CompilerServices.ExtensionAttribute...
    3) Collection initializers

    ОтветитьУдалить
  10. вот кста http://rsdn.ru/forum/dotnet/4829209.1.aspx

    ОтветитьУдалить
  11. @Vladimir: ух ты! Я про ExpressionTree не знал.

    Я так понимаю, что с ExtensionAttribute используется тот же самый трюк, что и с атрибутом ContractArgumentValidatorAttribute, который используется в Code Contracts для превращения метода в проверку предусловия.

    @jack128: да, спасибо за ссылку.

    ОтветитьУдалить
  12. >> var x2 = new { Items = list.GetEnumerator() };
    >> while (x2.Items.MoveNext())
    >> {
    >> Console.WriteLine(x2.Items.Current);
    >> }

    Никак не могу понять, почему здесь Current всегда 0. Как будто каждый раз снова вызывается GetEnumerator().

    ОтветитьУдалить
  13. В данном случае создается анонимный класс со свойством Items, которое возвращает каждый раз копию исходного итератора, а раз так, то MoveNext вызывается на временной копии и не изменяет настоящий итератор.

    ОтветитьУдалить
  14. Сергей, спасибо за ответ.

    Если я всё правильно понял, то метод GetEnumerator() возвращает структуру, которая располагается в стеке. У анонимного типа Items - свойство типа Get/Set, т.е. мы присваиваем копию енумератора внутри экземпляра анонимного типа. В дальнейшем мы обращаемся к свойству get анонимного типа, которое внутри является методом и этот метод возвращает нам новую копию енумератора. Который, соответственно, проинициализирован "с нуля".

    Если всё правильно, то вроде уложилось в голове :)

    ОтветитьУдалить
  15. Серёж, у тебя там опечаточка маленькая в строке где метод интерфейса explicitly реализуется:

    IEnumerator(Of T) IEnumerator(Of T).GetEnumerator() { }

    Интерфейс должен быть IEnumerable(Of T).

    PS. А как код вставлять? Угловые кавычки режутся, не ожидал такого от блогспота..

    ОтветитьУдалить
  16. Что-то немножко гонево:

    1) "// Вызываем IEnumerable GetEnumerator
    foreach (var i in (IEnumerable)list)
    { } "
    Это не афектит производительность, так как упаковка произойдёт один раз - при получении итератора.
    И вообще всё различие будет в том, что в первом случае на одно копирование больше в стеке, во втором случае на одно копирование больше в куче. Это будет афектить производительность, но не так сильно как было бы при упаковке.

    И соответственно
    2) "Именно по этой причине первый цикл while выведет ожидаемые 1, 2, 3, а второй цикл while … ну, проверьте сами. "
    Причины абсолютно разные. Во втором случае вы по сути объявили метод, который каждый раз возвращает новый объект в стэк. Естественно алгоритм не работает, но это не имеет отношения в тому, к чему вы привели объект. Попробуйте сделать двойное приведение, что бы убедиться.

    п.с. Если кто-то видит в чём я не прав - прошу рассказать в чем я ошибся.

    ОтветитьУдалить
    Ответы
    1. Гонево в том, что копирование в стеке - существенно более эффективная операция, чем выделение памяти в куче, копирование в куче, а потом чистка кучи.

      В случае одного цикла - разницы не будет. Но при наличии вложенных циклов, и большого внешнего и небольшого внутреннего, мы получим аллокацию в куче на каждую внешнюю итерацию. Которых может быть 100 500. Вот тогда, разница уже будет вполне существенная.

      И соответственно:
      > Во втором случае вы по сути объявили метод, который каждый раз возвращает новый объект в стэк.
      Причины именно такие, как я описал. Свойство возвращает экземпляр значимого типа по значению, а значит внутреннее состояние итератора не будет меняться, когда на нем будут дергать MoveNext. А вот если при конструировании анонимного типа привести итератор к ссылочному типу, то свойство Items станет полноценно мутабельным свойством этого объекта, что позволит внешнему коду изменять его внутрненнее состояние.

      Удалить
    2. О, спасибо за ответ! Кстати, спасибо за статью)

      1) Согласен. Просто из текста я понял, что упаковка должна выполняться при каждой итерации цикла, для которого создаётся итератор.

      2) Тут я пытаюсь сказать, что причина разного поведения не в том, что вызываете вы метод, который возвращает упакованный объект или метод, который возвращает структуру в стэке. - в результате и того и другого действия получатся ничем не отличающиеся объекты в стеке. Но причина в типе объявленного свойства. Другими словами, если вместо анонимного типа использовать именованный тип, то не будет иметь значение вызвали мы IEnumerable.GetEnumearator:IEnumerator или вызвали ли мы List.GetEnumerator:Enumerator
      И соответственно я оспариваю слова "Именно по этой причине первый цикл while выведет ожидаемые 1, 2, 3, а второй цикл while …"

      Либо я неправильно что-то прочитал/понял.

      Удалить