пятница, 11 октября 2013 г.

Внутреннее устройство массивов в .NET

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/dotnet/arrays-internal-structure/.


Иногда бывает полезно понимать, как выглядит внутреннее представление объектов, с которыми мы работаем. В этой статье я хотел бы поговорить о массивах: как именно они хранятся в памяти, какие IL-команды используются для работы с ними, как выглядит ассемблерный код при обращении к их элементам. Я рассмотрю три вида массивов: single (T[]), rectangular (T[,]), jagged (T[][]). Также будет затронута тема массивов с ненулевой нижней границей (T[*]) и нюансов работы с ними.

При рассмотрении низкоуровневых данных (например, дампов памяти) следует понимать, что адреса различных объектов будут меняться от одного запуска программы к запуску. В примерах нас больше будет интересовать относительное размещение объектов. В качестве целевой архитектуры взята x86. Для удобства восприятия многие данные переведены из родной шестнадцатеричной формы в десятичную (за исключением адресов, они начинаются с префикса 0x). Данная статья не претендует на фундаментальное описание внутреннего представления массивов, скорее это просто краткий обзор организации различных массивов на низком уровне. В качестве реализации платформы рассматривается стандартная MS.NET, Mono обсуждать не будем.

Single array

Такие массивы часто называются также SZ-массивами (single-dimensional, zero-based) или векторами.

Создадим обычный int[]-массив (каждый элемент занимает 4 байта) длинной 5 элементов, который заполним числами от 0 до 4:

int[] a = new int[5];
for (int i = 0; i < 5; i++)
    a[i] = i;

В памяти он будет представлен следующим образом:

0x03022424           0  // SyncBlockIndex
0x03022428  0x61B9C448  // *MethodTable
0x0302242C           5  // a.Length
0x03022430           0  // a[0]
0x03022434           1  // a[1]
0x03022438           2  // a[2]
0x0302243C           3  // a[3]
0x03022440           4  // a[4]

Воспользуемся расширением отладчика SOS и через Immediate Window посмотрим чуть больше информации о нашем массиве:

.load sos.dll
!DumpArray 0x03022428
Name:        System.Int32[]
MethodTable: 61b9c448
EEClass:     6180c0d0
Size:        32(0x20) bytes
Array:       Rank 1, Number of elements 5, Type Int32
Element Methodtable: 61b9c480
[0] 03022430
[1] 03022434
[2] 03022438
[3] 0302243c
[4] 03022440

Тут всё достаточно просто. Переменная a указывает на адрес 0x03022428, по которому хранится указатель на таблицу методов соответствующего типа (в данном случае System.Int32[]), которая занимает 4 байта (для x64 — 8 байт). Перед ней находится SyncBlockIndex (отсчитывается от 1, 0 означает пустое значение; размер под x86 — 4 байта, под x64 — 8 байт). После *MethodTable идёт сначала размер массива, а затем по порядку все его элементы.

Для операций с SZ-массивами предусмотрены следующие IL-команды:

  • newarr <etype>: создание нового массива с элементами типа etype
  • ldelem <typeTok>: добавить значение элемента по заданному индексу в стек
  • ldelema <class>: добавить адрес элемента по заданному индексу в стек
  • ldlen: добавить длину массива в стек
  • stelem <typeTok>: заменить значение элемента по заданному индексу значением из стека

Обращение к элементу на уровне ассемблера имеет примерно следующий вид: [ebx+ecx*4+8]. Здесь ebx обозначает базовый адрес массива, ecx — индекс элемента (он умножается на 4, т.к. Int32 занимает в памяти 4 байта), 8 — смещение для нулевого элемента (пропускаем MethodTable и количество элементов массива, т.е. два значения по 4 байта).

Rectangular array

Создадим двумерный массив

int[,] a = new int[2, 3];
for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++)
        a[i, j] = i * 3 + j;

и по аналогии взглянем на дамп памяти:

0x03022444           0  // SyncBlockIndex
0x03022448  0x61B5E938  // *MethodTable
0x0302244C           6  // a.Length
0x03022450           2  // a.GetLength(0)
0x03022454           3  // a.GetLength(1)
0x03022458           0  // a.GetLowerBound(0)
0x0302245C           0  // a.GetLowerBound(1)
0x03022460           0  // a[0, 0]
0x03022464           1  // a[0, 1]
0x03022468           2  // a[0, 2]
0x0302246C           3  // a[1, 0]
0x03022470           4  // a[1, 1]
0x03022474           5  // a[1, 2]
!DumpArray 0x03022448
Name:        System.Int32[,]
MethodTable: 61b5e938
EEClass:     617fd0c4
Size:        52(0x34) bytes
Array:       Rank 2, Number of elements 6, Type Int32
Element Methodtable: 61b9c480
[0][0] 03022460
[0][1] 03022464
[0][2] 03022468
[1][0] 0302246c
[1][1] 03022470
[1][2] 03022474

