ТЕСТИРОВАНИЕ ДИНАМИЧЕСКИХ МАССИВОВ
С АВТОМАТИЧЕСКОЙ ПРОВЕРКОЙ ИНДЕКСА
Рауль Шакиров
Институт машиноведения УрО РАН
raul@imach.uran.ru
Проходящее десятилетие, без преувеличения, можно назвать
декадой новых инструментов программирования. Эта особенность
в полной мере отражается на страницах массовой компьютерной
печати. Относительно меньшее внимание при этом уделяется таким
вопросам теории и технологии программирования, как проблемы
создания корректно работающих и мобильных программ. Такое
распределение приоритетов создает "социальный заказ" для
разработчиков инструментария - ориентироваться прежде всего на
реализацию новых функциональных возможностей, а проблемы
корректности и мобильности оставлять на усмотрение прикладных
программистов. Разумно это или нет? Не вдаваясь в детальное
обсуждение этого вопроса, отметим, что даже частичная
инструментальная поддержка могла бы существенно облегчить
разработку корректных программ. Один из методов такой
поддержки заключается в реализации динамических массивов с
автоматической проверкой индекса.
1. Автоматическая проверка индекса
Возможность автоматической проверки индекса при обращении
к элементу массива предусмотрена в ряде языков программи-
рования, из которых наиболее известным является Java. Важным
исключением являются языки С и С++ - там автоматической
проверки индекса нет, хотя в С++ ее можно реализовать с
помощью механизма шаблонов. Отсутствие автоматической
проверки индекса означает, что программист должен
гарантировать корректность индекса. Если такой гарантии нет,
то программа содержит скрытую ошибку, например, такую, как
знаменитая ошибка в программе sendmail или сбой при обработке
длинных MIME-имен в программе Microsoft Outlook.
Считается, что отсутствие автоматической проверки индекса
имеет и свои положительные стороны - большую свободу для
профессионального программиста и более высокую производитель-
ность программы. Справедливость этой точки зрения нуждается в
экспериментальной проверке, методика и результаты которой
будут обсуждаться в этой статье.
2. Динамические массивы
В отличие от обычного массива, размер которого фиксирует-
ся при сборке программы или при создании массива оператором
динамического распределения памяти, размер динамического
массива может меняться в процессе выполнения программы.
Динамические массивы могут быть реализованы, как часть
языка программирования или в виде класса - надстройки. Первый
вариант реализован, например, в системе программирования
Borland Delphi 4 [1]. Но наиболее известной и хорошо изученной
является реализация динамического массива в классе Vector.
Класс Vector предусмотрен в языке Java [2] и в новом
стандарте языка С++, где он декларирован составе библиотеки
шаблонов STL (Standard template library) [3]. Реализация
динамического массива в классе Vector основана на технике
хранения элементов в непрерывной области памяти, с
последовательным удвоением ее размеров по мере заполнения
массива данными. В Табл.1 сравнивается эффективность
непрерывных динамических массивов и динамических структур,
использующих размещение элементов в несмежных областях памяти
- таких, как связный список и двоичное дерево.
-----------------T-----------------T-------------------------¬
¦ Структуры ¦ Динамический ¦ Динамические структуры ¦
¦ Свойства ¦ массив ¦ с несмежным размещением ¦
+----------------+-----------------+-------------------------+
¦ Время доступа ¦ Не зависит от ¦ Пропорционально числу ¦
¦ к элементу по ¦ числа элементов ¦ элементов или логарифму ¦
¦ его индексу ¦ ¦ числа элементов ¦
+----------------+-----------------+-------------------------+
¦ Число операций ¦ Пропорционально ¦ Пропорционально числу ¦
¦ распределения ¦ логарифму числа ¦ элементов ¦
¦ памяти ¦ элементов ¦ ¦
L----------------+-----------------+--------------------------
Табл. 1. Сравнение различных динамических структур
Реализация класса Vector в языке Java страдает из-за
ограничений, свойственных этому языку. Из-за отсутствия в
языке Java шаблонов базовый массив класса Vector содержит не
значения, а ссылки на объекты, расположенные в динамической
памяти, что снижает производительность массива и приводит к
повышенному расходу памяти и увеличивает нагрузку на процесс
сборки "мусора". Для обращения к элементу массива нельзя
использовать привычную операцию [], т.к. в языке Java эту
операцию нельзя переопределить - вместо этого предлагается
использовать методы ElementAt и SetElementAt. При обращении к
несуществующему элементу массива возбуждается исключение.
Размер массива предлагается устанавливать вручную с помощью
метода EnsureCapacity.
Реализация динамических массивов в языке Java выглядит
шагом назад даже по сравнению с тем, чего можно добиться в
языке C++. Остается только сожалеть по поводу того, что столь
неполноценное решение закрепляется на десятилетия в рамках
популярного языка программирования.
В классе Vector библиотеки STL, в отличие от его тезки из
языка Java, вообще не предусмотрена проверка индексов, т.е.
программист не только должен вручную управлять размером
массива, но и даже не может рассчитывать на предсказуемое
поведение программы в случае ошибочной индексации. К счастью,
эта особенность не связана с какими-либо принципиальными
недостатками языка С++, а вытекает из установки разработчиков
библиотеки STL на максимальную производительность программы.
Реализация класса Vector в библиотеке STL отличается
довольно высокой эффективностью, интересными техническими
идеями и внушительным объемом программного кода - более 7000
строк только в заголовочных файлах.
3. Динамические массивы с автоматической проверкой индекса
Как упоминалось в п.1, автоматическая проверка индекса
при обращении к элементу массива уже реализована в языке Java,
При выходе индекса за границы массива виртуальная машина Java
возбуждает исключение. Возможность автоматического увеличения
размера массива не предусматривается, т.к. предполагается, что
размер массива должен задавать программист. По мнению автора,
такое решение является половинчатым - если уж создатели Java
пошли на накладные расходы, связанные с проверкой индексов, то
почему бы за счет этого не облегчить работу программиста
вместо того, чтобы просто его контролировать? Так мы приходим
к понятию динамического массива с автоматической проверкой
индекса.
Поскольку язык Java не позволяет реализовать динамические
массивы удобным и эффективным образом (см. п.2), то
соответствующая реализация проводилась автором для языка C++.
Результаты разработки представлены в виде заголовочного файла
exarray.h и вспомогательного файла exarray.cpp.
Динамический массив описывается шаблоном exarray и
создается с указанием типа элементов:
exarray<тип> имя;
Например, целочисленный массив vector объявляется так:
exarray<int> vector;
Размер массива не задается. Вместо этого постулируется,
что массив имеет неограниченное число элементов, которым
первоначально присвоены нулевые значения, либо значения,
заданные конструктором класса по умолчанию. Фактически, массив
первоначально имеет нулевой размер, но при обращении к любому
элементу размер массива автоматически увеличивается. При
переполнении разрядной сетки индекса или нехватке памяти
программа завершит работу с выдачей диагностики.
Для обращения к элементу массива с целью его чтения или
записи применяется стандартная нотация:
имя [индекс]
Предусмотрена возможность объявления многомерных массивов
с неограниченными размерами по всем измерениям. Например,
двумерная целочисленная матрица matrix объявляется так:
typedef exarray<int> vector;
exarray<vector> matrix;
Если требуется, то можно объявить комбинированный массив
с фиксированными и динамическими измерениями, например:
typedef int int5 [5];
exarray<int5> matrix;
Для передачи динамического массива в функцию в ней
объявляется параметр вида:
exarray<тип>& имя;
Чтобы облегчить применение динамических массивов, следует
избавить программиста от необходимости переучиваться. Для
этого класс exarray объявлен так, чтобы перевод программы на
использование динамических массивов можно было выполнить
путем простой замены деклараций, без необходимости коррекции
исполняемого кода.
Поскольку во многих программах для обращения к элементам
массивов используются указатели, то в файле exarray.h объявлен
шаблон expoint, реализующий концепцию динамического указателя.
Каждый динамический указатель привязан к определенному
динамическому массиву и характеризуется смещением в этом
массиве, которое разрешается менять с помощью арифметических
операций. При обращении через указатель к несуществующему
элементу размер массива автоматически увеличивается.
Динамический указатель объявляется как
expoint<тип> имя;
и может быть инициализирован динамическим массивом.
Например, указатель на массив vector объявляется так:
expoint<int> p = vector;
Далее можно выполнять привычные операции над указателем
типа p [3], p += 3, *p++, p = NULL, логические проверки и т.п.
Динамический массив exarray размещается в непрерывной
области памяти, адрес которой может меняться при изменении
размеров массива. Поэтому адреса элементов динамического
массива не могут храниться в обычных указателях, а
использование для этой цели динамических указателей ограничено
адресацией элементов одномерных массивов и старшего
динамического измерения многомерных массивов.
Указанные ограничения можно снять, если реализовать
динамический массив в виде непрерывного массива указателей на
значения элементов, а сами значения размещать по фиксированным
адресам в различных фрагментах динамической памяти. Такое
решение напоминает схему, принятую в языке Java и
характеризуется невысокой производительностью, т.к. на каждое
обращение к элементу динамического массива приходится два
обращения к оперативной памяти. С одной из реализаций этой
идеи можно познакомиться в работе [4].
4. Тестирование динамических массивов
Для проведения сравнительных испытаний использовались
программы перемножения матриц matrix1.cpp и matrix2.cpp.
Программа matrix1 написана в традиционном стиле с
использованием статических массивов. Программа matrix2
использует динамические массивы. В ней применяется
заголовочный файл exarray.h и функция распределения памяти
exmreloc.cpp, которые обсуждались выше. В остальном текст
matrix2 идентичен тексту matrix1. Чтобы обеспечить
достоверность результатов сравнения, при разработке программ
matrix1 и matrix2 не проводилась оптимизация под конкретные
трансляторы или вычислительные устройства.
Сравнивая программы, отметим, что в программе 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. Результаты тестов для матриц размером от 100 до
500 приведены в табл.2, где колонки 1 и 2 содержат результаты
для программ matrix1 и matrix2. Колонка 1' содержит результаты
для программы matrix1 после замены размерной константы DIM на
512. Колонка 2' содержит результаты для программы matrix2
после отключения проверки индексов во внутреннем цикле, для
чего выражение m1[i][k] * m2[k][j] заменялось выражением
m1.item(i).item(k) * m2.item(k).item(j).
Для удобства представления результатов время перемножения
матриц пересчитано на однократное прохождение внутреннего
цикла (т.е. поделено на dim в кубе) и указано в наносекундах.
Время ввода-вывода данных не учитывается.
------T--------T---------------------------------------------¬
¦ Раз ¦ Сум- ¦ Время 1-го прохода внутреннего цикла (нс) ¦
¦ мер ¦ марный +----------------------T----------------------+
¦(dim)¦ объем ¦ Без оптимизации ¦ С оптимизацией ¦
¦ ¦ матриц ¦ (Default) ¦ (Fastest Code) ¦
¦ ¦ (Кбайт)¦ 1 1' 2 2' ¦ 1 1' 2 2' ¦
+-----+--------+----------------------+----------------------+
¦ 100 ¦ 120 ¦ 235 216 281 132 ¦ 97 186 280 128 ¦
¦ 200 ¦ 480 ¦ 322 326 284 137 ¦ 180 288 283 131 ¦
¦ 300 ¦ 1080 ¦ 328 340 389 239 ¦ 183 298 389 235 ¦
¦ 400 ¦ 1920 ¦ 344 345 425 275 ¦ 200 309 424 271 ¦
¦ 500 ¦ 3000 ¦ 365 351 466 320 ¦ 221 315 466 319 ¦
L-----+--------+----------------------+-----------------------
Табл.2. Результаты тестов производительности
Комментируя результаты, следует прежде всего отметить
значительное влияние эффектов, связанных с особенностями
архитектуры процессоров Pentium.
В частности, замена размерного параметра DIM в программе
matrix1 на 512 влияет на производительность двояким образом:
1) При обращении к элементу матрицы вместо медленной
операции умножения выполняется быстрая операция сдвига.
2) Особенности устройства частично-ассоциативного кэша L1
процессоров Pentium [5] приводят к тому, что при обращении к
памяти с шагом 64*n +/- 4 байт эффективная емкость кэша падает
в 2 раза, при шаге 128*n байт - в 4 раза и.т.п. Поэтому при
последовательном обращении к m[k][j] с шагом 2048 байт
частично-ассоциативный кэш L1 не работает, и значения берутся
из более медленного кэша L2 или даже из оперативной памяти.
Поскольку два вышеупомянутых эффекта противоположны, то
результаты тестов 1 и 1' противоречивы. В основном, программа
matrix1 с DIM=500 работает быстрее, чем c DIM=512, и это
особенно заметно в режиме с оптимизацией, когда операция
умножения заменяется приращением рабочего указателя.
Динамические массивы в программе matrix2 не используют
операцию умножения, а для оптимизации загрузки кэша L1
применяется оригинальный алгоритм распределения памяти. Еще
один фактор ускорения заключается в том, что подсистема памяти
типа EDO или SDRAM работает быстрее при плотном размещении
данных в оперативной памяти. Этот эффект заметен при
перемножении матриц размерности 200.
Перемножение матриц является хорошим примером для
исследования автоматической оптимизации кода. Эффект
автоматической оптимизации наблюдается в программе matrix1 и
отсутствует в программе matrix2. Причина заключается в том,
что современные трансляторы языка С++ не приспособлены к
оптимизации кода для динамических массивов. Чтобы исследовать
эффект оптимизации кода в случае динамических массивов,
проверка индексов была отключена вручную; соответствующие
результаты приведены в колонке 2'.
Подведем итоги тестирования. Для целей сравнения обычных
и динамических массивов в режиме без оптимизации подходят
колонки 1 и 2, а в режиме с оптимизацией по скорости - колонки
1 и 2'. Судя по выбранным колонкам, время перемножения
динамических матриц на процессоре Pentium MMX меняется в
пределах 73-144% от времени перемножения обычных матриц при
среднем соотношении 119%. Эти результаты подтверждаются и
другими тестами. В частности, для случая одномерных массивов
было получено соотношение 120%. Следует особо отметить, что
обнаружить разницу в производительности удается только на
специально подобранных примерах при тщательном тестировании,
иначе разница будет скрыта более существенными эффектами,
связанными с архитектурными особенностями процессора и памяти.
Полученные результаты следует считать специфичными для
компьютеров на базе процессоров Pentuim и Pentium MMX, которые
характеризуются быстрым вычислительным ядром и относительно
медленной подсистемой оперативной памяти. Результаты
тестирования на компьютерах других типов и тестовые программы
публикуются на странице http://www.imach.uran.ru/exarray.
5. Возможности ручной оптимизации кода
Реализация динамических массивов позволяет при
необходимости отключить проверку индексов и организовать
доступ к массиву через обычный указатель. Поэтому результаты
ручной оптимизации кода зависит главным образом от
квалификации программиста, а не от того, какие массивы -
обычные или динамические - он применяет.
После ручной оптимизации кода время работы программ
matrix1 и matrix2 уменьшается до 80-100 нс/проход при любой
размерности матриц в пределах от 100 до 1000. Текст
оптимизированного варианта matrix2 приведен на листинге
matrix3.cpp. В этом варианте применяется транспонированная
матрица m2, а критический участок кода выделен в подпрограмму
scalar, использующую обычные указатели.
6. О применении динамических массивов
Одна из областей применения динамических массивов связана
с переводом существующих 16-разрядных программ в 32-разрядный
режим для увеличения размера обрабатываемых данных. Во многих
16-разрядных программах используется статическое распределение
памяти в пределах 640 КБайт, доступных для MS-DOS. В
32-разрядном варианте программы желательно иметь динамическое
распределение памяти, зависящее от объема обрабатываемых
данных. Для этого программа переводится на использование
динамических массивов:
1) Если в тексте программы имеются операторы & или sizeof
применительно к массивам, то & удаляется (это тавтология), а
sizeof заменяются размерными переменными или константами. Если
в программе применяются функции calloc, malloc и free, то они
заменяются на new и delete.
2) Параметры-массивы всех функций подразделяются на
входные и выходные. К указателям, соответствующим входным
массивам, добавляется модификатор const (использование этого
модификатора входит в понятие грамотного программирования, но
многие реальные программисты этим пренебрегают).
3) Там, где это требуется, обычные массивы и указатели
заменяются на динамические массивы и указатели.
При передаче динамического массива или указателя в
качестве входного параметра функции выполняется автоматическое
преобразование к обычному const-указателю. Доступ к
динамическому массиву по const-указателю выполняется без
проверки индексов в пределах заполненной части массива.
Существенный момент заключается в том, что в процессе
выполнения функции входной динамический массив не должен
менять свой размер - для этого следует обеспечить, чтобы при
вызове функции этот же массив не передавался в качестве одного
из ее выходных параметров.
Если динамический массив передается в качестве выходного
параметра функции, то соответствующий параметр объявляется как
exarray<тип>& или expoint<тип>. Первый вариант предпочтителен
с точки зрения производительности. Для передачи динамического
указателя следует использовать параметр вида expoint<тип>.
Если динамический массив или указатель передается в
качестве выходного параметра стандартной функции, текст
которой недоступен, то создается функция-оболочка, управляющая
размером массива (примеры - strcpy и strcat в exarray.h).
Если это требуется, то с помощью механизма перегрузки
можно задать несколько вариантов каждой функции с различными
способами передачи параметров.
Описанная методика была успешно использована для перевода
в 32-разрядный режим ряда небольших прикладных программ.
Выводы
Динамические массивы избавляют программиста от
необходимости заниматься распределением памяти и обеспечивают
полную защиту от любых ошибок индексации, при этом их
эффективность сопоставима с эффективностью обычных массивов,
не защищенных от ошибок индексации. Эксперименты на компьютере
с процессором Pentuim MMX показывают, что после перевода
32-разрядной программы на использование динамических массивов
производительность программы уменьшается в среднем на 20%,
причем в некоторых случаях наблюдается обратный эффект -
увеличение производительности.
Предложенную реализацию динамических массивов следует
считать предварительной, т.к. в ней не обеспечивается
автоматическая оптимизация программы, а также выдача
транслятором удобочитаемых диагностических сообщений. Для
полноценной реализации динамических массивов требуется, чтобы
их поддержка была включена в трансляторы языка C++. Судя по
тому, что динамические массивы (без автоматического увеличения
размеров) уже предусмотрены в трансляторе Borland Delphi 4,
такое развитие событий представляется весьма вероятным.
Ссылки
1. Delphi 4 Unleashed - Chapter 2. http://www.inprise.com
/delphi/books/del4unleashed/chapter2/
2. Патрик Нотон. Java. Справочное руководство. M.:
Восточная книжная компания, 1996. 448с.
3. Rogue Wave. Standard C++ Library User's Guide, Tutorial
and Class Reference. Rogue Wave Software Corvallis, Oregon USA.
4. Tom Cargill. C++ Gadfly. C++ Report Reprints: Jan 1994
http://www.inprise.com/borlandcpp/news/report/CR9401cargill.html
5. Intel Architecture Tutorials.
http://www.intel.ru/ contents/design/perftool/cbts