Реализация обобщенных типов в CLR

157

Едва ли можно встретить программу, не использующую какую-нибудь коллекцию, такую как List<T> или Dictionary<K,V>. Крупные приложения могут одновременно использовать сотни тысяч экземпляров коллекций. Правильно выбранный или написанный вами тип коллекций, наиболее полно отвечающий вашим потребностям, может значительно повысить производительность многих приложений. Поскольку, начиная с версии .NET 2.0, коллекции весьма тесно связаны с реализацией обобщенных типов (generics) в CLR, в этой статье мы рассмотрим структуру обобщенных типов, а в следующей опишем коллекции.

Достаточно часто возникает необходимость создать класс или метод, который одинаково хорошо может работать с данными любых типов. Полиморфизм и наследование способны помочь в этом, но до определенной границы; методы, которые должны быть абсолютно универсальными, принимают параметры типа System.Object, что влечет две основные проблемы обобщенного программирования в .NET до версии .NET 2.0:

Это весьма серьезные проблемы. Чтобы убедиться в этом, рассмотрим одну из простых коллекций В .NET 1.1 - ArrayList. Ниже приводится упрощенная ее реализация, которая, впрочем, вполне отчетливо демонстрирует проблемы, обозначенные выше:

public class ArrayList : IEnumerable, ICollection, IList //, ... 
{
    private object[] items;
    private int size;

    public ArrayList(int initialCapacity)
    {
        items = new object[initialCapacity];
    }

    public void Add(object item)
    {
        if (size < items.Length - 1)
        {
            items[size] = item;
            ++size;
        }
        else
        {
            // Создать массив большего размера, скопировать 
            // элементы и затем добавить в него item
        }
    }

    public object this[int index]
    {
        get
        {
            if (index < 0 || index >= size) 
			    throw new IndexOutOfBoundsException(index);
            return items[index];
        }
        set
        {
            if (index < 0 || index >= size) 
			    throw new IndexOutOfBoundsException(index);
            items[index] = value;
        }
    }
    // Остальные методы опущены
}

Мы выделили в коде все вхождения объектов типа System.Object, являющегося «обобщенным» типом, на котором основана коллекция. Хотя такое решение выглядит вполне допустимым, фактическое его использование оказывается далеко от идеала:

ArrayList employees = new ArrayList(7);
employees.Add(new Employee("Катя"));
employees.Add(new Employee("Вася"));
Employee first = (Employee)employees[0];

Такое неуклюжее приведение к типу Employee необходимо лишь потому, что тип ArrayList не сохраняет информацию о типах своих элементов. Кроме того, он никак не ограничивает типы элементов, вставляемые в него, чтобы хоть как-то обеспечить общность их типов. Взгляните:

employees.Add(42); 	// Скомпилируется и будет работать!
Employee third = (Employee)employees[2]; 	// Скомпилируется, но возбудит исключение во время выполнения...

Действительно, число 42 не принадлежит коллекции служащих (employees), но мы нигде не определяем, что коллекция типа ArrayList может хранить только экземпляры определенного типа. Теоретически вполне возможно определить тип ArrayList, накладывающий такое ограничение, но операции с такой коллекцией оказались бы слишком дорогостоящими, зато инструкции, такие как employees.Add(42), было бы невозможно скомпилировать.

Это - проблема безопасности типов; «обобщенные» коллекции, опирающиеся на тип System.Object, не могут гарантировать безопасность типов на этапе компиляции и откладывают все проверки до этапа выполнения. Тогда, может быть, такой подход снимает проблемы производительности? Как оказывается, такая реализация имеет проблемы и с производительностью, когда в работе участвуют типы значений. Исследуем следующий код, где используется структура Point2D из предыдущей статьи (простой тип значения с целочисленными координатами X и Y точки на плоскости):

ArrayList line = new ArrayList(1000000);
for (int i = 0; i < 1000000; ++i)
{
    line.Add(new Point2D(i, i));
}

Каждый экземпляр типа Point2D, добавляемый в массив ArrayList, упаковывается, потому что метод Add принимает параметр ссылочного типа (System.Object). Этот фрагмент создаст 1 000 000 объектов Point2D и разместит их в динамической памяти. Как было показано ранее, в 32-разрядной системе 1 000 000 упакованных объектов Point2D займет 16 000 000 байт памяти (против 8 000 000 байт, которые займут простые значения типа Point2D). Кроме того, в массив ArrayList будет добавлен 1 000 000 ссылок, которые все вместе займут еще 4 000 000 байта, всего будет занято 20 000 000 байт (как показано на рисунке ниже), хотя достаточно было бы лишь 8 000 000 байт. В действительности это та самая проблема, что вынудила нас отказаться от идеи создать ссылочный тип Point2D; ArrayList вынуждает нас использовать коллекцию, которая может работать только со ссылочными типами!

