Структура объектов в памяти

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

Внутренняя структура экземпляров типов

Перед тем как начинать рассуждение о строении управляющих блоков системы типов давайте посмотрим на сам объект, на экземпляр любого класса. Если мы создадим в памяти экземпляр любого ссылочного типа, будь то класс или же упакованная структура, то состоять он будет всего из трех полей: SyncBlockIndex (который на самом деле не только он), указатель на описатель типа и данные. Область данных может содержать очень много полей, но, не умаляя общности, ниже в примере полагаем, что в данных содержится одно поле. Так, если представить эту структуру графически, то мы получим следующее:

System.Object


  ----------------------------------------------
  |  SyncBlkIndx |   VMT_Ptr    |     Data     |
  ----------------------------------------------
  |  4 / 8 байт  |  4 / 8 байт  |  4 / 8 байт  |
  ----------------------------------------------
  |  0xFFF..FFF  |  0xXXX..XXX  |      0       |
  ----------------------------------------------
                 ^
                 | Сюда ведут ссылки на объект. Т.е. не в начало, а на VMT

  Sum size = 12 (x86) | 24 (x64)

Т.е. фактически размер экземпляра типа зависит от конечной платформы, на которой будет работать приложение.

Далее давайте проследуем по указателю VMT_Ptr и посмотрим, какая структура данных лежит по этому адресу. Для всей системы типов этот указатель является самым главным: именно через него работает и наследование, и реализация интерфейсов, и приведение типов, и много чего еще. Этот указатель - отсылка в систему типов .NET CLR, паспорт объекта, по которому CLR осуществляет приведение типов, понимает объем памяти, занимаемый объектом, именно при помощи него GC так лихо обходит объект, определяя, по каким адресам лежат указатели на объекты, а по каким - просто числа. Именно через него можно узнать вообще все об объекте и заставить CLR отрабатывать его по-другому. А потому именно им и займемся.

Структура Virtual Methods Table

Описание самой таблицы доступно по адресу в GitHub CoreCLR, и если отбросить все лишнее (а там 4381 строка), выглядит она следующим образом:

Это версия из CoreCLR. Если смотреть на структуру полей в .NET Framework, то она будет отличаться расположением полей и расположением отдельных битов системной информации из двух битовых полей m_wFlags и m_wFlags2.

```cpp // Low WORD is component size for array and string types (HasComponentSize() returns true). // Used for flags otherwise. DWORD m_dwFlags;

// Base size of instance of this class when allocated on the heap
DWORD m_BaseSize;

WORD  m_wFlags2;

// Class token if it fits into 16-bits. If this is (WORD)-1, the class token is stored in the TokenOverflow optional member.
WORD  m_wToken;

// <NICE> In the normal cases we shouldn't need a full word for each of these </NICE>
WORD  m_wNumVirtuals;
WORD  m_wNumInterfaces;

```

Согласитесь, выглядит несколько пугающе. Причем пугающе выглядит не то, что тут всего 6 полей (а где все остальные?), а то, что для достижения этих полей, необходимо пропустить 4,100 строк логики. Я лично ожидал тут увидеть что-то готовое, чего не надо дополнительно вычислять. Однако, тут все совсем не так просто: поскольку методов и интерфейсов в любом типе может быть различное количество, то и сама таблица VMT получается переменного размера. А это в свою очередь означает, что для достижения ее наполнения надо вычислять, где находятся все ее оставшиеся поля. Но давайте не будем унывать и попытаемся сразу получить выгоду из того, что мы уже имеем: мы, пока что, понятия не имеем, что имеется ввиду под другими полями (разве что два последних), зато поле m_BaseSize выглядит заманчиво. Как подсказывает нам комментарий, это - фактический размер для экземпляра типа. Мы только что нашли sizeof для классов! Попробуем в бою?

Итак, чтобы получить адрес VMT мы можем пойти двумя путями: либо сложным, получив адрес объекта, а значит и VMT:

```csharp class Program { public static unsafe void Main() { Union x = new Union(); x.Reference.Value = "Hello!";

    // Первым полем лежит указатель на место, где лежит указатель на VMT
    // - (IntPtr*)x.Value.Value - преобразовали число в указатель (сменили тип для компилятора)
    // - *(IntPtr*)x.Value.Value - взяли по адресу объекта адрес VMT
    // - (void *)*(IntPtr*)x.Value.Value - преобразовали в указатель
    void *vmt = (void *)*(IntPtr*)x.Value.Value;

    // вывели в консоль адрес VMT;
    Console.WriteLine((ulong)vmt);
}

[StructLayout(LayoutKind.Explicit)]
public class Union
{
    public Union()
    {
        Value = new Holder<IntPtr>();
        Reference = new Holder<object>();
    }

    [FieldOffset(0)]
    public Holder<IntPtr> Value;

    [FieldOffset(0)]
    public Holder<object> Reference;
}

public class Holder<T>
{
    public T Value;
}

} ```

Либо простым, используя .NET FCL API:

    var vmt = typeof(string).TypeHandle.Value;

