ОЦЕНКА ЭФФЕКТИВНОСТИ ДИНАМИЧЕСКИХ МАССИВОВ

УДК 681.3.02

ОЦЕНКА ЭФФЕКТИВНОСТИ ДИНАМИЧЕСКИХ МАССИВОВ

С АВТОМАТИЧЕСКОЙ ПРОВЕРКОЙ ИНДЕКСА

Р.Н. Шакиров

Институт машиноведения Уральского отделения РАН

620219, Екатеринбург, ул. Комсомольская 34а, Россия

Тел.: (+7) 3432-499-185, Факс: (+7) 3432-745-330

E-mail: raul@imach.uran.ru

Аннотация. Исследуется технология динамических массивов с автоматической проверкой индекса и ее влияние на производительность вычислительных программ. Исследование проводится на примере программы перемножения матриц, написанной на языке C++.

Ключевые слова: Динамический массив, автоматическая проверка индекса, C++

1. Автоматическая проверка индекса.

Производительность вычислительных программ и достоверность получаемых ими результатов в значительной степени зависит от применяемой технологии программирования. Для обеспечения большей достоверности результатов в некоторых языках программирования, таких, как Java [1], предусмотрена автоматическая проверка индекса при обращении к элементу массива. В других языках, таких, как C и C++, автоматической проверки индекса нет.

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

2. Динамические массивы.

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

Динамические массивы предусмотрены в системе программирования Delphi 4 [2] и в классе Vector библиотеки STL языка C++[3]. Реализация динамических массивов в классе Vector основана на технике хранения элементов в непрерывной области памяти, с последовательным удвоением ее размеров по мере заполнения массива данными. В табл. 1 проводится сравнение непрерывных динамических массивов и динамических структур, основанных на хранении элементов в несмежных областях памяти - таких, как связный список и двоичное дерево.

В классе Vector не предусмотрена автоматическая проверка индекса, т.е. программист должен управлять размером массива с помощью метода resize() и не может рассчитывать на предсказуемое поведение программы в случае ошибочной индексации.

Структуры

Свойства

Динамический массив

Динамические структуры с несмежным размещением элементов

Время доступа к элементу по его индексу

Не зависит от числа элементов

Пропорционально числу элементов или логарифму числа элементов

Число операций распределения памяти

Пропорционально лога-рифму числа элементов

Пропорционально числу элементов

Табл. 1. Сравнение различных динамических структур

3. Динамические массивы с автоматической проверкой индекса.

Как упоминалось, автоматическая проверка индекса при обращении к элементу массива уже реализована в языке Java, При выходе индекса за границы массива виртуальная машина Java возбуждает исключение. Возможность автоматического увеличения размера массива не предусматривается, т.к. предполагается, что размер массива должен задавать программист. Альтернативное решение заключается в автоматическом увеличении размера массива, что позволяет продолжать работу программы в штатном режиме. Так мы приходим к понятию динамического массива с автоматической проверкой индекса.

Реализация динамических массивов с автоматической проверкой индекса проводилась автором для языка C++. Результаты разработки представлены на листингах 1 и 2 в виде заголовочного файла exarray.h и вспомогательного модуля exarray.cpp.

// Файл exarray.h

// Шаблон динамических массивов с

// автоматической проверкой индекса

// (C)Р.Н.Шакиров, ИМАШ УрО PAH

template <class T> class exarray

{

T* e; // Базовый массив

unsigned len; // Число элементов

// Распределение памяти

void realloc (unsigned size);

void access (unsigned i);

public:

// Конструктор динамического массива.

exarray () { len = 0; e = 0; }

// Конструктор копирования и операция

// присваивания. Реализация отсутствует,

// поэтому при попытке присваивания

// динамических массивов выдается

// сообщение об ошибке.

exarray (const exarray<T>&);

exarray<T>& operator =

(const exarray<T>&);

// Деструктор динамического массива.

~exarray() { realloc (0); }

// Доступ к массиву с проверкой индекса.

// При выходе индекса за границы массива

// размер массива увеличивается, далее

// проводится обнуление памяти и вызов

// конструкторов по умолчанию для всех

// вновь организованных элементов.

T& operator [] (unsigned i)

{ if (len<=i) access(i); return e[i];}

T& operator [] (int i)

{ return (operator [] ((unsigned)i));}

T& operator * ()

{ if (len<=0) access(0); return e[0];}

// Доступ к массиву без проверки индекса.

T& item (unsigned i) { return (e[i]);}

T* base () { return (e); }

// Автоматическое преобразование в

// const T* для передачи массива в

// функцию через параметр const T*.

operator const T* () { return (e); }

};

// Прототипы функций модуля exarray.cpp.

void exmrealloc (void **p,

unsigned size, unsigned oldsize);

