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