Второй путь конечно же проще (хоть и дольше работает). Однако знание первого очень важно с точки зрения понимания структуры экземпляра типа. Использование второго способа добавляет чувство уверенности: если мы вызываем метод API, то вроде как пользуемся задокументированным способом работы с VMT, а если достаем через указатели, то нет. Однако не стоит забывать, что хранение VMT * - стандартно для практически любого ООП языка и для .NET платформы в целом: эта ссылка всегда находится на одном и том же месте, как самое часто используемое поле класса. А самое часто используемое поле класса должно идти первым, чтобы адресация была без смещения и, как результат, была быстрей. Отсюда делаем вывод, что в случае классов положение полей на скорость влиять не будет, а вот у структур - самое часто используемое поле можно поставить первым. Хотя, конечно же для абсолютного большинства .NET приложений это не даст вообще никакого эффекта: не для таких задач создавалась эта платформа.

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

Почему sizeof есть для Value Type, но нет для Reference Type? На самом деле вопрос открытый т.к. никто не мешает рассчитать размер ссылочного типа. Единственное обо что можно споткнуться - это не фиксированный размер двух ссылочных типов: Array и String. А также Generic группы, которая зависит целиком и полностью от конкретных вариантов. Т.е. оператором sizeof(..) мы обойтись не смогли бы: необходимо работать с конкретными экземплярами. Однако никто не мешает команде CLR сделать метод вида static int System.Object.SizeOf(object obj), который бы легко и просто возвращал бы нам то, что надо. Так почему же Microsoft не реализовала этот метод? Есть мысль, что платформа .NET в их понимании опять же - не та платформа, где разработчик будет сильно переживать за конкретные байты. В случае чего можно просто доставить планок в материнскую плату. Тем более что большинство типов данных, которые мы реализуем, не занимают такие большие объемы.

Но не будем отвлекаться. Итак, чтобы получить размер экземпляра класса, чей размер фиксированн, достаточно написать следующий код:

unsafe int SizeOf(Type type)
{
    MethodTable *pvmt = (MethodTable *)type.TypeHandle.Value.ToPointer();
    return pvmt->Size;
}

[StructLayout(LayoutKind.Explicit)]
public struct MethodTable
{
    [FieldOffset(4)]
    public int Size;
}

class Sample
{
    int x;
}

// ...

Console.WriteLine(SizeOf(typeof(Sample)));

Итак, что мы только что сделали? Первым шагом мы получили указатель на таблицу виртуальных методов. После чего мы считываем размер и получаем 12 - это сумма размеров полей SyncBlockIndex + VMT_Ptr + поле x для 32-разрядной платформы. Если мы поиграемся с разными типами, то получим примерно следующую таблицу для x86:

Тип или его определение	Размер	Комментарий
Object	12	SyncBlk + VMT + пустое поле
Int16	12	Boxed Int16: SyncBlk + VMT + данные (выровнено по 4 байта)
Int32	12	Boxed Int32: SyncBlk + VMT + данные
Int64	16	Boxed Int64: SyncBlk + VMT + данные
Char	12	Boxed Char: SyncBlk + VMT + данные (выровнено по 4 байта)
Double	16	Boxed Double: SyncBlk + VMT + данные
IEnumerable	0	Интерфейс не имеет размера: надо брать obj.GetType()
List\	24	Не важно сколько элементов в List, занимать он будет одинаково т.к. хранит данные он в array, который не учитывается
GenericSample\	12	Как видите, generics прекрасно считаются. Размер не поменялся, т.к. данные находятся на том же месте, что и у boxed int. Итог: SyncBlk + VMT + данные
GenericSample\	16	Аналогично
GenericSample\	12	Аналогично
GenericSample\	16	Аналогично
string	14	Это значение будет возвращено для любой строки, т.к. реальный размер должен считаться динамически. Однако он подходит для размера под пустую строку. Прошу заметить, что размер не выровнен по разрядности: по сути это поле использоваться не должно
int[]{1}	24554	Для массивов в данном месте лежат совсем другие данные, также их размер не является фиксированным, потому его необходимо считать отдельно

Как видите, когда система хранит данные о размере экземпляра типа, то она фактически хранит данные для ссылочного вида этого типа (т.е. в том числе для ссылочного варианта значимого). Давайте сделаем некоторые выводы:

Если вы хотите знать, сколько займет значимый тип как значение, используйте sizeof(TType)
Если вы хотите рассчитать, чего вам будет стоить боксинг, то вы можете округлить sizeof(TType) в большую сторону до размера слова процессора (4 или 8 байт) и прибавить еще 2 слова (2 * sizeof(IntPtr)). Или же взять это значение из VMT типа.
Рассчет выделеного объем памяти в куче представлен для следующих типов:
1. Обычный ссылочный тип фиксированного размера: мы можем забрать размер экземпляра из VMT;
2. Cтрока, необходимо вручную считать ее размер (это вообще редко когда может понадобиться, но, согласитесь, интересно)
3. Массив, то его размер также рассчитывается отдельно: на основании размера его элементов и их количества. Эта задачка может оказаться куда более полезной: ведь именно массивы первые в очереди на попадание в LOH

System.String