Тип ArrayList, содержащий упакованные объекты Point2D

Можно ли как-то улучшить ситуацию? В действительности можно было бы реализовать свою коллекцию двумерных точек, как показано ниже (хотя, при этом придется также предусмотреть специализированную реализацию интерфейсов IEnumerable, ICollection и IList для точек...). Она полностью идентична «обобщенной» реализации ArrayList, но принимает значение типа Point2D везде, где раньше принимался object:

public class Point2DArrayList : IPoint2DEnumerable, IPoint2DCollection, IPoint2DList // ... 
{
    private Point2D[] items;
    private int size;

    public Point2DArrayList(int initialCapacity)
    {
        items = new Point2D[initialCapacity];
    }
	
    public void Add(Point2D item)
    {
        if (size < items.Length - 1)
        {
            items[size] = item;
            ++size;
        }
        else
        {
            // Создать массив большего размера, скопировать 
            // элементы и затем добавить в него item
        }
    }
    public Point2D this[int index]
    {
        get
        {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
            return items[index];
        }
        set
        {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
            items[index] = value;
        }
    }

    // Остальные методы опущены
}

Реализовав похожую коллекцию объектов Employee можно было бы решить проблему безопасности типов, описанную выше. К сожалению, создавать специализированные коллекции для каждого типа данных совершенно непрактично. Определенно, данную функцию должен выполнять компилятор языка, как это сделано в .NET 2.0 - чтобы обеспечить поддержку обобщенных типов в классах и методах, и одновременно гарантировать безопасность типов и избавиться от принудительной упаковки.

Обобщенные типы в .NET

Обобщенные классы и методы позволяют писать по-настоящему обобщенный код, без применения System.Object с одной стороны и без специализации для каждого типа данных - с другой. Ниже приводится пример реализации обобщенного типа List<T>, взамен предыдущей нашей реализации ArrayList, которая решает обе проблемы, безопасности типов и принудительной упаковки:

public class List<T> : IEnumerable<T>, ICollection<T>, IList<T>  // ... 
{
    private T[] items;
    private int size;
    public List(int initialCapacity)
    {
        items = new T[initialCapacity];
    }
	
    public void Add(T item)
    {
        if (size < items.Length - 1)
        {
            items[size] = item;
            ++size;
        }
        else
        {
            // Создать массив большего размера, скопировать 
            // элементы и затем добавить в него item
        }
    }
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= size) 
			    throw new IndexOutOfBoundsException(index);
            return items[index];
        }
        set
        {
            if (index < 0 || index >= size) 
			    throw new IndexOutOfBoundsException(index);
            items[index] = value;
        }
    }

    // Остальные методы опущены
}

Тем, кто не знаком с синтаксисом обобщенных типов в языке C#, рекомендуем обратиться к статьям в разделе Руководство по C# - Часть 2, связанным с обобщениями.

Если прежде вам приходилось писать обобщенные классы или методы, вы наверняка знаете, насколько просто преобразовать псевдообобщенный код на основе System.Object в действительно обобщенный код, задействовав параметры обобщенного типа (generic type parameters). Не менее просто использовать обобщенные классы и методы, просто подставляя аргументы обобщенного типа (generic type arguments), где это необходимо:

List<Employee> employees = new List<Employee>(7);
employees.Add(new Employee("Kate"));
Employee first = employees[0]; // Приведение типа не требуется
employees.Add(42); // He компилируется!

List<Point2D> line = new List<Point2D>(1000000);
for (int i = 0; i < 1000000; ++i) 
{
    // Упаковка не производится, сохраняется по значению
    line.Add(new Point2D(i, i)); 
}

Как по волшебству, обобщенная коллекция обеспечивает безопасность типа (она не позволяет сохранять в ней элементы других типов) и не требует упаковки типов значений. Даже внутреннее хранилище - массив элементов - приспосабливается в соответствии с аргументом обобщенного типа: когда T соответствует типу Point2D, массив элементов получает тип Point2D[] и хранит значения, а не ссылки. Мы еще вернемся к этому волшебству ниже, а пока будем наслаждаться эффективным решением на уровне языка проблем обобщенного программирования.

