Блог переехал. Актуальная версия поста находится по адресу: 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[]) - Длины по каждому измерению массива (только для одномерных массивов с заданной нижней границей и многомерных массивов)
- Нижние индексы по каждому измерению массива (только для одномерных массивов с заданной нижней границей и многомерных массивов)
- Элементы массива
Комментариев нет:
Отправить комментарий