Про строки в вопросах практики мы поговорим отдельно: этому, относительно небольшому, классу можно выделить целую главу. А в рамках главы про строение VMT мы поговорим про строение строк на низком уровне. Для хранения строк применяется стандарт UTF16. Это значит, что каждый символ занимает 2 байта. Дополнительно в конце каждой строки хранится null-терминатор – значение, которое идентифицирует окончание строки. Также в экземпляре хранится длина строки в виде Int32 числа - чтобы не считать длину каждый раз, когда она понадобится (про кодировки мы поговорим отдельно). На схеме ниже представлена информация о занимаемой памяти строкой:

  // Для .NET Framework 3.5 и младше
  ----------------------------------------------------------------------------------------------------
  |  SyncBlkIndx |    VMTPtr     |  ArrayLength   |     Length     |   char   |   char   |   Term    |
  ----------------------------------------------------------------------------------------------------
  |  4 / 8 байт  |  4 / 8 байт   |    4 байта     |    4 байта     |  2 байта |  2 байта |  2 байта  |
  ----------------------------------------------------------------------------------------------------
  |      -1      |  0xXXXXXXXX   |        3       |        2       |     a    |     b    |   <nil>   |
  ----------------------------------------------------------------------------------------------------

  Term – null terminator
  Sum size = (8|16) + 2 * 4 + Count * 2 + 2 -> округлить в большую сторону по разрядности. (24 байта в примере)
  Count – количество символов в строке, не считая терминальный

  // Для .NET Framework 4 и старше
  -----------------------------------------------------------------------------------
  |  SyncBlkIndx |    VMTPtr     |     Length     |   char   |   char   |   Term    |
  -----------------------------------------------------------------------------------
  |  4 / 8 байт  |  4 / 8 байт   |    4 байта     |  2 байта |  2 байта |  2 байта  |
  -----------------------------------------------------------------------------------
  |      -1      |  0xXXXXXXXX   |        2       |     a    |     b    |   <nil>   |
  -----------------------------------------------------------------------------------
  Term - null terminator
  Sum size = (8|16) + 4 + Count * 2 + 2) -> округлить в большую сторону по разрядности. (20 байт в примере)
  Count – количество символов в строке, не считая терминальный
 ```
Перепишем наш метод, чтобы научить его считать размер строк:

 ```csharp
unsafe int SizeOf(object obj)
{
    var majorNetVersion = Environment.Version.Major;
    var type = obj.GetType();
    var href = Union.GetRef(obj).ToInt64();
    var DWORD = sizeof(IntPtr);
    var baseSize = 3 * DWORD;

    if (type == typeof(string))
    {
        if (majorNetVersion >= 4)
        {
            var length = (int)*(int*)(href + DWORD /* skip vmt */);
            return DWORD * ((baseSize + 2 + 2 * length + (DWORD-1)) / DWORD);
        }
        else
        {
            // on 1.0 -> 3.5 string have additional RealLength field
            var arrlength = *(int*)(href + DWORD /* skip vmt */);
            var length = *(int*)(href + DWORD /* skip vmt */ + 4 /* skip length */);
            return DWORD * ((baseSize + 4 + 2 * length + (DWORD-1)) / DWORD);
        }
    }
    else
    if (type.BaseType == typeof(Array) || type == typeof(Array))
    {
        return ((ArrayInfo*)href)->SizeOf();
    }
    return SizeOf(type);
}

Где SizeOf(type) будет вызывать старую реализацию - для фиксированных по длине ссылочных типов.

Давайте проверим код на практике:

    Action<string> stringWriter = (arg) =>
    {
        Console.WriteLine($"Length of `{arg}` string: {SizeOf(arg)}");
    };

    stringWriter("a");
    stringWriter("ab");
    stringWriter("abc");
    stringWriter("abcd");
    stringWriter("abcde");
    stringWriter("abcdef");
}

-----

Length of `a` string: 16
Length of `ab` string: 20
Length of `abc` string: 20
Length of `abcd` string: 24
Length of `abcde` string: 24
Length of `abcdef` string: 28

Расчеты показывают, что размер строки увеличивается не линейно, а ступенчато на каждые два символа. Это происходит потому, что размер каждого символа - 2 байта, а конечный размер должен без остатка делиться на разрядность процессора (в примере x86), почему происходит соответствующее выравнивание размера строки на 2 байта. Результат нашей работы прекрасен: мы можем посчитать, во что нам обошлась та или иная строка. Последним этапом нам осталось узнать, как расчитать размер массивов в памяти.

Массивы

Строение массивов несколько сложнее: ведь у массивов могут быть варианты их строения:

Они могут хранить значимые типы, а могут хранить ссылочные
Массивы могут быть как одномерными, так и многомерными
Каждое измерение(мера) может начинаться как с 0, так и с любого другого числа (это на мой взгляд очень спорная возможность, избавляющая программиста от необходимости в написании arr[i - startIndex] на уровне FCL). Сделано это, вроде как, для совместимости с другими языками, к примеру, в Pascal индексация массива может начинаться не с 0, а с любого числа, однако мне кажется, что это лишнее.