Однако, похоже, что этого решения недостаточно, когда необходимо, чтобы обобщенные параметры обладали некоторыми дополнительными особенностями. Взгляните на метод, выполняющий поиск методом дихотомии в отсортированном массиве. Полностью обобщенная версия не в состоянии выполнить такой поиск, потому что System.Object не обладает механизмом сравнения:

public static int BinarySearch<T>(T[] array, T element) 
{
    // В некоторый момент потребуется выполнить сравнение:
    if (array[x] < array[y]) {
        // ...
    }
}

Класс System.Object не поддерживает статический оператор <, из-за чего попытка скомпилировать метод потерпит неудачу! В действительности мы должны убедить компилятор, что для любого аргумента обобщенного типа, передаваемого в метод, он сможет отыскать все необходимые реализации используемых им методов (включая операторы). Теперь настало время поговорить об ограничениях обобщенных типов.

Ограничения обобщенных типов

Ограничения обобщенных типов указывают компилятору, что лишь некоторые фактические типы могут использоваться в качестве аргумента при использовании обобщенного типа. Всего существует пять типов ограничений:

// T должен реализовать интерфейс:
public string Format<T>(T instance) where T : IFormattable 
{
    return instance.ToString("N", CultureInfo.CurrentUICulture);

    // Хорошо, T должен иметь метод IFormattable.ToString(string, IFormatProvider)
}

// T должен наследовать базовый класс:
public void Display<T>(T widget) where T : Employee 
{
    widget.Display(0, 0);
    
    // Хорошо, T должен наследовать класс Employee, имеющий метод Display(int, int)
}

// T должен иметь конструктор без параметров: 
public T Create<T>() where T : new() 
{
    return new T();
    
    // Хорошо, T имеет конструктор без параметров. Компилятор C# скомпилирует 'new Т()' в не самый 
    // оптимальный вызов Activator.CreateInstance<T>(), 
    // но для этого ограничения отсутствует эквивалент на языке IL
}

// T должен быть ссылочным типом:
public void ReferencesOnly<T>(T reference) where T : class
{ }

// T должен быть типом значения:
public void ValuesOnly<T>(T value) where T : struct
{ }

Для примера реализации поиска методом дихотомии, наиболее полезным будет ограничение, требующее реализации интерфейса (и действительно, это наиболее часто используемый тип ограничений). В частности, мы можем потребовать от T реализовать интерфейс IComparable и сравнивать элементы массива с помощью метода IComparable.CompareTo(). Однако IComparable не является обобщенным интерфейсом, а его метод CompareTo() принимает параметр типа System.Object, что приводит к упаковке типов значений. Очевидно, что должна существовать обобщенная версия интерфейса IComparable - интерфейс IComparable<T>, который с успехом можно было бы использовать в нашем примере:

public static int BinarySearch<T>(T[] array, T element)
    where T : IComparable<T>
{
    // В некоторый момент потребуется выполнить сравнение:
    if (array[x].CompareTo(array[y]) < 0)
    {
        // ...
    }
}

Эта версия реализации поиска методом дихотомии не вызывает упаковку при сравнении экземпляров типов значений, работает с любыми типами, реализующими интерфейс IComparable<T> (включая все встроенные простые типы, строки и многие другие), и обеспечивает безопасность типов, не требуя определять наличие возможности сравнения во время выполнения.

Ограничение интерфейса и IEquatable<T>

В предыдущей статье было показано, насколько важно для производительности переопределить метод Equals в типах значений и реализовать интерфейс IEquatable<T>. Почему этот интерфейс так важен? Взгляните на следующий фрагмент:

public static void CallEquals<T>(T instance)
{
    instance.Equals(instance);
}

Вызов Equals внутри метода транслируется в вызов виртуального метода Object.Equals, который принимает параметр System.Object, что вызывает упаковку типов значений. Это - единственная альтернатива, которая с точки зрения компилятора C# гарантированно будет доступна для любых типов T. Если мы хотим убедить компилятор, что T имеет метод Equals, принимающий параметр данного типа T, следует явно определить ограничение:

public static void CallEquals<T>(T instance) 
   where T : IEquatable<T> 
{
    instance.Equals(instance);
}