Структура немного усложнилась. Сперва (как и в первом случае), идут SyncBlockIndex и *MethodTable (a указывает именно на *MethodTable, т.е. на 0x03022448). Далее точно также идёт длина массива, т.е. общее количество элементов, которые в нём содержатся. А после этого идут отличительные данные для rectangular-массива: длины по каждому измерению и нижние границы (их мы подробнее обсудим чуть позже, по умолчанию они равны нулю). Количество измерений массива (a.Rank) можно узнать из типа (System.Int32[,]). Далее идут непосредственно сами элементы.

Для работы с элементами rectangular-массива на IL-уровне нет специальных команд, приходится вызывать методы Get и Set. На уровне ассемблера для двумерного массива мы будем иметь инструкцию вида [ebx+ecx*4+18h]. ebx — базовый адрес массива, ecx — номер элемента (который высчитывается на основе индексов i, j), 18h — смещение (больше, чем в single-версии, т.к. теперь нам нужно пропустить больше служебных значений: 18h=24=6*4 — TypeHandle, a.Length, a.GetLength(0), a.GetLength(1), a.GetLowerBound(0), a.GetLowerBound(1)).

Jagged array

Создадим двумерный изломанный массив

int[][] a = new int[2][];
for (int i = 0; i < 2; i++)
{
    a[i] = new int[3];
    for (int j = 0; j < 3; j++)
        a[i][j] = i * 3 + j;
}

и по аналогии взглянем на дамп памяти:

0x03022478           0  // SyncBlockIndex (a)
0x0302247C  0x61B8D5BC  // *MethodTable (a)
0x03022480           2  // a.Length
0x03022484  0x617A4C8A  // *TypeDesc (int[])
0x03022488  0x03022494  // a[0]
0x0302248C  0x030224AC  // a[1]
0x03022490           0  // SyncBlockIndex (a[0])
0x03022494  0x61B9C448  // *MethodTable (a[0])
0x03022498           3  // a[0].Length
0x0302249C           0  // a[0][0]
0x030224A0           1  // a[0][1]
0x030224A4           2  // a[0][2]
0x030224A8           0  // SyncBlockIndex (a[1])
0x030224AC  0x61B9C448  // *MethodTable (a[1])
0x030224B0           3  // a[1].Length
0x030224B4           3  // a[1][0]
0x030224B8           4  // a[1][1]
0x030224BC           5  // a[1][2]
!DumpArray 0x0302247C
Name:        System.Int32[]
MethodTable: 61b8d5bc
EEClass:     618ab450
Size:        24(0x18) bytes
Array:       Rank 1, Number of elements 2, Type SZARRAY
Element Methodtable: 617a4c8a
[0] 03022494
[1] 030224ac

!DumpObj 0x0302247C
Name:        System.Int32[][]
MethodTable: 61b8d5bc
EEClass:     618ab450
Size:        24(0x18) bytes
Array:       Rank 1, Number of elements 2, Type SZARRAY
Fields:
None

!DumpArray 0x03022494
Name:        System.Int32[]
MethodTable: 61b9c448
EEClass:     6180c0d0
Size:        24(0x18) bytes
Array:       Rank 1, Number of elements 3, Type Int32
Element Methodtable: 61b9c480
[0] 0302249c
[1] 030224a0
[2] 030224a4

!DumpArray 0x030224AC
Name:        System.Int32[]
MethodTable: 61b9c448
EEClass:     6180c0d0
Size:        24(0x18) bytes
Array:       Rank 1, Number of elements 3, Type Int32
Element Methodtable: 61b9c480
[0] 030224b4
[1] 030224b8
[2] 030224bc

По сути int[][] представляет собой массив массивов. Т.е. это одномерный массив, элементами которого являются ссылки на другие массивы. Команда DumpArray не может нормально восстановить тип объекта, для этой цели необходимо пользоваться командой DumpObj.

Методы по работе с jagged-массивом на IL и ASM уровнях аналогичны single-массиву с той лишь разницей, что теперь нам необходимо перейти к нужному элементу одномерного массива не один раз, а несколько (в зависимости от количества размерностей). По адресу 0x03022484 находится указатель на TypeDesc для int[](тут можно почитать подробнее).

Non-zero based single array