Отсюда возникает некоторая путаность в реализации массивов и невозможность точно предсказать размер конечного массива: мало перемножить количество элементов на их размер. Хотя, конечно, для большинства случаев этого будет достаточно. Важным размер становится, когда мы боимся попасть в LOH. Однако у нас и тут возникают варианты: мы можем просто накинуть к размеру, подсчитанному "на коленке", какую-то константу сверху (например, 100), чтобы понять, перешагнули мы границу в 85000 или нет. Однако, в рамках данного раздела задача несколько другая: понять структуру типов. На нее и посмотрим:

  // Заголовок
  ----------------------------------------------------------------------------------------
  |   SBI   |  VMT_Ptr |  Total  |  Len_1  |  Len_2  | .. |  Len_N  |  Term   | VMT_Child |
  ----------------------------------opt-------opt------------opt-------opt--------opt-----
  |  4 / 8  |  4 / 8   |    4    |    4    |    4    |    |    4    |    4    |    4/8    |
  ----------------------------------------------------------------------------------------
  | 0xFF.FF | 0xXX.XX  |    ?    |    ?    |    ?    |    |    ?    | 0x00.00 | 0xXX.XX  |
  ----------------------------------------------------------------------------------------

  - opt: опционально
  - SBI: Sync Block Index
  - VMT_Child: присутствует, только если массив хранит данные ссылочного типа
  - Total: присутствует для оптимизации. Общее количество элементов массива с учетом всех размерностей
  - Len_2..Len_N, Term: присутствуют, только если размерность массива более 1 (регулируется битами в VMT->Flags)

Как мы видим, заголовок типа хранит данные об измерениях массива: их число может быть как 1, так и достаточно большим: фактически их размер ограничивается только null-терминатором, означающим, что перечисление закончено. Данный пример доступен полностью в файле GettingInstanceSize, а ниже я приведу только его самую важную часть:

public int SizeOf()
{
    var total = 0;
    int elementsize;

    fixed (void* entity = &MethodTable)
    {
        var arr = Union.GetObj<Array>((IntPtr)entity);
        var elementType = arr.GetType().GetElementType();

        if (elementType.IsValueType)
        {
            var typecode = Type.GetTypeCode(elementType);

            switch (typecode)
            {
                case TypeCode.Byte:
                case TypeCode.SByte:
                case TypeCode.Boolean:
                    elementsize = 1;
                    break;
                case TypeCode.Int16:
                case TypeCode.UInt16:
                case TypeCode.Char:
                    elementsize = 2;
                    break;
                case TypeCode.Int32:
                case TypeCode.UInt32:
                case TypeCode.Single:
                    elementsize = 4;
                    break;
                case TypeCode.Int64:
                case TypeCode.UInt64:
                case TypeCode.Double:
                    elementsize = 8;
                    break;
                case TypeCode.Decimal:
                    elementsize = 12;
                    break;
                default:
                    var info = (MethodTable*)elementType.TypeHandle.Value;
                    elementsize = info->Size - 2 * sizeof(IntPtr); // sync blk + vmt ptr
                    break;
            }
        }
        else
        {
            elementsize = IntPtr.Size;
        }

        // Header
        total += 3 * sizeof(IntPtr); // sync blk + vmt ptr + total length
        total += elementType.IsValueType ? 0 : sizeof(IntPtr); // MethodsTable for refTypes
        total += IsMultidimensional ? Dimensions * sizeof(int) : 0;
    }

    // Contents
    total += (int)TotalLength * elementsize;

    // align size to IntPtr
    if ((total % sizeof(IntPtr)) != 0)
    {
        total += sizeof(IntPtr) - total % (sizeof(IntPtr));
    }
    return total;
}

Этот код учитывает все вариации типов массивов, и может быть использован для расчета его размера:

Console.WriteLine($"size of int[]{{1,2}}: {SizeOf(new int[2])}");
Console.WriteLine($"size of int[2,1]{{1,2}}: {SizeOf(new int[1,2])}");
Console.WriteLine($"size of int[2,3,4,5]{{...}}: {SizeOf(new int[2, 3, 4, 5])}");

---
size of int[]{1,2}: 20
size of int[2,1]{1,2}: 32
size of int[2,3,4,5]{...}: 512

Выводы к разделу

На данном этапе мы научились нескольким достаточно важным вещам. Первое - мы разделили для себя ссылочные типы на три группы: ссылочные типы фиксированного размера, generic типы и ссылочные типы переменного размера. Также мы научились понимать структуру конечного экземпляра любого типа (про структуру VMT я пока молчу. Мы там поняли целиком пока что только одно поле: а это тоже большое достижение). Будь то ссылочный тип фиксированного размера (там все предельно просто) или неопределенного размера: массив или строка. Неопределенного потому, что его размер будет определен при создании. С generic типами на самом деле все просто: для каждого конкретного generic типа создается своя VMT, в которой будет проставлен конкретный размер.

Таблица методов в Virtual Methods Table (VMT)

Объяснение работы Methods Table, по большей части носит академический характер: ведь в такие дебри лезть - это как самому себе могилу рыть. С одной стороны, такие закрома таят что-то будоражащее и интересное, хранят некие данные, которые еще больше раскрывают понимание о происходящем. Однако, с другой стороны, все мы понимаем, что Microsoft не будет нам давать никаких гарантий, что они оставят свой рантайм без изменений и, например, вдруг не передвинут таблицу методов на одно поле вперед. Поэтому, оговорюсь сразу:

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

