Массивы. Статические или динамические?

Сегодня поговорим об удобной и такой привычной возможности языка Object Pascal - массивах.
Поскольку многие операции с однотипными данными производятся с помощью массивов, то мы рассмотрим следующие моменты:
- скорость доступа к данным в массиве;
- удобство программирования и лаконичность кода;
- отсутствие ошибок при доступе к массивам.

Историческая справка.
Статические массивы существуют в Паскале очень давно. Они всегда имеют фиксированный размер и объявляются следующим образом:
type
TArray = array [0..15] of integer;
var
A: TArray;
Динамические массивы появились с приходом Delphi. Их основное удобство заключается в возможности изменения размера. Объявление динамического массива:
type
TDynArray = array of integer;
var
B: TDynArray;
Основные функции для работы с динамическим массивом:
SetLength - устанавливает новый размер массива.
Length - возвращает количество элементов в массиве.
Low - индекс первого элемента в массиве (всегда 0 для динамических массивов).
High - индекс последнего элемента в массиве.
Copy - возвращает подмножество элементов массива.
Slice - используется при передаче динамического массива в процедуры в качестве открытого массива (open arrays).
Переменная динамического массива (в нашем примере B) представляет собой обычный указатель (4 байта). В отличие от статического массива, где переменная (в нашем примере А) является хранилищем данных массива и имеет размер, равный произведению количества элементов на их размер.
На что же указывает переменная динамического массива?
На некую область памяти, где лежат собственно данные массива. То есть фактически на первый элемент массива. Но самое интересное, что по отрицательному смещению (то есть перед данными) лежат еще 2 четырехбайтовых счетчика. По смещению -4 находится индикатор количества элементов в массиве, а по смещению -8 находится счетчик ссылок на массив. То есть размер динамического массива всегда на 8 байт больше того, что занимают его элементы. За исключением того случая, когда количество элементов равно 0. Тогда переменная динамического массива никуда не указывает и имеет значение nil.
Зачем нужен счетчик ссылок? Он позволяет иметь несколько переменных, ссылающихся на одни и те же данные в массиве и не заботиться об управлении памятью. Компилятор самостоятельно следит за доступом к данным и при уменьшении счетчика ссылок до 0 освобождает всю память массива. Пример:
procedure Test;
var
B, C: TDynArray;
begin
SetLength( B, 10 );
C := B; // Мы копируем не данные массива B, а всего лишь указатель на него.
  // Но счетчик ссылок массива увеличился до двух.
end;
При выходе из процедуры компилятор видит, что обе переменные являются локальными, уменьшает счетчик ссылок на два и освобождает память, выделенную вызовом SetLength. Но можно было освободить массив и вручную вызовом SetLength( B, 0 ).
Автоматический менеджмент памяти компилятором на этом не заканчивается. Доступ к динамическим массивам (и длинным строкам, которые являются их разновидностью) синхронизирован. То есть к ним можно одновременно обращаться из разных потоков (threads) без необходимости в дополнительной синхронизации.
Такая архитектура динамических массивов позволяет компилятору свободно изменять размер памяти под него, перемещать в другие участки оперативной памяти, а программисту соответственно не заниматься рутиной.




 
Все в динамических массивах хорошо. Но иногда приходится отказываться от такой удобной возможности.
Дело в том, что доступ к элементам динамического массива примерно в три раза медленнее, чем у статического массива (по моим измерениям). Если размер данных фиксирован и все операции с ними производятся в одном месте кода, то можно просто заменить динамический массив статическим.
В случае интенсивной работы с элементами больших массивов (например, сортировка), когда число элементов в массиве меняется, а доступ к ним производится из разных объектов или модулей, то есть смысл отказаться от обоих типов массивов и перейти к работе через указатель на статический массив.
Это довольно простой метод, позволяющий при минимуме дополнительного кодирования получить скорость статических массивов и гибкость динамических. Пример:
type
// Элемент массива
TRecord = record
Name: string; // любые данные
Color: TColor;
end;

PRecords = ^TRecords; // тип указателя на массив
TRecords = array [0..0] of TRecord; // массив из одного элемента

// Собственно сам массив
TArray = record
Items: PRecords; // указатель на элементы массива
Count: integer; // число элементов в массиве
end;
var
A: TArray = ( Items: nil; Count: 0 );


procedure SetRecordsLen( var AArray: TArray; const Len: integer );
begin
// Перераспределяем память
ReallocMem( AArray.Items, Len * sizeof( TRecord ) );