Явно объявить одномерный массив с ненулевой нижней границей нельзя, для этого нам понадобится метод Array.CreateInstance, в который передаётся тип элементов, массив длин и массив нижних границ. Создадим элемент из 5-ти элементов с нижней границей 2:
Array a = Array.CreateInstance(typeof(int), new[] { 5 }, new[] { 2 });
for (int i = 2; i < 7; i++)
    a.SetValue(i, i);

Взглянем на соответствующий дамп памяти:

0x030224FC           0  // SyncBlockIndex
0x03022500  1639311728  // *MethodTable
0x03022504           5  // a.Length
0x03022508           5  // a.GetLength(0)
0x0302250C           2  // a.GetLowerBound(0)
0x03022510           2  // a[2]
0x03022514           3  // a[3]
0x03022518           4  // a[4]
0x0302251C           5  // a[5]
0x03022520           6  // a[6]
!DumpArray 0x03022500
Name:        System.Int32[]
MethodTable: 61b5e970
EEClass:     617fd110
Size:        40(0x28) bytes
Array:       Rank 1, Number of elements 5, Type Int32
Element Methodtable: 61b9c480
[0] 03022508
[1] 0302250c
[2] 03022510
[3] 03022514
[4] 03022518
[5] 0302251c
[6] 03022520

!DumpObj 0x03022500
Name:        System.Int32[*]
MethodTable: 61b5e970
EEClass:     617fd110
Size:        40(0x28) bytes
Array:       Rank 1, Number of elements 5, Type Int32
Fields:
None

Тип данного объекта: System.Int32[*]. Знак * означает, что CLR знает о ненулевой нижней границе. Синтаксис C# не позволяет явно объявить переменную такого типа, также запрещается явное обращение к его элементам посредствам стандартного синтаксиса, поэтому приходится пользоваться методами GetValue и SetValue.

Обратите внимание, что команда DumpArray не умеет корректно отображать тип одномерного массива с ненулевой нижней границей. Правильный тип можно получить, используя команду DumpObj.

Что касается структуры массива в памяти, то она полностью аналогична структуре rectangular-массива. Для доступа к элементам массива специальных IL-команд не предусмотрено, приходится вновь явно вызывать методы.

Non-zero based rectangular array

А теперь создадим двумерный массив 2 на 3 с нижними границами 4 и 5. Поможет нам в этом уже знакомый метод Array.CreateInstance:

Array a = Array.CreateInstance(typeof(int), new[] { 2, 3 }, new[] { 4, 5 });
for (int i = 4; i < 6; i++)
    for (int j = 5; j < 8; j++)
        a.SetValue(i * 3 + j - 17, i, j);

Дамп памяти:

0x03022588           0  // SyncBlockIndex
0x0302258C  1639311672  // *MethodTable
0x03022590           6  // a.Legnth
0x03022594           2  // a.GetLength(0)
0x03022598           3  // a.GetLength(1)
0x0302259C           4  // a.GetLowerBound(0)
0x030225A0           5  // a.GetLowerBound(1)
0x030225A4           0  // a[4, 5]
0x030225A8           1  // a[4, 6]
0x030225AC           2  // a[4, 7]
0x030225B0           3  // a[5, 5]
0x030225B4           4  // a[5, 6]
0x030225B8           5  // a[5, 7]
!DumpArray 0x0302258C
Name:        System.Int32[,]
MethodTable: 61b5e938
EEClass:     617fd0c4
Size:        52(0x34) bytes
Array:       Rank 2, Number of elements 6, Type Int32
Element Methodtable: 61b9c480
[4][5] 030225a4
[4][6] 030225a8
[4][7] 030225ac
[5][5] 030225b0
[5][6] 030225b4
[5][7] 030225b8

Заметим, что для rectangular-массивов с ненулевой нижней границей команда DumpArray прекрасно работает. Несложно понять, что структура хранения и организации rectangular-массива не зависит от нижней границы: представление в памяти всегда будет одинаковое, тип всегда будет System.Int32[,], IL и ASM инструкции будут аналогичны.

Резюме

Общее устройство массива выглядит следующим образом:
  • SyncBlockIndex (по отрицательному смещению)
  • *MethodTable (по нулевому смещению)
  • Общая длина массива
  • *TypeDesc для элементов массива (только для массивов из элементов ссылочного типа; int[][] является частным случаем, т.к. это массив из int[])
  • Длины по каждому измерению массива (только для одномерных массивов с заданной нижней границей и многомерных массивов)
  • Нижние индексы по каждому измерению массива (только для одномерных массивов с заданной нижней границей и многомерных массивов)
  • Элементы массива

Комментариев нет:

Отправить комментарий