Ну все, предупредил. Теперь давайте окунемся в мир как говорится зазеркалья. Ведь до сих пор всё зазеркалье сводилось к знаниям структуры объектов: а её по-идее мы и так должны знать хотя бы примерно. И по своей сути эти знания зазеркальем не являются, а являются скорее входом в зазеркалье. А потому вернемся к структуре MethodTable, описанной в CoreCLR:

```cpp // Low WORD is component size for array and string types (HasComponentSize() returns true). // Used for flags otherwise. DWORD m_dwFlags;

// Base size of instance of this class when allocated on the heap
DWORD m_BaseSize;

WORD  m_wFlags2;

// Class token if it fits into 16-bits. If this is (WORD)-1, the class token is stored in the TokenOverflow optional member.
WORD  m_wToken;

// <NICE> In the normal cases we shouldn't need a full word for each of these </NICE>
WORD  m_wNumVirtuals;
WORD  m_wNumInterfaces;

```

А именно к полям m_wNumVirtuals и m_wNumInterfaces. Эти два поля определяют ответ на вопрос "сколько виртуальных методов и интерфейсов существует у типа?". В этой структуре нет никакой информации об обычных методах, полях, свойствах (которые объединяют методы). Т.е. эта структура никак не связана с рефлексией. По своей сути и назначению эта структура создана для работы вызова методов в CLR (и на самом деле в любом ООП: будь то Java, C++, Ruby или же что-то еще. Просто расположение полей будет несколько другим). Давайте рассмотрим код:

```csharp public class Sample { public int _x;

 public void ChangeTo(int newValue)
 {
     _x = newValue;
 }

 public virtual int GetValue()
 {
     return _x;
 }

}

public class OverridedSample : Sample { public override GetValue() { return 666; } }

```

Какими бы бессмысленными не казались эти классы, они нам вполне сгодятся для описания их VMT. А для этого мы должны понять, чем отличаются базовый тип и унаследованный в вопросе методов ChangeTo и GetValue.

Метод ChangeTo присутствует в обоих типах: при этом его нельзя переопределять. Это значит, что он может быть переписан так, и ничего не поменяется:

 public class Sample
 {
     public int _x;

     public static void ChangeTo(Sample self, int newValue)
     {
         self._x = newValue;
     }

     // ...
 }

// Либо в случае если бы он был struct
 public struct Sample
 {
     public int _x;

     public static void ChangeTo(ref Sample self, int newValue)
     {
         self._x = newValue;
     }

     // ...
 }

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

Заранее поясню, почему все объяснения вокруг наследования строятся вокруг примеров на статических методах: по сути все методы - статические. И экземплярные и нет. В памяти нет поэкземплярно скомпилированных методов для каждого экземпляра класса. Это занимало бы огромное количество памяти: проще одному и тому же методу каждый раз передавать ссылку на экземпляр той структуры или класса, с которыми он работает.

Для метода GetValue все обстоит совершенно по-другому. Мы не можем просто взять и переопределить метод переопределением статического GetValue в унаследованном типе: новый метод получит только те участки кода, которые работают с переменной как с OverridedSample, а если с переменной работать как с переменной базового типа Sample, вызвать сможете только GetValue базового типа, поскольку вы понятия не имеете, какого типа на самом деле объект. Для того чтобы понимать, какого типа является переменная и, как результат, какой конкретно метод вызывается, мы можем поступить следующим образом:

void Main()
{
    var sample = new Sample();
    var overrided = new OverridedSample();

    Console.WriteLine(sample.Virtuals[Sample.GetValuePosition].DynamicInvoke(sample));
    Console.WriteLine(overrided.Virtuals[Sample.GetValuePosition].DynamicInvoke(sample));
}

public class Sample
{
    public const int GetValuePosition = 0;

    public Delegate[] Virtuals;

    public int _x;

    public Sample()
    {
        Virtuals = new Delegate[1] { 
            new Func<Sample, int>(GetValue) 
        };
    }

    public static void ChangeTo(Sample self, int newValue)
    {
        self._x = newValue;
    }

    public static int GetValue(Sample self)
    {
        return self._x;
    }
}

public class OverridedSample : Sample
{
    public OverridedSample() : base()
    {
        Virtuals[0] = new Func<Sample, int>(GetValue);
    }

    public static new int GetValue(Sample self)
    {
        return 666;
    }
}

В этом примере мы фактически строим таблицу виртуальных методов вручную, а вызовы делаем по позиции метода в этой таблице. Если вы поняли суть примера, то вы фактически поняли, как строится наследование на уровне скомпилированного кода: методы вызываются по своему индексу в таблице виртуальных методов. Просто когда вы создаете экземпляр некоторого унаследованного типа, то в его VMT по местам, где у базового типа находятся виртуальные методы, компилятор расположит указатели на переопределенные методы, скопировав из базового типа указатели на методы, которые не переопределялись. Таким образом, отличие нашего примера от реальной VMT заключается только в том, что когда компилятор строит эту таблицу, он заранее знает с чем имеет дело и создает таблицу правильного размера и наполнения сразу же: в нашем примере чтобы построить таблицу для типов, которые будут делать таблицу более крупной за счет добавления новых методов, придется изрядно попотеть. Но наша задача заключается в другом, а потому такими извращениями мы заниматься не станем.

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