Наконец, нам может потребоваться дать возможность вызывающему коду использовать любой тип T и задействовать реализацию IEquatable<T>, если тип T предоставляет ее, чтобы избежать упаковки и обеспечить более высокую эффективность. В этом отношении довольно интересным выглядит подход, применяемый в реализации List<T>. Если бы класс List<T> требовал наличия ограничения IEquatable<T> для своего параметра обобщенного типа, его нельзя было бы использовать для хранения типов, не реализующих этот интерфейс. Поэтому List<T> не имеет ограничения IEquatable<T>. Для поддержки метода Contains (и других, проверяющих объекты на равенство) List<T> опирается на механизм проверки равенства объектов (equality comparer) - конкретную реализацию абстрактного класса EqualityComparer<T> (который, по стечению обстоятельств, реализует интерфейс EqualityComparer<T>, используемый непосредственно некоторыми коллекциями, включая HashSet<T> и Dictionary<K, V>).

Когда методу List<T>.Contains требуется вызвать Equals для сравнения двух элементов коллекции, он использует статическое свойство EqualityComparer<T>.Default, откуда извлекает реализацию механизма проверки равенства объектов, пригодную для сравнения экземпляров типа T, и вызывает его виртуальный метод Equals(T,T). Заполнение этого поля выполняет приватный статический метод EqualityComparer<T>.CreateComparer, который создает соответствующую реализацию при первом обращении и затем сохраняет ее для последующих вызовов.

Когда CreateComparer обнаруживает, что T реализует IEquatable<T>, он возвращает экземпляр GenericEqualityComparer<T>, имеющий ограничение IEquatable<T>, и вызывает Equals через интерфейс. В противном случае CreateComparer обращается к классу ObjectEqualityComparer<T>, не имеющему ограничений для типа T и вызывает виртуальный метод Equals класса Object.

Этот трюк, используемый классом List<T> для проверки равенства, может пригодиться и в других ситуациях. Когда ограничение определено, обобщенный класс или метод может использовать потенциально более эффективную реализацию, без проверки типа во время выполнения.

Как было показано выше, для математических операторов, таких как сложение и вычитание, не существует никаких ограничений обобщенных типов. Это означает, что нельзя написать обобщенный метод, использующий выражения, такие как a+b, с обобщенными параметрами. Стандартное решение, обеспечивающее возможность реализации обобщенных числовых алгоритмов заключается в использовании вспомогательной структуры, реализующей интерфейс IMath<T> с необходимыми арифметическими операциями, внутри обобщенного метода.

Исследовав значительную часть синтаксиса поддержки обобщенных типов в языке C#, мы можем перейти к их фактической реализации времени выполнения. Но, прежде чем углубиться в изучение этого вопроса, необходимо ответить на вопрос, - а существует ли вообще некое представление обобщенных типов во время выполнения? На этот вопрос легко можно ответить, заглянув в реализацию Reflection API, выполняющего операции с обобщенными типами во время выполнения:

Type openList = typeof(List<>);
Type listOfInt = openList.MakeGenericType(typeof(int));

IEnumerable<int> ints = (IEnumerable<int>)Activator.CreateInstance(listOfInt);

Dictionary<string, int> frequencies = new Dictionary<string, int>();

Type openDictionary = frequencies.GetType().GetGenericTypeDefinition();
Type dictStringToDouble = openDictionary
    .MakeGenericType(typeof(string), typeof(double));

Как здесь показано, мы можем динамически создавать обобщенные типы из существующих обобщенных типов и параметризовать «открытый» обобщенный тип для создания экземпляра «закрытого» обобщенного типа. Данный пример демонстрирует, что обобщенные типы являются обычными объектами и имеют представление времени выполнения, с которым мы сейчас и познакомимся.

Структура обобщенных типов в CLR

Синтаксически обобщенные типы CLR очень похожи на обобщенные типы Java и далее имеют некоторое сходство с шаблонами С++. Однако, как оказывается, их внутренняя реализация и ограничения, накладываемые на программы, использующие их, существенно отличаются от Java и С++.

Обобщенные типы - даже открытые, такие как List<T> - являются обычными объектами времени выполнения типа System.Type, и имеют таблицу методов и структуру EEClass. Обобщенные типы можно экспортировать из сборок (assemblies) и только одно определение обобщенного типа существует на этапе компиляции. Обобщенные типы не разворачиваются во время компиляции, но, как было показано выше, компилятор убеждается, что все операции с параметром обобщенного типа совместимы с указанными ограничениями.