unsigned excalcsize (unsigned size);

// Функция exmuladd вычисляет n*s + k.

// При переполнении выдается ~0u.

inline unsigned exmuladd

(unsigned s, unsigned n, unsigned k)

{ return((n<=(~0u-k)/s)? n*s + k: ~0u);}

// Фиктивный класс для вызова

// конструкторов и деструкторов без

// распределения памяти.

template <class T> struct __EXRELOC

{

T value;

void* operator new (unsigned, void* p)

{ return p ;}

void operator delete (void*) { ;}

};

// Приватный метод realloc устанавливает

// размер динамического массива в байтах.

// При увеличении размера вызываются

// конструкторы элементов, а при

// уменьшении размера - деструкторы.

template <class T> void exarray<T>::realloc (unsigned size)

{

unsigned i = len, n = size/sizeof (T);

while (i > n) // Вызов деструкторов

{ i--; delete (__EXRELOC<T> *)(e + i);}

exmrealloc // Распределение памяти

((void **)&e, size, sizeof(T)*i);

len = n;

while (i < n) // Вызов конструкторов

{ new (e + i)__EXRELOC<T>; i++; }

}

// Приватный метод access распределяет

// память для элементов с индексами от 0

// до i c дополнительным резервированим.

template <class T> void exarray<T>::access (unsigned i)

{

realloc (excalcsize (

exmuladd (sizeof(T), i, sizeof(T))));

}

// Модуль exarray.cpp.

// Функции распределения памяти.

// (C)Р.Н.Шакиров, ИМАШ УрО PAH

#include <malloc.h>

#include <string.h>

#include <stdlib.h>

// Функция exmrealloc выделяет, удлиняет,

// укорачивает и освобождает блоки

// памяти, заполненные нулями.

void exmrealloc (void **p,

unsigned size, unsigned oldsize)