Virtual Stub Dispatch (VSD) [In Progress]

Чтобы разобраться в этом вопросе, необходимо дополнительно вспомнить, что реализовать интерфейс можно двумя путями: сделать можно либо implicit реализацию, либо explicit. Причем сделать это можно частично: часть методов сделать implicit, а часть - explicit. Эта возможность на самом деле - следствие реализации и возможно даже не является заранее продуманной: реализуя интерфейс, вы показываете явно или неявно, что в него входит. Часть методов класса может не входить в интерфейс, а методы, существующие в интерфейсе, могут не существовать в классе (они, конечно, существуют в классе, но синтаксис показывает, что архитектурно частью класса они не являются): класс и интерфейс - это, в некотором смысле, - параллельные иерархии типов. Также, в плюс к этому, интерфейс - это отдельный тип, а значит у каждого интерфейса есть собственная таблица виртуальных методов: чтобы каждый смог вызывать методы интерфейса.

Давайте взглянем на таблицу: как бы могли выглядеть VMT различных типов:

interface IFoo	class A : IFoo	class B : IFoo
-> GetValue()	SampleMethod()	RunProcess()
-> SetValue()	Go()	-> GetValue()
	-> GetValue()	-> SetValue()
	-> SetValue()	LookToMoon()

VMT всех трех типов содержат необходимые методы GetValue и SetValue, однако они находятся по разным индексам: они не могут везде быть по одним и тем же индексам, поскольку была бы конкуренция за индексы с другими интерфейсами класса. На самом деле для каждого интерфейса создается интерфейс - дубль - для каждой его реализации в каждом классе. Имеем 633 реализации IDisposable в классах FCL/BCL? Значит имеем 633 дополнительных IDisposable интерфейса чтобы поддержать VMT to VMT трансляцию для каждого из классов + запись в каждом классе с ссылкой на его реализацию интерфейсом. Назовем такие интерфейсы частными интерфейсами. Т.е. каждый класс имеет свои собственные, частные интерфейсы, которые являются "системными" и являются прокси типами до реального интерфейса.

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

Диспетчеризация виртуальных методов через заглушки или Virtual Stub Dispatch (VSD) была разработана еще в 2006 году как замена таблицам виртуальных методов в интерфейсах. Основная идея этого подхода состоит в упрощении кодогенерации и последующего упрощения вызова методов, т.к. первичная реализация интерфейсов на VMT была бы очень громоздкой и требовала бы большого количества работы и времени для построения всех структур всех интерфейсов. Сам код диспетчеризации находится по сути в четырех файлах общим весом примерно в 6400 строк, и мы не строим целей понять его весь. Мы попытаемся в общих словах понять суть происходящих процессов в этом коде.

Всю логику VSD диспетчеризации можно разбить на два больших раздела: диспетчеризация и механизм заглушек (stubs), обеспечивающих кэширование адресов вызываемых методов по паре значений [тип;номер слота], которые их идентифицируют.

Для полного понимания протекающих при построении VSD процессов, давайте рассмотрим для начала их на очень высоком уровне, а затем - спустимся в самую глубь. Если говорить про механику диспетчеризации, то та откладывает их создание на потом, в силу логической параллельности иерархии интерфейсных типов, в силу того, что их в конечном счете станет очень много, и в силу того, что большую часть из них JIT никогда создавать не будет, т.к. наличие типов во Framework еще не означает, что их экземпляры будут созданы. Использование же традиционной VMT для частных интерфейсов создало бы ситуацию, при которой JIT пришлось бы создавать VMT для каждого частного интерфейса с самого начала. Т.е. создание каждого типа замедлилось бы как минимум в два раза. Основным классом, обеспечивающим диспетчеризацию, является класс DispatchMap, который внутри себя инкапсулирует таблицу типов интерфейсов, каждая из которых состоит из таблицы методов, входящих в эти интерфейсы. Каждый метод может быть, в зависимости от стадии своего жизненного цикла, в четырех состояниях: состояние заглушки типа "метод еще не был ни разу вызван, его надо скомпилировать и подложить новую заглушку на место старой", состояние заглушки типа "метод должен быть каждый раз найден динамически, т.к. не может быть определен однозначно", состояние заглушки типа "метод доступен по однозначному адресу, а потому вызывается без какого либо поиска", или же полноценное тело метода.

Рассмотрим строение этих структур с точки зрения их генерирования и структур данных, необходимых для этого.

DispatchMap