// Если новый размер больше старого, то затираем новые элементы нулями
if Len > AArray.Count then
FillChar( AArray.Items[AArray.Count],
( Len - AArray.Count ) * sizeof( TRecord ), 0 );

// Запоминаем новый размер
AArray.Count:= Len;
end;
 
...
...
 
SetRecordsLen( A, 10 );
try
A.Items[2] := AItems[3];
A.Items[7].Name := A.Items[7].Name + '7';
A.Items[8].Color := clRed;
finally
SetRecordsLen( A, 0 ); // не забываем освободить память
end;
 
В данном примере статическому массиву, состоящему якобы из одного элемента выделяется гораздо большая память. Конечно, в опциях компилятора нужно отключить Range checking. Мы получаем высокую скорость и довольно простой способ работы с массивом. Однако следует помнить, что такой массив не обладает функциями автоматического менеджмента памяти. Так что за собой придется аккуратно убирать :)
Наш массив при желании вполне можно оформить и в виде класса. Если же размер массива изменяется часто, а особенно в случае, если таких массивов много, то очень рекомендую для увеличения скорости и уменьшения фрагментации памяти выделять память под элементы массива "пачками" по несколько штук.
Подобная техника применяется в стандартном классе TList. Его свойство Capacity отвечает как раз за это. Аналогичное поле Capacity можно добавить и к нашему массиву. При увеличении размера массива память нужно будет перераспределять только в том случае, если запрошенное количество элементов Count уже не помещается в выделенном количестве элементов Capacity.
 
Напоследок еще пару слов о безопасности кода в связи с массивами.
Самом собой, выход индекса за границы массива не приведет ни к чему хорошему. Будет либо испорчена память по соседству, либо получим EAccessViolation. Первый случай гораздо хуже и может приводить к чрезвычайно трудноуловимым ошибкам в работе программы.
Но сейчас я хочу сказать о довольно популярной ошибке, которая может возникнуть из-за различной природы переменных статического и динамического массивов. Вот пример кода:
type
TArray = array [0..15] of integer;
TDynArray = array of integer;
var
A: TArray;
B: TDynArray;
 
// Хотим обнулить память массивов
FillChar( A, sizeof( A ) ); // OK
 
FillChar( B, sizeof( B ) );
// Затираем указатель B на данные массива, поскольку размер переменной B равен 4 байта.
// Счетчик ссылок массива остается в некорректном состоянии.
 
FillChar( B, Length( B ) * sizeof( integer ) );
// Самый худший случай. Затираем указатель B на данные массива и
// еще кучу памяти за ним, не имеющей никакого отношения к массиву.
Подобная ситуация может возникнуть при работе со многими функциями, принимающего в качестве параметров нетипизированные переменные. Для предотвращения такой ситуации нужно обращаться не к переменной динамического массива, а к его первому элементу. Верный код:
FillChar( B[0], Length( B ) * sizeof( integer ) );
А еще лучше:
FillChar( B[Low( B )], Length( B ) * sizeof( integer ) );
Такой код позволит в любой момент менять тип массива со статического на динамический и наоборот, не ползая по коду в поисках подозрительных мест.
Кстати, функции Length, Low и High довольно прожорливые по времени. Поэтому в местах интенсивных вычислений их значения желательно кэшировать. Вот пример неудачного и весьма тормозного кода:
while i < High( B ) do
begin
B[i + 1]:= B[i + 1] + B[i]; // конкретная операция с данными здесь неважна
inc( i );

Применять такой код стоит только в том случае, если в процессе работы цикла размер массива изменяется.
 
Хочу в очередной раз подчеркнуть, что нет никакого смысла заниматься всеми этими оптимизациями, если они не оказывают никакого влияния на реальную производительность приложения. Какая разница, если при нажатии пользователем на кнопку массив будет обработан за три миллисекунды, а не за одну. Кроме усложнения кода - никакой.
А исходный код программы собственно и является программой. И все ошибки проистекают именно из него. Да, да, из обычного текста, который мы редактируем. Поэтому борьба за лаконичность и ясность исходного кода должна быть второй натурой, если есть желание в нем разобраться хотя бы через пару дней, не говоря уж об исправлении ошибок.
Но исправление ошибок мы тоже как-нибудь заоптимизируем :)
 
Владимир Волосенков uno@tut.by