TEMPLATES FOR CHECK OF INDEXES IN
PROGRAMS ON LANGUAGES C++ AND С
Shakirov Raul Nurovich, Dr. Tech.
Institute of engineering science of
RAS (UB), 34, Komsomolskaya str, Ekaterinburg, Russia, 620219
Phone: (+7) 3432-689-336, Fax: (+7) 3432-74-53-30, E-mail: raul@imach.uran.ru
Abstract: Templates of dynamic arrays implement technique
of automatic allocation of memory and protect against memory overriding bugs
without appreciable decrease of performance. Templates have been applied for
purposes of fast implementation of computing algorithms, porting of legacy
16-bit programs to 32-bit environment and also implementation of debugging
check of indexes in programs on languages C++ and C.
For
obtaining of reliable results, some programming languages implement an
automatic check of an index during access to an element of an array to protect
against memory overriding bugs. It is often considered that absence of check of
indexes has also positive aspect - better performance. To check this point of
view, the author has implemented the template of dynamic arrays and program for
multiplication of matrixes.
Definition
of dynamic array indicates type of its elements:
exarray<type> name;
Size of
array need not be indicated. It is assumed that array have unlimited number of
elements, which initially have either zero values or values defined by default
constructor of class type. References to elements look as:
name [index]
Program stores matrixes in
two-dimensional dynamic arrays with unlimited number of elements per each
dimension, which are defined as the following:
typedef exarray<int> row;
exarray<row> matrix;
Dynamic
array stores elements within contiguous area of computer memory. Actually, no
memory is allocated just after construction of array. When program refers to
any element for either reading or writing, the template adjusts physical size
of array to be no less then required. This technique provides for the following
performance conditions:
1.
Time
to access an element does not depend on either index of the element or size of
an array.
2.
Number
of memory allocation operations is proportional to logarithm of actual size of
an array.
Computing
time for dynamic arrays fits into the range 67-300% of computing time for
static arrays; for most cases, the range is 120-180%. Detailed results of
testing are available at http://www.imach.uran.ru/exarray.