DispatchMap – это динамически строящаяся структура данных, являющаяся по своей сути основной структурой данных, на которую опирается работа интерфейсов в CLR. Структура ее выглядит следующим образом:

    DWORD: Количество типов = N
    DWORD: Тип №1
    DWORD: Количество слотов для типа №1 = M1
    DWORD: bool: смещения могут быть отрицательными
    DWORD: Слот №1
    DWORD: Целевой слот №1
    ...
    DWORD: Слот №M1
    DWORD: Целевой слот №M1
    ...
    DWORD: Тип №N
    DWORD: Количество слотов для типа №1 = MN
    DWORD: bool: смещения могут быть отрицательными
    DWORD: Слот №1
    DWORD: Целевой слот №1
    ...
    DWORD: Слот №MN
    DWORD: Целевой слот №MN

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

Для навигации по этой структуре данных предусмотрен класс EncodedMapIterator, который является итератором. Т.е. никакой другой доступ, кроме как foreach, к DispatchMap не предусмотрен. Мало того номера слотов получены как разница реального номера слота и ранее закодированного номера слота. Т.е. получить номер слота в середине таблицы можно, только просмотрев всю структуру с самого начала. Это вызывает множество вопросов касательно производительности работы вызова методов через интерфейсы: ведь если у нас массив объектов, реализующих некий интерфейс, то чтобы понять, какой метод необходимо вызвать, надо просмотреть всю таблицу реализаций. Т.е. по своей сути - найти нужный. Результатом на каждом шаге итерирования будет структура DispatchMapEntry, которая покажет, где находится целевой метод: в текущем типе или нет, и какой слот необходимо взять у типа, чтобы получить нужный метод.

// DispatchMapTypeID позволяет делать относительную адресацию методов. Т.е. отвечает на вопрос: относительно текущего типа где 
// находится необходимый метод? В текущем типе или же в другом?
//
// Идентификатор типа (Type ID) используется в карте диспетчеризации и хранит внутри себя один из следующих типов данных:
//   - специальное значение, говорящее, что это - "this" class
//   - специальное значение, показывающее, что это - тип интерфейса, не реализованный классом
//   - индекс в InterfaceMap
class DispatchMapTypeID
{
private:
    static const UINT32 const_nFirstInterfaceIndex = 1;

    UINT32 m_typeIDVal;

    // ...
}

struct DispatchMapEntry
{
private:
    DispatchMapTypeID m_typeID;
    UINT16            m_slotNumber;
    UINT16            m_targetSlotNumber;

    enum
    {
        e_IS_VALID = 0x1
    };

    UINT16 m_flags;

    // ...
}

TypeID Map

Любой метод в адресации по интерфейсам кодируется парой . TypeId - это, как следует из названия, идентификатор типа. Данное поле отвечает на вопросы: откуда берется этот идентификатор и каким образом его отразить на реальный тип. Класс TypeIDMap хранит карту типов как отражение некоторого TypeId на MethodTable конкретного типа, а также - дополнительно - в обратную сторону. Сделано это исключительно из соображений производительности. Построение этих хэш таблиц происходит динамически: по запросу TypeId относительно PTR_MethodTable возвращается либо FatId, либо просто Id. Это надо в некотором смысле просто помнить: FatId и Id - это просто два вида TypeId. И в некотором смысле это "указатель" на MethodTable, т.к. однозначно его идентифицирует.

TypeId - это идентификатор MethodTable. Он может быть двух видов: Id и FatId и по своей сути является обычным числом.

class TypeIDMap
{
protected:
    HashMap             m_idMap;  // Хранит map TypeID -> PTR_MethodTable
    HashMap             m_mtMap;  // Хранит map PTR_MethodTable -> TypeID1
    Crst                m_lock;
    TypeIDProvider      m_idProvider;
    BOOL                m_fUseFatIdsForUniqueness;
    UINT32              m_entryCount;

    // ...
}

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

Выводы

То, что для нас, как для программистов, на языке C# стало обыденностью и вросло корнями в наше сознание настолько, что мы даже не задумываясь понимаем, как делить приложение на классы и интерфейсы, порой реализовано так сложно для понимания, что требуются недели анализа исходных текстов для определения всех зависимостей и логики происходящего. То, что для нас настолько обыденно в использовании, что не вызывает тени сомнения в простоте реализации, на самом деле может скрывать эти сложности реализации. Это говорит нам о том, что инженеры, воплотившие данные идеи, подходили к решению проблем с большим умом, тщательно анализируя каждый шаг.

То описание, которое здесь дано, на самом деле очень поверхностное и короткое: оно очень высокоуровневое. Даже не смотря на то, что относительно любой книги по .NET мы погрузились очень глубоко, данное описание построения VSD и VMT является очень и очень высокоуровневым. Ведь код файлов, описывающих эти две структуры данных, занимает в сумме около 20,000 строк кода. Это еще не учитывая некоторые части, отвечающие за Generics.

Однако, это позволяет нам сделать несколько выводов:

