Оценка эффективности динамических массивов с автоматической проверкой индекса

Размещено на http://www.allbest.ru/

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

УДК 681.3.02

Оценка эффективности динамических массивов с автоматической проверкой индекса

Р.Н. Шакиров

Аннотация. Исследуется технология динамических массивов с автоматической проверкой индекса и ее влияние на производительность вычислительных программ. Исследование проводится на примере программы перемножения матриц, написанной на языке 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.

Листинг 1. Шаблон динамических массивов exarray.h

// Файл 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))));

}



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

// Модуль 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);

}

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

exarray<тип> имя;

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

exarray<int> vector;

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

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

typedef exarray<int> vector;

exarray<vector> matrix;

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

typedef int int5 [5];

exarray<int5> matrix;

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

exarray<тип>& имя;



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

4. Тестирование динамических массивов.

Для проведения сравнительных испытаний использовались программы перемножения матриц matrix1.cpp и matrix2.cpp на листингах 3 и 4. Программа matrix1 написана в традиционном стиле с использованием статических массивов. Программа matrix2 использует динамические массивы. В ней применяется заголовочный файл exarray.h и модуль exarray.cpp, которые обсуждались выше. В остальном, тексты программ идентичны. Чтобы обеспечить достоверность результатов сравнения, при разработке программ matrix1 и matrix2 не проводилась оптимизация под конкретные трансляторы или вычислительные устройства.

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

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

// Программа 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;

}

Сравнивая программы, отметим, что в программе 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 в кубе) и указано в наносекундах. Время ввода-вывода данных не учитывается.

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

Размер (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

Комментируя результаты, следует, прежде всего, отметить значительное влияние эффектов, связанных с особенностями подсистемы памяти архитектуры процессоров 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, использующую обычные указатели.

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

// Программа 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

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

Выводы

Динамические массивы с автоматической проверкой индекса освобождают программиста от необходимости заниматься распределением памяти и обеспечивают полную защиту от любых ошибок индексации, при этом их эффективность сопоставима с эффективностью обычных массивов, не защищенных от ошибок индексации. Эксперименты на компьютерах с процессорами 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

Размещено на Allbest.ru

...