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.