Вызов статичных методов и экземплярных практически ничем не отличаются. А это значит, что нам не надо беспокоиться о том, что работа с экземплярными методами как-то повлияет на производительность. Производительность обоих методов абсолютно идентична при одинаковых условиях
Вызов виртуальных методов хоть и идет через таблицу VMT, но из-за того, что индексы заранее известны, на каждый вызов дополнительно приходится лишь единственное разыменование указателя. В почти во всех случаях это ни на что не повлияет: проседание производительности (если вообще можно так выразиться) будет настолько маленьким, что им в принципе можно пренебречь
Если говорить об интерфейсах, то тут стоит помнить о диспетчеризации и понимать, что работа через интерфейсы сильно усложняет реализацию подсистемы типов на низком уровне, приводя к возможным проседаниям в производительности, когда слишком часто, при вызове методов, отсутствует определенность в том, какой метод и какого класса вызывать у интерфейсной переменной. Однако, "интеллект" JIT компилятора позволяет в очень многих случаях не проводить вызовы через диспетчеризацию, а напрямую вызывать метод, интерфейс реализующего
Если вспомнить об обобщениях, то тут возникает еще один слой абстракции, который вносит сложность в поиск необходимых для вызова методов у типов, реализующих generic интерфейсы.

Раздел вопросов по теме

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

Ответ прост: это непокрытая возможность CLR при проектировании языка, CLR этот вопрос никак не ограничивает. Мало того, это с высокой долей вероятности будет добавлено в ближайших версиях C#, благо они выходят достаточно быстро. Рассмотрим пример:

void Main()
{
    var foo = new Foo();
    var boo = new Boo();

    ((IDisposable)foo).Dispose();
    foo.Dispose();
    ((IDisposable)boo).Dispose();
    boo.Dispose();
}

class Foo : IDisposable
{
    void IDisposable.Dispose()
    {
        Console.WriteLine("Foo.IDisposable::Dispose");
    }

    public void Dispose()
    {
        Console.WriteLine("Foo::Dispose()");
    }
}

class Boo : Foo, IDisposable
{
    void IDisposable.Dispose()
    {
        Console.WriteLine("Boo.IDisposable::Dispose");
    }

    public new void Dispose()
    {
        Console.WriteLine("Boo::Dispose()");
    }
}

Здесь мы вызываем четыре различных метода и результат их вызова будет таким:

Foo.IDisposable::Dispose
Foo::Dispose()
Boo.IDisposable::Dispose
Boo::Dispose()

Причем несмотря на то, что мы имеем explicit реализацию интерфейса в обоих классах, в классе Boo explicit реализацию интерфейса IDisposable для Foo получить не получится. Даже если мы напишем так:

((IDisposable)(Foo)boo).Dispose();

Все равно мы получим на экране все то же результат:

Boo.IDisposable::Dispose

Что плохого в неявных и множественных реализациях интерфейсов?

В качестве примера "наследования интерфейсов", что аналогично наследованию классов, можно привести следующей код:

    Class Foo
        Implements IDisposable

        Public Overridable Sub DisposeImp() Implements IDisposable.Dispose
            Console.WriteLine("Foo.IDisposable::Dispose")
        End Sub

        Public Sub Dispose()
            Console.WriteLine("Foo::Dispose()")
        End Sub

    End Class

    Class Boo
        Inherits Foo
        Implements IDisposable

        Public Sub DisposeImp() Implements IDisposable.Dispose
            Console.WriteLine("Boo.IDisposable::Dispose")
        End Sub

        Public Shadows Sub Dispose()
            Console.WriteLine("Boo::Dispose()")
        End Sub

    End Class

    ''' <summary>
    ''' Неявно реализует интерфейс
    ''' </summary>
    Class Doo
        Inherits Foo

        ''' <summary>
        ''' Переопределение явной реализации
        ''' </summary>
        Public Overrides Sub DisposeImp()
            Console.WriteLine("Doo.IDisposable::Dispose")
        End Sub

        ''' <summary>
        ''' Неявное перекрытие
        ''' </summary>
        Public Sub Dispose()
            Console.WriteLine("Doo::Dispose()")
        End Sub

    End Class

    Sub Main()
        Dim foo As New Foo
        Dim boo As New Boo
        Dim doo As New Doo

        CType(foo, IDisposable).Dispose()
        foo.Dispose()
        CType(boo, IDisposable).Dispose()
        boo.Dispose()
        CType(doo, IDisposable).Dispose()
        doo.Dispose()
    End Sub

В нем видно, что Doo, наследуясь от Foo, неявно реализует IDisposable, но при этом переопределяет явную реализацию IDisposable.Dispose, что приведет к вызову переопределения при вызове по интерфесу, тем самым показывая "наследование интерфейсов" классов Foo и Doo.

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

interface IA
{
    void M() { WriteLine("IA.M"); }
}

interface IB : IA
{
    override void IA.M() { WriteLine("IB.M"); } // explicitly named
}

interface IC : IA
{
    override void M() { WriteLine("IC.M"); } // implicitly named
}

Почему это ужасно? Ведь на самом деле это порождает целый класс возможностей. Теперь нам не нужно будет каждый раз реализовывать какие-то методы интерфейсов, которые везде реализовывались одинаково. Звучит прекрасно. Но только звучит. Ведь интерфейс - это протокол взаимодействия. Протокол - это набор правил, рамки. В нем нельзя допускать существование реализаций. Здесь же идет прямое нарушение этого принципа и введение еще одного: множественного наследования. Я, честно, сильно против таких доработок, но... Я что-то ушел в сторону.

DispatchMap::CreateEncodedMapping