Когда среде выполнения CLR требуется создать экземпляр закрытого обобщенного типа, такого как List<int>, он создает таблицу методов и структуру EEClass, опираясь на открытый тип. Как обычно, вновь созданная таблица методов содержит указатели на методы, которые компилируются «на лету» JIT-компилятором. Однако, при этом выполняется одна важная оптимизация: скомпилированные тела методов закрытых обобщенных типов, которые ссылаются на параметр типа, могут использовать совместно. Чтобы было понятнее, рассмотрим метод List<T>.Add() и попробуем скомпилировать его в инструкции процессора x86, когда T является ссылочным типом:

public void Add(T item) 
{
    if (size < items.Length - 1) 
    {
        items[size] = item;
        ++size;
    } else
        AllocateAndAddSlow(item);
}
; Код на языке ассемблера для x86, когда T является ссылочным типом,
; предполагается, что ECX содержит ссылку this, a EDX - ссылку на элемент
mov eax, dword ptr [ecx+4]			; items
mov eax, dword ptr [eax+4]			; items.Length
dec eax
cmp dword ptr [ecx+8], eax			; size < items.Length - 1
jge AllocateAndAddSlow
mov eax, dword ptr [ecx+4]
mov ebx, dword ptr [ecx+8]
mov dword ptr [eax+4*ebx+4], edx	; items[size] = item
inc dword ptr [eax+8]				; ++size

Очевидно, что реализация метода в машинном коде никак не зависит от типа T и будет работать с любым ссылочным типом. Это обстоятельство позволяет JIT-компилятору экономить ресурсы (время и память) и совместно использовать указатель из таблицы методов для List<T>.Add() во всех таблицах методов, где T является ссылочным типом.

Эта идея имеет продолжение, которое, впрочем, мы не будем исследовать. Например, если тело метода содержит выражение new T [10], это могло бы потребовать создания отдельной реализации метода для каждого типа T или, по крайней мере, способа получения T во время выполнения (например, через дополнительный скрытый параметр, передаваемый методу). Кроме того, мы не коснулись особенностей влияния ограничений на генерируемый код, но у вас уже не должно быть сомнений, что вызов методов интерфейса или виртуальных методов базовых классов будет выполняться одинаково, независимо от типа.

Все сказанное выше не относится к типам значений. Например, если в параметре T указать тип long, компилятор сгенерирует иные машинные инструкции для выражения items[size] = item, потому что вместо 4 необходимо скопировать 8 байт. Более крупные типы значений могут потребовать сгенерировать более одной инструкции; и так далее.

Все ссылочные реализации List<T>

Для демонстрации на рисунке выше изображены таблицы методов закрытых обобщенных типов, полученные нами с помощью расширения SOS.DLL, которые являются реализациями одного и того же открытого обобщенного типа. Например, рассмотрим класс BasicStack<T> с двумя методами, Push и Pop:

class BasicStack<T>
{
    private T[] items;
    private int topIndex;

    public BasicStack(int capacity = 42)
    {
        items = new T[capacity];
    }

    public void Push(T item)
    {
        items[topIndex++] = item;
    }

    public T Pop()
    {
        return items[--topIndex];
    }
}

Таблицы методов для BasicStack<string>, BasicStack<int[]>, BasicStack<int> и BasicStack<double> приводятся ниже. Обратите внимание, что для закрытых обобщенных типов, если в аргументе обобщенного типа был указан ссылочный тип, элементы таблиц методов (то есть адреса) совпадают, а для типов значений - нет:

Таблицы методов для обобщенного типа

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

Структура методов в дизассемблированном коде

Выше уже говорилось, что реализация обобщенных типов в .NET обеспечивает полную безопасность типов на этапе компиляции. Остается только убедиться, что при использовании типов значений с коллекциями обобщенных типов не происходит их упаковка. В действительности, поскольку JIT-компилятор генерирует отдельные реализации методов для каждого закрытого обобщенного типа, если в аргументе обобщенного типа был указан тип значения, необходимость в упаковке отпадает.

В заключение заметим, что обобщенные типы в .NET обладают существенными преимуществами, по сравнению с обобщенными типами в Java или шаблонами в С++. Механизм ограничений обобщенных типов несколько ограничен, в сравнении с "диким западом" языка С++, но гибкая возможность экспортирования обобщенных типов из сборок и преимущества производительности, которые дает генерация кода по требованию затмевают все недостатки.

Пройди тесты
Лучший чат для C# программистов