UDK 681.3.02
ESTIMATION OF EFFICIENCY OF DYNAMIC ARRAYS WITH
AUTOMATIC CHECK OF AN INDEX
Raul N.Shakirov
Institute of
engineering science of Russian Academy of Sciences (UB)
34a, Komsomolskaya
str, Ekaterinburg, Russia, 620219
Phone: (+7)
3432-499-185, Fax: (+7) 3432-745-330
E-mail:
raul@imach.uran.ru
Abstract: The technology of dynamic arrays
with automatic check of an index and its influence on productivity of the
computing programs is investigated. The research was carried out on an example
of the program of multiplication of matrixes written on language C ++.
Keywords: Dynamic arrays, automatic check of
an index, C++
For obtaining of reliable results, some programming languages implement
an automatic check of index during access to an element of an array. At absence
of automatic check of an index, a programmer must ensure that index is correct,
otherwise program will contain hidden error. It is often considered that
absence of check of indexes has also positive aspect - more freedom for
programmer and better performance. Validity of this point of view requires
experimental check, which has been carried out here on example of program for
multiplication of matrixes. Program was used to compare ordinary static arrays
and dynamic arrays with automatic check of an index, which were implemented by
author as a template written on C++.
Definition of dynamic array indicates type of its elements:
exarray<type> name;
Size of array need not be indicated. Instead, 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 are implemented using the following standard notation:
name [index]
It must be pointed out that absence of restriction of number of elements reduces number of exceptions, which can arise on execution of a program. Fixing of initial values of elements excludes initializing of array by casual values. These conventions simplify successive verification and testing of a program.
Implementation of dynamic array stipulates for storing of all its
elements in a contiguous area of computer memory. Actually, no memory is
allocated just after construction of array. When program refers to any element
of the array for either reading or writing, the template adjusts physical size
of array to be no less then required. To minimize both number of memory
allocation operations and fragmentation of memory, physical size of array is
calculated by alternating multiplying of predefined minimal size by 2 and 1.5.
That is, consecutive multipliers are 1, 2, 3, 6, 9 etc. This technique provides
for the following performance conditions:
1.
Time of access to an element does not depend logically on either index
of the element or size of array
2.
Number of memory allocation operations is proportional to logarithm of
actual size of array.
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> vector;
exarray<vector> matrix;
Program has been compiled under Borland C++ 4.5, Visual C++ 6.0 and DEC
cxx. Tests were carried out on platforms Intel Pentium, AMD Athlon and DEC
Alpha for square matrixes with dimension from 100*100 up to 500*500. Computing
time for dynamic arrays fits into the range 67-300% of computing time for
static arrays; for most cases, the time fits into the range 120-180%.
Templates, test programs and results of testing are available at the page http://www.imach.uran.ru/exarray.