5.7. Реализация массивов

При реализации элементы массива размещаются в памяти последовательно. Если задан массив А, то адрес его элемента A(l) есть (см. рис. 5.2.):

addr (А) + size (element) * (/ - A.'First)

Например: адрес А(4) равен 20 + 4 * (4 - 1) = 32.

Сгенерированный машинный код будет выглядеть так:

L

oad R1,l Получить индекс

sub R1,A'First Вычесть нижнюю границу

multi R1 ,size Умножить на размер — > смещение

add R1 ,&А Добавить адрес массива — > адрес элемента

load R2,(R1) Загрузить содержимое

Вы, возможно, удивитесь, узнав, что для каждого доступа к массиву нужно столько команд! Существует много вариантов оптимизации, которые могут улучшить этот код. Сначала отметим, что если A'First — ноль, то нам не нужно вычитать индекс первого элемента; это объясняет, почему разработ­чики языка С сделали так, что индексы всегда начинаются с нуля. Даже если A'First — не ноль, но известен на этапе компиляции, можно преобразовать вычисление адреса следующим образом:

(addr (А) - size (element) * A'First) + (size (element) * i)

Первое выражение в круглых скобках можно вычислить при компиляции, экономя на вычитании во время выполнения. Это выражение будет известно во время компиляции при обычных обращениях к массиву:

A(I):=A(J);

но не в том случае, когда массив является параметром:

procedure Sort(A: A_Type) is

…

A(A'First+1):=A(J);

…

end Sort;

Основное препятствие для эффективных операций с массивом — умножение на размер элемента массива. К счастью, большинство массивов имеют про­стые типы данных, такие как символы или целые числа, и размеры их элемен­тов представляют собой степень двойки. В этом случае дорогостоящая опера­ция умножения может быть заменена эффективным сдвигом, так как сдвиг влево на n эквивалентен умножению на 2". В случае массива записей можно повысить эффективность (за счет дополнительной памяти), дополняя записи так, чтобы их размер был кратен степени двойки. Обратите внимание, что на переносимость программы это не влияет, но само улучшение эффективности не является переносимым: другой компилятор может скомпоновать запись по-другому.

Программисты, работающие на С, могут иногда повышать эффектив­ность обработки массивов, явно программируя доступ к элементам массива с помощью указателей вместо индексов. Следующие определения:

typedef struct {

int field;

} Rec;

Rec a[100];

могут оказаться более эффективными (в зависимости от качества оптимиза­ций в компиляторе) при обращении к элементам массива по указателю:

Rec* ptr;

C

for (ptr = &а; ptr < &a+100*sizeof(Rec); ptr += sizeof(Rec))

...ptr-> field...;

чем при помощи индексирования:

for(i=0; i<100;i++)

…a[i].field…

Однако такой стиль программирования чреват множеством ошибок; кроме того, такие программы тяжело читать, поэтому его следует применять только в исключительных случаях.

В языке С возможен и такой способ копирования строк:

while (*s1++ = *s2++)

в котором перед точкой с запятой стоит пустой оператор. Если компьютер поддерживает команды блочного копирования, которые перемещают со­держимое блока ячеек памяти по другому адресу, то эффективнее будет язык типа Ada, который допускает присваивание массива. Вообще, тем, кто программирует на С, следует использовать библиотечные функции, кото­рые, скорее всего, реализованы более эффективно, чем примитивный спо­соб, показанный выше.

Многомерные массивы могут быть очень неэффективными, потому что каждая лишняя размерность требует дополнительного умножения при вычис­лении индекса. При работе с многомерными массивами нужно также пони­мать, как размещены данные. За исключением языка Fortran, все языки хра­нят двумерные массивы как последовательности строк. Размещение

type T is array( 1 ..3, 1 ..5) of Integer;

показано на рис. 5.3. Такое размещение вполне естественно, поскольку сохраняет идентичность двумерного массива и массива массивов. Если в вычислении перебираются все элементы двумерного массива, проследите, чтобы последний индекс продвигался во внутреннем цикле:

intmatrix[100][200];

for(i = 0;i<100;i++)

for (j = 0; j < 200; j++)

m[i][j]=…;

Причина в том, что операционные системы, использующие разбиение на страницы, работают намного эффективнее, когда адреса, по которым проис­ходят обращения, находятся близко друг к другу.

Если вы хотите выжать из С-программы максимальную производитель­ность, можно игнорировать двумерную структуру массива и имитировать од­номерный массив:

m[]0[i]=…;

Само собой разумеется, что применять такие приемы не рекомендуется, а в случае использования их следует тщательно задокументировать.

Контроль соответствия типов для массива требует, чтобы попадание ин­декса в границы проверялось перед каждым доступом к массиву. Издержки этой проверки велики: два сравнения и переходы. Компиляторам для языков типа Ada приходится проделывать значительную работу, чтобы оптимизиро­вать команды обработки массива. Основной технический прием — использо­вание доступной информации. В следующем примере:

if A(I) = Key then ...

индекс I примет только допустимые для массива значения, так что никакая проверка не нужна. Вообще, оптимизатор лучше всего будет работать, если все переменные объявлены с максимально жесткими ограничениями.

Когда массивы передаются как параметры на языке с контролем соответ­ствия типов:

procedure Sort(A: A_Type) is ...

границы также неявно должны передаваться в структуре данных, называемой дескриптором массива (dope vector) (рис. 5.4). Дескриптор массива содержит

верхнюю и нижнюю границы, размер элемента и адрес начала массива. Как мы видели, это именно та информация, которая нужна для вычисления адресов при индексации массива.