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.