{

if (size) // Выделение памяти

{

if (size > (~0u)-9)

abort(); // Переполнение size

if ((*p = realloc (*p, size))==NULL)

abort(); // Ошибка размещения

if (size > oldsize)

memset // Обнуление

((char*)*p+oldsize, 0, size-oldsize);

}

else // Оcвобождение памяти.

{

if (*p) { free (*p); *p = NULL; }

}

// Функция excalcsize вычисляет размер

// блока памяти в байтах, который должен

// быть не меньше требуемого, для чего

// начальный размер SIZE_MOD поочередно

// умножается на 2 и 1.5.

// При переполнении выдается ~0u.

// Для уменьшения фрагментации

// динамической памяти учитывается

// размер системных данных SIZE_SYS,

// добавляемых функцией realloc.

// Для оптимизации работы кэша L1

// процесcоров Pentuim SIZE_MOD задается

// как 64**n +/- 16.

#define SIZE_MOD (112)

#define SIZE_SYS (sizeof(int) * 2)

unsigned excalcsize (unsigned size)

{

unsigned n = SIZE_MOD, k = 0;

for (;; k = ~k,

(k? (n <<= 1): (n += (n >> 1))))

{

n -= SIZE_SYS; if (n >= size) break;

n += SIZE_SYS; if ((int)n < 0)

{n =~0u; break;}

}

return (n);

}

Листинг 2. Вспомогательный модуль exarray.cpp

Динамический массив создается с указанием типа элементов:

exarray<тип> имя;

Например, целочисленный массив vector объявляется так:

exarray<int> vector;

Размер массива не задается. Вместо этого постулируется, что массив имеет неограниченное число элементов, которым первоначально присвоены нулевые значения, либо значения, заданные конструктором класса по умолчанию. Фактически, массив первоначально имеет нулевой размер, но при обращении к любому элементу размер массива автоматически увеличивается. При переполнении разрядной сетки индекса или нехватке памяти программа завершит работу с выдачей диагностики. Отсутствие ограничений на число элементов сокращает число особых ситуаций, которые могут возникнуть при выполнении программы. Фиксация начальных значений исключает возможность заполнения массива случайными значениями. Это облегчает процесс верификации и тестирования программы, в том числе с применением формальных методов, подобных описанным в [4].

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

typedef exarray<int> vector;

exarray<vector> matrix;

Если требуется, то можно объявить комбинированный массив с фиксированными и динамическими измерениями, например:

typedef int int5 [5];

exarray<int5> matrix;

Для передачи динамического массива в функцию в ней объявляется параметр:

exarray<тип>& имя;

Для обращения к элементу массива с целью его чтения или записи применяется стандартная нотация:

имя [индекс]

// Программа matrix1.cpp

// Перемножение матриц с использованием

// статических массивов.

#include <fstream.h>

#define DIM 500

int main (int argc, char **argv)

{

if (argc < 3) return 1;

static int m1[DIM][DIM];

static int m2[DIM][DIM];

static int m3[DIM][DIM];

int i,j,k,dim = 0;

// Ввод исходных данных

ifstream fin (argv[1]);

if (!fin) return 1;

fin >> dim;

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

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

fin >> m1[i][j];

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

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

fin >> m2[i][j];

// Перемножение матриц

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

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

{

int sum = 0;

for (k = 0; k < dim; k++)

sum += m1[i][k] * m2[k][j];

m3[i][j] = sum;

}

// Вывод результата

ofstream fout (argv[2]);

if (!fout) return 1;

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

{

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

{ fout.width(6); fout << m3[i][j]; }

fout << '\n';

}

return 0;

}

// Программа matrix2.cpp

// Перемножение матриц с использованием

// динамических массивов.

#include <fstream.h>

#include "exarray.h"

int main (int argc, char **argv)

{

if (argc < 3) return 1;

typedef exarray<int> vector;

exarray <vector> m1,m2,m3;

int i,j,k,dim = 0;

// Ввод исходных данных

ifstream fin (argv[1]);

if (!fin) return 1;

fin >> dim;

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

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

fin >> m1[i][j];

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

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

fin >> m2[i][j];

// Перемножение матриц

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

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

{

int sum = 0;

for (k = 0; k < dim; k++)

sum += m1[i][k] * m2[k][j];

m3[i][j] = sum;

}

// Вывод результата

ofstream fout (argv[2]);

if (!fout) return 1;

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

{

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

{ fout.width(6); fout << m3[i][j]; }

fout << '\n';

}

return 0;

}

Листинги 3 , 4. Программы перемножения матриц matrix1 и matrix 2.

Сравнивая программы, отметим, что в программе matrix1 нет проверки индексов, поэтому при попытке перемножения матриц с размером dim более 500 программа ведет себя непредсказуемым образом. Другой недостаток заключается в том, что для увеличения максимального размера матриц следует увеличить размер статических массивов; при этом увеличенный объем памяти потребуется даже при перемножении небольших матриц.

Указанные недостатки программы matrix1 можно преодолеть за счет применения оператора динамического распределения памяти new, но это сделает программу более громоздкой, а ее алгоритм - трудно читаемым. По наблюдениям автора, прикладные программисты предпочитает создавать некорректные и расточительные, но удобочитаемые программы, подобные matrix1. Интересно в связи с этим отметить, как стремительно растут требования к оперативной памяти в современных программах.

Программа matrix2, при полном сохранении удобочитаемости, не обладает ни одним из недостатков программы matrix1. Оперативная память распределяется автоматически по мере необходимости, а при ее нехватке программа прекращает работу.

Программы транслировались с помощью Borland C++ Compiler 4.5 с DOS Power Pack в режиме DPMI 32. Замеры производительности проводилось на Pentium-166 MMX, 430TX, 512К L2, 66Mhz SDRAM, Win 95 OSR2. Результаты замеров для матриц размера dim от 100 до 500 приведены в табл. 2, где колонки 1 и 2 содержат результаты для программ matrix1 и matrix2. Колонка 2' содержит результаты для matrix2 после отключения проверки индексов во внутреннем цикле, для чего выражение m1[i][k] * m2[k][j] заменялось не выражение m1.item(i).item(k) * m2.item(k).item(j). Для удобства анализа результатов время перемножения матриц пересчитано на однократное прохождение внутреннего цикла (т.е. поделено на dim в кубе) и указано в наносекундах. Время ввода-вывода данных не учитывается.

Размер

(dim)

Суммарный объем матриц

(Кбайт)

Время в пересчете на 1 проход внутреннего цикла (нс.)

Без оптимизации С оптимизацией

1 2 2' 1/2 1 2 2' 1/2'

100

200

300

400

500

120

480

1080

1920

3000

235 281 132 1.20

322 284 137 0.88

328 389 239 1.19

344 425 275 1.24

365 466 320 1.28

97 280 128 1.32

180 283 131 0.73

183 389 235 1.28

200 424 271 1.36

221 466 319 1.44

Табл. 2. Результаты замеров производительности.

Комментируя результаты, следует, прежде всего, отметить значительное влияние эффектов, связанных с особенностями подсистемы памяти архитектуры процессоров Pentium [5]. В частности, эти эффекты не позволяют оптимизировать программу matrix1 путем замены значения размерного параметра DIM с 500 до 512. Кроме того, производительность программы maxtrix1 страдает из-за неплотного размещения матриц в оперативной памяти, что особенно заметно для матриц размера dim = 200.

Перемножение матриц является хорошим примером для оценки эффективности автоматической оптимизации кода. Эффект автоматической оптимизации кода наблюдается в программе matrix1 и отсутствует в программе matrix2. Причина заключается в том, что существующие трансляторы C++ не приспособлены к оптимизации кода для динамических массивов. Чтобы исследовать эффект оптимизации кода для динамических массивов, проверка индексов была отключена вручную; соответствующие результаты приведены в колонке 2'.

Подведем итоги тестирования. Для целей сравнения обычных и динамических массивов в режиме без оптимизации подходят колонки 1 и 2, а в режиме с оптимизацией по скорости - колонки 1 и 2'. Судя по выбранным колонкам, время перемножения динамических матриц на процессоре Pentium MMX меняется в пределах 73-144% от времени перемножения статических матриц при среднем соотношении 119%. Эти результаты подтверждаются и другими тестами, проведенными автором. В частности, для одномерных массивов было получено соотношение 120%. Следует особо отметить, что обнаружить разницу в производительности удается только на специально подобранных примерах, иначе разница будет скрыта более существенными эффектами, связанными с архитектурными особенностями процессора и памяти.

Полученные результаты следует считать специфичными для компьютеров на базе процессоров Pentium и Pentium MMX, которые характеризуются относительно медленной по сравнению со скоростью ядра подсистемой кэширования оперативной памяти. Для процессоров следующих поколений - Pentium III, Pentium 4, AMD Athlon и DEC Alpha разброс результатов будет значительно выше: от 67 до 300% при средних показателях 120-180%. Результаты тестирования представлены на странице http://www.imach.uran.ru/exarray.

5. Возможности ручной оптимизации программ.

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

После ручной оптимизации программ matrix1 и matrix2 время их работы уменьшается до сведущих показателей:

79-100 нс./проход на Pentium MMX;

10-33 нс./проход на Pentium III/450;

3-6 нс./проход на Pentium 4/1500/RIMM;

4-15 нс./проход на AMD Athlon/1333/DIMM;

2.6-2.8 нс./проход на DEC Alpha/533;

Текст оптимизированного варианта matrix2 приведен на листинге 5. В оптимизированном варианте применяется транспонированная матрица m2, а критический участок кода выделен в подпрограмму scalar, использующую обычные указатели.

// Программа matrix3.cpp

// Оптимизированное перемножение матриц.

// (C)Р.Н.Шакиров, ИМАШ УрО PAH, 1998-99

#include <fstream.h>

#include "exarray.h"

int scalar (const int* p1, const int *p2,

int dim)

{

int sum = 0;

while (--dim >= 0)

sum += (*p1++) * (*p2++);

return (sum);

}

int main (int argc, char **argv)

{

if (argc < 3) return 1;

typedef exarray<int> vector;

exarray <vector> m1,m2,m3;

int i,j,k,dim = 0;

ifstream fin (argv [1]);

if (!fin) return 1;

fin >> dim;

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

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

fin >> m1[i][j];

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

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

fin >> m2[j][i];

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

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

m3[i][j] = scalar(m1[i],m2[j],dim);

ofstream fout (argv[2]);

if (!fout) return 1;

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

{

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

{ fout.width(6); fout << m3[i][j]; }

fout << '\n';

}

return 0;

}

Листинг 5. Оптимизированная программа перемножения матриц matrix3.

6. Выводы.

Динамические массивы с автоматической проверкой индекса освобождают программиста от необходимости заниматься распределением памяти и обеспечивают полную защиту от любых ошибок индексации, при этом их эффективность сопоставима с эффективностью обычных массивов, не защищенных от ошибок индексации. Эксперименты на компьютерах с процессорами Pentuim показывают, что после перевода 32-разрядной программы перемножения матриц на использование динамических массивов производительность программы уменьшается в среднем на 20-80%, причем иногда наблюдается обратный эффект - увеличение производительности.

Предложенная реализация динамических массивов является исследовательской, т.к. в ней не обеспечивается автоматическая оптимизация кода, а также выдача транслятором удобочитаемых диагностических сообщений. Для полноценной реализации динамических массивов требуется, чтобы их поддержка была включена в трансляторы языка C++.

Программное обеспечение динамических массивов размещается на странице http://www.imach.uran.ru/exarray.

СПИСОК ЛИТЕРАТУРЫ

1. Патрик Нотон. Java. Справочное руководство. M.: Восточная книжная компания, 1996. 448с.

2. Delphi 4 Unleashed. http://www.inprise.com/delphi/books/del4unleashed/chapter2

3. Standard C++ Library User's Guide, Tutorial and Class Reference. Rogue Wave Software Corvallis, Oregon USA.

4. Роберт Лоренс Бейбер. Программное обеспечение без ошибок. M.: Радио и связь, 1996. 176с.

5. Intel Architecture Tutorials. http://www.intel.ru /contents/design/perftool/cbts