Иногда бывает полезно понимать, как выглядит внутреннее представление объектов, с которыми мы работаем. В этой статье я хотел бы поговорить о массивах: как именно они хранятся в памяти, какие 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>
: создание нового массива с элементами типа etypeldelem <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.Length
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[]
)- Длины по каждому измерению массива (только для одномерных массивов с заданной нижней границей и многомерных массивов)
- Нижние индексы по каждому измерению массива (только для одномерных массивов с заданной нижней границей и многомерных массивов)
- Элементы массива